我有一个语法,想证明它不在 LL(1) 中:
S->SA|A
A->a
由于它是左递归文法,为了找到第一个和后续集合,我消除了左递归并得到:
S->AS'
S'->AS'|Empty
A->a
first of A={a} follow of S={$}
first of s'={a,ε} follow of S'={$}
first of S={a} follow of A={a,$}
但是当我填写解析表时,我没有得到任何包含 2 个条目的单元格。那么如何证明给定的文法不在 LL(1) 中呢?
最佳答案
首先,您在删除左递归的语法上找到 FIRST 和 FOLLOW。因此,如果您尝试创建 LL(1) 解析表,肯定不会有任何 2 个条目,因为删除了左递归并且语法是明确的。
语法[ S->SA|A A->a ] 不是 LL(1),因为存在左递归。为了通过构造 LL(1) 解析表来证明它,您只需要在此语法上找到 FIRST 和 FOLLOW,而无需对其进行修改。
从底部 A->a 开始,给出 FIRST(A)={a}
S->A ,给出 FIRST(S)=FIRST(A)={a}
S->SA ,给出 FIRST(S)=FIRST(S) ,我认为问题出现在这里。在这种递归调用规则中,计算 FIRST(S) 直到它发生变化,即直到在 FIRST(S) 中添加元素继续计算。一旦它停止改变就是你的答案
因此 FIRST(S)=FIRST(S)={a} ,你尽可能多地调用 FIRST(S) 它不会改变。
解析表:
a
------------
S S->SA
S->A
-------------
A A->a
所以 (S,a) 有两个条目。因此它不是 LL(1)
关于parsing - 如何使用解析表证明左递归文法不在 LL(1) 中,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/27703952/