4

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)。但我无法得出本书所期望的结论。我不明白什么？

4

1 回答 1

0

这是一个解决方案。G上面给出的语法并不强LL(2)。要看到这一点，请回忆一下强LL(k)文法的定义。语法G适用LL(k)于某些k > 0if，只要有两个最左边的推导

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确定性下推自动机无法识别，因为无法确定何时开始从堆栈中删除元素。

于 2011-06-21T21:39:59.933 回答