遞歸如何實現編譯原理

A. 編譯原理-句型、句子、短語、直接短語、句柄、素短語、最左素短語

在進行語法分析的時候，有時候會對這些詞語的概念不清晰，這里我們就詳細歸納總結一下。

可以看出這個裡面，最需要理解的概念就是短語，其他大部分概念都是在短語基礎上延伸的，從概念上可以看出：

假設有一個文法

針對文法的一個特定句型 (Sd(T)db) , 其推導過程如下:

這個句型 (Sd(T)db) 對應的 CFG 分析樹如下：

那個這個句型 (Sd(T)db) 有多少個短語呢？

還記得短語的定義么， S ⇒* αβδ ， αβδ 代表句型就是這里的 (Sd(T)db) 。

因此這個句型 (Sd(T)db) :

演算法非常簡單，就是通過分析樹的後序遍歷，先將子樹的葉節點從左到右排合並成字元串(即一個短語)，然後用它代表子樹的根節點的值，再和與子樹根節點同一層節點值合並，得到新的短語。就這樣從分析樹的最底層，一路合並到分析樹的根節點，就能得到所有的短語了。

通過遞歸的方法，獲取短語列表 phraseList , 直接短語列表 directPhraseList 和 素短語列表 plainPhraseList 。

運行結果:

B. 編譯原理左遞歸消除

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

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

C. 編譯原理為什麼存在遞歸文法

編譯原理中存在遞歸文法是因為編程語言的語法和結構往往具有遞歸性質。遞歸文法是一種用來描述編程語言語法的形式化表示方法，其中規則可以包含對同一語法結構的遞歸引用。這種遞歸性質反映了編程語言中常見的嵌套和遞歸結構。
以下是一些原因，說明為什麼編譯原理中存在遞歸文法：
1. 語法結構的嵌套：編程語言中的語法結構通常可以嵌套在其他語法結構中，例如，一個函數可以包含其他函數，一個條件語句可以包含另一個條件語句，等等。遞歸文法可以很自然地表示這種嵌套結構。
2. 語法的可擴展性：編程語言通常需要具有可擴展性，允許程序員定義新的語法結構或數據類型。遞歸文法可以輕松地擴展以包括新的語法規則。
3. 函數調用和表達式求值：編程語言中的函數調用和表達式求值通常是遞歸的過程。遞歸文法可以用於清晰地描述這些遞歸計算過程。
4. 簡潔性和可讀性：遞歸文法可以幫助編譯器設計者更簡潔地表示語言的語法，這有助於提高編譯器的可讀性和維護性。
5. 符合語言設計的自然表示：遞歸文法使得語法規則的表示更符合編程語言設計的自然結構，因為它們允許對語法結構進行遞歸定義，而不需要多次重復相似的規則。
雖然遞歸文法在編譯原理中非常有用，但它們也需要謹慎使用，以避免無限遞歸或歧義性。編譯器設計者需要確保遞歸文法能夠被正確解析和處理，通常需要使用遞歸下降解析器或其他技術來處理遞歸文法。

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

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

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

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

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

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