LL構文解析表の作成

ウィキペディア小見出し辞書

LL(1)構文解析表の作成

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/01/06 06:27 UTC 版)

「LL法」の記事における「LL(1)構文解析表の作成」の解説

構文解析表を作成するためには、非終端記号 'A' がスタックのトップにあり、記号 'a' が入力バッファの先頭にある場合に適用すべき文法規則を決定しなければならない。そのような規則はA → w という形式であり、さらにw に対応する言語に、先頭が 'a' の文字列が少なくとも1つ存在する場合に限られることは簡単に分かる。このため、文字列 w の先頭になりうる終端記号の集合 (First-set) を Fi(w) で表す。また、w が空文字列の可能性もある場合はFi(w)に ε を加える。A1 → w1, ..., An → wn という規則群から構成される文法があるとき、Fi(wi) と Fi(Ai) を各規則について以下のように求める。 各 Fi(wi) と Fi(Ai) を空集合で初期化する。 各規則 Ai → wi について、Fi(wi) を Fi(Ai) に追加する。ここで、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(ε) = { ε } 各規則 Ai → wi について Fi(wi) を Fi(Ai) に追加する。 ステップ2と3を全 Fi 集合が変化しなくなるまで繰り返す。 なお、First-set だけでは構文解析表は完成しない。これは、規則の右側の w が空文字列で書き換えられる可能性があるためである。従って構文解析器はεがFi(w)に含まれるとき、規則 A → w を使い A の後に続く可能性のある記号を考慮しなければならない。つまり A に続く記号の集合 (Follow-set) も必要で、これを Fo(A) と表記する。これは、記号列が αAaβ となるような終端記号 a の集合であり、開始記号から規則を適用していくことで導出される。各非終端記号についての Follow-set は以下のように求められる: 各 Fo(Ai) を空集合で初期化する。 Aj → wAiw' という形式の規則がある場合、終端記号 a が Fi(w' ) に含まれるなら、a を Fo(Ai) に追加する。 ε が Fi(w' ) に含まれるなら、Fo(Aj) を Fo(Ai) に追加する。 ステップ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)構文解析表の作成

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/01/06 06:27 UTC 版)

「LL法」の記事における「LL(k)構文解析表の作成」の解説

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