7

我正在玩弄编写编译器并学习语法分析背后的理论。我发现尽管它是理解识别算法的关键概念，但网络上关于它的信息却相当贫乏。StackOverflow 似乎在解决这个问题上处于一个独特的位置。

4

1 回答 1

9

语法的前瞻集是根据其每个非终结符的前瞻集定义的，而前瞻集又依赖于每个产生式的前瞻集。确定前瞻集可以帮助我们确定语法是否为LL(1)，如果是，我们需要哪些信息来为其构造递归下降解析器。

定义： LOOKAHEAD(X -> α)和LOOKAHEAD(X)：

LOOKAHEAD(X -> α) = FIRST(α) U FOLLOW(X), if NULLABLE(α)
LOOKAHEAD(X -> α) = FIRST(α), if not NULLABLE(α)
LOOKAHEAD(X) = LOOKAHEAD(X -> α) U LOOKAHEAD(X -> β) U LOOKAHEAD(X -> γ)

其中FIRST(α)是 α 可以开始的终结符集合，FOLLOW(X)是可以出现在语法中任何位置的X之后的终结符集合， NULLABLE(α)是 α 是否可以导出一个空序列终端（表示为 ε）。以下定义取自 Torben Mogensen 的免费书籍《编译器设计基础》。请参阅下面的示例。

定义： NULLABLE(X)：

NULLABLE(ε) = true
NULLABLE(x) = false, if x is a terminal
NULLABLE(αβ) = NULLABLE(α) and NULLABLE(β)
NULLABLE(P) = NULLABLE(α_1) or NULLABLE(α_2) or ... or NULLABLE(α_n),
               if P is a non-terminal and the right-hand-sides
               of all its productions are α_1, α_2, ..., α_n.

定义： FIRST(X)：

FIRST(ε) = Ø
FIRST(x) = {x}, assuming x is a terminal
FIRST(αβ) = FIRST(α) U FIRST(β), if NULLABLE(α)
          = FIRST(α), if not NULLABLE(α)
FIRST(P) = FIRST(α_1) U FIRST(α_2) U ... U FIRST(α_n),
               if P is a non-terminal and the right-hand-sides
               of all its productions are α_1, α_2, ..., α_n.

定义： 跟随（X）：

一个终结符号 a 在FOLLOW(X)中当且仅当从文法的起始符号 S 有一个推导使得 S ⇒ αX aβ，其中 α 和 β 是（可能为空的）文法符号序列。

直觉： FOLLOW(X)：

查看X在语法中出现的位置。所有可以跟随它的终端（直接或通过任何级别的递归）都在FOLLOW(X)中。此外，如果X出现在产生式的末尾（例如A -> foo X），或者后面跟着可以简化为 ε 的其他东西（例如A -> foo X B和B -> ε），那么无论A可以跟在什么后面，X也可以跟在 (ie FOLLOW(A) ⊆ FOLLOW(X)) 后面。

请参阅 Torben 书中确定FOLLOW(X)的方法以及下面的演示。

一个例子：

E -> n A
A -> E B
A -> ε
B -> + A
B -> * A

首先，NULLABLE和FIRST是确定的：

NULLABLE(E) = NULLABLE(n A) = NULLABLE(n) ∧ NULLABLE(A) = false
NULLABLE(A) = NULLABLE(E B) ∨ NULLABLE(ε) = true
NULLABLE(B) = NULLABLE(+ A) ∨ NULLABLE(* A) = false

FIRST(E) = FIRST(n A) = {n}
FIRST(A) = FIRST(E B) U FIRST(ε) = FIRST(E) U Ø = {n} (because E is not NULLABLE)
FIRST(B) = FIRST(+ A) U FIRST(* A) = FIRST(+) U FIRST(*) = {+, *}

在确定FOLLOWE' -> E $之前，添加产生式，其中$被认为是“文件结尾”非终端。然后确定FOLLOW：

FOLLOW(E): Let β = $, so add the constraint that FIRST($) = {$} ⊆ FOLLOW(E)
           Let β = B, so add the constraint that FIRST(B) = {+, *} ⊆ FOLLOW(E)
FOLLOW(A): Let β = ε, so add the constraint that FIRST(ε) = Ø ⊆ FOLLOW(A).
           Because NULLABLE(ε), add the constraint that FOLLOW(E) ⊆ FOLLOW(A).
           Let β = ε, so add the constraint that FIRST(ε) = Ø ⊆ FOLLOW(A).
           Because NULLABLE(ε), add the constraint that FOLLOW(B) ⊆ FOLLOW(A).
           Let β = ε, so add the constraint that FIRST(ε) = Ø ⊆ FOLLOW(A).
           Because NULLABLE(ε), add the constraint that FOLLOW(B) ⊆ FOLLOW(A).
FOLLOW(B): Let β = ε, so add the constraint that FIRST(ε) = Ø ⊆ FOLLOW(B).
           Because NULLABLE(ε), add the constraint that FOLLOW(A) ⊆ FOLLOW(B).

解决这些约束（也可以通过定点迭代来实现），

    {+, *, $} ⊆ FOLLOW(E)
    FOLLOW(E) ⊆ FOLLOW(A)
    FOLLOW(A) = FOLLOW(B)

    FOLLOW(E) = FOLLOW(A) = FOLLOW(B) = {+, *, $}.

现在可以确定每个生产的LOOKAHEAD ：

LOOKAHEAD(E -> n A) = FIRST(n A) = {n}     because ¬NULLABLE(n A)
LOOKAHEAD(A -> E B) = FIRST(E B)           because ¬NULLABLE(E B)
                    = FIRST(E) = {n}       because ¬NULLABLE(E)
LOOKAHEAD(A -> ε)   = FIRST(ε) U FOLLOW(A) because NULLABLE(ε)
                    = Ø U {+, *, $} = {+, *, $}
LOOKAHEAD(B -> + A) = FIRST(+ A)           because ¬NULLABLE(+ A)
                    = FIRST(+) = {+}       because ¬NULLABLE(+)
LOOKAHEAD(B -> * A) = {*}                  for the same reason

最后，可以确定每个非终结符的LOOKAHEAD ：

LOOKAHEAD(E) = LOOKAHEAD(E -> n A) = {n}
LOOKAHEAD(A) = LOOKAHEAD(A -> E B) U LOOKAHEAD(A -> ε)   = {n} U {+, *, $}
LOOKAHEAD(B) = LOOKAHEAD(B -> + A) U LOOKAHEAD(B -> * A) = {+, *}

通过这些知识，我们可以确定这个文法不是 LL(1)，因为它的非终结符有重叠的前瞻集。（也就是说，我们不能创建一个程序，它一次读取一个符号并明确地决定使用哪个产生式。）

于 2012-12-05T20:36:40.980 回答