LL文法

形式言語理論では、LL 文法はLL パーサーによって解析できる文脈自由文法であり、 LL パーサーは入力を左から右に解析し、文の最左導出を構築します (したがって LL であり、最右導出を構築する LR パーサーと比較されます)。LL文法を持つ言語はLL 言語として知られています。これらは、それぞれ決定論的文脈自由文法(DCFG) と決定論的文脈自由言語(DCFL)のサブセットを形成します。特定の文法または言語が「LL 文法/言語である」または単に「LL である」と述べて、それがこのクラスに属することを示します。

LL パーサーは、LR パーサーに似たテーブルベースのパーサーです。LL 文法は、予測パーサー(バックトラックのない再帰下降パーサー) によって解析できるものとして特徴付けられ、簡単に手作業で記述できます。この記事では、LL 文法の形式的な特性について説明します。解析については、 LL パーサーまたは再帰下降パーサーを参照してください。

自然数 が与えられたとき、文脈自由文法 はLL(k) 文法であるとは、 ${\displaystyle k\geq 0}$ ${\displaystyle G=(V,\シグマ,R,S)}$

• 最大記号の長さの各終端記号文字列について、${\displaystyle w\in \Sigma ^{*}}$${\displaystyle k}$
• 各非終端記号に対して、${\displaystyle A\in V}$
• 各終端記号文字列について、${\displaystyle w_{1}\in \Sigma ^{*}}$

ある終端記号文字列に対して、 ${\displaystyle r\in R}$${\displaystyle w_{2},w_{3}\in \Sigma ^{*}}$

• 文字列は開始記号から派生し、${\displaystyle w_{1}Aw_{3}}$${\displaystyle S}$
• ${\displaystyle w_{2}}$は、まず規則を適用した後に導出することができ、${\displaystyle A}$${\displaystyle r}$
• との最初の記号は一致する。^[2]${\displaystyle k}$${\displaystyle w}$${\displaystyle w_{2}w_{3}}$

代替の、しかし同等の正式な定義は次の通りである: は、任意の導出に対して、 LL(k)文法である。${\displaystyle G=(V,\シグマ,R,S)}$

${\displaystyle {\begin{array}{cccccccc}S&\Rightarrow ^{L}&w_{1}A\chi &\Rightarrow &w_{1}\nu \chi &\Rightarrow ^{*}&w_{1}w_{ 2}w_{3}\\S&\Rightarrow ^{L}&w_{1}A\chi &\Rightarrow &w_{1}\omega \chi &\Rightarrow ^{*}&w_{1}w'_{2}w'_{3},\\\end{配列}}}$

の最初の記号がの最初の記号と一致するとき、 となる。^{[3] [4]}${\displaystyle k}$${\displaystyle w_{2}w_{3}}$${\displaystyle w'_{2}w'_{3}}$${\displaystyle \nu =\omega }$

非公式には、パーサーが を、その最も左の非終端記号と がすでに入力から消費された状態で導出した場合、それを調べ、現在の入力の次の記号を調べることで、パーサーはの生成規則を確実に識別できます。 ${\displaystyle w_{1}Aw_{3}}$${\displaystyle A}$${\displaystyle w_{1}}$${\displaystyle w_{1}}$${\displaystyle k}$${\displaystyle w}$${\displaystyle r}$${\displaystyle A}$

過去の入力を考慮しなくても規則の識別が可能な場合、その文法は強いLL(k)文法と呼ばれます。^[5]強いLL( k )文法の正式な定義では、の普遍量指定子は省略され、の「for some」量指定子に追加されます。すべてのLL( k )文法に対して、構造的に同等な強いLL( k )文法を構築できます。^[6]${\displaystyle w_{1}}$${\displaystyle w_{1}}$${\displaystyle w_{1}}$${\displaystyle w_{2},w_{3}}$

LL( k )言語のクラスは、集合の厳密に増加するシーケンスを形成します: LL(0) ⊊ LL(1) ⊊ LL(2) ⊊ …。^[7]与えられた文法GがLL( k )であるかどうかは決定可能ですが、任意の文法が何らかのkに対してLL( k )であるかどうかは決定できません。与えられたLR( k )文法が何らかのmに対してLL( m )文法でもあるかどうかも決定可能です。^[8]

すべてのLL( k )文法はLR( k )文法でもある。εを含まないLL(1)文法はSLR(1)文法でもある。空導出と非空導出の両方を持つ記号を持つLL(1)文法もLALR(1)文法である。空導出のみを持つ記号を持つLL(1)文法はLALR(1)である場合もそうでない場合もある。^[9]

LL文法は左再帰を含む規則を持つことができない。^[10] ε-freeの各LL( k )文法は、同等のグライバッハ標準形のLL( k )文法に変換できる（定義上、左再帰を含む規則を持たない）。^[11]

を終端アルファベットとします。の分割は、すべての に対して言語が正則である場合、正則分割と呼ばれます。 ${\displaystyle \Sigma }$ ${\displaystyle \pi}$${\displaystyle \Sigma^{*}}$${\displaystyle R\in \pi }$${\displaystyle R}$

を文脈自由文法とし、を の正規分割とする。任意の導出に対して、 がLL( ) 文法であるとは、${\displaystyle G=(V,\シグマ,R,S)}$${\displaystyle \pi =\{R_{1},\dotso ,R_{n}\}}$${\displaystyle \Sigma^{*}}$${\displaystyle G}$${\displaystyle \pi}$

${\displaystyle {\begin{array}{cccccccc}S&\Rightarrow ^{L}&w_{1}A\chi _{1}&\Rightarrow &w_{1}\nu \chi _{1}&\Rightarrow ^{ *}&w_{1}x\\S&\Rightarrow ^{L}&w_{2}A\chi _{2}&\Rightarrow &w_{2}\omega \chi _{2}&\Rightarrow ^{*}&w_{2}y,\\\end{配列}}}$

となる。[ ^12]${\displaystyle x\equiv y\mod \pi }$${\displaystyle \nu =\omega }$

文法GがLL 正規(LLR)であるとは、 Gが LL( )となるような正規分割が存在する場合です。言語が LL 正規であるとは、LL 正規文法によって生成される場合です。 ${\displaystyle \Sigma^{*}}$${\displaystyle \pi}$

LLR 文法は明確であり、左再帰にはなりません。

すべてのLL( k )文法はLLRである。すべてのLL( k )文法は決定論的であるが、決定論的ではないLLR文法も存在する。^[13]したがって、LLR文法のクラスは、各kに対するLL( k )の和集合よりも厳密に大きい。

正規分割が与えられた場合、与えられた文法が LL( ) であるかどうかは決定可能です。しかし、任意の文法Gが LLR であるかどうかは決定できません。これは、文法G が正規言語を生成するかどうかを決定すること(これはGの正規分割を見つけるために必要) が、ポスト対応問題に還元できるという事実によるものです。 ${\displaystyle \pi}$${\displaystyle \pi}$

すべてのLLR文法はLR正規文法（LRR、LR( k )文法の対応する^[明確化]同等物）であるが、LLRではないLR(1)文法が存在する。^[13]

歴史的に、LLR 文法は LRR 文法の発明に続いて生まれました。正規のパーティションが与えられれば、ムーア マシンを構築して構文解析を右から左に変換し、正規の生成のインスタンスを識別できます。これが完了すると、LL(1) パーサーは変換された入力を線形時間で処理するのに十分です。したがって、LLR パーサーは、LL( k ) パーサーよりも厳密に大きい文法のクラスを、同等の効率で処理できます。それにもかかわらず、LLR の理論には大きな用途がありません。考えられる非常にもっともらしい理由の 1 つは、LL( k ) および LR( k ) パーサーの生成アルゴリズムはあるものの、事前に正規のパーティションを構築しておかない限り、LLR/LRR パーサーを生成する問題は決定不可能であるということです。しかし、文法が与えられた場合に適切な正規のパーティションを構築する問題でさえ決定不可能です。

文脈自由文法は、単純決定論的文法^[14]または単に単純文法[ ^15]と呼ばれる。

• これはグライバッハ標準形（つまり各規則は の形を持つ）であり、${\displaystyle Z\rightarrow aY_{1}\ldots Y_{n},n\geq 0}$
• 同じ非終端記号の異なる右辺は常に異なる終端記号で始まります。${\displaystyle Z}$${\displaystyle a}$

文字列のセットは、単純な決定論的文法を持つ場合、単純な決定論的言語、または単に単純な言語と呼ばれます。

グライバッハ正規形でεフリーLL(1)文法を持つ言語のクラスは、単純決定論的言語のクラスに等しい。^[16] この言語クラスには、εを含まない正規集合が含まれる。^[15]同値性は決定可能であるが、包含は決定不可能である。^[14]

LL文法、特にLL(1)文法は、LLパーサーまたは再帰下降パーサーのいずれかによって解析が容易であるため、実用上非常に興味深いものであり、多くのコンピュータ言語^{[明確化]は、この理由からLL(1)になるように設計されています。高い値の}kを持つ文法に基づく言語は、伝統的に解析が難しいと考えられてきました^{[引用が必要]が、任意の}kに対してLL( k )文法をサポートするパーサージェネレーターが利用可能で広く使用されていることを考えると、これは現在ではそれほど当てはまりません^{[引用が必要]}。

• LL(k) および LL(*) パーサーのリストに対するパーサー ジェネレータの比較

• シッポ、セッポ。ソイサロン＝ソイネン、エルジャス（1990）。解析理論: LR(k) および LL(k) 解析。シュプリンガーのサイエンス＆ビジネスメディア。ISBN 978-3-540-51732-0。