「LL法」の版間の差分

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

:{| border="1" align="center" cellspacing="3" padding="5" class="wikitable" alignstyle="text-align: center"

|! || '''(''' !! || ''')''' ||!! '''1''' !! + ||!! '''+'''$

| '''S''' || 2 || - || 1 || - || -

| -

| '''F'''- || - || - 3 || 3 - || -

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

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

#* 終端記号 ''a'' が ''Fi''(''w' ''）) に含まれるなら、''a'' を '''Fo'''(''A''_''i'') に追加する。