时间戳

首页 > 解决方案 > 如果不使用经典方法并将其转换为 LL(1)，则找到语法不是 LL(1)

compiler-construction - 如果不使用经典方法并将其转换为 LL(1)，则找到语法不是 LL(1)

问题描述

假设我有这个语法：

S -> A C x | u B A
A -> z A y | S u | ε
B -> C x | y B u
C -> B w B | w A

这个语法显然不是 LL(1)，我可以找到它来构建解析表。但是，如果不使用经典方法，即不构造解析表或发现任何冲突，我有什么方法可以证明这个语法不是 LL(1)？

另外，我怎样才能将此语法转换为 LL(1)？我认为我必须同时使用 epsilon-derivation 消除和左递归消除，但这有点棘手，而且我尝试过很多次都无法将其转换为 LL(1)。

先感谢您。

标签： compiler-constructiongrammarcontext-free-grammarcompiler-theory

解决方案

S/A和B/都C涉及间接左递归。

由于没有左递归语法（直接或间接）对于任何k都是 LL(k) ，因此您可以简单地通过显示左递归循环来证明该语法不是 LL(1)。（另一方面，如果你有一个计算 FIRST 和 FOLLOW 集的工具，“经典”方法真的很简单。）

消除间接左递归涉及首先找到非终结符的一种可能的拓扑类型，然后通过用非终结符的右侧替换非终结符的某些用途来打破推导循环。之后，可以应用简单的左递归消除算法。

您可以在 StackOverflow或此处或任何有关解析理论的好教科书中找到这种转换的具体示例。（或者，当然，通过搜索术语“间接左递归”并寻找具有一定可信度的页面。）

推荐阅读