LL(1)语法验证

Question

假设G是这样一种语法：

S -> aBa
B -> bB | \epsilon

其中\epsilon表示空字符串。

在计算了FIRST和FOLLOW之后，有没有一种方法可以在不依靠解析表的情况下判断G是否为LL(1)？

Answer 1

在计算了G的变量的FIRST和FOLLOW集合之后，您可以计算G的变量和规则的长度为1的前视集合LA(1)。则G是强LL(1)当且仅当满足以下条件：

LA(1)(A -> wi) partition LA(1)(A) for each variable A such that A -> wi is a rule.

或者，您可以从强LL(k)文法的定义证明G是强LL(1)，而不需要计算FIRST和FOLLOW集。这通常比为像G这样的小语法计算FIRST和FOLLOW更容易，也不那么乏味。

我手头没有一本书，所以其中一些定义或计算可能会有错误。但这就是我解决这个问题的方法。计算FIRST和FOLLOW集可以得到以下结果：

FIRST(1)(S) = trunc(1)({x : S =>* x AND x IN Σ*})
            = trunc(1)({ab^na : n >= 0})
            = {a}

FIRST(1)(B) = trunc(1)({x : B =>* x AND x IN Σ*})
            = trunc(1)({b^n : n >= 0})
            = {ε,b}

FOLLOW(1)(S) = trunc(1)({x : S =>* uSv AND x IN FIRST(1)(v)})
             = trunc(1)({x : x IN FIRST(1)(ε)})
             = trunc(1)(FIRST(1)(ε))
             = {ε}

FOLLOW(1)(B) = trunc(1)({x : S =>* uBv AND x IN FIRST(1)(v)})
             = trunc(1)({x : x IN FIRST(1)(a)})
             = trunc(1)(FIRST(1)(a))
             = {a}

通过计算变量和规则的长度为1的前瞻集合，可以得出：

LA(1)(S) = trunc(1)(FIRST(1)(S)FOLLOW(1)(S))
         = trunc(1)({a}{ε})
         = trunc(1){a}
         = {a}
LA(1)(B) = trunc(1)(FIRST(1)(B)FOLLOW(1)(B))
         = trunc(1)({ε,b}{a})
         = trunc(1){a,b}
         = {a,b}

LA(1)(S -> aBa) = trunc(1)(FIRST(1)(a)FIRST(1)(B)FIRST(1)(a)FOLLOW(1)(S))
                = trunc(1){a}
                = {a}
LA(1)(B -> bB)  = trunc(1)(FIRST(1)(b)FIRST(1)(B))
                = trunc(1){b} 
                = {b}
LA(1)(B -> ε)   = trunc(1)(FIRST(1)(ε)FOLLOW(1)(b))
                = trunc(1)({ε}{a})
                = {a}

因为LA(1)(B -> ε)和LA(1)(B -> bB)分区LA(1)(B)和LA(1)(S -> aBa)很容易分区LA(1)(S)，所以G是强LL(1)。