編譯原理左遞歸

1. 編譯原理中 左遞歸具體解釋是什麼

定義：
"一個文法是左遞歸的，若我們可以找出其中存在某非終端符號A，最終會推導出來的句型(sentential form)裡麵包含以自己為最左符號(left-symbol)的句型"
即
A -> Aa 或
A -> Ba
B -> A
兩種形式的文法.

2. 編譯原理左遞歸消除

這些題很難啊！！！
都有間接左遞歸。要先變成直接左遞歸，然後消除掉。
--------------------
G3.1
S->SA|Ab|b|c
A->Bc|a
B->Sb|b
--------------------
間接左遞歸轉直接左遞歸
B代入A：A ->(Sb|b)c|a -> Sbc|bc|a
A代入S：S -> S(Sbc|bc|a)|(Sbc|bc|a)b|b|c -> SSbc|Sbc|Sa|Sbcb|bcb|ab|b|c
消除直接左遞歸
S->bcbS'|abS'|bS'|cS'
S'->SbcS'|bcS'|aS'|bcbS'|ε
S'還是有直接左遞歸，繼續消除
S'->bcS'T|aS'T|bcbS'T
T->bcS'T|ε
最後，這題答案就是S,S',T的產生式

--------------------
下面兩題更難了，上一題反復代入還能把其他非終結符消掉，下面兩個文法都是最後代入還剩下兩個非終結符反復迭代，佛了！
G3.2
E->ET+|T

T->TF*|F

F->E|i
--------------------
F代入T: T->T(E|i)*|(E|i)->TE*|Ti*|E|i
T代入E：

--------------------
G3.3
S->V_1

V_1->V_2|V_1 2 V_2

V_2->V_3|V_2 + V_3
V_3->V_1 * |(
這些字母我都不認識了，換一下
S->A|SiA
A->B|A+B
B->S*|(
--------------------
B代入A：A->(S*|()|A+(S*|()->S*|(|A+S*|A+(
A代入S：

--------------------

3. 【編譯原理】自頂向下LL（1）分析中，消除左遞歸和提取左因子的目的是什麼

提取左因子---避免程序回溯；
消除左遞歸---消除死循環。

4. 編譯原理的消除左遞歸是怎麼回事啊

如果一個CFG像這樣
A -> Ab
A -> e

就是有左遞歸，語法分析里的遞歸下降法和LL（1）就不能處理啦，因為程序會陷入遞歸而無法前進。
而CFG
A -> bA'
A' -> bA'|e
和前面一個表達的語言是一樣的，但所有語法的第一項都是終結符，就消除了左遞歸。

有消除左遞歸的演算法，一般編譯原理書上會有介紹，不是很復雜。

5. 如何消除左遞歸

首先，什麼叫做左遞歸呢？ 一個左遞歸的語法通常有這樣的形式 : A-> Aa .而自頂向下的語法分析是無法處理左遞歸語法的。為什麼呢？無論是遞歸分析還是預測分析或者是LL文法分析，在碰到左遞歸這種語法時都會陷入死循環當中。如果我們用遞歸分析，那麼在分析A這個非終結符號的時候就會調用functionA，functionA將A分解成A，a，然後在我們再次碰到A的時候又會調用functionA，這樣便形成了無限遞歸。如果我們用非遞歸的LL文法分析，那麼在我們將把A->Aa無限次地壓入到棧中，即每次彈出A都會壓入Aa。所以我們必須採取手段消除左遞歸，下面給出標准方法。
其中β1…βn 不是從A開始
其實原理在於通過轉換將A的語法不從非終結符號（A本身）開始，而是從終結符號β1…βn 開始。雖然A的原語法是從A本身開始的，但是第一個符號一定是β1…βn中的一個，而不可能是任何一個α。所以我們通過一個中間變數A』來表示剩下的α，然而不要忘記由於A』 ->αA』 這條規則，A』 -> ε 必須也存在於語法規則中，否則末尾將無法匹配完成。
但是，上述方法只適用於立即左遞歸，還有一種更隱蔽的非立即左遞歸，如 S -> Aa | b , A -> Sc | d ,我們如果用自頂向下的分析方法會陷入 S -> Aa -> Sca 這樣的死循環中。當然，也有相應的解決辦法。
將所有非終端符號以某個固定的順序A_1, \ldots A_n排列
從 i = 1 到 n {
從 j = 1 到 i – 1 {
設A_j的生成規則為
A_j \rightarrow \delta_1 | \ldots | \delta_k
將所有規則 A_i \rightarrow A_j \gamma換成
A_i \rightarrow \delta_1\gamma | \ldots | \delta_k\gamma
移除A_i規則中的直接左遞歸
}
}
也許看上面的規則過於抽象，我們用S -> Aa | b , A -> Sc | d 來實踐一下上述的方法。我們以S，A的順序排列。則只需執行一次主程序體，且Ai 為A，Aj為S。則：
A -> Aac | bc | d, 然後再運用前面的規則消除直接左遞歸可得：A -> bcA』 | dA』 , A』 -> acA』 | ε
請注意，以上的解決方案是基於右遞歸的文法，並不是完全適用於所有的情況。我們得到的文法可能含有 ε表達式，並且可能會改變語法的結合律。解決方案就是保留左遞歸的語法，不用自頂向下的方式分析。

6. 編譯原理中的左遞歸

1.A->Aa
2.A->Ba
B->Ab
(A和B屬於非終結符，a和b屬於終結符)
通俗點講：左遞歸就是情況1所說的「->」兩邊都含有同一個非終結符；
情況2所說的A->Ba中「->」後面的B
與
B->Ab中「->」前面的B是相同的非終結符
這兩種情況就叫作左遞歸。

7. 編譯原理，如何消除文法的左遞歸

T::=ST'

T'::=,ST'|ε

8. 編譯原理：消除文法中的左遞歸

總得有個規則吧。如果不能提供，可以自己看看bison源代碼分析--gcc源代碼分析語法分析部分。

9. 編譯原理 清除左遞歸

先提公因子

10. 編譯原理語法分析中消除左遞歸的問題。比如A→Ab|c中為什麼說它是左遞歸呢，明明是A定義為Ab或者

A->Ab|c為什麼是左遞歸，和為什麼要消除左遞歸：

定義，就無需爭辯了。至於為什麼自頂向下文法不能處理左遞歸,解釋如下：

c∈FIRST(A)，所以當預測分析的棧頂出現非終結符A，而輸入字元串最左邊為c時，就不知道用產生式A->Ab還是A->c了。無法構造預測分析表。比如輸入字元串為cbb，我們人當然容易知道是A->Ab->Abb->cbb了，但是電腦沒那麼聰明，如果不消除左遞歸，只有回溯了。