c語言文法規則左遞歸變右遞歸

A. 什麼是左遞歸

左遞歸在計算機科學裡面，左遞歸是一種遞歸的特殊狀況。在上下文無關文法內里的說法，，若一個非終端符號(non-terminal)r有任何直接的文法規則或者透過多個文法規則，推導出的句型(sentential form)其中最左邊的符號 又會出現r，則我們說這個非終端符號r是左遞歸的。使用類似的方式我們可以定義出某文法本身是左遞歸的。若我們可以找出其中存在某非終端符號A，最終會推導出來的句型(sentential form)裡麵包含以自己為最左符號(left-symbol)的句型"[1][編輯]直接左遞歸直接左遞歸(Immediate left recursion)以下面的句型規則出現：這里跟代表不同的非終端符號跟終端符號組成的序列，並且不一定要包含。

舉例來說，以下規則就是一個直接左遞歸的例子。 這規則的遞歸下降分析器(recursive descent parser)可能會像這樣：function Expr()
{
Expr(); match('+'); Term();
}
然後這個遞歸下降分析器在嘗試去解析包含此規則的文法時，會陷入一個無窮的遞歸。[編輯]間接左遞歸間接左遞歸(indirect left recursion)最簡單的形式如下：這規則可能產生 這種生成。簡單的說，間接左遞歸就是，並非在一條規則內完成左遞歸，而是在許多條規則之後，於產生的句子最左邊出現了一開始的非終端符號。更一般化的說法，對非終端符號，間接左遞歸被定義為以下的型態：這里的都是一堆終端與非終端符號的序列。[編輯]在由上而下語法分析(top-down parsing)里容納左遞歸一個包含左遞歸的形式文法不能以簡易的 遞歸下降分析器進行語法分析，除非將文法轉變為weakly equivalent 的右遞歸形式 (相對的，在LALR分析器裡面則比較偏好左遞歸，因為比起右遞歸來說會使用比較少的堆棧)；然而，比較復雜的由上而下(top-down)語法分析器裡面可以藉由使用縮減(by use of curtailment)來實做一般的上下文無關文法。 在2006年, Frost 和 Hafiz 提出一個演算法，可以容納包含直接左遞歸生成規則的 模糊文法*(ambiguous grammers)。[2] 在2007年，Frost，Hafiz和Callaghan 將此演算法延伸為一個完整的，可以適用並在多項式時間內處理直接或間接左遞歸，而且可以為高度模糊文法接近指數數目的分析樹，產生小一些多項式空間的表示法。[3]這些人後來在Haskell編程語言裡面以這個演算法實做了一個的分析器組合(parser combinator)的集合。[4][編輯]移除左遞歸[編輯]移除直接左遞歸一個一般化後移除直接左遞歸的演算法如下所述。 這個方法已經有過許多的改進，包括Robert C. Moore所撰寫，名為"Removing Left Recursion from Context-Free Grammars"的改進。[5]對於每個規則如下(注意這里：A 是一個有左遞歸的非終端符號 是一個終端與非終端符號的序列，而且不為空字串 () 是一個不以A開頭的，以終端與非終端符號組成的序列)將A的規則改成以下規則：然後對新創造出來非終端符號的規則這個新創造出來的符號常被稱為"尾巴"(tail)，或者"rest"(剩餘)舉例，考慮以下規則我們可以改寫為然後最後一個規則可以縮短改寫為來避免掉左遞歸的出現[編輯]移除間接左遞歸如果文法內不存在 (代表空字串)的生成 (不存在這樣的規則)，而且不是循環(cyclic)的文法(對所有非終端符號A，不存在像是這種形式的規則)，以下這個一般化的演算法可以用來去除文法的間接左遞歸：將所有非終端符號以某個固定的順序排列從 i = 1 到 n {
從 j = 1 到 i – 1 {
設的生成規則為將所有規則 換成移除規則中的直接左遞歸}}[編輯]陷阱上面的轉換使用右遞歸的文法來避免掉左遞歸的出現；但是這樣會改變規則的結合律。左遞歸會創造出向左的結合律；但是右遞歸則會創造出向右的結合律。範例 :一開始我們拿到以下文法：在我們使用上面的轉換方式來移除掉左遞歸之後，我們取得了以下文法：我們將字串 'a + a + a'用一個LALR分析器(這種分析器可以處理左遞歸的文法)使用原先的文法來分析，會得到下面的分析樹(parse tree)： Expr
/ | \
Expr + Term
/ | \ \
Expr + Term Factor
| | |
Term Factor Int
| |
Factor Int
|
Int
整個分析樹是往左邊長，代表在這里的規則，'+'這個符號是左結合(left associative)的，或者說這規則代表(a + a) + a。但是我們改變了文法之後，那這個分析樹會變成： Expr ---
/ \
Term Expr' --
| / | \
Factor + Term Expr' ------
| | | \ \
Int Factor + Term Expr'
| | |
Int Factor
|
Int
我們可以看出這棵樹現在是往右邊成長，意思上代表了a + ( a + a)。我們將'+'的結合綠改變了, 變成是右結合的規則。 在處理加法的文法時這不是什麼問題，但是如果我們現在處理的是減法，這就會變成是很嚴重的問題。問題的關鍵在於有很多常用的算術規則要求左結合的規則。我們有幾種解決辦法： (a) 將規則重新改為左遞歸，(b) 使用更多的非終端符號來改寫規則，以強迫文法合乎正確的結合(c) 如果使用YACC 或者Bison，他們有所謂算符宣告(operator declarations)， %left, %right and %nonassoc，這一些算符可以告訴語法分析器產生程式(parser generator)應該遵從哪一種結合。

B. 已知文法G[S]: S->(L)|a L->L，S|S (1)消除文法G的左遞歸,並為每個非終結符構造不帶回溯的遞歸子程序；

（1）S→(L)|aS』 S』→S|ε L→SL』 L』→SL』|ε (2) FIRST 和 FOLLOW FIRST)S)＝{(，a} FOLLOW(S)＝{#，，，)} FIRST(S』)＝{，a,ε} FOLLOW(S』)＝{#，，，)} FIRST(L)＝{(，a} FOLLOW(L)＝{ )} FIRST(L』)＝{，，ε} FOLLOW(L』〕＝{ )}

C. 什麼是語法規則的遞歸性，請舉例說明

遞歸性，也可相近地理解為層次性或有機性。是機體或系統的共性，是系統得以存在，運作和發展的基本手段。遞歸性不僅是轉換生成語法中的一種語法屬性，而且它與任意性、 線性一樣是語言的根本性質之一。

語言結構層次和言語生成中相同結構成分的重復或相套。反復地使用構成句法關系的有限的幾種句法規則，不斷地進行同功能替換，以構成復雜的短語或句子。

在句法組合中，遞歸性有兩種表現，一種是從初始結構開始，自始至終重復運用同一條語法規則。

例如"計算機/我//喜歡"這個句子是主謂結構，它們的謂語( / 以後的部分)本身又是主謂結構，這里，"主語+謂語"這條語法規則不間斷地使用了兩次；另外一種表現是，同一條語法規則可以在一個結構上間隔地重復使用。

(3)c語言文法規則左遞歸變右遞歸擴展閱讀：

遞歸性是語言的根本性質之一，語言的遞歸性賦予語言無限的創造性，說話者可以創造出自己從未聽過或者講過的話語。遞歸性是語言結構層次和言語生成中相同結構成分的重復或相套 。句子能夠很好地體現語言的遞歸性，而通常我們認為，句子是語言中最大的句法單位，所以句法成為人們研究的核心。

人有限的記憶和無限的思維之間的矛盾促生了詞的遞歸性，遞歸性在所有語言里都有表現，印歐語系的詞根，詞綴，縮寫等即是遞歸性的表現。遞歸的最終目的是形成詞素，漢語的通常意義的"字"是較完善的遞歸的結果。

它應稱為"詞素"較合適，漢語的"字"有時做詞用(例"會")，即人們常說的單字詞。有時做詞素用(例"協會")，漢語"字"由詞向詞素的過渡是漢語的一場革命。

D. 關於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)|ε

E. 消除文法的左遞歸性

為了消除那些經多步推導所出現的左遞歸性，可首先查出那些具有左遞歸性的非終結符號，然後對以這些非終結符號為左部的產生式，通過逐步代入有關產生式的方式將它們化為直接左遞歸的產生式，最後再消除其中的全部直接左遞歸即可。顯然，這是一個十分繁瑣的過程。下面，我們再介紹一種一次消去文法的一切左遞歸性的方法，為此，先引入文法的一種矩陣表示。
設G是一前後文無關文法，它的VN中含有n個非終結符號：X1,X2,…,Xn，對於G的每一產生式
Xi→γ1|γ2|…|γm，
我們可將它的各候選式γ1,γ2,…,γm分為兩類： 把以非終結符號打頭的γi歸為一類；而將以終結符號打頭的歸為另一類。例如，若某個γk以Xj打頭，就把γk寫成Xjαji (αji∈V+)。此時，若將元語言符號→及|形式地用「=」及「+」表示，即可將此產生式寫成
Xi=X1α1i+X2α2i+…+Xnαni+β i
其中，β i是那些以終結符號打頭的諸候選式之「和」。此外，若此產生式不含以某一非終結符號Xj打頭的候選式，則相應的αji為。這樣，我們就可將G的諸產生式寫成如下的矩陣方程
(X1 X2 … Xn)=(X1 X2 … Xn)·α11[]α12[]…[]α1n
α21[]α22[]…[]α2n
…[]…[]…[]…
αn1[]αn2[]…[]αnn+(β1 β2 … βn)(411)
或
X=XA+B(412)
式(411)或式(412)即為文法G的一種矩陣表示。不過，需要注意的是，對上面各式中所出現的運算符應作如下的理解： 乘法運算表示字元串的連接，加法運算表示選擇。仿342中的討論可知，矩陣方程(412)有形如
X=BA*(413)
的解。顯然，要計算矩陣A的閉包A*一般是很困難的，但可設法予以迴避。事實上，由於
A*=I+A+A2+…=I+AA*
其中
I=ε[][][]…[]
[]ε[][]…[]
…[]…[]…[]…[]…
[][][]…[]ε
若設
A*=Z=z11[]z12[]…[]z1n
z21[]z22[]…[]z2n
…[]…[]…[]…
zn1[]zn2[]…[]znn
則可得如下兩個矩陣式
X=BZ(414)
Z=I+AZ(415)
由於列矩陣B的各元素的每一項均以終結符號開始，故矩陣式(414)相應的諸產生式的右部符號串也以終結符號開始，也就是說它們都不是左遞歸的。至於由式(415)新引入的產生式，由於它們的左部為zij，顯然也不會有任何的左遞歸性。此外，從式(412)推演到式(414)和式(415)的過程中，實際上只進行了一些等價的代換演算，故由式(414)和式(415)所表示的文法將與原文法G等價。但若新文法中含有無用的產生式 (它們可能由式(415)引入)，則應予以剔除。
例41考慮文法
S→Sa|Ab|a(416)
A→Sc
顯然，其中S，A都是左遞歸的非終結符號。首先寫出此文法的矩陣表示
(S A)=(S A)a[]c
b[]+(a )
令
a[]c
b[]*=Z=z11[]z12
z21[]z22
則有
(S A)=(a ) z11[]z12
z21[]z22
z11[]z12
z21[]z22=ε[]
[]ε+a[]c
b[]z11[]z12
z21[]z22
於是，我們就得到了與文法(416)等價的文法
S→az11A→az12
z11→az11|cz21|ε
z12→az12|cz22
z21→bz11z22→bz12|ε
刪除其中的無用產生式，我們有
S→az11
z11→az11|cz21|ε
z21→bz11

F. 編譯中左遞歸與右遞歸的差異在哪裡，為什麼要把左

採納我告訴你答案
-」接線柱出；被測電壓不要超過電壓表的量程；

G. 具有左遞歸的文法對遞歸下降分析有何影響

你說的應該是編譯原理吧。
遞歸下降分析程序的實現思想是：識別程序由一組子程序組成。每個子程序對應於一個非終結符號。
每一個子程序的功能是：選擇正確的右部，掃描完相應的字。在右部中有非終結符號時，調用該非終結符號對應的子程序來完成。

所以，當有左遞歸出現時，遞歸下降分析程序就會出現回朔，將可能產生無限的循環，所以遞歸下降分析的前提條件之一就是消除左遞歸。

H. 編譯原理一個文法的EBNF表示

首先
lexp-seq->lexp-seq lexp|lexp
消除左遞歸 得
lexp-seq->lexp q'
q'->lexp q'|空

解的ebnf為

lexp->NUMBER|(+|-|*)lexp{lexp}
就得
S->{NUMBER(+|-|*)}NUMBER
{}中間表示0次或以上

I. 編譯原理文法問題，急急急

第一題
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

J. 編譯原理中的左遞歸

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

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