parsing - 如何使用解析表证明左递归文法不在 LL(1) 中

Question

我有一个语法，想证明它不在 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) 中呢？

Answer 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)