編譯中左遞歸的原理

㈠ 編譯原理——LR分析表

自底向上的語法分析

LR分析表的結構如上，其分為兩個部分 Action Goto

兩個參數狀態i，終結符號a（s(i)代表第i個狀態，r(i)代表第i條表達式）

Goto[i,A]=j

文法

容易得知這個文法可以推出 0 1 00 01 等的字元串。因為它是 左遞歸 。不適用於 LL 文法分析，只能使用 LR 分析。

因為本題入口有兩個—— S → L·L S → L ，所以需要構造額外的產生式 S'->S

2.1 第一次遍歷

我們從 [S -> . L·L] 開始，構造這個狀態的閉包，也就是加上所有能從這個產生式推出的表項。

首先，判斷 . 後面是否為 非終結符號A 。如果是，那我們就得找所有由 A-> 推出的產生式，並將它們添加進入 閉包 里(也就是State包里)。循環做即可。

因此我們可以得到 State 0 有

下一步，就是我的 . 往下一位移動。對每個符號X後有個 . 的項，都可以從 State 0 過渡到其他狀態。

由以上6條式子可以得知下一位符號可以是 S L B 0 1 。所以自然可以得到5個狀態。

State 1 是由 State 0 通過 S 轉移到這里的，所以我們找出所有 State 0 中在 S 前有 . 的項。

此狀態作為結束狀態 Accept ，不需要繼續狀態轉移了。

State 2 是由 State 0 通過 L 轉移到這里的，所以我們找出所有 State 0 中在 L 前有 . 的項。

S -> . L·L S -> . L L -> . LB

有3條式子，現在我們將 . 向後推一格，就得到 State 1 的項了。

但是 . 之後的符號分別是 · $ B ， B 為非終結符號，我們得包含 B -> 的項

State 3 是由 State 0 通過 B 轉移到這里的，所以我們找出所有 State 0 中在 B 前有 . 的項。

因為 . 後沒有其他符號了，因此這個狀態不需要繼續轉移了。

State 4 是由 State 0 通過 0 轉移到這里的，所以我們找出所有 State 0 中在 0 前有 . 的項。

因為 . 後沒有其他符號了，因此這個狀態不需要繼續轉移了。

很簡單，同樣的道理找 State 5

State 5 是由 State 0 通過 1 轉移到這里的，所以我們找出所有 State 0 中在 1 前有 . 的項。

因為 . 後沒有其他符號了，因此這個狀態不需要繼續轉移了。

好的，現在我們第一次遍歷完成。

2.2 第二次遍歷

第二次遍歷自然從 State 2 開始。

我們回到 State2 ，可以看出 . 之後的符號有 · B 0 1 。

State 6 是由 State 2 通過 · 轉移到這里的，所以我們找出所有 State 2 中在 · 前有 . 的項。

S -> L. ·L 只有1條，我們往後移發現 L 又為非終結符號，參考 State 0 做的操作，我們得找出所有的式子。

共有5條式子，共同組成 State 6 ，由上面的式子可以看出我們還得繼續下一次遍歷。先不管著，我們進行下一次狀態查找。

State 7 是由 State 2 通過 B 轉移到這里的，所以我們找出所有 State 2 中在 B 前有 . 的項。

L -> L. B 也是只有1條，我們往後移發現沒有非終結符號了，那就不需要再繼續添加其他式子了。

這個狀態也不需要繼續進行轉移了。

接下來很關鍵，因為我們通過 State2 的 . 後的符號找出了 State 6 State 7 ，接下來還差符號 0 1 ，那麼是否像之前一樣按例添加狀態呢， 答案是不是的 ，因為我們發現通過 0 1 找到的閉包集分別是 B -> 0 B -> 1 ，這與我們的之前的 State 4 State 5 相同。所以我們得將其整合起來，相當於 State 2 通過 0 1 符號找到了 State 4 State 5 狀態。

2.3 第三次遍歷

回頭看第二次遍歷，可以看出只有 State 6 可以進行狀態轉移了。

那麼就將 State 6 作為第三次遍歷的源頭，可以看出 . 之後的符號有 L B 0 1 。

State 8 是由 State 6 通過 L 轉移到這里的，所以我們找出所有 State 6 在 L 前有 . 的項。

S -> L· .L L -> . LB 有兩條式子，往後移發現有非終結符號 B ，所以經過整合可以得到

可以看出 . 的後面還有一個符號，所以這里我們還得再進行一次遍歷。

接下來，又是遇到重復的包的情況，可以看出我們由 State 6 通過 B 0 1 得到的閉包分別是 L->B B->0 B->1 ，很明顯，這分別對應於 State 3 State 4 State 5 。

第三次遍歷也就結束了。

2.4 第四次遍歷

回看第三次遍歷，可以看出只有 State 8 可以進行狀態轉移，其 . 之後的符號分別是 B 0 1 。

誒，感覺很熟悉，就是上面幾行剛說的情況，也就是說通過這三個符號找到的閉包是我們之前遇到的狀態，分別是 State 3 State 4 State 5 。

做到這里，我們發現我們已經全部遍歷完畢！

總共有8個狀態，通過以上流程做成個圖是什麼樣子的？來看看！

這么一看就很清晰明了了，我們就可以通過這個圖做出我們的 LR分析表

其實就是我們之前呈現的表

在狀態 I2 和 I8 中，既有 移入 項目，也有 規約 項目，存在 移入 - 規約的沖突 ，所以不是 LR(0) 文法，但是因為 FOLLOW(S) ∩ {0, 1} = ∅，所以可以用 FOLLOW 集解決沖突，所以該文法是 SLR(1) 文法。

上表我們發現還有 r1，r2，r3 等。這個其實就是代表狀態停止轉移時為 第幾條表達式 ，r3代表第三條表達式 L -> LB 。

當我們構建了表之後，我們如何運用起來呢？

下面我們通過一個例子來說明

以上字元串是如何被SLR分析器識別的呢？

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

從分析樹的根節點到葉節點方向構造分析樹。
即從開始符號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) 。

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

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

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

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

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

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

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

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

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

通常LL(1) 是以函數遞歸調用來實現的
如文法: A -> A + a | a
代碼實現則為:
function A()
{
A();
match('+');
Term(a);
}
這樣你可以看得出死循環了吧...?
將文法消除左遞歸後
A -> aA'
A' -> +aA'
則可以避免這一問題
提出公因式 就像樓上說的一樣,避免程序回溯,消除二義性.
樓上高手啊,求搞基.

㈥ 關於LL(1)文法的編譯原理題目

判斷是不是LL(1)，首先看候選式的首字元有沒有相同的，第二判斷首字元迭代進去是否會構成左遞歸。
如果首字元不相同，也沒用左遞歸就說明此文法是LL(1)
M→MaH｜H
H→(M)｜b(M)｜b
第一個產生式中存在左遞歸:M->MaH
第二個產生式中存在首字元相同:H->b(M) ,
H->b
怎麼改呢？
對第一個產生式，消除左遞歸就是要變成右遞歸，把右邊剩下的符號提到前面:
M->aHM'

M'->aHM'
對第二個產生式，提出公共因子
H->b( (M)|ε)
=>
H->bH'

H'->(M)|ε

㈦ 編譯原理A->A,(A)|a消除左遞歸

A::=aA'
A'::=,(A)A'|ε

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

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

㈨ 編譯原理左遞歸消除

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

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

㈩ 編譯原理-LL1文法詳細講解

我們知道2型文法( CFG )，它的每個產生式類型都是 α→β ,其中 α ∈ VN , β ∈ (VN∪VT)*。

例如, 一個表達式的文法:

最終推導出 id + (id + id) 的句子，那麼它的推導過程就會構成一顆樹，即 CFG 分析樹：

從分析樹可以看出，我們從文法開始符號起，不斷地利用產生式的右部替換產生式左部的非終結符，最終推導出我們想要的句子。這種方式我們稱為自頂向下分析法。

從文法開始符號起，不斷用非終結符的候選式(即產生式)替換當前句型中的非終結符，最終得到相應的句子。
在每一步推導過程中，我們需要做兩個選擇:

因為一個句型中，可能存在多個非終結符，我們就不確定選擇那一個非終結符進行替換。
對於這種情況，我們就需要做強制規定，每次都選擇句型中第一個非終結符進行替換(或者每次都選擇句型中最後一個非終結符進行替換)。

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

最終的結果是要推導出一個特定句子(例如 id + (id + id) )。
我們將特定句子看成一個輸入字元串，而每一個非終結符對應一個處理方法，這個處理方法用來匹配輸入字元串的部分，演算法如下:

方法解析:

這種方式稱為遞歸下降分析( Recursive-Descent Parsing )：

當選擇的候選式不正確，就需要回溯( backtracking )，重新選擇候選式，進行下一次嘗試匹配。因為要不斷的回溯，導致分析效率比較低。

這種方式叫做預測分析( Predictive Parsing )：

要實現預測分析，我們必須保證從文法開始符號起，每一個推導過程中，當前句型最左非終結符 A 對於當前輸入字元 a ,只能得到唯一的 A 候選式。

根據上面的解決方法，我們首先想到，如果非終結符 A 的候選式只有一個以終結符 a 開頭候選式不就行了么。
進而我們可以得出，如果一個非終結符 A ，它的候選式都是以終結符開頭，並且這些終結符都各不相同，那麼本身就符合預測分析了。

這就是S_文法，滿足下面兩個條件:

例子:

這就是一個典型的S_文法，它的每一個非終結符遇到任一終結符得到候選式是確定的。如 S -> aA | bAB , 只有遇到終結符 a 和 b 的時候，才能返回 S 的候選式，遇到其他終結符時，直接報錯，匹配不成功。

雖然S_文法可以實現預測分析，但是從它的定義上看，S_文法不支持空產生式(ε產生式)，極大地限制了它的應用。

什麼是空產生式(ε產生式)？

例子

這里 A 有了空產生式，那麼 S 的產生式組 S -> aA | bAB ，就可以是 a | bB ,這樣 a , bb , bc 就變成這個文法 G 的新句子了。

根據預測分析的定義，非終結符對於任一終結符得到的產生式是確定的，要麼能獲取唯一的產生式，要麼不匹配直接報錯。

那麼空產生式何時被選擇呢？

由此可以引入非終結符 A 的後繼符號集的概念:
定義: 由文法 G 推導出來的所有句型，可以出現在非終結符 A 後邊的終結符 a 的集合，就是這個非終結符 A 的後繼符號集，記為 FOLLOW(A) 。

因此對於 A -> ε 空產生式，只要遇到非終結符 A 的後繼符號集中的字元，可以選擇這個空產生式。
那麼對於 A -> a 這樣的產生式，只要遇到終結符 a 就可以選擇了。

由此我們引入的產生式可選集概念:
定義: 在進行推導時，選用非終結符 A 一個產生式 A→β 對應的輸入符號的集合，記為 SELECT(A→β)

因為預測分析要求非終結符 A 對於輸入字元 a ,只能得到唯一的 A 候選式。
那麼對於一個文法 G 的所有產生式組，要求有相同左部的產生式，它們的可選集不相交。

在 S_文法基礎上，我們允許有空產生式，但是要做限制:

將上面例子中的文法改造:

但是q_文法的產生式不能是非終結符打頭，這就限制了其應用，因此引入LL(1)文法。

LL(1)文法允許產生式的右部首字元是非終結符，那麼怎麼得到這個產生式可選集。
我們知道對於產生式:

定義: 給定一個文法符號串 α ， α 的 串首終結符集 FIRST(α) 被定義為可以從 α 推導出的所有串首終結符構成的集合。

定義已經了解清楚了，那麼該如何求呢？
例如一個文法符號串 BCDe , 其中 B C D 都是非終結符， e 是終結符。

因此對於一個文法符號串 X1X2 … Xn ，求解 串首終結符集 FIRST(X1X2 … Xn) 演算法:

但是這里有一個關鍵點，如何求非終結符的串首終結符集？

因此對於一個非終結符 A , 求解 串首終結符集 FIRST(A) 演算法:

這里大家可能有個疑惑，怎麼能將 FIRST(Bβ) 添加到 FIRST(A) 中，如果問文法符號串 Bβ 中包含非終結符 A ，就產生了循環調用的情況，該怎麼辦?

對於 串首終結符集 ，我想大家疑惑的點就是，串首終結符集到底是針對 文法符號串 的，還是針對 非終結符 的，這個容易弄混。
其實我們應該知道， 非終結符 本身就屬於一個特殊的 文法符號串 。
而求解 文法符號串 的串首終結符集，其實就是要知道文法符號串中每個字元的串首終結符集:

上面章節我們知道了，對於非終結符 A 的 後繼符號集 :
就是由文法 G 推導出來的所有句型，可以出現在非終結符 A 後邊的終結符的集合，記為 FOLLOW(A) 。

仔細想一下，什麼樣的終結符可以出現在非終結符 A 後面，應該是在產生式中就位於 A 後面的終結符。例如 S -> Aa ，那麼終結符 a 肯定屬於 FOLLOW(A) 。

因此求非終結符 A 的 後繼符號集 演算法：

如果非終結符 A 是產生式結尾，那麼說明這個產生式左部非終結符後面能出現的終結符，也都可以出現在非終結符 A 後面。

我們可以求出 LL(1) 文法中每個產生式可選集:

根據產生式可選集，我們可以構建一個預測分析表，表中的每一行都是一個非終結符，表中的每一列都是一個終結符，包括結束符號 $ ，而表中的值就是產生式。
這樣進行語法推導的時候，非終結符遇到當前輸入字元，就可以從預測分析表中獲取對應的產生式了。

有了預測分析表，我們就可以進行預測分析了，具體流程:

可以這么理解：

我們知道要實現預測分析，要求相同左部的產生式，它們的可選集是不相交。
但是有的文法結構不符合這個要求，要進行改造。

如果相同左部的多個產生式有共同前綴，那麼它們的可選集必然相交。
例如:

那麼如何進行改造呢？
其實很簡單，進行如下轉換:

如此文法的相同左部的產生式，它們的可選集是不相交，符合現預測分析。

這種改造方法稱為 提取公因子演算法 。

當我們自頂向下的語法分析時，就需要採用最左推導方式。
而這個時候，如果產生式左部和產生式右部首字元一樣(即A→Aα)，那麼推導就可能陷入無限循環。
例如:

因此對於:

文法中不能包含這兩種形式，不然最左推導就沒辦法進行。

例如:

它能夠推導出如下:

你會驚奇的發現，它能推導出 b 和 (a)* (即由 0 個 a 或者無數個 a 生成的文法符號串)。其實就可以改造成:

因此消除 直接左遞歸 演算法的一般形式：

例如:

消除間接左遞歸的方法就是直接帶入消除，即

消除間接左遞歸演算法：

這個演算法看起來描述很多，其實理解起來很簡單：

思考 : 我們通過 Ai -> Ajβ 來判斷是不是間接左遞歸，那如果有產生式 Ai -> BAjβ 且 B -> ε ,那麼它是不是間接左遞歸呢？
間接地我們可以推出如果一個產生式 Ai -> αAjβ 且 FIRST(α) 包括空串ε，那麼這個產生式是不是間接左遞歸。