gpt4 book ai didi

computer-science - 验证语法是否强 LL(2)

转载 作者:行者123 更新时间:2023-12-01 06:45:06 25 4
gpt4 key购买 nike

Sudkamp 的语言和机器的问题 19.5 要求读者验证语法

G : S' -> S##
S -> aSa | bSb | λ

很强大 LL(2) . FIRSTFOLLOW设置变量 S使用算法 19.5.1(第 583 页,第 3 版)计算:
FIRST(2)(S)   = {λ,aa,bb,ab,ba}

FOLLOW(2)(S) = {##,a#,b#,aa,bb,ab,ba}

很明显, S 的长度为 2 的前瞻集规则不会对 S 的长度为 2 的前瞻集进行分区, 由于规则 S -> λ ,这产生了由 FOLLOW(2)(S) 组成的长度为 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 , 或 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 的前瞻规则不会对 S 的长度为 2 的前瞻集进行分区, 那么语法不应该强 LL(2) .但我无法得出本书所期望的结论。我不明白什么?

最佳答案

这是一个解决方案。语法G上面给出的不强LL(2) .要看到这一点,请记忆一下强 LL(k) 的定义。语法。语法GLL(k)对于一些 k > 0如果,只要有两个最左边的推导

S =>* u1Av1 => u1xv1 =>* uzw1          S =>* u2Av2 => u2yv2 =>* u2zw2

在哪里 ui,wi IN Σ*对于 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不能被确定性下推自动机识别,因为无法确定何时开始从堆栈中删除元素。

关于computer-science - 验证语法是否强 LL(2),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/6398852/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com