适合小白理解的消除文法的左递归.doc资源-CSDN文库

需积分: 5 96 浏览量 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α | β

步骤如下：

本内容试读结束，登录后可阅读更多

下载后可阅读完整内容，剩余2页未读，立即下载

内容反馈

梦回阑珊

粉丝: 4021
资源: 1455

最新资源

资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！点击此处反馈

feedback-tip