編譯原理

CompilerPrinciples2013年9月閆雷鳴第二章文法與語言討論問題：文法和語言的概念和定義文法和語言的分類文法等價變換句型分析簡單回顧對程序的理解程序是計算機執行的一系列指令；程序是計算任務的處理對象和處理規則的描述。

?對程序設計語言的理解程序設計語言是程序的書寫規范；程序設計語言的要素：一組記號(符號)和一組規則。程序設計語言程序是程序設計語言之符號集合上的、按一定規則組成的符號串。?語言是一切句子的集合；程序設計語言是一切程序的集合；把程序看做程序設計語言的句子。?程序是(程序設計）語言的句子?如何系統地構造程序？或者，一般地，如何為一個(程序設計)語言生成句子？

2.1符號串與符號串集合語言實際上是一個符號串集合；文法規定語言中句子的構造規則。句子是一個語言之字母表上按一定規則構造的符號串。2.1.1字母表字母表:有窮非空的符號集合。例A={a,b,c}∑={0,1}C語言字母表={字母，數字，界限符}

不同的語言有不同的字母表。字母表上的元素（即符號）組成符號串。2.1.2

符號串:1.符號串及其長度

符號串:由字母表上的符號所組成的有窮序列。字母表A={a,b,c}上的符號串：

a,b,c,ab,ba,aaa,aab,baa,abcab,ε(空串)

注意：順序是重要的,ab≠baC語言字母表上的符號串？長度：|aabcaca|=7|ε|=02.子符號串若u=xvy，其中|v|≠0（|u|>=|v|）則v是u中的子符號串。（非空符號串）例a+(b-c)/d中的子符號串3.符號串的頭與尾（前綴、后綴）

abc的頭：a,ab,abc,?x=t…

abc的尾：c,bc,abc,?x=…t

4.對符號串的運算聯結（或并置）：

x=aby=baxy=abbayx=baab

對任何符號串x，有x=x=x。

方冪：xn=xx…x(x自身聯結n次)xn=xn-1x=xxn-1

x0=?

x3=(ab)3=ababab|xy|=|x|+|y||xn|=n|x||x0|=02.1.3

符號串集合（語言）1.符號串集合的定義1)它是一切元素都是某字母表上的符號串的集合。

2)表示法枚舉法{1，11，111，1111}

省略法{1，11，111，1111，┅}

描述法{1i|i≥1}或{x|x全由1組成,|x|≥1}

注意：一定不能涉及含義,如{x|x=∑10i}。字母表∑上的一個語言就是∑上的一些符號串組成的集合。

空集ф

是一個語言，僅含一個空符號串集合{ф}也是一個語言。特別需要指出的是，?和{?}是不同的語言。2.對符號串集合的運算乘積：AB={xy|x∈A且y∈B}{1,0}{a,b,c}=?

對任何符號串x有x=x=x，A0={ε}因此，{}A=A{}=A，但?A=A?=?。

方冪：An=AA…A(n個A乘積）

An=An-1A=AAn-1

特例，字母表A的方冪，x∈An,|x|=n{1,0}3=?{1,0}n=?3.字母表的閉包與正閉包閉包A*=A0∪A1∪┅∪An∪┅{0，1，2}*

正閉包A+=A1∪┅∪An∪┅=A*-{}{0，1，2}+

x∈A+,則|x|>=1

x∈A*,則|x|>=0

任何一個語言是其字母表之正閉包的真子集。如何找出此真子集？或說，如何找出其句子？2.2文法與語言的形式定義2.2.1文法的形式定義1.重寫規則（產生式規則）定義：有序對（U，u)或U::=u

A→α（或A::=α）其中，A是一個符號，稱為產生式規則的左部，而α是有窮非空符號串，稱為產生式規則的右部，“→

”和“::=”表示“定義為”或“由……組合成的”或“生成”，其含義是左部符號用右部的符號串定義或左部符號生成右部符號串。產生式規則可合寫，如：A→α和A→β可寫為A→α|β

1.重寫規則（產生式規則）規則表示法：通常的E::=E+TE::=T

或E::=E+T|T

擴充的E::=T{+T}

術語：非終結符號，非終結符號集VN

終結符號，（不會出現在規則左部）終結符號集VT

（

VN∩VT=?V=

VN∪VT）單規則：右部是單個非終結符{}用于指定重復次數<標識符>::=<字母>{<字母數字>}05[]內中符號至多出現一次<整數>::=[+|-]<數字>{<數字>}()提公因子E::=E+T|E-T可改寫為E::=E(+|-)T16規則構造的例子C語言標識符的規則：<標識符>::=<字母下劃線><標識符>::=<標識符><字母下劃線><標識符>::=<標識符><數字><字母下劃線>::=A|…|Z<字母下劃線>::=a|…|z<字母下劃線>::=_<數字>::=0|…|917用規則產生句子的例子如：用標識符產生式規則產生句子area.<標識符><標識符><字母下劃線><標識符>a

<標識符><字母下劃線>a <標識符>ea <標識符><字母下劃線>ea <標識符>rea<字母下劃線>rea

area其中，“=>”為推導。2.文法的定義文法G[Z]是非空有窮的重寫規則集合，其中Z是識別符號（或稱開始符號），G是文法名。例G1[E]：E::=E+TE::=TT::=T*FT::=FF:=(E)F::=iG2[E]：E::=E+T|TT::=T*F|FF::=(E)F::=iG[E]：E::=T{+T}T::=F{*F}F::=(E)|i文法的四要素：VN，VT，P，ZP有窮非空的重寫規則集，識別符號ZVN3.

應用文法產生語言的句子

G[<句子>]:1.<句子>::=<主語><謂語><狀語>2.<主語>::=<名詞>3.<謂語>::=<動詞>4.<狀語>::=<介詞><名詞>5.<名詞>::=Peter6.<名詞>::=Berry7.<名詞>::=river8.<動詞>::=swims9.<介詞>::=in例試以文法G[<句子>]為例考察如何應用文法來生成句子。

替換為?句子?=>?主語??謂語??狀語?

(規則1)

=>?名詞?

?謂語?

?狀語?(規則2)=>Peter?謂語??狀語?

(規則5)=>Peter?動詞?

?狀語?(規則3)=>Peterswims

?狀語?(規則8)=>Peterswims?介詞??名詞?

(規則4)=>Peterswims

in

?名詞?(規則9)=>Peterswimsinriver(規則7)應用文法生成句子的步驟：步驟1以識別符號為當前符號串；步驟2對當前符號串中的一個非終結符號進行替換，把它替換為以此非終結符號為左部的規則之右部符號串，生成新的當前符號串；步驟3重復步驟2,直到當前符號串中不包含非終結符號，最終不包含非終結符號的符號串就是所生成的句子。說明：每步的當前符號串將稱為句型，最終的終結符號串稱為句子。

按上述步驟應用各個規則，可生成：

Berryswimsinriver

甚至可生成：riverswimsinPeter

表明：語法上的正確性不能保證語義上的正確性。

對當前句型中任一非終結符號進行替換，都將生成新的句型，最終生成句子。但宜用系統的方式進行推導，如，每步對最左的或最右的非終結符號進行替換。這時，分別稱為最左推導與最右推導。引進句子生成中的兩個重要概念：推導與歸約。直接推導：=>xUy=>xuy

?句子?=>?主語??謂語??狀語?

?主語??謂語??狀語?=>?名詞??謂語??狀語?

?名詞??謂語??狀語?=>Peter?謂語??狀語?Peter?謂語??狀語?=>Peter?動詞??狀語?Peter?動詞??狀語?=>Peterswims?狀語?Peterswims?狀語?=>Peterswims?介詞??名詞?Peterswims?介詞??名詞?=>Peterswimsin?名詞?Peterswimsin?名詞?=>Peterswimsinriver

直接推導時，給定v=xUy,

找到規則U::=u，把u代替U，

得到w=xuy稱v直接推導到w，記為：v=>w或xUy=>xuy推導（直接推導序列）：=>+<句子>

=>?主語??謂語??狀語?=>?名詞??謂語??狀語?=>Peter?謂語??狀語?=>Peter?動詞??狀語?=>Peterswims?狀語?=>Peterswims?介詞??名詞?=>Peterswimsin?名詞?=>Peterswimsinriver

推導時，給定符號串v,

找到v=>u1=>u2=>…=>un-1=>w,

得到符號串w,稱v推導到w，記為：v=>+w。一般，從識別符號開始推導，例如，

<句子>=>+Peter?謂語??狀語?<句子>=>+Peterswimsinriver

推導長度：直接推導的步數。直接推導

:=>

直接推導時，給定v=xUy，在其中找出U，應用規則U::=u,

得到w=xuy，稱v直接推導到w,或w直接歸約到v,記為v=>w

一般，總有：U::=uxUy=>xuy推導:=>+

推導時，給定符號串v,找出直接推導序列：

v=>u1=>u2=>…=>un-1=>w得到符號串w,稱v推導到w,或w歸約到v,記為:v=>+wn稱為推導的長度。

廣義推導：=>*

若v=>+w或v=w，則稱v廣義推導到w,或廣義歸約到v。對照：直接推導v=>w(U::=uv=xUyw=xuy)(推導長度=1)

推導v=>+w(v=>u1=>…=>un-1=>w)(推導長度1)

廣義推導v=>*w(v=>+w或v=w)(推導長度0)通常考慮的都是從識別符號出發的推導：

Z=>*xx∈(VN

∪VT)+

直接歸約：v=>ww直接歸約為v

歸約:v=>+ww歸約為v

廣義歸約:v=>*ww廣義歸約為v

請對照比較推導與歸約這兩個概念。重要概念：句型、句子句型：Z=>*x,x∈(VN∪VT)+

句子：Z=>*x,x∈VT+

例Peterswimsinriver注意：句子和<句子>在概念上的區別注意：應用文法生成句子僅是形式上的。例riverswimsinPeter注：句子也是句型，但句型不一定是句子。文法產生句型和句子的例子【例】設有文法G[Z]:Z::=aZb|?有推導：Z=>*?Z=>*aZb=>aaZbb=>*aaabbb可見，符號串

ε，aZb，aaZbb和aaabbb都是文法G[Z]的句型，而

ε

和aaabbb才是文法G[Z]的句子。30文法產生句型和句子的例子

【例】設有文法G[E]:

E::=E+T|E-T|TT::=T*F|T/F|FF::=(E)|i

試證明i+i*i是它的一個句子。

分析：只有證明i+i*i可由文法G從開始符號E推導出，即可證明i+i*i是它的一個句子。

證明：

EE+TE+T*FE+T*iE+F*iE+i*iT+i*iF+i*ii+i*i

即有E

*i+i*i

又因i+i*i中的每個符號均為終結符號，故i+i*i是它的一個句子。思考設計編程語言時，是先設計語言形式，還是先設計BNF形式的文法？例如要表示形如i+i,i+i*i的表達式建議：學習時注意積累，何種典型文法可以得到某種典型的語言形式考試考查：能夠由文法寫出語言，也能由語言設計出文法為什么有窮規則集合的文法能定義無窮的語言？文法G[<無正負號整數>]：

1）<無正負號整數>::=<數字序列>2）<數字序列>::=<數字序列><數字>3）<數字序列>::=<數字>4）<數字>::=05)<數字>::=16）<數字>::=27)<數字>::=38)<數字>::=49)<數字>::=510)<數字>::=611)<數字>::=711)<數字>::=812)<數字>::=9VN={<無正負號整數>,<數字序列>,<數字>}VT={0,1,2,3,4,5,6,7,8,9}<無正負號整數>=><數字序列>=><數字序列><數字>=><數字序列><數字><數字>=><數字><數字><數字>=>1<數字><數字>=>12<數字>=>123<無正負號整數>=><數字序列>=><數字序列><數字>=><數字序列><數字><數字>=><數字序列><數字><數字><數字>=>…

遞歸地定義規則，即，U::=U…,使得有窮個規則可能定義潛在地無窮的語言。重要概念：短語、簡單短語

已知w=xuy是文法G的句型,

短語

u:Z=>*xUyU∈VN

U=>+u

簡單短語

u:Z=>*xUyU∈VN

U=>u

理解：句型w=xuy中

⑴可(直接)歸約且

⑵(直接)歸約后所得新符號串仍為句型

的子符號串u。

例句子123中,1、2、3都是簡單短語。

1、12、123、2、3都是短語。

句型<數字序列>1<數字>2

中：

簡單短語有：1、2

短語有：<數字序列>1、1、<數字序列>1<數字>、2

句柄

:句型中最左的簡單短語。句柄是重要概念之一。歸約是自底向上的語法分析關鍵，何時進行歸約則必須依賴句柄。分析句型時，要搞清楚哪些符號串能構成短語和直接短語。36求短語、直接短語和句柄的例子

【例】設有文法G[E]:

求出句型(F+i)－T*(E－T)的短語、簡單短語和句柄。

分析：從句型的推導過程中找出其全部短語、直接短語和句柄。37

可以看出：

句型(F+i)－T*(E－T)包含以下短語：

F，i，F+i，(F+i)，E－T，(E－T)，T*(E－T)，(F+i)－T*(E－T)；簡單短語有：F，i，E－T；句柄為F。注意：選擇符號串判斷是否短語時，必須同時滿足兩個條件：1）可歸約；2）歸約后仍是句型（即可由識別符號推導出）概括文法G:有窮非空的重寫規則集合四要素：VN，VT，P，Z句型：Z=>*t,t∈(VN∪VT)+句子：Z=>*t,t∈VT+概念：推導，歸約簡單短語，短語，句柄4.文法句子之生成的實現實質是推導的構造。要點是推導在計算機內的存儲表示。文法符號序號

后繼符號結點指針其中包含兩類結點，一類結點結構形如：另一類結點結構形如：這易于用C語言結構類型實現，例如，對第一類，

typedefstruct直接推導鏈首結點{struct符號結點*句型首符號結點指針；

struct直接推導鏈首結點*下一直接推導鏈頭指針；}直接推導鏈首結點類型；

句型首符號結點指針

下一直接推導鏈頭指針顯然每一“列”（垂直鏈）中各結點相應的符號組成一個句型。這易于用C語言結構類型實現。以最左推導的建立為例，程序控制流程示意圖如下。

建立最左推導

置初值

把識別符號置為當前句型,

建立一“列”結點

當前句型中包含

N

非終結符號

Y

復制當前句型一“列”結點，把所復制的作為當前句型，并建立與原有當前句型的鏈接

取到當前句型的最左非終結符號U相應的結點

以U為左部的Y

規則僅一個

N

顯示以U為左部的各規則

用戶選擇一個規則，

k=規則序號

關于規則k的右部生成結點鏈，代替U相應的結點出口k=規則序號

由于推導過程中，進行替換的非終結符號可能作為多個規則的左部，在尚未討論分析技術的情況下，宜于采用交互方式由用戶自己選擇進行直接推導的規則。這涉及到文法規則在計算機內的存放。文法的存儲表示：

?一種是數組表示

?一種是鏈表表示

例G[E]：

E::=E+TE::=TT::=T*FT::=FF::=(E)F::=i?數組表示：左部右部符號串右部長度C語言數據結構定義：typedefstruct{符號左部符號；符號右部符號串[MaxRightPartLength+1];int右部長度；}規則;規則

文法[MaxRuleNum+1];其中，typedefchar符號[MaxLength+1]；符號

非終結符號集[MaxVnNum+1];

符號

終結符號集[MaxVtNum+1];

為便于處理，以符號的序號代替符號本身：typedefstruct{int左部符號序號；

int右部符號串[MaxRightPartLength+1];int右部長度；}規則;規則

文法[MaxRuleNum+1];為區分非終結符與終結符，將非終結符的序號+100文法[1]中的規則E::=E+T,在計算機內的存儲表示:

文法[1]：

{101，

{0，101，

1，

102}，

3}文法[2]中的規則E::=T，在計算機內的存儲表示：文法[2]：

{101，

{0，102}，

1}T∈VT：T在VT中的序號

U∈VN：U在VN中的序號+100

注意：C語言數組元素的下標值從0開始，已把0號元素棄之不用。文法的鏈式表示：文法G[E]的數據結構G[E]：E::=E+TE::=TT::=T*FT::=FF::=(E)F::=i2.2.2語言的定義程序設計語言L是一切程序P的集合。

PL

L∑+

（∑=VT

）語言是相應文法一切句子的集合。

L(G[Z])={x|Z=>*x,x∈VT+

}

一個文法確定唯一的語言。反之？

L(G[<程序>])={P|<程序>=>*P,P∈VT+

}

語言可能是有窮的，也可能是無窮的。重要概念：遞歸規則遞歸規則左遞歸：U::=U…

一般遞歸：U::=…U…

規則右遞歸：U::=…U文法遞歸文法左遞歸:U=>+U…

一般遞歸：U=>+…U…

文法右遞歸：U=>+…U遞歸，使有窮多個規則定義的語言可以是無窮的。C語言中的規則遞歸和文法遞歸規則左遞歸有：

<整型常量>::=<整型常量><數字>

規則右遞歸有：

<因式>::=!<因式>

文法右遞歸于<語句>：

<語句>::=<控制語句><控制語句>::=<條件語句><條件語句>::=if(<表達式>)<語句>else<語句>

因此，

<語句>=>+…<語句>

也可以說，C語言文法遞歸于<語句><語句>=>+…<語句>…為語言構造文法

L1={aibjck|i,j,k≥1}aa…aabb…bbcc…ccABCABCABCSG1[S]:S::=ABCA::=Aa|aB::=Bb|bC::=Cc|c

aa…aabb…bbcc…ccAAABBSSG1’[S]:S::=Sc|BcB::=Bb|AbA::=Aa|a注：同一種語言可設計出不同的文法；注意擴展！L2={aibick|i,k≥1}

a…aabb…bcc…cAAASSG2[S]:S::=Sc|AcA::=aAb|ab

L3={aibici|i≥1}G3[S]:S::=abC|aSBCCB::=CDCD::=BDBD::=BCbB::=bbbC::=bccC::=ccL4={a2i|i≥1}G4[S]:S::=ACaBCa::=aaCCB::=DBCB::=EaD::=DaAD::=ACaE::=EaAE::=ε56文法產生語言的例子【例1】設有文法G[Z]:Z::=aaZbb|ab求該文法所描述的語言。

分析：語言：57文法產生語言的例子【例2】設有文法G[Z]:求該文法所描述的語言。

分析：由括號組成的終結符號，且左右括號匹配。

【例3】設有文法G[Z]:求該文法所描述的語言。

分析：1后面緊跟的符號必為0或為空，即該文法產生的是不包括兩個相鄰1的所有0、1串。

語言：

概括1.程序設計語言是一切程序的集合；程序是在程序設計語言字母表上按一定規則構造的符號串；程序設計語言是其字母表正閉包的真子集。2.文法是重寫規則的集合文法四要素：VN、VT、P、Z

文法的句型：由識別符號推導所得的符號串。文法的句子：全由終結符號組成的句型。3.語言是一切句子的集合；文法確定，則語言確定，語言給定，但可為該語言構造若干文法。遞歸，使有窮多個規則能定義無窮的語言。4.重要概念句型、句子推導、歸約短語、簡單短語、句柄遞歸（規則遞歸、文法遞歸）應用文法生成句子的步驟：步驟1以識別符號為當前句型步驟2對當前句型進行直接推導（把其中一個非終結符號替換為以其為左部的規則之右部符號串）步驟3重復步驟2，直到無非終結符號可被替換。通常應以系統的有規則的方式進行替換

·對最左的非終結符號進行替換（最左推導）

·對最右的非終結符號進行替換（最右推導）2.3.1Chomsky文法類和語言類1.Chomsky分類法對文法四要素概括與抽象。定義：Chomsky文法G=（VN,VT,P,Z)VNVTPZ文法及例：

G[S]:S::=Sc|BcB::=Bb|AbA::=Aa|a2.3語言的分類2.3.1Chomsky文法類和語言類1.Chomsky分類法對文法四要素概括與抽象。定義：Chomsky文法G=（VN,VT,P,Z)VNVTPZ文法及例：

G[S]:S::=Sc|BcB::=Bb|AbA::=Aa|a

G1=（VN,VT,P1,S1)VN={S1,A,B}VT={a,b,c}P1:S1::=S1c|BcB::=Bb|AbA::=Aa|aL(G1)={aibjck|i,j,k≥1}G2=（{S2,A},{a,b,c},P2,S2)P2:S2::=S2c|AcA::=aAb|abL(G2)={aibick|i,k≥1}G3=({S3,B,C,D},{a,b,c},P3,S3)P3:S3::=abC|aS3BCCB::=CDCD::=BDBD::=BCbB::=bbbC::=bccC::=ccL(G3)={aibici|i≥1}G4=({S4,A,B,C,D,E},{a},P4,S4)P4:S4::=ACaBCa::=aaCCB::=DBCB::=EaD::=DaAD::=ACaE::=EaAE::=εL(G4)={a2i

|i≥1}分類：按規則的定義形式對文法分類

0型文法（短語結構文法PSG）：

u::=v

u∈(VN∪VT)+,v∈(VN∪VT)*1型文法（上下文有關文法CSG）：

xUy::=xuyU∈VN,x,y∈(VN∪VT)*,u∈(VN∪VT)+2型文法（上下文無關文法CFG）：

U::=xuy

U∈VN,x,y∈(VN∪VT)*,u∈(VN∪VT)+3型文法（正則文法RG）：

U::=VT

或U::=T

U,V∈VN,T∈VT

相應地有4類Chomsky語言：

0型語言（短語結構語言PSL）

1型語言（上下文有關語言CSL）

2型語言（上下文無關語言CFL）

3型語言（正則語言RL）注意：有時對2型文法，擴充有ε規則與ε句子

ε規則：U::=εε句子：Z=>*ε2.3.2*

形式語言與自動機Chomsky語言類和自動機的對應關系：

3型語言~有窮狀態自動機

FA2型語言~下推自動機PDA1型語言~線性界限自動機LBA0型語言~圖靈機TM

2.3.3形式語言的分類與程序設計語言

1.程序設計語言一般用上下文無關文法定義：

U::=u2.但語言一般是上下文有關的

(1)<標號>::=<標識符><變量>::=<標識符>goto<標號>::=goto<標識符>

<標號>:<語句>::=<標識符>:<語句>

(標識符由所在上下文確定是否標號)(2)<函數標識符>'('<實在參數表>')

'

<數組變量>'['<下標表達式表>']

'<變量>=<表達式>(標識符由后跟符號確定是函數標識符、數組變量還是變量)3.通常：詞法正則文法語法上下文無關文法語義口語2.3.4對上下文無關文法的進一步討論1*.上下文無關文法的自嵌套特性如果一個上下文無關文法G中存在具有下列特性的非終結符號U：

U=>*xUy其中x,y∈V+，則稱U為自嵌套的非終結符號，包含自嵌套非終結符號的文法G稱為自嵌套的上下文無關文法。

若一個上下文無關文法G不是自嵌套的，則L(G)是一個正則語言。

對任何一個正則語言，必定可構造不是自嵌套的文法。一個嚴格的上下文無關語言，必不能構造非自嵌套的文法。自嵌套特性把正則語言與嚴格的上下文無關語言區別開來。

2.與推導有關的特性⑴對于CFG，若存在句型x=x1x2…xn,有

x1x2…xn=>*y,

則必存在y1,y2,…,yn，使得

xi=>*yi(i=1,2,…,n),Z

且y=y1y2…yn。⑵設x=>*y,若x的首符號∈VT,X1X2…Xn

則y的首符號也∈VT

。反之，y的首符號∈VN,則y1y2…yn

x的首符號也∈VN

。3.ε規則

ε規則：U::=ε

Chomsky2型文法U::=u中，u∈VT+,

不包含ε規則，但有時讓u∈VT*,

例如進行文法等價變換，便引進ε規則。引進ε規則，便可能產生ε句子：

Z=>*ε

對于所有非0型的語言，包括上下文無關語言，刪去或添加一個ε句子，不改變原來的語言類。4*.上下文無關語言的可判定性對于一個程序設計語言來說，重要的是能機械且高效地在有限的時間內判定一個符號串是否是語法上正確的程序，換句話說，就是判定一個符號串是否是屬于該(程序設計)語言的句子。這就是可判定性問題。一般地，可判定性問題可以這樣描述：設集合L是集合S的一個子集，而x是S的一個任意元素,問:是否可能機械而高效地判定x是否L的一個成員?

對于上下文無關語言，這問題的答案是肯定的。

2.4文法等價和等價變換2.4.1文法等價的概念文法G1與G2等價，若L(G1)=L(G2)。1.例L1={aibjck|i,j,k≥1}G1[S]:S::=ABCA::=Aa|aB::=Bb|bC::=Cc|cG1'[S]:S::=Sc|BcB::=Bb|AbA::=Aa|aG1與G1'等價。2.文法等價變換的必要性文法等價變換的概念：對文法進行變換，使得變換后的文法滿足某種要求，并且與原文法等價，這種變換稱為文法的等價變換。文法等價變換的必要性

?使文法類與語言類一致

?消去二義性

?使文法適用于某種分析技術

?特殊需要文法等價變換的種類：

?壓縮文法等價變換

?消去左遞歸文法等價變換

?消除單規則文法等價變換

?增廣文法等價變換

2.4.2壓縮文法等價變換1.壓縮了的文法目的：使文法中任一規則都能用來生成文法的句子，使文法中無多余規則。多余規則：U::=U形規則不滿足下列條件的規則Ｕ::=u：條件１Ｚ=>*…U…(U出現在句型中）條件２u=>*tt∈VT+(可推導到終結符號串）概念：若文法中任一規則都滿足上述條件１和條件2,則稱壓縮了的文法。

Z=>*xUy=>xuy=>*tt∈VT+,即，t是句子。76文法壓縮（化簡）的基本思想條件1）若一符號不能出現在文法的任何句型中，則該符號是無用的。

條件2）若一個非終結符不能推導出終結符號串，則該非終結符是無用的。

從識別符號開始或從終結符號開始。刪除這些規則，不會改變文法描述的語言2.無用規則的判別算法

算法步驟如下:

步驟１規則展開成非縮寫形式并刪除U::=U形規則;

步驟２判別條件１，刪除不滿足條件１的規則;

步驟３判別條件２，刪除不滿足條件２的規則;

步驟４重復步驟２和步驟３，直到無規則被刪除。實現：采用加標記的算法。

采用加標記的算法。對條件1：U::=xVy中，若規則左部U加過標記，則對右部非終結符號V加標記。對條件2：U::=xVy,若規則右部全由終結符號和加過標記的非終結符號組成,則對左部非終結符號加標記。對于文法G[Z]：

Z∷=BeA∷=Ae｜A｜eB∷=Ce｜AfC∷=CfD∷=f

步驟1展開并刪除U::=U形規則成：

Z∷=BeA∷=AeA∷=eB∷=CeB∷=AfC∷=CfD∷=f步驟2判條件1，加標記：

*******

Z∷=BeA∷=AeA∷=eB∷=Ce

****

B∷=AfC∷=CfD∷=f規則D∷=f是多余的,應刪除。從而得到文法

G'[Z]：

Z∷=BeA∷=AeA∷=eB∷=CeB∷=AfC∷=Cf

步驟3判條件2，加標記：

*****

Z∷=BeA∷=AeA∷=e

*

*

B∷=CeB∷=AfC∷=Cf

規則B∷=Ce與C∷=Cf是多余的，應刪除。

重復判條件1與2，最終得到與文法G[Z]等價的壓縮了的文法G″[Z]:Z∷=BeA∷=AeA∷=eB∷=Af

壓縮文法等價變換的規范步驟：步驟１規則展開成非縮寫形式并刪除U::=U形規則;步驟２判別條件１，刪除不滿足條件１的規則;步驟３判別條件２，刪除不滿足條件２的規則;步驟４重復步驟２和步驟３，直到無規則被刪除。3.*

實現之考慮2.4.3消去左遞歸的文法等價變換左遞歸的存在將導致自頂向下語法分析失敗自頂向下：即從識別符號出發，使用不同規則進行推導。左遞歸可使分析陷入無窮循環，導致棧溢出U=>Ux=>Uxx=>Uxxx=>…=>因此，對自頂向下分析技術，需要消除左遞歸。2.4.3消去左遞歸的文法等價變換1.規則左遞歸的消去(U::=Ux|y)U=>Ux=>Uxx=>Uxxx=>…=>yxx…xx例G[E]：E::=E+T|TU'T::=T*F|FF::=(E)|iE=>E+T=>E+T+T=>…U'=>T+T+T…+T+TU'a.改成右遞歸T+T+T…+T+TU::=Ux|y→U::=yU'U'::=xU'|εE'例E::=TE'E'::=+TE'|?E'T::=FT'T'::=*FT'|?E'一般情況下，U::=Ux1|Ux2|…|Uxm|y1|y2|…|ynU::=Ux1|Ux2|…|Uxm|y1|y2|…|yn→U::=U(x1|x2|…|xm)|(y1|y2|…|yn)→U::=(y1|y2|…|ym)U'U’::=(x1|x2|…|xn)U'|ε

b.用擴充表示法

U::=Ux|y→U::=y{x}一般情況下，

U::=Ux1|Ux2|…|Uxn|y1|y2|…|ym→U::=U(x1|x2|…|xn)|(y1|y2|…|ym)→U::=(y1|y2|…|ym){x1|x2|…|xn}2.文法左遞歸的消去（間接的規則左遞歸）基本思想:對非終結符號排序成U1、U2、…、Un后文法等價變換成呈下形:U1::=Ui1…(或U1::=T…)i1>1U2::=Ui2…(或U2::=T…)i2>2…Uj::=Uij…(或Uj::=T…)ij>j…Un-1::=Un…(或Un-1::=T…)Un::=T…T∈VT一般地，對于Ui::=Uj…必有：j>i,從而不可能產生U=>+U…U->…->Ua文法左遞歸消去文法左遞歸的算法步驟:

步驟１把非終結符號排序成U1,U2,…,Un

步驟２以上列順序執行下列程序：

for(i=1;i<=n;i++){for(j=1;j<=i-1;j++){把形如Ui::=Ujr的規則改寫成:Ui::=xj1r|xj2r|…|xjkr

其中Uj::=xj1|xj2|…|xjk是對于Uj的一切規則

}

消除關于Ui的規則左遞歸;}消去文法左遞歸等價變換的解題規范：步驟1識別是規則左遞歸還是文法左遞歸步驟2進行相應的文法等價變換步驟3給出消去了左遞歸的等價文法例設有文法G[S]：

G[S]：S∷=Sa｜Tbc｜Td

T∷=Se｜gh

試消去其文法左遞歸。

G[S]：S∷=Sa｜Tbc｜Td

T∷=Se｜gh解:步驟1排序：U1=SU2=T(n=2)

步驟2執行循環：

i=1，j=1：j＞i－1，不執行關于j的循環，消去關于U1=S的規則左遞歸（改寫成右遞歸）：

S∷=(Tbc|Td)S'S'∷=aS'|εi=2，j=1：有規則T∷=Se|gh，呈U2::=U1…形，把S∷=(Tbc|Td)S'代入，得

T∷=(Tbc|Td)S'e|gh因此,T∷=T((bc|d)S'e)|gh

消去關于U2=T的規則左遞歸如下:T∷=ghT'T'∷=(bc|d)S'eT'|ε最后得到文法G[S]：

G[S]：S∷=Sa｜Tbc｜TdT∷=Se｜gh消去了左遞歸的等價文法G'[S]：

S∷=T(bc｜d)S'S'∷=aS'|εT∷=ghT'T'∷=(bc|d)S'eT'|ε例設有文法G[A]：

G[A]:A∷=Ba|Cb|c

B∷=dA|Ae|f

C∷=Bg|Ah

試消去該文法的左遞歸。

G[A]:A∷=Ba|Cb|c

B∷=dA|Ae|f

C∷=Bg|Ah解：首先判別知，該文法存在文法左遞歸。步驟1排序成：U1=A，U2=B,U3=C；步驟2執行循環：

i=1,j=1:j＞i－1，不執行關于j的循環，且關于U1=A不存在規則左遞歸。

i=2,j=1:有規則B∷=Ae|dA|f，呈U2::=U1…形，把規則A∷=Ba|Cb|c代入，得

B∷=(Ba|Cb|c)e|dA|f或B∷=Bae｜Cbe｜ce｜dA｜f消去關于U2=B的規則左遞歸，所以,B∷=(Cbe|ce|dA|f)B'B'::=aeB'|ε

i=3,j=1:有規則C::=Ah|Bg，呈U3::=U1…形，把規則A::=Ba|Cb|c代入,C::=(Ba|Cb|c)h|Bg或C::=B(ah|g)|(Cb|c)hi=3,j=2:由規則C∷=B(ah|g)|(Cb|c)h,呈U3::=U2…形，把規則B∷=(Cbe|ce|dA|f)B'代入，得

C::=(Cbe|ce|dA|f)B'(ah|g)|(Cb|c)h或C::=C(beB'(ah|g)|bh)|(ce|dA|f)B'(ah|g)|ch消去關于U3=C的規則左遞歸，得到

C∷=((ce|dA|f)B'(ah|g)|ch)C'|εC'::=(beB'(ah|g)|bh)C'|ε最后得到消去了左遞歸的等價文法

G'[A]:A∷=Ba｜Cb｜cB∷=(Cbe|ce|dA|f)B'

B'::=aeB'|εC∷=((ce|dA|f)B'(ah|g)|ch)C'|εC'::=(beB'(ah|g)|bh)C'|ε3.*

實現之考慮要點:·識別文法是規則左遞歸還是文法左遞歸

·文法在計算機內的存儲表示2.5

語法分析樹與句型分析

2.5.1語法分析樹的概念1.語法分析樹的引進

<句子>

術語：結點根結點末端結點

<主語><謂語><狀語>

邊

分支

<名詞><動詞><介詞><名詞>

分支名字結點

分支結點

Berryswimsinriver

分支結點符號串子樹子樹末端結點符號串樹末端結點符號串語法分析樹

一個句型推導過程的樹形表示稱為語法分析樹，或簡稱語法樹。語法樹的優點是：它有助于理解一個句子語法結構的層次。語法樹通常表示成一棵倒立的樹，根在上，樹葉在下。

語法樹離不開句型，一棵語法樹是相對于某個句型而存在，脫離句型的語法樹是不存在的。句子

Berryswinsinriver的推導：<句子>=><主語><謂語><狀語>=><名詞><謂語><狀語>=>Berry<動詞><狀語>=>Berryswins<狀語>=>Berryswins<介詞><名詞>=>Berryswinsin<名詞>

=>Berryswinsinriver如何為它構造語法分析樹？2.從推導構造語法分析樹從推導構造語法分析樹的步驟如下.

步驟1以識別符號為根結點，對應于第一個直接推導向下作分支。步驟2從第二個直接推導左邊被替換的非終結符號相應的結點向下作分支,對應于此直接推導。步驟3類似地對應于每個直接推導,從左邊被替換的非終結符號對應的結點向下作分支,相應于此直接推導。如此繼續，直到推導完。重要性質：

分支的分支結點符號串是相應句型中相對于分支名字結點的簡單短語。

Z=>*xUy=>xuyU=>u

子樹的末端結點符號串是相應句型中相對于子樹根結點的短語。

Z=>*xUy=>+xuyU=>+u利用語法分析樹尋找句型中的簡單短語和短語。3.從語法分析樹構造推導這是從推導構造語法分析樹的逆過程。

EF*i+i=>i*i+iT*i+i=>F*i+i=>i*i+iE+TT*F+i=>T*i+i=>F*i+i=>i*i+i