我有一个语法,想证明它不在 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)
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)