验证语法是强LL(2)
Sudkamp的语言和机器的问题19.5要求读者验证语法
G : S' -> S##
S -> aSa | bSb | λ是强LL(2)。变量FIRST和FOLLOW集使用算法19.5.1计算(第583页，第3版)：
FIRST(2)(S) = {λ,aa,bb,ab,ba}
FOLLOW(2)(S) = {##,a#,b#,aa,bb,ab,ba}很明显，S规则的length-2查找集不会对S的length-2查找集进行分区，因为规则S -> λ导致了由FOLLOW(2)(S)组成的length-2查找集。
LA(2)(S) = {##,a#,b#,aa,bb,ab,ba}
LA(2)(S -> aSa) = {a#,aa,ab}
LA(2)(S -> bSb) = {b#,bb,ba}
LA(2)(S -> λ) = {##,a#,b#,aa,bb,ab,ba}现在，我可能在计算FIRST、FOLLOW或G的LA(2)集时出错了。然而，我很有信心我已经正确地执行了算法。特别是，我可以回到它们的定义：
FIRST(2)(S) = trunc(2)({x : S =>* x AND x IN Σ*})
= trunc(2)({uu^R : u IN {a,b}^*})
= {λ,aa,bb,ab,ba}
FOLLOW(2)(S) = trunc(2)({x : S' =>* uSv AND x IN FIRST(2)(v)})
= trunc(2)({x : x IN FIRST(2)({a,b}^*{##})})
= trunc(2)({##,a#,b#,aa,bb,ab,ba})
= {##,a#,b#,aa,bb,ab,ba}现在的问题是:为什么语法强LL(2)。如果S规则的length-2查找集不对S的length-2查找集进行分区，那么语法不应该是强LL(2)。但我无法得出这本书所期望的结论。我有什么不明白的？
回答 1
Stack Overflow用户
发布于 2011-06-21 21:39:59
这里有一个解决办法。上面给出的语法G不是强LL(2)。要了解这一点，请回顾强LL(k)语法的定义。语法G是某些k > 0的LL(k)，如果有两个最左边的导子
S =>* u1Av1 => u1xv1 =>* uzw1 S =>* u2Av2 => u2yv2 =>* u2zw2ui,wi IN Σ* for i IN {1,2}和|z| = k，然后是x = y。考虑上面语法G中最左边的派生项：
S =>* aaSaa## (u1 = aa, v1 = aa##) S =>* baSab## (u2 = ba, v2 = ab##)
=>1 aaaa## (x = λ) =>1 baaSaab## (y = aSa)
=>* aaaA## (z = aa, w1 = aa##) =>* baaaab## (z = aa, w2 = ab##)导子满足强LL(2)文法定义的条件。但是，λ \= aSa，因此G不是强LL(2)。
显然，我们可以构建许多最左边的派生，以证明G不是强LL(2)。但是，G不强大的LL(2)还有其他几个原因。例如，显然不能用确定性的下推自动机重新定义G，因为无法确定何时开始从堆栈中删除元素。
https://stackoverflow.com/questions/6398852
复制相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号