7

私はコンパイラーを書いて、構文解析の背後にある理論について学んでいます。認識アルゴリズムを理解するための重要な概念ですが、ネット上の情報はかなり貧弱であることがわかりました。StackOverflowは、この問題を解決するための独自の立場にあるようです。

4

1 に答える 1

9

文法の先読みセットは、各非終端記号の先読みセットの観点から定義されます。これは、各プロダクションの先読みセットに依存します。先読みセットを判別すると、文法がLL（1）であるかどうか、および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（α）はαが次の空のシーケンスを導出できるかどうかです。端子（εで示される）。以下の定義は、TorbenMogensenの無料の本「BasicsofCompilerDesign」から抜粋したものです。例については、以下を参照してください。

定義： 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.

定義： FOLLOW（X）：

終端記号aは、S⇒αXaβとなるような文法の開始記号Sからの派生がある場合にのみ、 FOLLOW（X）にあります。ここで、αとβは（おそらく空の）文法記号のシーケンスです。

直感： FOLLOW（X）：

文法のどこでXが発生するかを見てください。（直接または任意のレベルの再帰によって）それに続く可能性のあるすべての端末は、 FOLLOW（X）にあります。さらに、Xがプロダクションの最後に発生する場合（eg A -> foo X）、またはεに還元できる他の何かが続く場合（eg A -> foo X Band 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(*) = {+, *}

FOLLOWが決定される前に、プロダクションE' -> 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）ではないと判断できます。（つまり、一度に1つのシンボルを読み取り、使用するプロダクションを明確に決定するプログラムを作成することはできません。）

于 2012-12-05T20:36:40.980 に答える