LLパーサー

コンピュータサイエンスにおいて、LLパーサーとは、制限付き文脈自由言語のためのトップダウンパーサーである。入力を左から右へと解析し、文の最左導出を実行する。

LL パーサーは、文を解析する際にk 個の先読みトークンを使用する場合、 LL( k ) パーサーと呼ばれます。文法は、LL ( k ) パーサーを構築できる場合、LL( k ) 文法と呼ばれます。形式言語は、LL( k ) 文法を持つ場合、LL( k ) 言語と呼ばれます。各k ≥ 0に対して、LL( k ) 言語の集合は、LL( k + 1) 言語の集合に適切に含まれます。 ^[¹^]このことから、すべての文脈自由言語が LL( k )パーサーによって認識されるわけではないことがわかります。

LL パーサーは、LL 正規言語を解析する場合、LL 正規 (LLR) と呼ばれます。^[²^]^[³^]^[⁴^] LLR 文法のクラスには、すべてのkに対するすべての LL( k ) 文法が含まれます。すべての LLR 文法に対して、その文法を線形時間で解析する LLR パーサーが存在します。

2 つの命名上の外れ値パーサータイプは LL(*) と LL(finite) です。パーサーが LL(*)/LL(finite) 構文解析戦略を使用する場合、そのパーサーは LL(*)/LL(finite) と呼ばれます。^{[ 5 ]}^{[ 6 ]} LL(*) および LL(finite) パーサーは、機能的にはPEGパーサーに近いです。LL(finite) パーサーは、先読みと先読み比較の量で任意の LL( k ) 文法を最適に解析できます。LL(*) 戦略で解析可能な文法のクラスには、構文述語と意味述語の使用により、文脈依存言語が含まれますが、特定されていません。LL(*) パーサーはTDPLパーサーとして考える方が適切であると示唆されています。^{[ 7 ]} 一般的な誤解とは異なり、LL(*) パーサーは一般的に LLR ではなく、平均的には劣る (線形時間に対して超線形)、最悪の場合にははるかに劣る (線形時間に対して指数関数的) ことが構造上保証されています。

LL文法、特にLL(1)文法は、これらの文法のパーサーを簡単に構築できるため、実用上非常に興味深いものであり、多くのコンピュータ言語はこの理由でLL(1)となるように設計されている。^{[ 8 ]} LLパーサーはテーブルベースである場合もある^{[ 9 ]} 、つまりLRパーサーに似ているが、LL文法は再帰下降パーサーによって解析することもできる。WaiteとGoos(1984)によると^[¹⁰^] 、 LL( k )文法はStearnsとLewis(1969)によって導入された。^[¹¹^]

概要

与えられた文脈自由文法に対して、パーサーは最も左の導出を見つけようとします。例として文法Gを挙げます。

$S\to E$
$E\to (E+E)$
$E\to i$

最も左の導出 $w=((i+i)+i)$ は：

S\ {\overset {(1)}{\Rightarrow }}\ E\ {\overset {(2)}{\Rightarrow }}\ (E+E)\ {\overset {(2)}{\Rightarrow }}\ ((E+E)+E)\ {\overset {(3)}{\Rightarrow }}\ ((i+E)+E)\ {\overset {(3)}{\Rightarrow }}\ ((i+i)+E)\ {\overset {(3)}{\Rightarrow }}\ ((i+i)+i)

一般的に、左端の非終端記号を展開するルールを選択する際には、複数の選択肢があります。前の例のステップ2では、パーサーはルール2とルール3のどちらを適用するかを選択する必要があります。

{\displaystyle S\ {\overset {(1)}{\Rightarrow }}\ E\ {\overset {(?)}{\Rightarrow }}\

効率的に行うには、パーサーは可能な限りバックトラックせずに決定論的にこの選択を行うことができなければなりません。一部の文法では、未読の入力を覗き見することによって（読み込まずに）これを行うことができます。この例では、パーサーが次の未読シンボルが（であることを知っている場合、使用できる唯一の正しいルールは2です。

一般的に、LL( k )パーサーはk個の記号を先読みできます。しかし、与えられた文法に対して、それを認識するあるkに対するLL( k )パーサーが存在するかどうかを判定する問題は決定不能です。各kに対して、LL( k )パーサーでは認識できないが、 LL( k +1)パーサーでは認識できる言語が存在します。

上記の分析を用いて、以下の正式な定義を与えることができる。

G を文脈自由文法とし、k ≥ 1とする。任意の 2 つの左端導出に対して、次の条件が満たされる場合、Gは LL( k ) であると言う。

$S\ \Rightarrow \ \cdots \ \Rightarrow \ wA\alpha \ \Rightarrow \ \cdots \ \Rightarrow \ w\beta \alpha \ \Rightarrow \ \cdots \ \Rightarrow \ wu$
$S\ \Rightarrow \ \cdots \ \Rightarrow \ wA\alpha \ \Rightarrow \ \cdots \ \Rightarrow \ w\gamma \alpha \ \Rightarrow \ \cdots \ \Rightarrow \ wv$

以下の条件が成り立つ：文字列の接頭辞 $u$ 長さ $k$ 文字列の接頭辞に等しい $v$ 長さkのということは $\beta =\gamma$ 。

この定義では、 $S$ は開始記号で、 $A$ 任意の非終端記号。既に導出された入力 $w$ しかし、読まれていない $u$ そして $v$ は終端記号の文字列です。ギリシャ文字 $\alpha$ 、 $\beta$ そして $\gamma$ 終端記号と非終端記号の両方を含む任意の文字列（空の場合もある）を表します。接頭辞の長さは先読みバッファのサイズに対応し、このバッファは異なる単語の任意の2つの派生を区別するのに十分であると定義されています。

パーサー

LL( k )パーサーは、入力シンボルを読み込むことなく次のk個のシンボルを覗き見ることができる決定性プッシュダウンオートマトンです。バッファと入力アルファベットはどちらも有限サイズであるため、先読みバッファの内容を有限状態空間に格納することで、この覗き見機能をエミュレートできます。結果として、これはオートマトンをより強力にするものではなく、便利な抽象化となります。

スタックアルファベットは $\Gamma =N\cup \Sigma$ 、どこ：

$N$ は非終端記号の集合です。
$\Sigma$ 入力終了記号$を持つ終端（入力）記号のセット。

パーサースタックには、最初はEOIの上に開始シンボル[S $ ]が含まれています。動作中、パーサーはシンボルを繰り返し置き換えます。 $X$ スタックの一番上に:

いくつか $\alpha$ 、もし $X\in N$ そしてルールがある $X\to \alpha$ ;
と $\epsilon$ （一部の表記では） $\lambda$ つまり、 $X$ スタックからポップされた場合、 $X\in \Sigma$ この場合、入力シンボル $x$ 読み取られ、もし $x\neq X$ パーサーは入力を拒否します。

スタックから最後に削除されるシンボルがEOI（入力終了記号）であれば、解析は成功し、オートマトンが空のスタックを介して受理する。

状態と遷移関数は明示的に与えられず、より便利な構文解析表を用いて指定（生成）されます。この表は以下のマッピングを提供します。

行: スタックの最上位シンボル $X$
列: | w | ≤ k先読みバッファの内容
セル: ルール番号 $X\to \alpha$ または $\epsilon$

パーサーが有効な遷移を実行できない場合、入力は拒否されます（空のセル）。表をよりコンパクトにするため、通常は終端記号のない行のみが表示されます。これは、終端記号の場合も処理は同じであるためです。

具体的な例

設定

LL(1)構文解析器の動作を説明するために、以下の小さなLL(1)文法を考えてみましょう。

S → F
S → ( S + F )
F → a

そして、以下の入力を解析します。

( a + a )

文法のLL(1)構文解析表は、各非終端記号に対応する行と、各終端記号に対応する列を持ちます（入力ストリームの終わりを示すために使用される特殊終端記号$も含まれます）。

表の各セルは、文法の規則を最大で 1 つ指すことができます (番号で識別されます)。たとえば、上記の文法の構文解析表では、非終端記号「S」と終端記号「」のセルは、（'はルール番号2を指しています。

構文解析テーブルを作成するアルゴリズムについては後のセクションで説明しますが、まずはパーサーが構文解析テーブルを使って入力を処理する方法を見ていきましょう。

解析手順

各ステップにおいて、パーサーは入力ストリームから次に使用可能なシンボルを読み取り、スタックの最上位シンボルを読み取ります。入力シンボルとスタックの最上位シンボルが一致する場合、パーサーは次の入力シンボルに進み、スタックの最上位シンボルをポップすることで、両方のシンボルを破棄します。この処理は、入力シンボルとスタックの最上位シンボルが一致しなくなるまで繰り返されます。

したがって、最初のステップで、パーサーは入力シンボル「（' とスタックトップシンボル 'S'。解析テーブル命令は入力シンボル ' で始まる列から来ます。（' とスタックトップ記号 'S' で始まる行。このセルには '2' が含まれており、これはパーサーにルール (2) を適用するように指示します。パーサーは 'S' を ' に書き換える必要があります。( S + F )スタックから「S」を削除し、「)」、「F」、「」をプッシュすることで、スタック上に「」を追加します。+', 'S', '（' をスタックに書き込み、これによりルール番号 2 が出力に書き込まれます。スタックは次のようになります。

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

2 番目のステップでは、パーサーは「'」を削除します。（入力ストリームとスタックが一致するようになったので、スタックは次のようになります。

[ S, + , F, ) , $ ]

これで、パーサーの入力ストリームには「a」があり、スタックのトップには「S」があります。構文解析テーブルは、文法の規則（1）を適用し、規則番号1を出力ストリームに書き込むように指示します。スタックは次のようになります。

[ F, + , F, ) , $ ]

パーサーの入力ストリームには「a」があり、スタックのトップには「F」があります。構文解析テーブルは、文法の規則（3）を適用し、規則番号3を出力ストリームに書き込むように指示します。スタックは次のようになります。

[ a、+、 F、)、$ ]

パーサーに「入力ストリーム上のa'と '1' はスタックの先頭にあります。同じなので、入力ストリームから削除し、スタックの先頭からポップします。パーサーはその後 ' を持ちます。+入力ストリーム上で、+' はスタックの最上位にあるため、'a' と同様にスタックからポップされ、入力ストリームから削除されます。その結果、次のようになります。

[ F, ) , $ ]

次の 3 つのステップで、パーサーはスタック上の「F」を「」に置き換えます。1'、ルール番号3を出力ストリームに書き込み、'を削除します。1' そして '）スタックと入力ストリームの両方から ' を取得します。したがって、パーサーは ' で終了します。$スタックと入力ストリームの両方で。

この場合、パーサーは入力文字列を受け入れたことを報告し、以下のルール番号のリストを出力ストリームに書き込みます。

[ 2, 1, 3, 3 ]

これは確かに、入力文字列の最左導出に関する規則のリストであり、次のとおりです。

S → ( S + F ) → ( F + F ) → ( a + F ) → ( a + a )

C++によるパーサーの実装

以下に、例の言語に対するテーブルベースのLLパーサーのC++実装を示します。

#include <iostream> #include <map> #include <stack>enum Symbols { // シンボル: // 終端記号: TS_L_PARENS 、// ( TS_R_PARENS 、// ) TS_A 、// a TS_PLUS 、// + TS_EOS 、// $、この場合は '\0' に対応TS_INVALID 、// 無効なトークン// 非終端記号: NTS_S 、// S NTS_F // F };/*有効なトークンを対応する終端記号に変換します*/ Symbols lexer ( char c ) { switch ( c ) { case '(' : return TS_L_PARENS ; case ')' : return TS_R_PARENS ; case 'a' : return TS_A ; case '+' : return TS_PLUS ; case '\0' : return TS_EOS ; // スタックの末尾: $ 終端記号default : return TS_INVALID ; } }int main ( int argc , char ** argv ) { using namespace std ;if ( argc < 2 ) { cout << "使用法: \n\t ll '(a+a)'" << endl ; return 0 ; }// LLパーサーテーブル、<非終端記号、終端記号>のペアをアクションにマッピングしますmap < Symbols , map < Symbols , int >> table ; stack < Symbols > ss ; //シンボルスタックchar * p ; // 入力バッファ//シンボルスタックを初期化しますss.push ( TS_EOS ) ; //終端記号、$ ss.push ( NTS_S ); // 非終端記号、S// シンボルストリームカーソルを初期化しますp = & argv [ 1 ][ 0 ];// 解析テーブルを設定しますtable [ NTS_S ][ TS_L_PARENS ] = 2 ; table [ NTS_S ][ TS_A ] = 1 ; table [ NTS_F ][ TS_A ] = 3 ;while ( ss . size () > 0 ) { if ( lexer ( * p ) == ss . top ()) { cout << "Matched symbols: " << lexer ( * p ) << endl ; p ++ ; ss . pop (); } else { cout << "Rule " << table [ ss . top ()][ lexer ( * p )] << endl ; switch ( table [ ss . top ()][ lexer ( * p )]) { case 1 : // 1. S → F ss . pop (); ss . push ( NTS_F ); // F break ;case 2 : // 2. S → ( S + F ) ss . pop (); ss . push ( TS_R_PARENS ); // ) ss . push ( NTS_F ); // F ss . push ( TS_PLUS ); // + ss . push ( NTS_S ); // S ss . push ( TS_L_PARENS ); // ( break ;case 3 : // 3. F → a ss . pop (); ss . push ( TS_A ); // a break ;default : cout << "解析テーブルがデフォルトになりました" << endl ; return 0 ; } } }cout << "解析完了" << endl ;return 0 ; }

Pythonでのパーサーの実装

from enum import Enum from collections.abc import Generatorclass Term ( Enum ): passクラスRule ( Enum ):渡す# すべての定数は0からインデックス付けされますclass Terminal ( Term ): LPAR = 0 RPAR = 1 A = 2 PLUS = 3 END = 4 INVALID = 5def __str__ ( self ) : return f " T_ { self.name } "クラスNonTerminal (ルール): S = 0 F = 1def __str__ ( self ) : return f " N_ { self.name } "# テーブルを解析するtable = [[ 1 , - 1 , 0 , - 1 , - 1 , - 1 ], [ - 1 , - 1 , 2 , - 1 , - 1 , - 1 ]]ルール= [ [ NonTerminal . F ], [ Terminal . LPAR , NonTerminal . S , Terminal . PLUS , NonTerminal . F , Terminal . RPAR , ], [ Terminal . A ], ]stack = [ Terminal.END , NonTerminal.S ]def lexical_analysis ( input_string : str ) -> Generator [ Terminal ]: print ( "字句解析 " ) for c in input_string : match c : case "a" : yield Terminal . A case "+" : yield Terminal . PLUS case "(" : yield Terminal . LPAR case ")" : yield Terminal . RPAR case _ : yield Terminal . INVALID yield Terminal . ENDdef syntactic_analysis ( tokens : list [ Terminal ]) -> None : print ( "tokens:" , end = " " ) print ( * tokens , sep = ", " ) print ( "Syntactic analysis" ) position = 0 while stack : svalue = stack . pop () token = tokens [ position ] if isinstance ( svalue , Term ): if svalue == token : position += 1 print ( "pop" , svalue ) if token == Terminal . END : print ( "input accepted" ) else : raise ValueError ( "bad term on input:" , str ( token )) elif isinstance ( svalue , Rule ): print ( f " { svalue = !s} , { token = !s} " ) rule = table [ svalue . value ][ token . value ] print ( f " { rule = } " ) for r in reversed ( RULES [ rule ]): stack . append ( r ) print ( "stacks: " , end = " " ) print ( * stack , sep = ", " )if __name__ == "__main__" : inputstring = "(a+a)" syntactic_analysis ( list ( lexical_analysis ( inputstring )))

出力:

字句解析トークン: T_LPAR、T_A、T_PLUS、T_A、T_RPAR、T_END構文解析svalue = N_S、トークン = T_LPARルール = 1スタック: T_END、T_RPAR、N_F、T_PLUS、N_S、T_LPAR T_LPARスタックをポップ: T_END、T_RPAR、N_F、T_PLUS、N_S svalue = N_S、トークン = T_Aルール = 0スタック: T_END、T_RPAR、N_F、T_PLUS、N_F svalue = N_F、トークン = T_Aルール = 2スタック: T_END、T_RPAR、N_F、T_PLUS、T_A T_A スタックをポップ: T_END、T_RPAR、N_F、T_PLUS T_PLUSスタックをポップ: T_END、T_RPAR、N_F svalue = N_F、トークン = T_Aルール = 2スタック: T_END、T_RPAR、T_A T_Aスタックをポップ: T_END、T_RPAR T_RPARスタックをポップ: T_END T_END入力が受け入れられたスタック:

備考

例からわかるように、パーサーはスタックの最上位が非終端記号、終端記号、または特殊記号$のいずれであるかに応じて、3 種類のステップを実行します。

トップが非終端記号の場合、パーサーは入力ストリーム上の記号と非終端記号に基づいて構文解析テーブルを検索し、スタック上の非終端記号を置き換えるためにどの文法規則を使用すべきかを判断します。規則の番号は出力ストリームに書き込まれます。構文解析テーブルに該当する規則がない場合、パーサーはエラーを報告して停止します。
先頭が終端記号の場合、パーサーはそれを入力ストリーム上の記号と比較し、両者が等しい場合は両方とも削除します。等しくない場合は、パーサーはエラーを報告して停止します。
先頭が$で、入力ストリームにも$が含まれている場合、パーサーは入力の解析が成功したと報告し、そうでない場合はエラーを報告します。どちらの場合も、パーサーは停止します。

これらの手順はパーサーが停止するまで繰り返され、その後、入力の解析が完了して左端導出が出力ストリームに書き込まれるか、エラーが報告されます。

LL(1)構文解析テーブルの構築

構文解析テーブルを埋めるには、パーサーがスタックの最上位に非終端記号A があり、入力ストリームに記号aがある場合に、どの文法規則を選択すべきかを確立する必要があります。このような規則はA → wの形式であるべきであり、 wに対応する言語にはaで始まる文字列が少なくとも 1 つあるべきであることは容易にわかります。この目的のために、 wの第一集合(ここではFi ( w ) と表記) を、 w内の何らかの文字列の先頭に見つかる終端記号の集合として定義します。ただし、空文字列もwに属する場合は ε を追加します。規則A ₁ → w ₁、 ...、A _n → w _nを持つ文法が与えられた場合、各規則についてFi ( w _i ) とFi ( A _i ) を次のように計算できます。

すべてのFi ( A _i ) を空集合で初期化する
すべてのルールA _i → w _iに対して、 Fi( w _i ) をFi ( A _i ) に追加します。ここで、Fi は次のように定義されます。
- $Fi(aw') = {a}$ はすべての終端aに対して成り立つ。
- $Fi(Aw') = Fi (A)は、ε が$ Fi ( A )に含まれないすべての非終端Aに対して成り立つ。
- $Fi(Aw') = (Fi (A) ∖ { ε }) \cup Fi(w')は、ε が$ Fi ( A )に含まれるすべての非終端記号 Aに対して成り立つ。
- Fi(ε) = { ε }
すべてのルールA _i → w _iに対してFi( w _i ) をFi ( A _i )に追加する
すべてのFiセットが同じ状態になるまで、手順2と3を繰り返します。

その結果、以下の連立方程式に対する最小不動点解が得られる。

各ルール A → wに対して $Fi$ $($ $A$ $) \supseteq$ $Fi$ $($ $w$ $)が成り立つ。$
$Fi (a) \supseteq {a}、$ 各終端aについて
$Fi (w 0 w 1) \supseteq Fi (w 0)\cdot Fi (w 1) 、$ すべての単語w ₀およびw _{1について}
$Fi (ε) \supseteq {ε}$

ここで、単語の集合UとVに対して、切り捨て積は次のように定義される。 $U\cdot V=\{(uv):1\mid u\in U,v\in V\}$ 、w:1 は、長さが 2 以上の単語 w の最初の長さ - 1 の接頭辞、またはw の長さが 0 または 1 の場合はw自体を表します。

残念ながら、First-setsだけでは構文解析テーブルを計算するには不十分です。これは、ルールの右辺w が最終的に空文字列に書き換えられる可能性があるためです。したがって、パーサーは、 εがFi ( w )に含まれており、入力ストリームにAに続く可能性のあるシンボルが見つかった場合、ルールA → wも使用する必要があります。そのため、ここではFo ( A )と表記されるAのFollow-setも必要です。これは、開始シンボルから派生できるシンボル列αAaβが存在するような終端記号aの集合として定義されます。入力ストリームの終了を示す特別な終端記号として$ を、開始シンボルとしてS を使用します。

文法における非終端記号のフォローセットを計算するには、次のようにします。

Fo ( S )を{ $ }で初期化し、他のすべてのFo ( Ai )を空集合で初期化する_。
A _j → wA _iw ′の形の規則がある場合、
- 終端a がFi ( w ′ )に含まれている場合、a をFo ( A _i )に追加します。
- εがFi ( w ′ )に含まれる場合、 Fo ( Aj )を_Fo ( Ai )_に加える
- w' の長さが 0 の場合、 Fo ( A _j ) をFo ( A _i )に加える
すべてのFoセットが同じ状態になるまで、ステップ 2 を繰り返します。

これは、以下のシステムに対する最小不動点解を提供する。

$Fo (S) \supseteq {$}$
$Fo (A) \supseteq Fi (w)\cdot Fo (B)$ は、次の形式の各ルールについて成り立つ。 $B\to \dots Aw$ ⁠

これで、構文解析表のどこにどの規則が現れるかを正確に定義できます。T [ A , a ]が非終端記号Aと終端記号aの表のエントリを表す場合、

T [ A , a ] は、 A → w ルールを含むのは、

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

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

言い換えれば、T [ A , a ] は、各 $a$ $\in$ $Fi$ $($ $w$ $)\cdot$ $Fo$ $($ $A$ ) に対して規則A → wを含む $。$

テーブルの各セルに最大で1つのルールしか含まれていない場合、パーサーは常にどのルールを使用すべきかを把握できるため、バックトラックすることなく文字列を解析できます。まさにこのような場合に、文法はLL(1)文法と呼ばれます。

LL( k )構文解析テーブルの構築

LL(1)パーサーの構成は、k > 1の場合のLL( k )に以下の変更を加えることで適応させることができます。

切り捨て積は次のように定義される $U\cdot V=\{(uv):k\mid u\in U,v\in V\}$ ここで、w : k は、長さ > kの単語の最初の長さk接頭辞を表すか、w の長さがk以下であれば、 w自体を表します。
Fo ( S ) = { $ ^k }
LL(1) に対して与えられたFiの構成のステップ 2 でもFi ( αβ ) = Fi ( α ) ⋅ Fi ( β )を適用します。
Fo構成のステップ 2 では、 A _j → wA _i w ′に対して、Fi ( w ′ )· Fo ( A _j ) をFo ( A _i ) に加えるだけです。

ここで、入力にはk 個の末尾マーカー$が付加され、 k 個の先読みコンテキストを完全に考慮します。このアプローチは ε の特殊なケースを排除し、LL(1) の場合にも同様に適用できます。

1990 年代半ばまでは、LL( k ) 構文解析( k > 1 の場合) は、最悪の場合パーサーテーブルのサイズがkに対して指数関数的になるため、実用的ではないと広く信じられていました。 ^[¹²^]^:^263–265この認識は、1992 年頃にPurdue Compiler Construction Tool Setがリリースされてから徐々に変化しました。このツールセットでは、多くのプログラミング言語が、パーサーの最悪ケースの動作を引き起こすことなく、LL( k ) パーサーによって効率的に解析できることが実証されました。さらに、特定のケースでは、無制限の先読みでも LL 構文解析が可能です。これに対し、yaccのような従来のパーサージェネレータは、 LALR(1)パーサーテーブルを使用して、固定の 1 トークン先読みを持つ制限付きLR パーサーを構築します。

紛争

序論で述べたように、LL(1)パーサーはLL(1)文法を持つ言語を認識します。LL(1)文法は文脈自由文法の特殊なケースです。LL(1)パーサーはすべての文脈自由言語を認識できるわけではありません。LL(1)言語はLR(1)言語の真部分集合であり、LR(1)言語はすべての文脈自由言語の真部分集合です。文脈自由文法がLL(1)文法であるためには、特定の矛盾が生じてはなりません。

用語

A を非終端記号とする。FIRST( A )は、 Aから派生した任意の文字列の最初の位置に現れることができる終端記号の集合として定義される。FOLLOW( A ) は、次の集合の和集合である。^{[ 13 ]}

FIRST( B ) ここでBは、生成規則の右辺でA の直後に続く任意の非終端記号です。
FOLLOW( B ) ここでBはB → wAの形式のルールの任意のヘッドです。

LL(1)の衝突

LL(1)の衝突には主に2つの種類があります。

第一/第一の衝突

FIRSTセットは、同じ非終端記号に対して2つの異なる文法規則を交差させます。LL(1) FIRST/FIRSTの競合の例を以下に示します。

S -> E | E 'a' E -> 'b' | ε

FIRST( E ) = { b , ε} および FIRST( E a ) = { b , a }であるため、表が描画されると、生成規則Sの終端bの下で競合が発生します。

特殊なケース：左再帰

左再帰は、すべての選択肢との間でFIRST/FIRST競合を引き起こします。

E -> E '+' 項 | alt1 | alt2

最初に/次に衝突する

文法規則の FIRST セットと FOLLOW セットは重複しています。FIRSTセットに空文字列(ε) が含まれている場合、どちらの選択肢を選ぶべきか不明です。LL(1) の競合の例を以下に示します。

S -> A 'a' 'b' A -> 'a' | ε

Aの最初の集合は{ a , ε} であり、次の集合は { a } です。

LL(1)衝突の解決策

左因数分解

よくある左辺因子は「因数分解される」。

A → X | XYZ

になる

A -> XB B -> YZ | ε

FIRST/FIRST のように、2 つの選択肢が同じ記号で始まる場合に適用できます。

上記のFIRST/FIRST競合の例を用いた別の例（より複雑な例）：

S -> E | E 'a' E -> 'b' | ε

（単一の非終端記号に統合される）

S -> 'b' | ε | 'b' 'a' | 'a'

そして左因数分解によって、

S -> 'b' E | E E -> 'a' | ε

代替

間接的な競合や FIRST/FOLLOW の競合を解消するために、あるルールを別のルールに置き換える。ただし、これにより FIRST/FIRST の競合が発生する可能性があることに注意してください。

左再帰の削除

^[¹⁴^]を参照

一般的な方法については、「左再帰の除去」を参照してください。左再帰除去の簡単な例：次の生成規則は、E に対して左再帰を持っています。

E -> E '+' T E -> T

このルールは、'+'で区切られたTのリストに他なりません。正規表現では、T ('+' T)* となります。したがって、このルールは次のように書き換えることができます。

E -> TZ Z -> '+' TZ Z -> ε

これで左再帰は発生せず、どちらのルールにも矛盾はなくなりました。

しかし、すべての文脈自由文法が同等のLL(k)文法を持つわけではありません。例:

S -> A | B A -> 'a' A 'b' | ε B -> 'a' B 'b' 'b' | ε

この文法によって生成される言語を受理するLL(k)文法は存在しないことが示される。

注記

↑ Rosenkrantz, DJ; Stearns, RE (1970). "Properties of Deterministic Top Down Grammars" . Information and Control . 17 (3): 226– 256. doi : 10.1016/s0019-9958(70)90446-8 .
↑ジャルザベク、スタニスラフ。クロチク、トマシュ (1974)。「LL-正規文法」。マジン・マテマティチニッチ研究所：107–119。
↑ジャルザベク、スタニスラフ。クロチク、トマシュ (1975 年 11 月)。「LL-正規文法」。情報処理レター。4 (2): 31–37。土井: 10.1016/0020-0190(75)90009-5。
↑ David A. Poplawski (1977年8月). LL正規言語の特性（技術報告書）。パデュー大学、コンピュータサイエンス学科。
↑ Parr, Terence; Fisher, Kathleen (2011). "LL (*) ANTLR パーサージェネレータの基礎". ACM SIGPLAN Notices . 46 (6): 425– 436. doi : 10.1145/1993316.1993548 .
↑ Belcak, Peter (2020). "最適な LL(k) 構文解析のための LL(finite) 構文解析戦略". arXiv : 2010.07874 [ cs.PL ].
↑ Ford, Bryan (2004). "構文解析式文法: 認識に基づく構文基盤". ACM SIGPLAN Notices . doi : 10.1145/982962.964011 .
↑パット・テリー (2005). C# と Java によるコンパイル. ピアソン・エデュケーション. pp. 159–164 . ISBN 9780321263605。
↑ 「LL(1)構文解析テーブルの構築」。2019年2月27日。
↑ウィリアム・M・ウェイト、ゲルハルト・グース（1984）。コンパイラ構築。コンピュータサイエンスのテキストとモノグラフ。ハイデルベルク：シュプリンガー。ISBN 978-3-540-90821-0。参照箇所：第 5.3.2節、121～127ページ、特に 123ページ。
↑ Richard E. Stearnsおよび PM Lewis (1969). "Property Grammars and Table Machines" . Information and Control . 14 (6): 524– 549. doi : 10.1016/S0019-9958(69)90312-X .
↑ Fritzson, Peter A. (1994年3月23日). Compiler Construction: 5th International Conference, CC '94, Edinburgh, UK, April 7–9, 1994. Proceedings . Springer Science & Business Media. ISBN 978-3-540-57877-2。
↑ 「LL Grammars」（PDF）。2010年6月18日にオリジナルからアーカイブ（PDF）。 2010年5月11日に取得。
↑最新のコンパイラ設計、Grune、Bal、Jacobs、Langendoen

外部リンク

C#でLL(1)パーサーを実装するためのチュートリアル（アーカイブ済み）
構文解析シミュレータこのシミュレータは、構文解析テーブル LL(1) を生成し、本書の演習問題を解くために使用されます。
LL文法とLR文法の言語理論的比較

[1] Rosenkrantz, DJ; Stearns, RE (1970). "Properties of Deterministic Top Down Grammars" . Information and Control . 17 (3): 226– 256. doi : 10.1016/s0019-9958(70)90446-8 .

[2] ジャルザベク、スタニスラフ。クロチク、トマシュ (1974)。「LL-正規文法」。マジン・マテマティチニッチ研究所：107–119。

[3] ジャルザベク、スタニスラフ。クロチク、トマシュ (1975 年 11 月)。「LL-正規文法」。情報処理レター。4 (2): 31–37。土井: 10.1016/0020-0190(75)90009-5。

[4] David A. Poplawski (1977年8月). LL正規言語の特性（技術報告書）。パデュー大学、コンピュータサイエンス学科。

[5] Parr, Terence; Fisher, Kathleen (2011). "LL (*) ANTLR パーサージェネレータの基礎". ACM SIGPLAN Notices . 46 (6): 425– 436. doi : 10.1145/1993316.1993548 .

[6] Belcak, Peter (2020). "最適な LL(k) 構文解析のための LL(finite) 構文解析戦略". arXiv : 2010.07874 [ cs.PL ].

[7] Ford, Bryan (2004). "構文解析式文法: 認識に基づく構文基盤". ACM SIGPLAN Notices . doi : 10.1145/982962.964011 .

[8] パット・テリー (2005). C# と Java によるコンパイル. ピアソン・エデュケーション. pp. 159–164 . ISBN 9780321263605。

[9] 「LL(1)構文解析テーブルの構築」。2019年2月27日。

[10] ウィリアム・M・ウェイト、ゲルハルト・グース（1984）。コンパイラ構築。コンピュータサイエンスのテキストとモノグラフ。ハイデルベルク：シュプリンガー。ISBN 978-3-540-90821-0。参照箇所：第 5.3.2節、121～127ページ、特に 123ページ。

[11] Richard E. Stearnsおよび PM Lewis (1969). "Property Grammars and Table Machines" . Information and Control . 14 (6): 524– 549. doi : 10.1016/S0019-9958(69)90312-X .

[12] Fritzson, Peter A. (1994年3月23日). Compiler Construction: 5th International Conference, CC '94, Edinburgh, UK, April 7–9, 1994. Proceedings . Springer Science & Business Media. ISBN 978-3-540-57877-2。

[13] 「LL Grammars」（PDF）。2010年6月18日にオリジナルからアーカイブ（PDF）。 2010年5月11日に取得。

[14] 最新のコンパイラ設計、Grune、Bal、Jacobs、Langendoen

[

[

[

[

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[

[

[

[ 13 ]

[

概要