前瞻集的精确定义是什么?

语法的lookahead集是根据其每个非终端的lookahead集来定义的,而这些非终端又依赖于每个产品的lookahead集。确定先行集可以帮助我们确定语法是否正确 LL(1)

定义: 展望(X->±) 和 展望(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 -> γ)

哪里 是可以开始的一组端子, 跟随(X) 十 语法上的任何地方 可为空(±) Basics of Compiler Design . 请参见下面的示例。

:

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(ε) = Ø
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位于 跟随(X) 当且仅当从语法的起始符号S派生出S±xa,其中±和是(可能是空的)语法符号序列。

直觉: 跟随(X) :

看看在哪里 发生在语法中。所有可能的终端 跟随 跟随(X) . 另外,如果 十 在生产结束时发生(例如。 A -> foo X ),或后面是其他可以减少到(例如。 A -> foo X B B -> ε ),那就随便了 后面可以是, 也可以后跟(即。 FOLLOW(A) ⊆ FOLLOW(X) ).

跟随(X) 在托本的书和下面的演示中。

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

第一, 可为空的 和

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(*) = {+, *}

之前 跟随 E' -> E $ 已添加,其中 $ 被认为是“文件结尾”非终端。那么 跟随 确定为:

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(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(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) = {+, *}