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

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

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

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

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

B. 編譯原理問題：求解

E是文法開頭。ε代表終結符號(推理中代表終點或結果，程序語言中代表常量等)。E T 這些大寫字母一般代表非終結符號（這些代表中間過程，非結果。程序中代表函數等等）。開始是E。因為有個G(E)。E就是文法開始符號。推導就有E開始，它也是一個非終結符(代表函數、或者一個推導過程，類似於程序中的main(c++)、winmain(vc++)、dllmain(dll)等主函數）。

1算術表達式文法：這個文法是一個遞歸文法。計算機進行邏輯推導時會走很多彎路（類似於遍歷一顆樹的過程）。為了不讓計算機走彎路（提高效率的目的），可以變換為第二種文法。這種文法消除了遞歸（消除了歧義，類似於後綴表達式），使計算機可以一條直線走到底兒推導出結果。

我也很久沒看編譯原理了。 呵呵

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

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

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

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

D. 編譯原理中,形式語言里怎麼區分2型文法與3型文法

通過演算法對文法的每一產生式進行分析,如果存在復雜遞歸,則必是上下文無關文法,否則就是正則文法.
1、像A->Aa|ε這樣的文法,雖然存在遞歸,但卻是單一的自遞歸,可以通過有窮自動機表示和分析處理,所以是正則文法；
2、但是像E->E+T,T->id|(E)這樣的文法顯然非單一的自遞歸,而是存在復雜遞歸,自動機是無法表示和處理的,必然是上下文無關文法.
另外還請注意：
1、正則文法是上下文文法的子集,正則文法也屬於上下文無法,但有的上下文文法不一定是正則文法；
2、同時再結合這兩個的形式定義認真揣摩必定能悟出一二.

E. 求解編譯原理的一道題:設有文法如下

首先要做這題你要知道判別文法類型
包括四個層次：

0-型文法（無限制文法或短語結構文法）包括所有的文法。該類型的文法能夠產生所有可被圖靈機識別的語言。可被圖靈機識別的語言是指能夠使圖靈機停機的字串，這類語言又被稱為遞歸可枚舉語言。注意遞歸可枚舉語言與遞歸語言的區別，後者是前者的一個真子集，是能夠被一個總停機的圖靈機判定的語言。
1-型文法（上下文相關文法）生成上下文相關語言。這種文法的產生式規則取如 αAβ -> αγβ 一樣的形式。這里的A 是非終結符號，而 α, β 和 γ 是包含非終結符號與終結符號的字串；α, β 可以是空串，但 γ 必須不能是空串；這種文法也可以包含規則 S->ε ，但此時文法的任何產生式規則都不能在右側包含 S 。這種文法規定的語言可以被線性有界非確定圖靈機接受。
2-型文法生成上下文無關語言。這種文法的產生式規則取如 A -> γ 一樣的形式。這里的A 是非終結符號，γ 是包含非終結符號與終結符號的字串。這種文法規定的語言可以被非確定下推自動機接受。上下文無關語言為大多數程序設計語言的語法提供了理論基礎。
3-型文法（正規文法）生成正規語言。這種文法要求產生式的左側只能包含一個非終結符號，產生式的右側只能是空串、一個終結符號或者一個非終結符號後隨一個終結符號；如果所有產生式的右側都不含初始符號 S ，規則 S -> ε 也允許出現。這種文法規定的語言可以被有限狀態自動機接受，也可以通過正則表達式來獲得。正規語言通常用來定義檢索模式或者程序設計語言中的詞法結構。
正規語言類包含於上下文無關語言類，上下文無關語言類包含於上下文相關語言類，上下文相關語言類包含於遞歸可枚舉語言類。這里的包含都是集合的真包含關系，也就是說：存在遞歸可枚舉語言不屬於上下文相關語言類，存在上下文相關語言不屬於上下文無關語言類，存在上下文無關語言不屬於正規語言類。

1）本題應該是--上下文無關文法

句子是產生式在推導時「僅僅有終結符」的任何一步
2）%mm%nn 是一個句子

由於下面一題的圖我等級不夠 不能貼圖 發你郵箱

F. 編譯原理，遞歸下降子程序語法分析

沒學過編譯原理，看描述，是讓寫一個腳本執行軟體。
終結符我查了下，就是不可再分的。比如iε。
輸入是EGTSFI*/ε組成的字元串。
規則需要預處理。注意轉意符在字元串中的效果。因為有/字元。

不會c或c++，只會c#。你可以到貼吧發帖。強人工智慧吧 就挺好。演算法吧有點亂。

最重要的，不要錢。

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

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

H. 編譯原理中，形式語言里怎麼區分2型文法與3型文法

二型文法如下:
S->Ac
S->Sc
A->ab
A->aAb
三型文法如下:
S->aS
A->bA
B->cB
B->c
A->Bb
A、2型文法是上下文無關文法，表現在產生式上就是產生式的左部只有一個非終結符；3型文法從廣義上講包括左線形文法、右線形文法和正規文法 。
B、左線形文法產生式的右部要麼沒有非終結符，如果有非終結符也只能有一個，且必須位於產生式右部的最左端。
C、右線形文法產生式的右部要麼沒有非終結符，如果有非終結符也只能有一個，且必須位於產生式右部的最右端 。
D、正規文法是右線形文法的一個子集，其產生式右部只有三種情況：
1）空串
2）只有一個終結符
3）只有一個終結符後接一個非終結符
E、所有的3型文法都是2型文法。

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

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

J. 編譯原理中的左遞歸

1.A->Aa
2.A->Ba
B->Ab (A和B屬於非終結符，a和b屬於終結符)

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