适合小白理解的消除文法的左递归.doc
需积分: 5 12 浏览量
2024-05-23
21:01:27
上传
评论 1
收藏 19KB DOC 举报
消除文法中的左递归是编译器构造中的一个常见任务。左递归可以是直接的或间
接的。直接左递归发生在一个规则中，如 A -> Aα | β，其中 A 是非终结符，α
和 β 是任意字符串。间接左递归发生在多个规则之间，如 A -> Bγ 和 B ->
Aδ，导致循环引用。
以下是如何在文法中消除左递归的步骤：
1. 消除直接左递归
对于文法规则 A -> Aα | β，可以将其转换为非左递归形式。假设 A 是非终结符，
α 和 β 是包含终结符和/或非终结符的字符串，且 β 不以 A 开头。
步骤如下：
1. 引入新的非终结符 A'。
2. 重写规则为：
A -> βA'
A' -> αA' | ε
其中，ε 表示空串。
示例：
A -> Aα | β
转化为：
A -> βA'
A' -> αA' | ε
2. 消除间接左递归
对于间接左递归，需要重排和重新定义规则，以便先消除直接左递归。
假设有文法规则：
A -> Bγ | δ
B -> Aα | β
步骤如下：
资源评论
