验证语法是否强大 LL(2)

Question

Sudkamp 的《Languages and Machines》的问题 19.5 要求读者验证语法

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

是否强LL(2)。变量 S 的 FIRST 和 FOLLOW 集是使用算法 19.5.1（第 583 页，第三版）计算的：

FIRST(2)(S)   = {λ,aa,bb,ab,ba}

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

很明显由于规则 S -> S 规则，S 规则的 length-2 先行设置不会对 S 的 length-2 先行设置进行分区。 λ，它产生由 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 规则的 length-2 前瞻集未对 S 的 length-2 Lookahead 集进行分区，则语法不应为强LL(2)。但我无法得出书中所期望的结论。我不明白什么？

Answer 1

这是一个解决方案。上面给出的语法G并不强LL(2)。要了解这一点，请回忆一下强 LL(k) 语法的定义。对于某些k > ，语法G是LL(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，因为无法确定何时开始从堆栈中删除元素。