LL文法

文脈自由文法の種類

C文法^[1]はLL(1)ではありません。下の部分は、トークン「 」を消化しint v;main(){、非終端記号「 」を導出するための規則を選択しようとしているパーサを示していますStmt。最初の先読みトークン「v」だけを見ても、「 」の2つの選択肢のどちらを選択すべきか判断できませんStmt。なぜなら、2つの入力継続が考えられるからです。2番目の先読みトークン（黄色の背景）を見ることで、それらを区別することができます

形式言語理論において、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,\Sigma ,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,\Sigma ,R,S)}$

${\displaystyle {\begin{array}{ccccccc}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{array}}}$

の最初の記号が の最初の記号と一致するとき、 となる。^{[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 )文法の正式な定義では、 の普遍量化子は省略され、の「何らかの」量化子に追加されます。すべての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 )文法でもある。ε - free 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,\Sigma ,R,S)}$ ${\displaystyle \pi =\{R_{1},\dotso ,R_{n}\}}$ ${\displaystyle \Sigma ^{*}}$ ${\displaystyle G}$ ${\displaystyle \pi }$

${\displaystyle {\begin{array}{ccccccc}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{array}}}$

となる。^[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(*)パーサーのリストについては、パーサージェネレータの比較を参照してください

注釈

1. EBNFのような表記法で簡略化された抜粋を示しています
2. k =0の場合を考慮していない。
3. ここで「」は最左導出による導出可能性を示し、、、および ${\displaystyle \Rightarrow ^{L}}$ ${\displaystyle w_{1},w_{2},w_{3},w'_{2},w'_{3}\in \Sigma ^{*}}$ ${\displaystyle A\in V}$ ${\displaystyle \chi ,\nu ,\omega \in (\Sigma \cup V)^{*}}$
4. ウェイト＆グース (1984, p. 123) Def. 5.22
5. ローゼンクランツ＆スターンズ（1970年、235ページ）定義2
6. Rosenkrantz & Stearns (1970, p. 235) 定理2
7. Rosenkrantz & Stearns (1970, p. 246–247): " " を使用して「または」を表すと、文字列セットには がありますが、各 に対してε フリー文法はありません。 ${\displaystyle +}$ ${\displaystyle \{a^{n}(b^{k}d+b+cc)^{n}:n\geq 1\}}$ ${\displaystyle LL(k+1)}$ ${\displaystyle LL(k)}$ ${\displaystyle k\geq 1}$
8. ローゼンクランツ＆スターンズ（1970年、254～255ページ）
9. ビーティ（1982）
10. Rosenkrantz & Stearns (1970, pp. 241) 補題5
11. Rosenkrantz & Stearns (1970, p. 242) 定理4
12. Poplawski, David (1977). 「LL正規言語の特性」. パデュー大学. {{cite journal}}:ジャーナルを引用するには|journal=（ヘルプ）が必要です
13. David A. Poplawski (1977年8月). LL正規言語の特性（技術レポート）.パデュー大学、コンピュータサイエンス学部.
14. コレンジャクとホップロフト (1966)
15. ホップクロフト＆ウルマン (1979, p. 229) 演習9.3
16. ローゼンクランツ＆スターンズ（1970年、243ページ）

出典

• Beatty, JC (1982). 「LL(1)文法とLR(1)文法の関係について」(PDF) . Journal of the ACM . 29 (4 (10月)): 1007–1022 . doi :10.1145/322344.322350. S2CID  14700480
• ホップクロフト, ジョン・E.; ウルマン, ジェフリー・D. (1979). 『オートマトン理論、言語、計算入門』 . アディソン・ウェスレー. ISBN 978-0-201-02988-8。
• ブライアン・W. カーニハン、デニス・M. リッチー（1988年4月）。『プログラミング言語C』。プレンティス・ホール・ソフトウェア・シリーズ（第2版）。ニュージャージー州エングルウッド・クリフス：プレンティス・ホール。ISBN 978-013110362-7。
• Korenjak, AJ; Hopcroft, JE (1966). 「単純決定性言語」. IEEE Con​​f. Rec. 第7回スイッチングおよびオートマトン理論シンポジウム (SWAT) . IEEE Pub. No. Vol. 16-C-40. pp.  36– 46. doi :10.1109/SWAT.1966.22
• Parr, T.; Fisher, K. (2011). 「LL(*): ANTLRパーサージェネレータの基礎」(PDF) . ACM SIGPLAN Notices . 46 (6): 425– 436. doi :10.1145/1993316.1993548.
• Rosenkrantz, DJ; Stearns, RE (1970). 「決定論的トップダウン文法の特性」.情報制御. 17 (3): 226– 256. doi : 10.1016/s0019-9958(70)90446-8 .
• ウェイト、ウィリアム・M; グース、ゲルハルト (1984).コンパイラ構築. コンピュータサイエンスのテキストとモノグラフ. ハイデルベルク: シュプリンガー. ISBN 978-3-540-90821-0。

さらに詳しい情報

• Sippu, Seppo; Soisalon-Soininen, Eljas (1990). Parsing Theory: LR(k) and LL(k) Parsing . Springer Science & Business Media. ISBN 978-3-540-51732-0。

「https://en.wikipedia.org/w/index.php?title=LL_grammar&oldid=1188738022」より取得