第3章語法分析(1)計算機科學與技術(shù)學院國家示范性軟件學院第3章語法分析1詞法分析看語言：字符串集合；字符串由字符組成、線性結(jié)構(gòu)語法分析看語言：句子的集合；句子由記號組成、非線性結(jié)構(gòu)1.語法規(guī)則：上下文無關(guān)文法（子集：LL文法或LR文法）2.語法分析：自上而下分析、自下而上分析；下推自動機（LL分析器、LR分析器）本章主要內(nèi)容:語法分析的雙重含意:第3章語法分析23Parser的位置：Parser的作用(任務(wù))：3.1.1語法分析器的作用3.1語法分析的若干問題根據(jù)詞法分析器提供的記號流，為結(jié)構(gòu)正確的輸入構(gòu)造分析樹(或語法樹)（這是本章的重點）；檢查輸入中的語法錯誤（可能包括詞法錯誤），并調(diào)用出錯處理器進行適當處理。

43.1語法分析的若干問題3.1.2語法錯誤的處理原則<1>源程序中可能出現(xiàn)的錯誤（第1章學習中已討論）。<2>語法錯誤處理的目標<3>語法錯誤的基本恢復策略自學了解即可5定義3.1CFG是一個四元組G=(T，N，S，P)，其中：(1)T

是終結(jié)符的有限集合(Terminals)；(2)N

是非終結(jié)符的有限集合(NonTerminals)；(3)S

∈N，稱為文法的開始符號(StartSymbol)；(4)P

是產(chǎn)生式的有限集合(Productions)。每個產(chǎn)生式的書寫形式為A→α，其中：

左部A∈N，右部α∈(N∪T)*。若α=ε，則稱A→ε為空產(chǎn)生式（也可記為A→）。3.2.1CFG的定義與表示[ContextFreeGrammar,CFG]3.2上下文無關(guān)文法(CFG)注：兩類符號統(tǒng)稱為文法符號且N∩T=Φ注：唯一性注：ε不是

文法符號6N=

T

=

S=P:例3.2

如下CFG描述了簡單算術(shù)表達式：<1>產(chǎn)生式的一般讀法(G3.1)3.2.1CFG的定義與表示{E}

{+,*,(,),-,id}

EE→E+E（1）

E→E*E（2）

E→（E）（3）E→-E（4）

E→id

（5）巴克斯范式(BNF)可將→

讀作“定義為”或者“可導出”。更一般的，“E→E+E”可用自然語言表述為“算術(shù)表達式定義為兩個算術(shù)表達式相加”，或者“一個算術(shù)表達式加上另一個算術(shù)表達式，仍然是一個算術(shù)表達式”。7對于一個正確的CFGG=(T,N,S,P)，定義中：∵

產(chǎn)生式形如A→α，A∈N，α∈(N∪T)*

，N∩T=Φ，∴

N是必須出現(xiàn)在產(chǎn)生式左部的符號的集合；

T是只

出現(xiàn)在產(chǎn)生式右部的符號的集合(不包括ε)。P:E→E+E（1）

E→E*E（2）

E→（E）（3）

E→-E（4）

E→id（5）可知其定義中，S=

N={

}T={

}E E+，*，(，)，-，id3.2.1CFG的定義與表示<2>用產(chǎn)生式集合表示CFG再約定：

第一個產(chǎn)生式的左部是文法開始符號S；則：CFG可用產(chǎn)生式集表示。8①

用大小寫區(qū)分：E→id②

用""區(qū)分：E→"id"E→E"+"E③

用<>區(qū)分：<E>→<E>+<E><3>終結(jié)符與非終結(jié)符書寫上的區(qū)分3.2.1CFG的定義與表示本課程/教材中的約定：非終結(jié)符:大寫英文字母，如A、B、C。終結(jié)符：小寫英文字母，如a、b、c等；

小寫字母打頭的單詞，如id、num等,

特殊符號，如+、*等。任意文法符號序列：小寫希臘字母α、β、δ等。特別注意：

ε始終表示空串、空輸入。9將具有相同左部(非終結(jié)符)的產(chǎn)生式合并為一個產(chǎn)生式：其左部:仍是該非終結(jié)符，且產(chǎn)生式以此非終結(jié)符命名；右部:原來所有右部的“或”運算。E→E+E（1）

|E*E（2）

|（E）（3）(G3.2)

|-E（4）

|id（5）P:E→E+E（1）

E→E*E（2）

E→（E）（3）

E→-E（4）

E→id（5）<4>產(chǎn)生式的縮寫形式稱其為“E產(chǎn)生式”。用“|”連接的每個右部稱為一個候選項，具有平等地位。如E*E

是一個表達式，-E

也是一個表達式，且優(yōu)先級相同。3.2.1CFG的定義與表示例3.3G3.1可以重寫為如下形式：(G3.1)CFG通過推導的方法產(chǎn)生語言，即(非正式地講)：從開始符號S開始，反復使用產(chǎn)生式，將非終結(jié)符替換

為其產(chǎn)生式右部的文法符號序列(展開非終結(jié)符，用=>表示)，直到得到一個終結(jié)符序列。

10例3.4

根據(jù)G3.2產(chǎn)生-(id+id)的過程：3.2.2產(chǎn)生語言的基本方法：推導E=>E=>-E by(4)=>-(E) by(3)=>-(E+E)by(1)=>-(id+E)by(5)=>-(id+id)by(5)E→E+E（1）

|E*E（2）

|（E）（3）(G3.2)

|-E（4）

|id（5）若對于任意文法符號序列α1，α2，...，αn，有α1=>α2=>...=>αn，則稱此過程為零步或多步推導，記為α1αn

。其中:

若α1＝αn，則稱此過程為零步推導；若α1≠αn，即推導過程中至少使用一次產(chǎn)生式，則稱此過程為至少一步推導，記為

α1αn

。定義3.2用產(chǎn)生式A→γ的右部替換文法符號序列αAβ中的A得到

αγβ的過程，稱αAβ直接推導出αγβ，記為αAβ=>αγβ。11定義3.2強調(diào)了兩點：

α，有αα，即推導具有自反性；

若αβ，βγ，則αγ，即推導具有傳遞性。3.2.2產(chǎn)生語言的基本方法：推導12定義3.3

由CFGG所產(chǎn)生的語言

L(G)

被定義為:L(G)={ω┃Sωandω∈T*}，

L(G)稱為上下文無關(guān)語言(ContextFreeLanguage,CFL)，ω稱為句子。若Sα，α∈(N∪T)*

，則稱α為G的一個句型。定義3.4

在推導過程中，若每次直接推導均替換句型中

最左邊的非終結(jié)符，則稱為最左推導，由最左推導

產(chǎn)生的句型被稱為左句型?！镱愃频?，可以定義最右推導與右句型，最右推導也被稱為規(guī)范推導。3.2.2產(chǎn)生語言的基本方法：推導13E=>-E=>-(E)=>-(E+E)=>-(id+E)=>-(id+id)α1α2α3α4α5α6E→E+E（1）

|E*E（2）

|（E）（3）(G3.2)|-E（4）

|id（5）再考察-(id+id)的推導過程（這是一個最

推導）：左句型？句子？根據(jù)定義3.3可知，α6是句子，αi(i=1..6)均是句型。句型是一個相當廣泛的概念。3.2.2產(chǎn)生語言的基本方法：推導14對于推導E

-(id+id)：

E=>-E=>-(E)=>-(E+E)=>-(id+E)=>-(id+id)

它產(chǎn)生句子的過程很不直觀，看起來十分困難。

分析樹是推導的圖形表示，很直觀，并且同時反映語言結(jié)構(gòu)的實質(zhì)。3.2.3推導、分析樹與語法樹151.每一步直接推導對應一棵僅有父子關(guān)系的子樹，即產(chǎn)生式

左部非終結(jié)符“長出”右部對應的孩子；2.分析樹的全部葉子，從左到右構(gòu)成G的一個句型。特別地，若所有葉子僅由終結(jié)符和/或ε標記，則該句型就是句子。分析樹與語言和文法的關(guān)系：3.2.3推導、分析樹與語法樹定義3.5

對CFGG的句型，分析樹

被定義為具有下述性質(zhì)

的一棵樹:（1）根由開始符號標記；（2）每個內(nèi)部結(jié)點由一個非終結(jié)符標記；（3）每個葉子由一個終結(jié)符、非終結(jié)符、或ε標記；（4）若一個父結(jié)點由非終結(jié)符Ａ標記，且其孩子從左到右依次由X1,X2,...,Xn標記，則A→X1X2...Xn是一個產(chǎn)生式。若A僅有一個標記為ε的孩子，則A→ε是G的一個產(chǎn)生式。16E→E+E（1）

|E*E（2）

|（E）（3）(G3.2)|-E（4）

|id（5）E=>-E=>-(E)=>-(E+E)=>-(id+E)=>-(id+id)

用分析樹表示如下：最左推導和最右推導的中間過程對應的分析樹可能不同，因為句型不同：-(id+E)

或

-(E+id)

但是最終的分析樹相同，因為最終是同一個句子-(id+id)

例3.5

再考察-(id+id)的推導過程。

分析樹既反映了產(chǎn)生句型的推導過程，又反映了句型的結(jié)構(gòu)。idE-E(E)E+E最右推導：=>-(E+id)=>-(id+id)

α1α2α3α4α5α63.2.3推導、分析樹與語法樹二義17定義3.6

表達式的

語法樹

被定義為具有下述性質(zhì)的樹:（1）

根與內(nèi)部結(jié)點由表達式中的操作符標記；（2）

葉子由表達式中的基本操作數(shù)標記；（3）用于改變運算次序的括弧被隱含在語法樹的結(jié)構(gòu)中。1+21*(2+3)3.2.3推導、分析樹與語法樹18例3.6

句子-(id+id)和句型ifCthens1elses23.2.3推導、分析樹與語法樹1+21*(2+3)19例3.6

句子-(id+id)和句型ifCthens1elses2因為語法樹中忽略了推導過程，所以也被稱為抽象語法樹(AST)，而分析樹也被稱為具體語法樹。3.2.3推導、分析樹與語法樹語法樹與分析樹的最根本區(qū)別是非葉子結(jié)點的標記：分析樹：非葉子結(jié)點由非終結(jié)符標記；左部非終結(jié)符“長出”右部符號對應的孩子。語法樹：非葉子結(jié)點由操作符（終結(jié)符）標記。操作符“作用于”操作數(shù)。20定義3.1CFG定義3.2

直接推導、

零或多步推導、

至少一步推導定義3.3CFL、句子、句型定義3.4

最左(右)推導、左(右)句型定義3.5

分析樹定義3.6

語法樹重要概念21上節(jié)：句子-(id+id)的兩棵分析樹相同。問題：是否任何一個句子的分析樹只有一棵？E→E+E|E*E|（E）|-E|id(G3.2)*優(yōu)先級高+優(yōu)先級高+左結(jié)合+右結(jié)合EE+EE*EidididEE*EE+EidididEE+EE+EidididEE+EE+Eididid下頁(1)(2)(3)(4)(5)3.2.4.1二義性（歧義，Ambiguity）3.2.4二義性與二義性的消除例3.7

句子id+id*id和id+id+id可能的分析樹：22定義3.7

若文法G對同一句子產(chǎn)生不止一棵分析樹，則稱

文法G是二義的。二義的本質(zhì)：在產(chǎn)生句子的過程中，某些直接推導有

多于一種選擇。如上例3.7中，id+id*id的第一步直接推導。3.2.4二義性與二義性的消除對比例3.5和例3.7可知：1.句型的分析樹是否多于一棵與推導方法無關(guān)；僅與文法&句型有關(guān)。2.造成二義性的

根本原因文法中缺少對文法符號優(yōu)先級和結(jié)合性的規(guī)定。23例3.8

條件語句if(x<3)if(x>0)x=5elsex=-5根據(jù)產(chǎn)生式(2)，有if(x<3)if(x>0)x=5

elsex=-5else與離它遠的if匹配“懸空（dangling）else”問題S→if(C)S (1)|if(C)SelseS (2)|id=E (3)(G3.3)C→E==E|E<E|E>E (4)~(6)E→E+E|-E|id|n (7)~(10)24根據(jù)產(chǎn)生式(1)，有if(x<3)if(x>0)x=5elsex=-5程序設(shè)計語言不能二義的！else與離它近的if匹配S→if(C)S (1)|if(C)SelseS (2)|id=E (3)(G3.3)C→E==E|E<E|E>E (4)~(6)E→E+E|-E|id|n (7)~(10)例3.8

條件語句if(x<3)if(x>0)x=5elsex=-5“懸空（dangling）else”問題25消除文法二義的兩種方法：①改寫二義文法為非二義文法；②規(guī)定文法符號的優(yōu)先級和結(jié)合

性，使僅產(chǎn)生一棵分析樹。<1>改寫二義文法為非二義文法再推導id+id*id和id+id+id：例3.9

與G3.2等價的非二義文法:

E→E+T|T T→T*F|F(G3.4)F→（E）|-F|id問題：如何將二義文法改寫為非二義文法？E→E+E|E*E|（E）(G3.2)|-E|idEE+TT*FFidTFidid3.2.4.2二義性的消除26二義文法G3.2的分析樹文法G3.4的分析樹句子id+id+id的分析樹<1>改寫二義文法為非二義文法可以看出G3.4的特點1.引入新的非終結(jié)符，限制了每一步直接推導均有唯一選擇；2.最終分析樹的形狀，與推導方法無關(guān)，而與文法&句子有關(guān)；3.新非終結(jié)符的引入，增加了推導步驟（分析樹增高）；與G3.2等價的非二義文法:

E→E+T|TT→T*F|FF→（E）|-F|id(文法G3.4)27<1>改寫二義文法為非二義文法可以看出G3.4的特點1.引入新的非終結(jié)符，限制了每一步直接推導均有唯一選擇；2.最終分析樹的形狀，與推導方法無關(guān)，而與文法&句子有關(guān)；3.新非終結(jié)符的引入，增加了推導步驟（分析樹增高）；4.越接近S的文法符號X，其優(yōu)先級越低；5.對于A→αAβ，若β中包含終結(jié)符a(即A在a的左邊)，則a

具有左結(jié)合性質(zhì);若α中包含a，則a具有右結(jié)合性質(zhì)。文法G3.4的分析樹1.引入新的非終結(jié)符，限制了每一步直接推導均有唯一選擇；2.最終分析樹的形狀，與推導方法無關(guān)，而與文法&句子有關(guān)；3.新非終結(jié)符的引入，增加了推導步驟（分析樹增高）；4.越接近S的文法符號X，其優(yōu)先級越低；5.對于A→αAβ，若β中包含終結(jié)符a(即A在a的左邊)，則a

具有左結(jié)合性質(zhì);若α中包含a，則a具有右結(jié)合性質(zhì)。28可以看出G3.4的特點<1>改寫二義文法為非二義文法與G3.2等價的非二義文法:

E→E+T|TT→T*F|FF→（E）|-F|id(文法G3.4)改寫二義文法的關(guān)鍵步驟：1.引入一個新的非終結(jié)符，增加一個子結(jié)構(gòu)并提高一級優(yōu)先級；2.遞歸非終結(jié)符在終結(jié)符左邊，使該終結(jié)符具有左結(jié)合性，反之具有右結(jié)合性。29改寫二義文法的關(guān)鍵步驟：1.引入一個新的非終結(jié)符，增加一個子結(jié)構(gòu)并提高一級優(yōu)先級；2.遞歸非終結(jié)符在終結(jié)符左邊，使該終結(jié)符具有左結(jié)合性，反之具有右結(jié)合性。例3.9

改寫二義文法G3.2為G3.4E→E+E|E*E|（E）(G3.2)|-E|id1.優(yōu)先級：{+}<{*}<{(),-,id}2.非終結(jié)符與運算：E:+ T:* F:-,(),id（E產(chǎn)生式，左遞歸）（T產(chǎn)生式，左遞歸）（F產(chǎn)生式，右遞歸）3.結(jié)合性：左結(jié)合:+,*

右結(jié)合:-

無結(jié)合:

id()E→E+T|TT→T*F|FF→-F|(E)|id<1>改寫二義文法為非二義文法30一般原則：else與(其左邊)最近的if匹配，即右結(jié)合。改寫文法的關(guān)鍵：是將S分為完全匹配（MS）和不完全匹配(UMS)兩類，并且在UMS中規(guī)定else右結(jié)合。S→if(C)S|if(C)SelseS|id=E(G3.3)C→E==E|E<E|E>EE→E+E|-E|id|nS→MS (1)|UMS (2)MS→if(C)MSelseMS(3)|id=E (4)UMS→if(C)S (5)|if(C)MSelseUMS(6)

(G3.5)再討論“懸空else”問題E→E+T|T (10)~(11)T→-T|id|n (12)~(14)C→E==E|E<E|E>E(7)~(9)<1>改寫二義文法為非二義文法31if(x<3)if(x>0)x=5elsex=-5S→MS (1)|UMS (2)MS→if(C)MSelseMS(3)|id=E (4)UMS→if(C)S (5)(G3.5)|if(C)MSelseUMS(6) C→E==E|E<E|E>E(7)~(9)E→E+T|T (10)~(11)T→-T|id|n (12)~(14)<1>改寫二義文法為非二義文法32S→MS (1)|UMS (2)MS→if(C)MSelseMS (3)|id=E (4)UMS→if(C)S (5)(G3.5)|if(C)MSelseUMS (6) if(x<3)if(x>0)x=5else x=-5不可能！<1>改寫二義文法為非二義文法不可行！不可行！33對于：id+id*id

為二義文法規(guī)定優(yōu)先級和結(jié)合性（YACC的方法）：

E:E'+'E|E'*'E|'-'E|'('E')'|idE→E+E|E*E|-E|(E)|idE→E+T|T T→T*F|FF→(E)|-F|id%left'+'%left'*'%right'-'二義文法的優(yōu)點：①比非二義文法容易理解；②分析效率高（分析樹低，直接推導步驟少）。<2>為文法符號規(guī)定優(yōu)先級和結(jié)合性34if x<3then ifx>0 thenx:=5;

endif;elsex:=-5;endif;②給表達式加括號。如Pascal中關(guān)系運算和算術(shù)運算：

(a+b)>(c*d)

①明確給出結(jié)束標志。如Ada中用endif，于是有：if x<3then ifx>0 thenx:=5; elsex:=-5;

endif;endif;ifx<3thenifx>0thenx:=5;endif;elsex:=-5;endif;ifx<3thenifx>0thenx:=5;elsex:=-5;endif;

endif;3.2.4.2二義性的消除<3>修改語言的語法（表現(xiàn)形式被改變）35文法的重要作用：1.給出精確、易于理解的語言結(jié)構(gòu)說明；2.以文法為基礎(chǔ)的語言，便于加入新的、或修改、刪除舊的語言結(jié)構(gòu)；3.有些類別的文法，可以自動生成高效的分析器。

本節(jié)從理論的角度對文法進行簡單地討論。討論建立在形式語言與自動機的理論之上，且僅引用結(jié)論而忽略數(shù)學的證明，有興趣的同學可以查閱相關(guān)文獻。希望通過本節(jié)的討論，對文法的分類和它們在編譯器構(gòu)造中的作用有一定的了解。3.3語言與文法簡介36推論3.1

正規(guī)式所描述的語言均可用CFG描述，反之不一定。從正規(guī)式到CFG的構(gòu)造方法：1.構(gòu)造正規(guī)式的NFA；2.對于每個狀態(tài)i，均引入非終結(jié)符Ai。(初態(tài)對應于開始符號）3.對于move(i,a)=j，引入產(chǎn)生式Ai→aAj；4.對于move(i,ε)=j，引入產(chǎn)生式

Ai→Aj；5.若i是終態(tài)，則引入產(chǎn)生式Ai→ε。例3.11

從正規(guī)式(a|b)*abb的NFA構(gòu)造CFG：

A0→A1→A2→A3→經(jīng)驗的方法：A→HTT→abbH→ε|aH|bHabb的分析樹：aA0bA2bA3ε|bA0|aA1<1>正規(guī)式到CFG的轉(zhuǎn)換3.3.1正規(guī)式與上下文無關(guān)文法371.詞法規(guī)則簡單，用正規(guī)式描述足矣；2.正規(guī)式的表示比CFG更直觀、簡潔、易于理解；3.有限自動機的構(gòu)造比下推自動機簡單，且分析效率高；4.區(qū)分詞法和語法，為編譯器前端的模塊劃分提供方便。貫穿詞法分析和語法分析始終的思想：3.3.1正規(guī)式與上下文無關(guān)文法<2>為什么用正規(guī)式而不用CFG描述詞法1.語言的描述、語言的識別是表示一個語言的兩個不同側(cè)面，二者缺一不可；2.用正規(guī)式和CFG描述的語言，對應的識別方法（自動機）不同；3.一般情況下，正規(guī)式適合描述線性結(jié)構(gòu)，CFG適合描述具有嵌套（層次）性質(zhì)的非線性結(jié)構(gòu)。38程序設(shè)計語言中除了CFG可以描述的結(jié)構(gòu)之外，還有一些是CFG無法描述的所謂上下文有關(guān)的結(jié)構(gòu)。其中比較典型的結(jié)構(gòu)如：

變量的聲明與引用必須一致；過程調(diào)用時實參與形參的個數(shù)＆類型必須一致。描述它們的文法是上下文有關(guān)文法（ContextSensitiveGrammar,CSG）。3.3.2上下文有關(guān)文法（CSG）3.3.2上下文有關(guān)文法(CSG)39L1={ωcω|ω∈(a|b)*} (標識符聲明與引用一致性的抽象)L2={anbmcndm|n≥1和m≥1} (形參與實參一致性的抽象)L3={anbncn|n≥1}

(計數(shù)問題的抽象)結(jié)構(gòu)相近的CFL：L1'={ωcωr|ω∈(a|b)*}L2'={anbmcmdn|n≥1,m≥1}L2''={anbncmdm|n≥1,m≥1}L3'={ambmcn|m,n≥1}L3''={akbmcn|k，m，n≥1}CFG：S→aSa|bSb|cS→aSd|aAdA→bAc|bcS→ABA→aAb|abB→cBd|cdS→ACA→aAb|abC→cC|ca+b+c+例3.12

不能用CFG描述的語言：3.3.2上下文有關(guān)文法(CSG)正規(guī)集教材【例3.14】給出了L3''的CFG40對0型文法施加以下第i條限制，即得到i型文法。G的任何產(chǎn)生式α→β（S→ε除外）滿足|α|≤|β|；G的任何產(chǎn)生式形如A→β，其中A∈N，β∈(N∪T)*；G的任何產(chǎn)生式形如A→a或者A→aB(或者A→Ba)，

其中A∈N，B∈N，a∈T。文法語言自動機短語文法(０型)短語結(jié)構(gòu)語言圖靈機ＣＳＧ(１型)ＣＳＬ線性界線自動機ＣＦＧ(２型)ＣＦＬ下推自動機正規(guī)文法(３型)正規(guī)集有限自動機定義3.8

若文法G=(T，N，S，P)的每個產(chǎn)生式α→β中，均有(1)α∈(N∪T)*，且至少含有一個非終結(jié)符，

(2)β∈(N∪T)*，則稱G為0型文法。3.3.3形式語言與自動機簡介41結(jié)論：文法的描述能力(從左到右)依次遞減但是：能力越強的文法，其文法的設(shè)計和自動機的構(gòu)造越困難因此：語法分析僅用到CFG（除特別指出，文法即指CFG）文法0型文法CSGCFG正規(guī)文法語言0型語言CSLCFL正規(guī)集思考：這4種文法(4語言)之間是否存在子集-超集關(guān)系？

若存在，誰是誰的子集/超集？3.3.3形式語言與自動機簡介第3章語法分析(2)計算機科學與技術(shù)學院國家示范性軟件學院3.4~3.5語法分析43本課程討論的§3.4§3.5直接編碼型表驅(qū)動型表驅(qū)動型3.4自上而下語法分析44一般方法左遞歸及其消除左因子及其提取FIRST集合、FOLLOW集合遞歸下降的預測分析：工作原理構(gòu)造方法非遞歸的預測分析：工作原理分析表的結(jié)構(gòu)、構(gòu)造方法LL(1)文法/語言/分析器3.4自上而下語法分析453.4.1自上而下分析的一般方法基本思想——推導：對于任何一個輸入序列（記號流），從S開始反復進行最左推導，直到得到一個合法句子或發(fā)現(xiàn)一個非法結(jié)構(gòu)。特點：推導過程中，從左到右掃描輸入序列，并試圖用一切可能的方法，自上而下、自左向右地建立輸入的分析樹。自上而下分析是一種試探的過程，是反復使用不同產(chǎn)生式謀求與輸入序列匹配的過程。3.4自上而下語法分析46例3.16

用下述文法分析輸入序列：cadS→cAdA→ab|a問題：若有A→αβ1|αβ2，(公共左因子)，則會虛假匹配和大量回溯；造成分析效率低、語義動作難以恢復、以及出錯位置的報告不確切等。若有A→Aα，(左遞歸)，則會陷入死循環(huán)，使分析無法進行下去。重寫文法：消除左遞歸，以避免陷入死循環(huán)。提取左因子，以避免回溯。X3.4.2消除左遞歸47定義3.9若文法G中的非終結(jié)符A，對某個文法符號序列α存在推導

AAα，則稱

G是左遞歸的。若G中有形如A→Aα的產(chǎn)生式，則稱“該產(chǎn)生式對A直接左遞歸”。<1>消除文法的直接左遞歸替換為：βα*考慮：A→Aα|β

產(chǎn)生的語言：A→βA'A'→αA'|ε

消除了直接左遞歸<1>消除文法的直接左遞歸48A→Aα1|Aα2|...|Aαm|β1|β2|...|βn算法3.1

消除直接左遞歸A→β1

A'|β2

A'|...|βn

A'A'→α1

A'|α2

A'|...|αm

A'|ε輸入有直接左遞歸的文法G輸出

等價的、不含直接左遞歸的G'方法

對于每個有直接左遞歸的非終結(jié)符A

應用下述方法。

(1)整理A的全部產(chǎn)生式為如下形式：其中αi均非空，βj均不以A開始。對比：A→βA'

A'→αA'|εA→Aα|β(2)用下述產(chǎn)生式代替原先的A產(chǎn)生式：<1>消除文法的直接左遞歸49例3.17

用算法3.1消除算術(shù)表達式文法的直接左遞歸：消除直接左遞歸的結(jié)果：E→TE' (1)E'→+TE'|ε(2)(G3.4')T→FT'(3)T'→*FT'|ε(4)F→(E)|-F|id(5)..(7)E→E+T|TT→T*F|F(G3.4)F→(E)|-F|id算法3.1:替換：A→Aα|β

為：A→βA'A'→αA'|ε關(guān)鍵：將實際的符號序列對應到A、α和β具體到E產(chǎn)生式：

E→E+T|TAAα

β<1>消除文法的直接左遞歸50

分析輸入序列：id+id*idE→E+T|TT→T*F|FF→(E)|-F|id(G3.4)E→TE' (1)E'→+TE'|ε(2)T→FT'(3)T'→*FT'|ε(4)F→(E)|-F|id(5)..(7)(G3.4')E→E+E|E*E|(E)|-E|id(G3.2)<2>消除文法的左遞歸51文法：S→Aa|bA→Ac|Sd|ε因為：S=>Aa=>Sda所以：S左遞歸(不是直接左遞歸)核心思想：將無直接左遞歸的非終結(jié)符展開到其他產(chǎn)生式中。for(i=1;i<=n;++i）{}算法3.2

消除左遞歸輸入無回路文法G輸出

無左遞歸的等價文法G'方法首先，將非終結(jié)符合理排序：A1，A2，...，An。for(

j=1;j<=i-1;++j){}消除Ai產(chǎn)生式中的直接左遞歸;對每個形如Ai→Ajγ產(chǎn)生式中的Aj用

Aj→δ1|δ2|...|δk的右部替換,得到新產(chǎn)生式Ai→δ1γ|δ2γ|...|δkγ<2>消除文法的左遞歸52例3.18

消除文法S→Aa|bA→Ac|Sd|ε中的左遞歸。關(guān)鍵步驟：合理排序非終結(jié)符：A1，A2，...，An;用Aj→δ1|δ2|...|δk右部

替換Ai→Ajγ中的Aj

得到Ai→δ1γ|δ2γ|...|δkγ;

消除Ai產(chǎn)生式中的直接左遞歸。①S產(chǎn)生式?jīng)]有直接左遞歸，跳過；②將S的右部展開在A中，得到：

A→Ac|Aad|bd|ε②消除新產(chǎn)生式中的直接左遞歸，得到：S→Aa|bA→算法3.1:替換：A→Aα|β

為：

A→βA'

A'→αA'|εbd|εAc|Aad一種排序：S,AA→bdA'|A'A'→cA'|adA'|ε3.4.3提取左因子53當難以確定用A產(chǎn)生式的哪個候選項替換A時，可以改寫A產(chǎn)生式來推遲這種決定，直到看見足夠的輸入，能正確決定所需選擇為止。這一過程被稱為提取左因子。（類似于FA的確定化）公共左因子(前綴)：A→αβ1|αβ2將：(對照算術(shù)表達式的提取公因式)A→αA'替換為：A→αβ1|αβ2A'→β1|β23.4.3提取左因子54算法3.3

提取文法的左因子輸入

文法G輸出

等價的無左因子文法G'方法對于每個有左因子的非終結(jié)符A，應用下述方法。例3.20

考察簡化的懸空else文法：

S→i(C)S

|i(C)SeS|aC→b提取左因子，得到如下文法：Q:既有左遞歸又含左因子？A:先消除左遞歸。（為什么？試試

例3.19）S→i(C)SS'|aS'→ε|eSC→b將： A→αβ1|αβ2改為：A→αA' A'→β1|β2(1)重排A產(chǎn)生式：A→αβ1|αβ2|...|αβn

|γ1|...|γm(2)將上述A產(chǎn)生式替換為：A→αA'

|γ1|...|γmA'→β1|β2|...|βn☆重復該過程，直到所有A、A'的候選項中不再有任何左因子。3.4.4FIRST,FOLLOW55定義3.11

非終結(jié)符A的FOLLOW集合為:FOLLOW(A)

={a|S…Aa…，a∈T}，☆若A是某句型的最右符號，則

#∈FOLLOW（A）。例如：FIRST(E)={} FOLLOW(E)={}定義3.10

文法符號序列α的FIRST集合為:

FIRST(α)={a|α

a…，a∈T}，☆若αε，則ε∈FIRST(α)。FOLLOW算法L→E;L|εG3.9'E→TE'E'→+TE'|-TE'|εT→FT'T'→*FT'|/FT'|modFT'|εF→(E)|id|num(idnum；)分析表構(gòu)造3.4.4FIRST,FOLLOW56算法3.4

計算X的FIRST集合輸入

文法符號X輸出

X的FIRST集合方法

應用下述規(guī)則：(1)若X∈T，則FIRST(X)={X}。(2)若X∈N，且有X→ε，則加入ε到FIRST(X)。(3)若X∈N，且有X→Y1Y2…Yn

(n≥1)，則運用下述過程：for(j=1;j<=n;++j){FIRST(X)∪＝(FIRST(Yj)–{ε})if(ε

∈FIRST(Yj))continue;elsebreak;}if(j>n)

FIRST(X)∪＝

{ε};//每個Yj均可推導出ε，//所以X可推導出ε//依次掃描Y1,Y2,…//X可推導出Yj+1Yj+2…Yn//X推導不出Yj+1Yj+2…Yn規(guī)則(3)也指出：如何計算任意文法符號序列的FIRST集合。并集3.4.4FIRST,FOLLOW57例3.21

計算全體非終結(jié)符的FIRST。提示：自下而上計算FIRST。L→E;L|εG3.9'E→TE'E'→+TE'|-TE'|εT→FT'T'→*FT'|/FT'|modFT'|εF→(E)|id|numFIRST(F)=建議的計算順序：FIRST(F)FIRST(T')FIRST(T)FIRST(E')FIRST(E)FIRST(L)FIRST((E))∪FIRST(id)∪FIRST(num)={}(for(j=1;j<=n;++j){FIRST(X)∪＝(FIRST(Yj)–{ε})if(ε

∈FIRST(Yj))continue;elsebreak;}if(j>n)

FIRST(X)∪＝

{ε};idnum3.4.4FIRST,FOLLOW58例3.21

計算全體非終結(jié)符的FIRST。提示：自下而上計算FIRST。L→E;L|εG3.9'E→TE'E'→+TE'|-TE'|εT→FT'T'→*FT'|/FT'|modFT'|εF→(E)|id|numFIRST(F)=FIRST((E))∪FIRST(id)∪FIRST(num)={}(idnumFIRST(T')=FIRST(*FT')∪FIRST(modFT')={}*/modε∪FIRST(/FT')∪FIRST(ε)3.4.4FIRST,FOLLOW59例3.21

計算全體非終結(jié)符的FIRST。提示：自下而上計算FIRST。L→E;L|εG3.9'E→TE'E'→+TE'|-TE'|εT→FT'T'→*FT'|/FT'|modFT'|εF→(E)|id|num★★★請大家自己計算：FIRST(E')FIRST(E)FIRST(L)請自學

例3.22!!!

{}(idnumFIRST(T')={}*/modεFIRST(T)=FIRST(FT')={}(idnumfor(j=1;j<=n;++j){FIRST(X)∪＝(FIRST(Yj)–{ε})if(ε

∈FIRST(Yj))continue;elsebreak;}if(j>n)

FIRST(X)∪＝

{ε};FIRST(F)=3.4.4FIRST,FOLLOW60算法3.5

計算所有非終結(jié)符的FOLLOW集合輸入

文法G輸出

G中所有非終結(jié)符的FOLLOW集合方法

應用下述規(guī)則:規(guī)則3的理解：若SδAa… a緊跟A之后

則=>δαBa… a也緊跟B之后（A→αB）或者=>δαBβa…δαBa…（A→αBβ）

【若ε∈FIRST(β)】加入#到FOLLOW(S)。若有產(chǎn)生式A→αBβ，則將FIRST(β)的所有非ε元素

加入到FOLLOW(B)。若有產(chǎn)生式A→αB

或A→αBβ且ε∈FIRST(β)，

則把

FOLLOW(A)

的全體加入到

FOLLOW(B)。FOLLOW定義例3.233.4.4FIRST,FOLLOW61例3.23

計算非終結(jié)符的FOLLOW。提示：自上而下計算FOLLOW.FOLLOW(L)=FOLL0W(E)=FOLLOW(E')=FOLLOW(T)=FOLLOW(T')=FOLLOW(F)={#}{

}{;)}{}{+

-

;)}{*

/

mod

};)+

-

;)

;)+

-L→E;L|εG3.9'E→TE'E'→+TE'|-TE'|εT→FT'T'→*FT'|/FT'|modFT'|εF→(E)|id|numFIRST(F)=例3.21FIRST(T')=FIRST(T)=FIRST(E')=FIRST(E)=FIRST(L)={(idnum}{*

/

modε}{+

-ε}{(idnum}{(idnum}{(idnumε}FOLLOW算法3.4.5遞歸下降的預測分析62本質(zhì)：以程序中的過程調(diào)用來模擬最左推導?；舅枷耄?.子程序是遞歸的（因為文法是遞歸的）。2.程序與文法（直接）相關(guān)。3.其編寫方法是非形式化的，只要能寫出子程序，用什么樣的方法和步驟均可。4.其中的預測分析法：它對文法的限制是不能有公共左因子和左遞歸、無二義。每個非終結(jié)符A對應一個子程序（過程），過程體是將A產(chǎn)生式展開所得：多個候選項：展開為分支結(jié)構(gòu)；右部的非終結(jié)符B：調(diào)用B的子程序；右部的終結(jié)符

T：與輸入記號進行匹配。特點：3.4.5遞歸下降的預測分析63消除左遞歸后的等價文法:

L→E;L|εE→TE'E'→+TE'|-TE'|εG3.9'T→FT'T'→*FT'|/FT'|modFT'|εF→(E)|id|num<1>構(gòu)造狀態(tài)轉(zhuǎn)換圖且化簡構(gòu)造文法的狀態(tài)轉(zhuǎn)換圖并且化簡；將轉(zhuǎn)換圖轉(zhuǎn)化為EBNF形式的文法；根據(jù)EBNF文法構(gòu)造子程序。EBNF表示穩(wěn)妥的方法：每個非終結(jié)符對應一個狀態(tài)轉(zhuǎn)換圖。先構(gòu)造轉(zhuǎn)換圖，后化簡。<1>構(gòu)造狀態(tài)轉(zhuǎn)換圖且化簡64L→E;L|εE→TE'E'→+TE'|-TE'|εT→FT'T'→*FT'|/FT'|modFT'|εF→(E)|id|numL:3012E；Lε（1）構(gòu)造狀態(tài)轉(zhuǎn)換圖①為非終結(jié)符A建立一個初態(tài)和一個終態(tài)；②為A→X1X2...Xn構(gòu)造從初態(tài)到終態(tài)的路徑，

邊上標記依次為X1、X2、...、Xn。<1>構(gòu)造狀態(tài)轉(zhuǎn)換圖且化簡65（2）化簡，方法如下：①標記為A的邊可等價為標記ε的邊

轉(zhuǎn)向A轉(zhuǎn)換圖的初態(tài)。②ε連接的兩個狀態(tài)可以合并。③不可區(qū)分的狀態(tài)可以合并。化簡前E,E'的狀態(tài)圖：1.合并不可區(qū)分的狀態(tài)：3.合并ε連接的節(jié)點：4.將E'的轉(zhuǎn)換圖代入E：5.合并ε連接的節(jié)點：6.合并不可區(qū)分的狀態(tài)：2.轉(zhuǎn)向E'的初態(tài)：<2>文法的擴展表示形式66最終化簡的轉(zhuǎn)換圖：①閉包：

s+,s*環(huán)

循環(huán)②可缺?。簊?

if③多選一：s1|s2|…if/switch④()：改變運算順序。將狀態(tài)圖轉(zhuǎn)換為EBNF文法：L→(E;

)*E→T(

(+|-)T)*T→F(

('*'

|/|mod)F)*F→'('E')'|id|num

文法G3.9'G3.9''<2>文法的擴展表示形式--EBNF<3>遞歸下降子程序67if(select_alt(lookahead,A,α1)){展開

α1

}

elseif(select_alt(lookahead,A,α2)){展開

α2}…

elseif(select_alt(lookahead,A,αn

)){展開αn

}else{錯誤處理

}產(chǎn)生式展開為過程體的參考方法：

若A產(chǎn)生式為：A→α1?|?α2?|?…?|?αn設(shè)：變量lookahead保存下一輸入終結(jié)符，boolselect_alt(lookahead,A,αk){if(lookahead∈FIRST(αk))returntrue;if(ε∈FIRST(αk)andlookahead∈FOLLOW(A))returntrue;returnfalse;}若αi為ε，則展開為空語句<3>遞歸下降子程序68L→(E;

)*E→T(

(+|-)T)*T→F(

('*'|/|mod)F)*F→'('E')'|id|num

G3.9''voidparser_main(){//分析器入口函數(shù)lookahead=nextToken();//

取第一個記號L();//

調(diào)用開始符號的子程序，即開始推導

//

當調(diào)用返回后，語法分析結(jié)束}voidL(){//

展開非終結(jié)符L

//

遇到輸入結(jié)束時，函數(shù)返回while(lookahead!=EOF){E();//

調(diào)用E的子程序，即推導Ematch(SEMICO);}}請精讀完整的示例程序。下面是教材中示例（簡）：boolmatch(tokenKind){if(tokenKind==lookahead){lookahead=nextToken();returntrue;}error("syntaxerror1");returnfalse;}voidE(){//

展開ET();//FIRST(

(+|-)T)while(lookahead==PLUS||lookahead==MINUS){ match(lookahead);T();}}<3>遞歸下降子程序69L→(E;

)*E→T(

(+|-)T)*T→F(

('*'|/|mod)F)*F→'('E')'|id|num

G3.9''voidF(){//

展開非終結(jié)符Fswitch(lookahead){caseLP://

'('∈

FIRST(

'('E')')match(LP);E();match(RP);break;caseID:match(ID);break;caseNUM:match(NUM);break;default:error("syntaxerror2");}}請精讀完整的示例程序。下面是教材中示例（簡）：3.4.6非遞歸的預測分析70非遞歸的預測分析器的核心概念：工作方式：格局、格局變換分析表的結(jié)構(gòu)、驅(qū)動器（模擬算法）預測分析表的構(gòu)造LL(1)文法／語言／分析器3.4.6.1非遞歸的預測分析器的工作模式<1>預測分析表71L→E;L|εE→TE'E'→+TE'|-TE'|εT→FT'T'→*FT'|/FT'|modFT'|εF→(E)|id|numidnum+-*/mod();#LE;LE;LE;LεETE'TE'TE'E'+TE'-TE'εεTFT'FT'FT'T'εε*FT'/FT'modFT'εεFidnum(E)文法：G3.9'分析表(M)：構(gòu)造

M[A,a]的內(nèi)容：當前棧頂是非終結(jié)符A、當前

輸入是a時，分析器要進行的動作。<2>工作方式72從某個初始格局開始，經(jīng)過一系列的格局變化，最終到達接受格局，表明分析成功；或到達出錯格局，表明發(fā)現(xiàn)語法錯誤。格局：（棧內(nèi)容，當前剩余輸入，改變格局的動作）

*top

*ip改變格局的動作：①匹配終結(jié)符：②展開非終結(jié)符：③接受：④報錯：分析過程是格局的變化過程(播放幻燈片)：若*top=*ip(但≠#)，則pop且next(ip)。若

*top=X且

M[X,*ip]=X→α，則pop且push(α)。若*top=

*ip

=#，則分析成功并結(jié)束。其它情況，調(diào)用錯誤恢復例程。<3>驅(qū)動器算法73算法3.6

非遞歸的預測分析輸入

輸入序列ω、文法G的預測分析表M輸出

若ω∈L(G),得到ω的一個最左推導;否則指出一個錯誤方法

初始格局為:（#S，ω#，分析器的第一個動作?）令ip

指向ω#

中的第一個符號，top指向S;while(true){

x

=*top;a=*ip;}if(M[x,a]=X→Y1Y2...Yk){pop(X);

push(YkYk-1...Y2Y1);}//展開非終結(jié)符elseerror(3);//出錯：沒有可用產(chǎn)生式if(a==#)return;//

剩余輸入為空，接受elseerror(1);//

出錯：剩余輸入無效if(x==a){pop(x);next(ip);}//匹配終結(jié)符elseerror(2);//

出錯：a和x不匹配if(x==#){//

棧為空}elseif(x∈T){}else{//

x∈N}12<4>用預測分析器分析句子74idnum+-*/mod();#LE;LE;LE;LεETE'TE'TE'E'+TE'-TE'εεTFT'FT'FT'T'εε*FT'/FT'modFT'εεFidnum(E)

id+id*id;<4>用預測分析器分析句子75棧 當前剩余輸入 動作說明#L id+id*id;# pop(L),push(E;L) (L→E;L)#L;E id+id*id;# pop(E),push(TE') (E→TE')#L;E'T id+id*id;# pop(T),push(FT') (T→FT')#L;E'T'F id+id*id;# pop(F),push(id) (F→id)#L;E'T'id id+id*id;# pop(id),next(ip) id#L;E'T' +id*id;# pop(T') (T'→ε)#L;E' +id*id;# pop(E'),push(+TE') (E'→+TE')#L;E'T+ +id*id;# pop(+),next(ip)

+#L;E'T id*id;# pop(T),push(FT') (T→FT')#L;E'T'F id*id;# pop(F),push(id) (F→id)#L;E'T'id id*id;# pop(id),next(ip)

id#L;E'T' *id;# pop(T'),push(*FT') (T'→*FT')#L;E'T'F* *id;# pop(*),next(ip)

*#L;E'T'F id;# pop(F),push(id) (F→id)#L;E'T'id id;# pop(id),next(ip)

id#L;E'T' ;# pop(T') (T'→ε)#L;E' ;# pop(E') (E'→ε)#L; ;# pop(;),next(ip)

;#L # pop(L) (L→ε)# # 接受

正確結(jié)束3.4.6.2構(gòu)造預測分析表76首先計算：候選項的FIRST集合，非終結(jié)符的FOLLOW集合；然后根據(jù)兩組集合構(gòu)造預測分析表。3.4.6.2構(gòu)造預測分析表回顧：集合的定義3.4.6.2構(gòu)造預測分析表77算法3.7

構(gòu)造預測分析表輸入

文法G輸出

分析表M方法

應用下述規(guī)則：1.對文法的每個產(chǎn)生式(候選項)A→α，執(zhí)行2和3；2.對FIRST(α)的每個終結(jié)符a，加入α到M[A，a]；3.若ε∈FIRST(α)，則對FOLLOW(A)的每個元素符b，

加入α到M[A，b]；4.M中其它沒有填寫的條目均是error。M[A，a]如何指導下一步動作：1.若當前棧頂為A，當前輸入為a，則規(guī)則2表示接下來的動作是A=>αa…。

∵a∈FIRST(α),∴展開后下一次正好匹配a。2.若當前棧頂為A，當前輸入為b，則規(guī)則3表示接下來的動作是A=>αε。

∵b∈FOLLOW(A)，∴彈出A后下一次正好匹配b。

2.對FIRST(α)的每個終結(jié)符a，加入α到M[A，a]；3.若ε∈FIRST(α)，則對FOLLOW(A)每個元素b，加入α到M[A，b]；3.4.6.2構(gòu)造預測分析表78FOLLOW(L)={#}FOLL0W(E/E')={);}FOLLOW(T/T')={+-;)}idnum+-*/mod();#LEE'TT'FE;LE;LE;LL→E;L|εE→TE'E'→+TE'|-TE'|εT→FT'T'→*FT'|/FT'|modFT'|εF→(E)|id|numεFIRST(L→E;L)={(,id,num}FIRST(L→ε)={ε}……例3.23

例3.21

G3.9'2.對FIRST(α)的每個終結(jié)符a，加入α到M[A，a]；3.若ε∈FIRST(α)，則對FOLLOW(A)每個元素b，加入α到M[A，b]；3.4.6.2構(gòu)造預測分析表79FOLLOW(L)={#}FOLL0W(E/E')={);}FOLLOW(T/T')={+-;)}idnum+-*/mod();#LEE'TT'FE;LE;LE;LTE'TE'TE'L→E;L|εE→TE'E'→+TE'|-TE'|εT→FT'T'→*FT'|/FT'|modFT'|εF→(E)|id|numεFIRST(E→TE')={(,id,num}例3.23

例3.21

G3.9'2.對FIRST(α)的每個終結(jié)符a，加入α到M[A，a]；3.若ε∈FIRST(α)，則對FOLLOW(A)每個元素b，加入α到M[A，b]；3.4.6.2構(gòu)造預測分析表80FOLLOW(L)={#}FOLL0W(E/E')={);}FOLLOW(T/T')={+-;)}idnum+-*/mod();#LEE'TT'FE;LE;LE;LTE'TE'TE'+TE'-TE'L→E;L|εE→TE'E'→+TE'|-TE'|εT→FT'T'→*FT'|/FT'|modFT'|εF→(E)|id|numεεεFIRST(E'→