LL法

LL法またはLL構文解析とは、文脈自由文法のサブセットのためのトップダウン構文解析法の一種である。入力文字列を左 (Left) から構文解析していき、左端導出 (Leftmost Derivation) を行う（このため、LL法と呼ぶ。LR法も参照されたい）。この方式で構文解析可能な文法のクラスを LL文法 と呼ぶ。

以下では、表駆動型の構文解析を解説する。他の手法として、個々の構文規則に対応するサブルーチンの呼び出しから成る再帰下降構文解析もある。表駆動型は計算機による生成に向き、再帰下降構文解析はコードの手書きに向いている（しかし、再帰下降構文解析のコードを自動生成する ANTLR のようなツールもある）。

k 個の字句（トークン）を先読みする場合、LL(k) と表記する。ある文法について LL(k) 構文解析器が存在し、バックトラッキングなしで構文解析できる場合、その文法を LL(k) 文法であるという。LL(1) 文法は機能が限定されるが、次のトークンだけを先読みすればよいため、構文解析器の生成が容易であり、よく使われている。一般に設計に問題がある言語は大きな k が必要となる傾向があり（k が大きいということは、人がプログラムを読む場合にも、たくさん読まないと意味を把握できないということである）、構文解析が大変になる。

以下では、構文解析表に基づいたトップダウン構文解析による左端導出について解説する。

構文解析器は特定の形式文法に従った文字列を扱う。

構文解析器は以下の要素から構成される。

• 入力バッファ: 入力トークン列を格納する。
• スタック: 解析対象文法の終端記号と非終端記号を格納する。
• 構文解析表: スタックのトップにある記号と次の入力トークンに従って適用すべき文法規則を示す。

構文解析器はスタックのトップにある記号と入力バッファ上の現在の記号から適用すべき規則を決定する。

構文解析器が動作開始したとき、既に以下の2つの記号がスタックにある。

[ S, $ ]

ここで、'$' は特殊な終端記号で、スタックの底と入力バッファの最後を示す。'S' はその文法の開始記号である。構文解析器はスタックの内容を入力バッファの内容に従って書き換えていく。しかし、書き換えが必要かどうかはスタック上の内容だけで決定される。

例を示すため、次のような規則1から3の小さなLL(1)文法を想定する:

(1) S → F

(2) S → ( S + F )

(3) F → 1

そして、次の入力の構文解析を行う:

( 1 + 1 )

この文法の構文解析表は次のようになる:

	(	)	1	+	$
S	2	-	1	-	-
F	-	-	3	-	-

$ という特殊な終端記号に関する行があることに注意されたい。$ は入力の終わりを示す。

最初に、構文解析器は入力バッファから '(' を読み込み、スタックから 'S' を読み込む。表を参照すると、規則2を適用すべきであることがわかる。規則2はスタック上の 'S' を '( S + F )' に書き換え、規則番号を出力する。スタックの内容は次のようになる。

[ (, S, +, F, ), $ ]

次に、入力バッファとスタック双方から '(' を取り除く。

[ S, +, F, ), $ ]

次に、入力バッファには '1' があり、スタックのトップが 'S' であることから規則1が適用されて、スタックのトップが 'F' に書き換えられ、さらに規則3が適用される（適用した規則の番号として 1 と 3 が出力される）。スタックは次のようになる。

[ F, +, F, ), $ ]
[ 1, +, F, ), $ ]

さらに、入力バッファの先頭の '1' と '+' はスタックのトップと同じなので、これらが双方から取り除かれる。スタックは以下のようになる。

[ F, ), $ ]

次に、スタック上の 'F' が '1' に書き換えられ、規則番号3が出力される。そして、'1' と ')' は入力バッファとスタック上でマッチするので取り除かれる。この時点で入力バッファもスタックも '$' だけとなり、構文解析が完了する。

この例では、入力文字列が受容され、以下の規則が順に適用されたことが出力される。

[ 2, 1, 3, 3 ]

以上が左端導出である。ここでの左端導出は以下のように行われた。

S → ( S + F ) → ( F + F ) → ( 1 + F ) → ( 1 + 1 )

例が示すように、LL法の構文解析器はスタックのトップが終端記号の場合、非終端記号の場合、特殊記号 $ の場合の3種類のステップを実行する。

• トップが非終端記号の場合、構文解析表を参照し、適用すべき文法規則を決定して実行し（スタックを書き換え）、適用した規則の番号を出力する。構文解析表において、その非終端記号と入力バッファ上のトークンの組み合わせで適用すべき規則が記されていない場合、エラーを通知して停止する。
• トップが終端記号の場合、入力バッファとスタックの記号を比較し、それらが同じである場合に取り除く。違っていた場合、エラーを通知して停止する。
• トップが $ の場合、入力バッファも $ なら、構文解析成功を通知する。入力がまだある場合、エラーを通知する。いずれの場合も構文解析器は停止する。

これらのステップは構文解析器が停止するまで繰り返され、構文解析が成功して左端導出を出力するか、さもなくばエラーを通知する。

構文解析表を作成するためには、非終端記号 'A' がスタックのトップにあり、記号 'a' が入力バッファの先頭にある場合に適用すべき文法規則を決定しなければならない。そのような規則はA → w という形式であり、さらにw に対応する言語に、先頭が 'a' の文字列が少なくとも1つ存在する場合に限られることは簡単に分かる。このため、文字列 w の先頭になりうる終端記号の集合 (First-set) を Fi(w) で表す。また、w が空文字列の可能性もある場合はFi(w)に ε を加える。A₁ → w₁, ..., A_n → w_n という規則群から構成される文法があるとき、Fi(w_i) と Fi(A_i) を各規則について以下のように求める。

1. 各 Fi(w_i) と Fi(A_i) を空集合で初期化する。
2. 各規則 A_i → w_i について、Fi(w_i) を Fi(A_i) に追加する。ここで、Fi は以下のように定義される:
   • Fi(a w' ) = { a } 、a は すべての終端記号
   • Fi(A w' ) = Fi(A)、A は非終端記号で、Fi(A) には ε は含まれない。
   • Fi(A w' ) = Fi(A) \ { ε } ∪ Fi(w' )、A は非終端記号で、Fi(A) には ε が含まれる。
   • Fi(ε) = { ε }
3. 各規則 A_i → w_i について Fi(w_i) を Fi(A_i) に追加する。
4. ステップ2と3を全 Fi 集合が変化しなくなるまで繰り返す。

なお、First-set だけでは構文解析表は完成しない。これは、規則の右側の w が空文字列で書き換えられる可能性があるためである。従って構文解析器はεがFi(w)に含まれるとき、規則 A → w を使い A の後に続く可能性のある記号を考慮しなければならない。つまり A に続く記号の集合 (Follow-set) も必要で、これを Fo(A) と表記する。これは、記号列が αAaβ となるような終端記号 a の集合であり、開始記号から規則を適用していくことで導出される。各非終端記号についての Follow-set は以下のように求められる:

1. 各 Fo(A_i) を空集合で初期化する。
2. A_j → wA_iw' という形式の規則がある場合、
   • 終端記号 a が Fi(w' ) に含まれるなら、a を Fo(A_i) に追加する。
   • ε が Fi(w' ) に含まれるなら、Fo(A_j) を Fo(A_i) に追加する。
3. ステップ2を全ての Fo 集合が変化しなくなるまで繰り返す。

以上で構文解析表の各マスにどの規則を入れるかが決定される。非終端記号 A と終端記号 a に対応する表のマスを T[A, a] で表したとき、以下が成り立つ。

T[A,a] に規則 A → w が入るのは以下の場合だけである。

a が Fi(w) に含まれるか、または

ε が Fi(w) に含まれ、a が Fo(A) に含まれる。

構文解析表の各マスに高々1つの規則だけが入る場合、構文解析器はバックトラッキングなしで常にどの規則を適用すべきかを判断できる。正確には、そのような場合の文法を「LL(1)文法」と呼ぶ。

1990年代中ごろまで、k が 1 より大きい LL(k) の構文解析はほとんど実用化されなかった。というのも、k が増えると指数関数的に構文解析表が大きくなるためである。この状況を変えたのは1992年の PCCTS の登場である（現在ではANTLRと呼ばれている）。PCCTS は多くのプログラミング言語を LL(k)構文解析器で効率的に構文解析でき、最悪ケースの問題も発生しないことを示した。さらに、先読みが限定されていてもLL法が有効な場合もあることが示された。一方、従来からの構文解析器生成ツール（yaccやbison）はLALR(1)構文解析表に基づいており、限定された先読みによるLR法を使っている。

複数トークンの先読みをするLL法の構文解析器を生成する実装例はパーサジェネレータ#実装を参照。

• An easy explanation of First and Follow Sets