編譯語法首先消除左遞歸

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

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

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

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

⑵ 編譯原理左遞歸消除

這些題很難啊！！！
都有間接左遞歸。要先變成直接左遞歸，然後消除掉。
--------------------
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：

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

⑶ 如何消除左遞歸

首先，什麼叫做左遞歸呢？ 一個左遞歸的語法通常有這樣的形式 : 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』 | ε
請注意，以上的解決方案是基於右遞歸的文法，並不是完全適用於所有的情況。我們得到的文法可能含有 ε表達式，並且可能會改變語法的結合律。解決方案就是保留左遞歸的語法，不用自頂向下的方式分析。

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

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

⑸ 編譯原理文法問題，急急急

第一題
S->AB

A->aA'b
A'->aA'b|ε
B->B'
B'->dB'|ε
----------------------
第二題
S->aS'b

S'->aS'b|D
D->dD|ε
----------------------
第三題
最左推導的話，我認為要先消除左遞歸才行（把左遞歸轉成右遞歸），消除之後:
N->DN'
N'->DN'|ε
D->0|1|2|...|9
最左推導為 N->DN'->2N'->2DN'->25N'->25DN'->258N'->258
規范推導(最右推導)為N->ND->N8->ND8->N58->D58->258
----------------------
第四題
構造一下語法樹就知道了。直接短語是深度為2的節點（根節點是深度0）。短語是深度為2的節點代入深度為1的產生式中。句柄是所有直接短語中最左的那個。
1.baaa
>>>
_________S
_______/___\
______A_____B
_____/__\____|
____A___a___a
___/__\
__b___B
_______|
______a
直接短語為 Aa、a
短語為 Aaa
句柄為 Aa
2.bBaa
>>>
_________S
_______/___\
______A_____B
_____/__\____|
____A___a___a
___/__\
__b___B
直接短語為 Aa、a
短語為 Aaa
句柄為 Aa

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

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

⑺ 【編譯原理】第四章：語法分析

從分析樹的根節點到葉節點方向構造分析樹。
即從開始符號S推導出詞串w的過程。

例：

總是選擇每個句型的 最左非終結符 進行替換。

總是選擇每個句型的 最右非終結符 進行替換。

在自底向上的分析中，總是採用 最左規約 的方式，因此把 最左規約 稱為 規范規約 ，對應的 最右推導 稱為 規范推導 。

最左推導、最右推導具有唯一性。

自頂向下的語法分析採用最左推導方試，總是選擇每個句型的 最左非終結符 進行替換。

由一組 過程 組成，每一個過程對應一個 非終結符 。
從文法開始符號S開始，遞歸調用文法中的其他非終結符，最終掃描整個輸入串，完成分析。

如果其間有不唯一的產生式，就可能需要退回上一步重新嘗試的情況，稱為 回溯 。

預測分析 是 遞歸下降分析 技術的一個特例，通過輸入中向前看固定個數的符號選擇正確的產生式。
如果一個文法可以構造出向前看k個符號的預測分析器，稱為LL(k)文法 。

預測分析不需要回溯，具有確定性。

含有 形式產生式的文法稱為是 直接左遞歸 的。
如果一個文法中有一個非終結符A使得對某個串存在推導 ，那麼這個文法是 左遞歸 的。其中，經過兩步或以上推導產生的左遞歸，稱為 間接左遞歸 的。
左遞歸會使遞歸下降分析器陷入無限循環。

文法
即
該文法是直接左遞歸的，會陷入無限循環。

將以上文法轉換為：


即可消除左遞歸。事實上，這個過程把左遞歸轉換成了右遞歸。

消除直接左遞歸的一般形式

使用代入法。

對於一個文法，通過改寫產生式來 推遲決定 ，等獲得足夠多的輸入信息再做正確的決定。

例：文法：

可以改寫為：

從文法的開始符號S開始，每一步推導根據當前句型的最左非終結符A和當前輸入符號α，選擇正確的A-產生式。為保證分析的確定性，選出的候選式必須是唯一的。

S_文法（簡單的確定型文法）

可能在某個舉行中緊跟在A後面的終結符a的集合，記為 FOLLOW(A) 。
如果A是某個句型的最右符號，則將結束符「 $ 」添加到FOLLOW(A)中。

例：文法：






中，FOLLOW(B) = {a, c}

產生式 的可選集是指可以選用該產生式進行推導時對應的輸入符號的集合，記為 SELECT(A->β) 。
例如
SELECT(A -> aβ)={a}
SELECT(A -> aβ | bγ)={a, b}
SELECT(A -> ε)=FOLLOW(A)

q_文法

文法符號串α串首終結符的集合，記作 FIRST(A) 。

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

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

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

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