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種類しゅるいのステップを実行じっこうする。

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

これらのステップは構文こうぶん解析かいせき器きが停止ていしするまで繰くり返かえされ、構文こうぶん解析かいせきが成功せいこうして左端ひだりはし導出どうしゅつを出力しゅつりょくするか、さもなくばエラーを通知つうちする。

LL(1)構文こうぶん解析かいせき表ひょうの作成さくせい

構文こうぶん解析かいせき表ひょうを作成さくせいするためには、非終端ひしゅうたん記号きごう '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)文法ぶんぽう」と呼よぶ。

LL(k)構文こうぶん解析かいせき表ひょうの作成さくせい

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

LL(k) 構文こうぶん解析かいせき器き生成せいせいツール

複数ふくすうトークンの先読さきよみをするLL法ほうの構文こうぶん解析かいせき器きを生成せいせいする実装じっそう例れいはパーサジェネレータ#実装じっそうを参照さんしょう。

外部がいぶリンク

• An easy explanation of First and Follow Sets