編譯原理左遞歸方法

❶ 編譯原理左遞歸消除

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

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

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

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

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

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

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

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

❹ 遞歸下降和遞歸向上以及左遞歸

遞歸下降、遞歸向上以及左遞歸是編譯原理與語法解析中關鍵概念。遞歸下降是一種自頂向下的語法解析方法，每個非終結符對應解析函數，通過遞歸調用處理特定文法規則。此方法直觀易懂，適用於上下文無關文法，但可能受到左遞歸影響，需進行特殊處理避免無限遞歸。

遞歸向上則為自底向上的語法解析方法，從最低級終結符開始解析，逐步構建語法樹，直至最高級非終結符。遞歸向上常用於LR分析器，如LR(1)與LALR(1)，這類分析器通過自底向上推導樹解析輸入文本，相比遞歸下降，通常能處理更復雜語法，解析效率更高。

左遞歸指的是非終結符規則中以自身開頭的特性，如A->Aα。此結構可能使遞歸下降解析器陷入無限遞歸，導致解析失敗。處理左遞歸是編寫遞歸下降解析器時的重要步驟，常見解決方式為消除左遞歸，將左遞歸規則轉換為非左遞歸規則。例如，對於左遞歸規則A->Aα|β，可通過引入新非終結符A'進行轉換，如A->βA'，A'->αA'|ε。

遞歸下降與遞歸向上是不同語法解析方法，適用於不同文法類型。處理左遞歸在編寫遞歸下降解析器時至關重要。根據語言特性與需求，選擇合適的解析方法極為重要。

❺ 編譯原理文法定型規則

編譯原理中的文法定型規則是指將任意上下文無關文法（Context-Free Grammar, CFG）轉化為某個特定形式的上下文無關文法的規則。這個特定形式的上下文無關文法通常是Chomsky範式或Greibach範式。
以下是文法定型規則的具體步驟：
1. 消除文法中的ε產生式（epsilon-proction），即產生空串的產生式。
2. 消除文法中的單一產生式（unit-proction），即右側只有一個非終結符的產生式。
3. 消除文法中的左遞歸產生式（left-recursive proction）。
4. 將文法轉化為無二義性的文法。
上述步驟的具體實現方法如下：
1. 消除文法中的ε產生式：
1. 對於所有含有ε產生式的非終結符，將其ε產生式刪除。
2. 對於所有產生式右側含有已刪除非終結符的產生式，將其右側的已刪除非終結符替換為ε。
3. 重復執行上述步驟，直到所有含有ε的產生式都被消除為止。
2. 消除文法中的單一產生式：
1. 對於所有單一產生式A → B，將其刪除。
2. 對於所有產生式右側含有被刪除產生式的非終結符的產生式，將其替換為被刪除產生式的右側符號B。
3. 重復執行上述步驟，直到所有單一產生式都被消除為止。
3. 消除文法中的左遞歸產生式：
1. 對於每個非終結符A，將所有形如A → Aα的產生式改為A → β1A'、A' → β2A' | ε的形式。
2. 其中，β1是所有右側不含有A的A產生式的右側符號串，β2是所有右側含有A的A產生式的右側符號串，α是所有產生式右側不含有A的符號串。
3. 重復執行上述步驟，直到所有左遞歸產生式都被消除為止。
4. 將文法轉化為無二義性的文法：
1. 消除文法中的二義性產生式，即產生式右側存在兩個或以上的不同符號串。
2. 引入新的非終結符，將二義性產生式拆分為多個不同的產生式。
3. 對於所有產生式右側含有多個符號的產生式，使用括弧或其他符號進行明確區分。
4. 重復執行上述步驟，直到文法不存在二義性為止。
以上是文法定型規則的具體步驟和實現方法。通過執行這些步驟，可以將任意上下文無關文法轉化為某個特定形式的上下文無關文法，從而方便進行語法分析和編譯。

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

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