Sudkamp 的语言和机器的问题 19.5要求读者验证语法
G : S' -> S##
S -> aSa | bSb | λ
很强大LL(2)
。变量的FIRST
和FOLLOW
集合S
使用算法 19.5.1(第 583 页,第 3 版)计算:
FIRST(2)(S) = {λ,aa,bb,ab,ba}
FOLLOW(2)(S) = {##,a#,b#,aa,bb,ab,ba}
很明显,S
规则的长度为 2 的前瞻集不会对 的长度为 2 的前瞻集进行分区S
,因为规则S -> λ
导致长度为 2 的前瞻集包括FOLLOW(2)(S)
:
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
时LA(2)
出错了G
。但是,我相当有信心我已经正确执行了算法。特别是,我可以恢复他们的定义:
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
规则的长度为 2 的前瞻集不分割长度为 2 的前瞻集S
,则语法不应该是强的LL(2)
。但我无法得出本书所期望的结论。我不明白什么?