なぜLL文法を左回帰的に使うことができないのですか？次のように<em><a href="http://en.wikipedia.org/wiki/Compilers%3a_Principles,_Techniques,_and_Tools">dragon book</a></em>で

Question

は、LL文法が定義され：任意の生産A -> a|bために、以下の2つの条件が当てはまる場合だけ

文法はLLです。

1. FIRST(a)とFIRST(b)は互いに素です。これはbは、その後aがFIRST(a)とFOLLOW(A)は互いに素でなければならないですFOLLOW(A)で始まる任意の文字列を導き出すことができない、EMPTYを引き出すことができれば、彼らは両方のEMPTY

2. を導き出すことができないことを意味します。

LL文法は再帰的に残ることはできませんが、正式な理由は何ですか？左回帰文法はルール2に反するだろうと思いますよね？ FIRST(SA) = {a, empty}とFOLLOW(S) ={$, a}、その後、FIRST(SA)とFOLLOW(S)は互いに素ではないので、この文法はLLではありませんので

S->SA|empty 
A->a 

：例えば、私は、次の文法を書きました。しかし、私はそれが左回帰であるかどうか分かりませんFIRST(SA)とFOLLOW(S)は別の理由がありますか？別の言い方をすれば、すべての左回帰文法がLL文法の条件2に違反する生産をすることは事実ですか？

S -> SA 
S -> empty 
A -> a 

今すぐ文字列aaaを考慮してください。

S->SA|empty 
A->a 

これは、3つの規則の省略形です：

Answer 1

OK、私は、それを把握

S->B 

FIRST（B）はFIRST（SA）のサブセットであるため、これらは結合されているため、条件1に違反します。FIRST（B）とFIRST（SA）の両方の端末に対応する解析テーブルエントリを、 。要約すると、左回帰文法は、2つ以上のプロダクションのFIRSTセットに共通の端末を持ち、条件1に違反する可能性があります。

Answer 2

はあなたの文法を考えてみましょう。それはどのように作られたのですか？あなたは何の先読みを持っていない場合は、次のように始めるので、あなただけの（あなたが開始記号としてSを持っている）、一度に1つの文字を読むことができます：

S -> SA 
S -> empty 
A -> a 

ファインは、あなたが最初にaを生産しています。しかし、今では、非端末がなくなるため、これ以上ルールを適用することはできません。あなたは立ち往生している！あなたがやるべき何

は、このでした：

S -> SA 
S -> SA 
S -> SA 
S -> empty 
A -> a 
A -> a 
A -> a 

しかし、あなたは文字列全体を読まずにこれを知りません。先読みは無限に必要です。

一般的には、はいのように、すべての左回帰文法は無限の先読みを持たない曖昧な文字列を持つことがあります。例をもう一度見てください。Sには2つの異なる規則があります。どちらを使うべきですか？その後

S->SA 

言って、何とかそれは再帰を「仕上げる」ために別の生産が含まれている必要があります：文法は以下のように、左再帰的な生産が含まれている場合

Answer 3

LL(k)文法は、kシンボルだけの確定的な降下パーサーの構築を可能にするものです先のことを考える。左回帰の問題は、完全な入力文字列が調べられるまでどのルールを適用するかを決定することが不可能になり、必要とされるkが潜在的に無限になることです。あなたの例を使用して

、kを選択し、パーサに長さn >= kの入力シーケンスを与える：それは先に理由kシンボルを見て、S->SAまたはS->emptyを適用する必要がある場合

aaaaaaa... 

パーサは決めることができません決定はこれまでに何度も選択されたことに依存し、それはパーサーにはない情報です。

パーサが一度S->SA正確n回とS->emptyを選択しなければならない、それが右の入力ストリームの最初のkシンボルを見ることであるかを決定することは不可能です。

パーザは完全な入力シーケンスを調べて、何度も何度も選択されているが、そのようなパーサーはLL(k)の定義外になることを知る必要があります。

パーサは限られたリソースで動作するため、無限の先読みは解決策ではないため、出力を生成する前にパーサーをクラッシュさせるほどの長さの有限入力シーケンスが常に存在することに注意してください。