LLパーサー

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

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

LL パーサは、LL 正規言語を解析する場合、LL 正規 (LLR) と呼ばれます。^{[要説明] [2] [3] [4]} 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パーサはテーブルベース^{[要出典] 、つまり}LRパーサに似ていますが、LL文法は再帰下降パーサによって解析することもできます。WaiteとGoos（1984）によると、^[9] LL( k )文法はStearnsとLewis（1969）によって導入されました。^[10]

与えられた文脈自由文法に対して、パーサーは最も左の導出を見つけようとします。 次のような文法の例を考えてみましょう。 ${\displaystyle G}$

1. ${\displaystyle S\to E}$
2. ${\displaystyle E\to (E+E)}$
3. ${\displaystyle E\to i}$

の左端の導出は次のようになります。 ${\displaystyle w=((i+i)+i)}$

${\displaystyle 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 です。 ${\displaystyle (}$

一般に、パーサーはシンボルを先読みすることができます。しかし、文法が与えられた場合、それを認識するパーサーが存在するかどうかを判断する問題は決定不可能です。各 に対して、パーサーでは認識できないが では認識できる言語が存在します。 ${\displaystyle LL(k)}$${\displaystyle k}$${\displaystyle LL(k)}$${\displaystyle k}$${\displaystyle k}$${\displaystyle LL(k)}$${\displaystyle LL(k+1)}$

上記の分析を使用して、次の正式な定義を与えることができます。

を文脈自由文法、 とします。任意の 2 つの左端導出に対して が である場合に限り、 が であると 言えます。${\displaystyle G}$${\displaystyle k\geq 1}$${\displaystyle G}$${\displaystyle LL(k)}$

1. ${\displaystyle S\\Rightarrow\\cdots\\Rightarrow\wA\alpha\\Rightarrow\\cdots\\Rightarrow\w\beta\alpha\\Rightarrow\\cdots\\Rightarrow\wu}$
2. ${\displaystyle S\ \Rightarrow \ \cdots \ \Rightarrow \ wA\alpha \ \Rightarrow \ \cdots \ \Rightarrow \ w\gamma \alpha \ \Rightarrow \ \cdots \ \Rightarrow \ wv}$

次の条件が成立します:長さの文字列のプレフィックスが長さの文字列のプレフィックスに等しいということは、を意味します。 ${\displaystyle u}$${\displaystyle k}$${\displaystyle v}$${\displaystyle k}$${\displaystyle \beta \ =\ \gamma }$

この定義では、 は開始記号で、 は任意の非終端記号です。すでに導出されている入力、およびまだ読み込まれていない、は終端記号の文字列です。ギリシャ文字、、 は終端記号と非終端記号の両方 (空の場合もある) の任意の文字列を表します。プレフィックスの長さは先読みバッファ サイズに対応し、定義ではこのバッファは異なる単語の任意の 2 つの導出を区別するのに十分であるとされています。 ${\displaystyle S}$${\displaystyle A}$${\displaystyle w}$${\displaystyle u}$${\displaystyle v}$${\displaystyle \alpha}$${\displaystyle \beta}$${\displaystyle \gamma}$

パーサーは、読み取りを行わずに次の入力シンボルを覗き見る機能を備えた決定論的なプッシュダウン オートマトンです。バッファと入力アルファベットはどちらもサイズが有限であるため、この覗き見機能は、先読みバッファの内容を有限状態空間に格納することでエミュレートできます。結果として、これによってオートマトンが強力になるわけではありませんが、便利な抽象化になります。 ${\displaystyle LL(k)}$${\displaystyle k}$

スタック アルファベットは です。ここで、 ${\displaystyle \Gamma =N\cup \Sigma }$

• ${\displaystyle N}$非終端記号の集合です。
• ${\displaystyle \Sigma }$特殊な入力終了 (EOI) 記号を含む終端 (入力) 記号のセット。${\displaystyle \$}$

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

• いくつかの と の場合、規則があります。${\displaystyle \alpha}$${\displaystyle X\in N}$${\displaystyle X\to \alpha }$
• （一部の表記では）の場合、すなわち の場合、 がスタックからポップされます。この場合、入力シンボルが読み込まれ、 の場合、パーサーは入力を拒否します。${\displaystyle \epsilon }$${\displaystyle \lambda}$${\displaystyle X}$${\displaystyle X\in \Sigma }$${\displaystyle x}$${\displaystyle x\neq X}$

スタックから削除される最後のシンボルが EOI である場合、解析は成功し、オートマトンは空のスタックを介して受け入れます。

状態と遷移関数は明示的に指定されていません。代わりに、より便利な解析テーブルを使用して指定 (生成) されます。テーブルは次のマッピングを提供します。

• 行: スタックの先頭のシンボル${\displaystyle X}$
• 列:先読みバッファの内容${\displaystyle |w|\leq k}$
• セル:またはのルール番号${\displaystyle X\to \alpha }$${\displaystyle \epsilon }$

パーサーが有効な遷移を実行できない場合、入力は拒否されます (空のセル)。テーブルをよりコンパクトにするために、ターミナルのアクションは同じであるため、非ターミナル行のみが共通して表示されます。

LL(1)パーサーの動作を説明するために、次の小さなLL(1)文法を考えてみましょう。

1. S → F
2. S → ( S + F )
3. F → ア

次の入力を解析します。

( ア + ア )

文法のLL(1)解析表には、非終端記号ごとに行が1つと、終端記号ごとに列が1つあります（ここでは入力ストリームの終わりを示すために使用される$で表される特殊な終端記号を含む）。

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

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

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

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

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

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

[ S, + , F, ) , $ ]

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

[ F, + , F, ) , $ ]

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

[ a、+、 F 、)、$ ]

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

[ F, ) , $ ]

次の 3 つのステップでは、パーサーはスタック上の' F' を' a'に置き換え、ルール番号 3 を出力ストリームに書き込み、スタックと入力ストリームの両方から ' a'と ' )'を削除します。こうして、パーサーはスタックと入力ストリームの両方に ' $'を残して終了します。

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

[ 2, 1, 3, 3 ]

これは実際に入力文字列の 左端の導出に関する規則のリストです。

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

以下は、サンプル言語のテーブルベース 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 ) {名前空間std を使用;    

	  

	if ( argc < 2 ) { cout << "usage: \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 << "一致したシンボル: " << lexer ( * p ) << endl ; p ++ ; ss . pop (); } else { cout << "ルール " << 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 << "parsed table defaulted" << endl ; return 0 ; } } }					    
					 
			
		
	

	cout << "解析が終了しました" << endl ;    

	0 を返す; } 

# すべての定数は 0 からインデックスされます
TERM  =  0 
RULE  =  1

# 端末
T_LPAR  =  0 
T_RPAR  =  1 
T_A  =  2 
T_PLUS  =  3 
T_END  =  4 
T_INVALID  =  5

# 非終端記号
N_S  =  0 
N_F  =  1

# テーブルを解析します。
table  =  [[  1 ,  - 1 ,  0 ,  - 1 ,  - 1 ,  - 1 ], 
         [ - 1 ,  - 1 ,  2 ,  - 1 ,  - 1 ,  - 1 ]]

ルール =  [[( RULE ,  N_F )], 
         [( TERM ,  T_LPAR ),  ( RULE ,  N_S ) ,  ( TERM ,  T_PLUS ),  ( RULE ,  N_F ),  ( TERM ,  T_RPAR )], 
         [( TERM ,  T_A )]]

スタック =  [( TERM ,  T_END ),  ( RULE ,  N_S )]

def  lexical_analysis ( inputstring :  str )  - >  list : 
    print ( "字句解析" ) tokens 
    =  [  ] 
    for c  in  inputstring  : if 
        c  ==    "  + " :  tokens.append ( T_PLUS ) elif c == " ( " : tokens.append ( T_LPAR ) elif c == " ) " : tokens.append ( T_RPAR ) elif c == " a " : tokens.append ( T_A ) else : tokens.append ( T_INVALID ) tokens.append ( T_END ) print ( tokens ) return tokens
            
            
            
         
    
    
     

def  syntactic_analysis ( tokens :  list )  ->  None : 
    print ( "構文解析" ) 
    position  =  0 
    while  len ( stack )  >  0 : 
        ( stype ,  svalue )  =  stack . pop () 
        token  =  tokens [ position ] 
        if  stype  ==  TERM : 
            if  svalue  ==  token : 
                position  +=  1 
                print ( "pop" ,  svalue ) 
                if  token  ==  T_END : 
                    print ( "入力が受け入れられました" ) 
            else : 
                print ( "入力の項が間違っています:" ,  token ) 
                break 
        elif  stype  ==  RULE : 
            print ( "svalue" ,  svalue ,  "token" ,  token ) 
            rule  =  table [ svalue ][ token ] 
            print ( "rule" ,  rule ) 
            for  r  in  riversed ( RULES [ rule ]): 
                stack . append ( r ) 
        print ( "stack" ,  stack )

入力文字列 =  "(a+a)"
構文解析(語彙解析(入力文字列))

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

• 最上位が非終端記号の場合、パーサーは、この非終端記号と入力ストリーム上のシンボルに基づいて、スタック上の非終端記号を置き換えるために使用する文法のルールを解析テーブルで検索します。ルールの番号は出力ストリームに書き込まれます。解析テーブルにそのようなルールがないことが示される場合、パーサーはエラーを報告して停止します。
• 先頭が端末の場合、パーサーはそれを入力ストリーム上のシンボルと比較し、等しい場合は両方とも削除されます。等しくない場合、パーサーはエラーを報告して停止します。
• 先頭が$で、入力ストリームにも$がある場合、パーサーは入力を正常に解析したことを報告し、そうでない場合はエラーを報告します。どちらの場合も、パーサーは停止します。

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

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

1. すべてのFi ( A _i ) を空集合で初期化する
2. すべての規則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 ) \ { ε }) ∪ Fi( w' ) ε がFi ( A )に含まれるすべての非終端記号 Aに対して
   • Fi(ε) = {ε}
3. あらゆるルールA _i → w _iに対して、 Fi( w _i )をFi ( A _i )に追加する
4. すべてのFiセットが同じになるまで、手順 2 と 3 を実行します。

結果は、次のシステムに対する最小の固定点解です。

• Fi ( A ) ⊇ Fi ( w ) の各規則 A → wに対して
• Fi ( a ) ⊇ { a }、各端末aについて
• Fi ( w ₀ w ₁ ) ⊇ Fi ( w ₀ )· Fi ( w ₁ )、すべての単語w ₀とw _{1について}
• フィ（ε）⊇ {ε}

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

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

文法内の非終端記号の Follow-set を計算するには、次のようにします。

1. Fo ( S ) を{ $ }で初期化し、他のすべてのFo ( A _i ) を空集合で初期化する
2. A _j → wA _i w'という形式の規則がある場合、
   • 端末aがFi ( w' )内にある場合、aをFo ( Ai )に追加する_。
   • εがFi ( w' )に含まれる場合、Fo ( A _j )をFo ( A _i )に加える。
   • w'の長さが0の場合、Fo ( A _j ) をFo ( A _i )に追加する。
3. すべてのFoセットが同じになるまで手順 2 を繰り返します。

これは、次のシステムに対して最小の固定点ソリューションを提供します。

• フォ（S）⊇{ $ }
• Fo ( A ) ⊇ Fi ( w )· Fo ( B ) の各規則について B → ... A w

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

T [ A , a ] が規則A → wを含むのは、

aはFi ( w )または

εはFi ( w )にあり、 aはFo ( A )にあります。

同様に、T [ A , a ]には、各a∈Fi ( w )· Fo ( A )に対して規則A → wが含まれます。

テーブルの各セルに最大で1つのルールしか含まれていない場合、パーサーは常にどのルールを使用しなければならないかを認識しているため、バックトラックせずに文字列を解析できます。まさにこの場合、その文法はLL（1）文法と呼ばれます。

LL(1)パーサの構築は、次の変更を加えることで k >1のLL( k )に適応できる。

• 切り捨てられた積は定義される。ここでw:kは長さがkより大きい単語の最初の長さkの接頭辞、またはwの長さがk以下の場合はw自身を表す。${\displaystyle U\cdot V=\{(uv):k\mid u\in U,v\in V\}}$
• Fo ( S ) = { $ ^k }
• LL(1)のFi構築のステップ2にもFi (αβ) = Fi (α) Fi (β)を適用する。${\displaystyle \cdot}$
• Fo構築のステップ2では、A _j → wA _i w'に対して、 Fi ( w' ) Fo ( A _j ) をFo ( A _i ) に追加するだけです。${\displaystyle \cdot}$

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

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

序論で述べたように、LL(1)パーサーは文脈自由文法の特殊なケースであるLL(1)文法を持つ言語を認識します。LL(1)パーサーはすべての文脈自由言語を認識できるわけではありません。LL(1)言語はLR(1)言語の適切なサブセットであり、LR(1)言語はすべての文脈自由言語の適切なサブセットです。文脈自由文法がLL(1)文法であるためには、特定の競合が発生してはなりません。このセクションでは、それについて説明します。

A を非終端記号とする。FIRST( A ) はAから派生した文字列の最初の位置に現れる終端記号の集合である（と定義される）。FOLLOW( A ) は以下の和集合である: ^[12]

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

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

同じ非終端記号に対する2つの異なる文法規則のFIRSTセットが交差します。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 }である。

一般的な左因数は「因数分解」されます。

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 競合が発生する可能性があることに注意してください。

参照。^[13]

一般的な方法については、左再帰の除去を参照してください。左再帰の除去の簡単な例：次の生成規則は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) 文法は存在しないことが示されます。

• パーサージェネレータの比較
• 解析ツリー
• トップダウン解析
• ボトムアップ解析

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