第3章語法分析本章要點上下文無關文法自上而下語法分析自下而上語法分析語法分析器的自動生成

語法分析器的功能語法分析器的功能：分析、判斷記號序列是否符合語法規則。詞法分析器記號取下一個記號源程序分析樹前端的其余部分語法分析器中間表示符號表3.1上下文無關文法3.1.1上下文無關文法的定義正規式能定義一些簡單的語言，能表示給定結構的固定次數的重復或者沒有指定次數的重復 例：a(ba)5,a(ba)*正規式不能用于描述配對或嵌套的結構 例1：配對括號串的集合 例2：{wcw|w是a和b的串}

可以用形式語言中的文法來描述產生式產生式(規則)是定義語法單位的一種書寫規則。它的形式為：α→β（或α::=β）

其中：“→”讀作“定義為”

α，β為符號串箭頭左邊稱為產生式左部箭頭右邊稱為產生式右部

例：S→0S1，0S→01上下文無關文法上下文無關文法G是一個四元組（VT,VN,S,P）

VT：終結符集合-通常表示語言集中不能再分割的單詞記號

VN：非終結符-表示程序語言中的語法單位，且

VN∩VT=φ

S：開始符號，至少在某個產生式左部出現一次

P：產生式集合（有限），每個產生式的形式為：

P→α，P∈VN，α∈（VN∪VT）*例：算術表達式文法({id,+,,,(,)},{expr,op},expr,P)

VT：{id,+,,,(,)}VN：{expr,op}S：exprP：{expr

expr

op

exprop+expr(expr)op

expr

exprexpr

id}

說明：為書寫方便，常把若干左部相同的產生式合并為一個，并用元語言符號“|”隔開。上例簡化表示expr

expr

op

expr |

(expr)|

expr|idop+|習慣上，常用大寫字母表示非終結符，小寫字母表示終結符。上例簡化表示E

EAE|(E)|E|idA+|例：文法G(S)

G(S)=（VT，VN，S，P）其中:

VT={a,b}VN={S,A}

P={S→bA,A→aA|a}

是上下文無關文法文法G(E):

E

EAE|0E0|a

A

b|c

也是上下文無關文法

G(S)=（VT,

VN,

S,

P)

VT:{id,

+,*,

(

,

),

}VN:{S,E,A}P:{S→id=E

EEAE|(E)|E|idA+|}

例：賦值語句的上下文無關文法描述3.1.2推導把產生式看成重寫規則，把符號串中的非終結符用其產生式右部的串來代替,這個過程在語法分析中有重要意義。例:E

E+E|E

E|(E)|

E|idE

E

(E)

(E+E)

(id+E)(id+id)顯然，(id+id)是合法的表達式概念直接推出

如果A→γ是一個產生式，而α，β∈（VT∪VN）*，則將產生式A→γ用于符號串αAβ得到符號串αγβ，記為αAβ=>αγβ，稱αAβ直接推出αγβ。

如：E=>(E),(E+E)=>(i+E)推導設α1,α2,…,αn(n>0)∈(VT∪VN)*，且有α1=>α2=>…=>αn

則稱這個序列是從α1到αn的一個推導。若存在一個α1到αn的一個推導，則稱α1可推導出αn，記為：α1=>+αn

(經一步或若干步推導）或α1=>*αn

（經0步或若干步推導）句型假定G是一個文法，S是它的開始符號，如果S=>α，則稱α是文法G的一個句型。如：(E+E),(i+E),(i+i),E都是G（E）的句型。句子僅由終結符組成的句型稱為句子。

如：(i×i+i),(i+i)都是G（E）的句子。語言文法G所產生句子的全體,即:L(G)={α|S=>+α，α∈VT*}概念最左(右)推導若某推導中任何一步直接推出α=>β都是對α中的最左（最右）非終結符進行替換，則稱其為最左（最右）推導。例:E

E+E|E

E|(E)|

E|id最左推導 E lm

Elm

(E)lm

(E

+E)

lm

(id+E)lm(id+id)最右推導（規范推導） E rm

Erm

(E)rm

(E+E)

rm

(E+id)rm(id+id)E=>(E)=>(E+E)=>(E×E+E)=>(E×E+i)。既非最右也非最左推導。3.1.3分析樹文法句型（句子）推導的樹形表示即語法分析樹，簡稱分析樹。分析樹的構造

語法分析樹是一棵根在上，葉子在下的倒立的樹，（1）根結點由開始符號標記，隨著推導的展開，向下畫一分支；（2）某個非終結符被它的某個候選式所替換時，產生下一代新結點，候選式中自左到右的每個符號作為新結點的標記；（3）每個新結點和其父結點間有一條連線。3.1.3分析樹例：E

E+E|E

E|(E)|

E|id

(id+id)的分析樹EE()EEE+idid在一棵語法樹生長過程中的任何時刻，所有那些沒有后代的端末結點自左到右排列起來就是一個句型。3.1.4二義性

例：E

E+E|E

E|(E)|

E|id

句子idid+id的最左推導如下

E

E

E

E

E+E idE

E

E+E

id

E+E id

E+E

idid+E idid+E idid+id idid+idEEE*+EEidididEEidE*+EEidid如果一個文法存在某個句子對應兩棵不同的語法樹,則稱這個文法是二義的。文法二義不代表語言一定是二義的。當產生一個語言的所有文法都是二義時,這個語言才稱為二義的。有些語法分析器希望處理的文法是無二義的，則要構造無二義文法；出于某些需要，也可以構造允許二義文法的分析器，不過文法要附帶消除二義性的規則。如對文法G(E)，規定“*”的優先級高于“+”，并服從左結合，文法改寫為 E→T|E+T

T→F|T*F

F→(E)|id是無二義性的。文法的二義性3.2語言和文法文法的優點

文法給出了精確的，易于理解的語法說明自動產生高效的分析器可以給語言定義出層次結構以文法為基礎的語言的實現便于語言的修改文法的問題文法能描述編程語言的大部分語法，但不是所有。3.2.1

正規式和上下文無關文法的比較正規式可以描述的語言都能用上下文無關文法描述，通過NFA可以變換出相應文法。正規式(a|b)*ab文法A0

a

A0|bA0|a

A1A1

b

A2A2

12開始a0abb3.2.2分離詞法分析器理由為什么要用正規式定義詞法

詞法規則非常簡單，不必用上下文無關文法對于詞法記號，正規式描述簡潔且易于理解從正規式構造出的詞法分析器效率高從軟件工程角度看，詞法分析和語法分析的分離有如下好處簡化詞法分析器設計，改進編譯器的效率編譯器的可移植性加強便于編譯器前端的模塊劃分3.2.3驗證文法產生的語言例：G:S

(S)S|L(G)：配對的括號串的集合按推導步數進行歸納：推出的是配對括號串歸納基礎：S

歸納假設：少于n步的推導都產生配對的括號串歸納步驟：n步的最左推導如下：

S(S)S*(x)S*(x)y3.2.3驗證文法產生的語言例：G:S

(S)S|L(G)：配對的括號串的集合按串長進行歸納：配對括號串可由S推出歸納基礎：S

歸納假設：長度小于2n的都可以從S推導出來歸納步驟：考慮長度為2n(n

1)的w=(x)y

S(S)S*(x)S*(x)y3.2.4適當的表達式文法

用一種層次觀點看待表達式

idid(id+id)+idid+id

id

id

(id+id)

文法 expr

expr+term|term term

term

factor|factor

factor

id|(expr)expr

expr+term|termterm

term

factor|factor

factor

id|(expr)expridtermfactorididterm*termfactorfactor*exprexpr+idfactortermididterm*termfactorfactorid+idid分析樹

ididid分析樹

3.2.4適當的表達式文法

3.2.5消除二義性stmt

ifexprthenstmt |ifexprthenstmtelsestmt |other句型：ifexprthenifexprthenstmt

elsestmt兩個最左推導：

stmtifexprthenstmt

ifexprthenifexprthenstmtelsestmt

stmtifexprthenstmtelsestmt

ifexprthenifexprthenstmt

elsestmt

無二義的文法stmt

matched_stmt

|unmatched_stmtmatched_stmt

ifexprthenmatched_stmt

elsematched_stmt

|otherunmatched_stmt

ifexprthenstmt |ifexprthenmatched_stmt

elseunmatched_stmt3.2.5消除二義性3.2.6形式語言鳥瞰文法G=(VT

,VN,S,P)0型文法：，,(VNVT)*,||13.2.6形式語言鳥瞰文法G=(VT

,VN,S,P)0型文法：，,(VNVT)*,||1短語文法3.2.6形式語言鳥瞰文法G=(VT

,VN,S,P)0型文法：，,(VNVT)*,||11型文法：||||，但S可以例外短語文法3.2.6形式語言鳥瞰文法G=(VT

,VN,S,P)0型文法：，,(VNVT)*,||11型文法：||||，但S可以例外短語文法、上下文有關文法3.2.6形式語言鳥瞰文法G=(VT

,VN,S,P)0型文法：，,(VNVT)*,||11型文法：||||，但S可以例外2型文法：A，AVN,(VN∪VT)*短語文法、上下文有關文法3.2.6形式語言鳥瞰文法G=(VT

,VN,S,P)0型文法：，,(VNVT)*,||11型文法：||||，但S可以例外2型文法：A，AVN,(VN∪VT)*短語文法、上下文有關文法、上下文無關文法3.2.6形式語言鳥瞰文法G=(VT

,VN,S,P)0型文法：，,(VNVT)*,||11型文法：||||，但S可以例外2型文法：A，AVN,(VN∪VT)*3型文法：AaB或Aa，A,BVN,aVT

短語文法、上下文有關文法、上下文無關文法3.2.6形式語言鳥瞰文法G=(VT

,VN,S,P)0型文法：，,(VNVT)*,||11型文法：||||，但S可以例外2型文法：A，AVN,(VN∪VT)*3型文法：AaB或Aa，A,BVN,aVT

短語文法、上下文有關文法、上下文無關文法、正規文法上下文有關文法舉例例 L3＝{anbncn|n1}的上下文有關文法S

aSBC

S

aBC

CB

BCaB

ab

bB

bb bC

bccC

ccanbncn的推導過程如下：S*an-1S(BC)n1 用S

aSBCn-1次S+an(BC)n 用S

aBC1次S+anBnCn 用CB

BC交換相鄰的CBS+anbBn1Cn 用aB

ab1次S+anbnCn 用bB

bbn-1次S+anbncCn-1 用bC

bc1次S+anbncn 用cC

cc

n-1次3.3自上而下分析3.3.1自上而下分析的一般方法對任何的輸入串(單詞記號流),試圖用一切可能的辦法,從文法的開始符號出發,為輸入串尋找一個最左推導,也就是自上而下地為輸入串建立一棵語法樹。這是一種帶回溯的試探過程。

判定輸入串x*y是否為它的句子?

SxAySxAyS**用S→xAy

推導過程：S=>xAy用A→*用A→**=>x**yxAy*(成功)(回溯)(回溯)=>x*y(成功)例:文法G：S→

xAy

A→**│*

一個文法,如果存在非終結符：P=>+

Pα，稱它是含有左遞歸的。文法的左遞歸使分析過程陷入無限循環。回溯使分析走大段錯路。存在虛假匹配現象。報告分析不成功時，難于知道輸入串中出錯的確切位置。效率低，代價高，有理論意義，實踐價值不大。自上而下分析面臨的問題3.3.2LL(1)文法對于LL(1)文法，可以進行不帶回溯的自上而下的LL(1)分析。LL(1)是指從左(Left)到右掃描輸入串；構造句子的最左(Leftmost)推導；分析時每步向前看一個字符。消除左遞歸消除回溯FIRST集合,FOLLOW集合LL(1)文法LL(1)分析方法1.消除左遞歸例：

E→E+T│TT→T*F│F F→(E)│i

P→Pα│β(α≠ε，β不以P開頭)P→βP'

P'→αP’│εE→TE’E’→＋TE’│εT→FT’T’→*FT’│εF→(E)│i(1)消除直接左遞歸一般地:若P→Pα1│Pα2│…│Pαm│β1│β2│…│βn其中：αi≠ε，βi不以P開頭改寫為:P→β1P’│β2P’│...│βnP’P’→α1P’│α2P’│…│αmP’│ε(2)消除間接左遞歸例:設文法G(S)為：

S→Qc│c Q→Rb│b R→Sa│a

該文法不含直接左遞歸，但含間接左遞歸。如：S=>Qc=>Rbc=>Sabc等等解:

1）排序:R、Q、S

2）代入:Q→Sab│ab│b

S→Sabc│abc│bc│c

消除直接左遞歸:

S→abcS’│bcS’│cS’

S’→abcS’│ε

Q→Sab│ab│b

R→Sa│a

3）化簡:S→abcS’│bcS’│cS’

S’→abcS’│εG(S):

S→Qc│c

Q→Rb│b

R→Sa│a例:為文法消除間接左遞歸算法

1）排序:P1、P2、…、Pn2）FORi:=1TOnDOBEGINFORj:=1TOi-1DO

把形如Pi→Pjγ的規則改寫為：

Pi→δ1γ│δ2γ│…│δkγ

其中：Pj→δ1│δ2│…│δk

消除關于Pi規則的直接左遞歸

END3）化簡:刪除永不使用的產生式

解2:

1）排序：S、Q、R

2）代入得：S→Qc│c Q→Rb│b R→Rbca│bca|ca|a

消除直接左遞歸：

S→Qc│c Q→Rb│b R→bcaR‘│caR’|aR‘

R’→bcaR‘│εG(S):

S→Qc│c

Q→Rb│b

R→Sa│a例:為文法消除間接左遞歸在分析過程中，對任非終結符A,用它匹配輸入串時要求能夠根據當前輸入，準確地指派一個候選式,若匹配成功,則不虛假,若匹配不成功,則其它的候選式也不會成功。即當A執行匹配時,A→α1│α2│…│αn

若A面臨的第一個輸入符號為a,則應該準確地指派某一個αi,其成敗完全代表A,無需進行試探和回溯。2.消除回溯定義：符號串α的終結首符集FIRST(α)

FIRST(α)={a│α=>*a…,a∈VT}特別地，若α=>*ε，則規定ε∈FIRST(α）對文法的任一非終結符號A，A→α1│α2│…│αn，

若要準確地指派候選式，則應滿足FIRST(αi)∩FIRST(αj)=Φ，i≠j通過提取公共左因子，將文法改造成任何非終結符的所有候選首符集兩兩不相交。

設A→δβ1│δβ2│…│δβn│

γ1│γ2│…│γm

（其中γ1、

γ2、

…、

γm不以δ開頭） 改寫:

A→δB│γ1│γ2│…│γm

B→β1│β2│…│βn例1：文法G：S→aSb|aS|ε解：提取：S→aS(b|ε）

S→ε引入新符：S→aSA|ε A→b|ε 提取左因子例2：對文法G2：A→ad提左公因子

A→Bc B→aA B→bB

解：先替換為：

A→ad A→aAc A→bBc B→aA B→bB再提取A→a（Ac|d)A→bBcB→aAB→bB引入新符A→aA‘A→bBcA’→Ac|dB→aAB→bB一般地，經過反復提取左因子可把每一個非終結符的所有候選首符集變成兩兩不相交。結論當文法滿足：（1）消除了左遞歸（2）FIRST(αi)∩FIRST(αj)=Φ，i≠j）對某個輸入符號a，及待匹配的非終結符A，若a∈FIRST（αi），則對A選用αi候選式工作。這種選擇是唯一、確定和無虛假匹配的。3.

LL(1)文法當文法滿足以上兩個條件，但對任意αi，a都不屬于FIRST（αi）時，該如何選擇A的候選式，或者就認為a的出現是一種語法錯誤？例：G(S): S→aA|d 輸入符號串abd是否為句子？

A→bAS|εS=>aA=>abAS=>abS=>abd這是因為A有產生式A→ε,而從開始符號S可以得出S=>*…Ad…

定義A的后繼終結符號集FOLLOW(A)設S是文法G的開始符號，對G的任何非終結符A，定義A的后繼終結符號集為：

FOLLOW(A)＝{a│S=>*…Aa…,a∈VT}當特別地,若S=>*…A，則規定$∈FOLLOW(A)非終結符A面臨輸入符號a，如果a∈/FIRST(αi)(對任意i)，ε∈FIRST(A)，那么，當a∈FOLLOW(A)時，就選用產生式A→ε工作。此時滿足：FIRST(A)∩FOLLOW(A)

=Φ要正確進行不帶回溯的語法分析，文法應滿足以下條件：（1）文法不含左遞歸；（2）對文法中每個非終結符A的各個產生式的候選首符集兩兩不相交，即A→α1│α2│…│αn

，FIRST(αi)∩FIRST(αj)=Φ，（i≠j）；（3）對文法中的每個非終結符A，若它存在某個候選首符集中包含ε，則FIRST(A)∩FOLLOW（A）=Φ稱滿足以上條件的文法為LL（1）文法。LL(1)文法對一個LL(1)文法，可以對某個輸入串進行有效的無回溯的自上而下分析。設面臨的輸入符號為a，要用非終結符A進行匹配，且A→α1│α2│…│αn

，則可如下分析(1)若a∈FIRST（αi)，則指派αi執行匹配任務；(2)否則

1)若ε∈FIRST(A)，且a∈FOLLOW(A),則讓A與ε自動匹配；

2)否則，a的出現是一種語法錯誤。LL(1)分析方法4.FIRST集合和FOLLOW集合的構造

FIRST(α)={a│α=>*a…,a∈VT}FOLLOW（A）＝{a│S=>*…Aa…,a∈VT}以下討論：對于每個文法符號X∈VT∪VN，構造FIRST(X)對于符號串α=X1X2…Xn，構造FIRST(α)對于文法的每個非終結符，構造FOLLOW(A)FIRST(X)構造對于文法G的每個文法符號X∈VT∪VN，構造FIRST(X)的方法

1）若X∈VT，則FIRST（X）={X}；

2）若X∈VN，且有產生式X→a…,a∈VT，則把a加入到FIRST（X）中，若有X→ε，則把ε加入FIRST（X）；

3）若X∈VN,且X→Y…,Y∈VN,則FIRST(Y)-{ε}加到 FIRST(X)中，若X→Y1Y2…Yk

,Y1,Y2,…,Yi

-1∈VN,ε∈FIRST(Yj) (1<=j<=i-1)則FIRST(Yi)-{ε}加到FIRST(X)中。特別地，若ε∈FIRST(Yj)(1<=j<=k)，則ε加入FIRST(X)例

G:E→TE’E’→＋TE’│εT→FT’T’→*FT’│εF→(E)│i求每個非終結符號的FIRST集合解：

FIRST(E)=FIRST(T)=FIRST(F) ={(,i}FIRST(E’)={+,ε}FIRST(T’)={*,ε}對于符號串α=X1X2…Xn，構造FIRST(α)1）置FIRST(α)=FIRST(X1)-{ε};2）若對1<=j<=i-1,ε∈FIRST(Xj),

則把FIRST(Xi)-{ε}加到FIRST(α)中；

3）若對1<=j<=n,ε∈FIRST(Xj),則把ε加到 FIRST(α)中。FIRST(α)構造例G:E→TE’E’→＋TE’│εT→FT’T’→*FT’│εF→(E)│i求每個產生式右部符號串的FIRST集合

解

FIRST(TE’)={(,i}FIRST(+TE’)={+}FIRST(FT’)={(,i}FIRST(*FT’)={*}FIRST((E))={(} FIRST（i)={i}

對于文法G的每個非終結符，構造FOLLOW(A)的方法是:1）若A為文法開始符號，置$于FOLLOW(A）中;2）若有產生式B→αAβ,

則將FIRST(β)-{ε}加到FOLLOW(A)中;3）若有B→αA或B→αAβ,且β=>*ε

則將FOLLOW(B)加到FOLLOW(A)中；

4）反復使用以上規則,直至FOLLOW(A)不再增大為止FOLLOW(A)構造例

G:E→TE’E’→＋TE’│εT→FT’T’→*FT’│εF→(E)│i

求每個非終結符號的FOLLOW集合解

FOLLOW(E)={$,)}FOLLOW(E’)=FOLLOW(E)

={$,)}

FOLLOW(T)={+,$,)}FOLLOW(T’)=FOLLOW(T) ={+,$,)}FOLLOW(F)={*,+,$,)}

3.3.3遞歸下降的預測分析預測分析是指能根據當前的輸入符號為非終結符確定一個候選式，LL(1)文法滿足這個要求。遞歸下降的預測分析是為每一個非終結符寫一個分析過程，由于文法定義是遞歸的，因此這些過程也是遞歸的。在處理輸入串時，首先執行的是開始符號的過程，然后根據產生式右部出現的非終結符，依次調用相應的過程，這種逐步下降的過程調用序列隱含地定義了輸入的分析樹。程序構造對每一個非終結符A，編寫一個相應的子程序P(A),如果A→α1│α2│…│αn相應的子程序為：

IFchINFIRST(α1)THENP(α1)

ELSEIFch

INFIRST(α2)THENP(α2)ELSE……ELSEIFchINFIRST(αn)THENP(αn)ELSEIF(ε

∈

FIRST(A))AND(chINFOLLOW(A))THENRETURN

ELSEERROR對于符號串α=γ1γ2γ3…γm相應的子程序P(

α)為：

BEGINP(γ1)P(γ2)…P(γm)END如果γi∈VT,則P(γi)為:

IFch=γiTHENread(ch)ELSEERROR；如果γi∈VN,則P(

γi)為非終結符相應的子程序程序構造例

E→TE’;E’→+TE’|;T→FT’;T’→*FT’|;F→(E)|iFIRST(＋TE’)={+}FIRST(*FT’)={*}

FOLLOW(E’)={),$}FOLLOW(T’)={+,),$}FIRST((E))={(}FIRST(i)={i}E→TE’

P(E)BeginP(T)；P(E’)；End;E’→+TE’|P(E’)BeginIfch=‘+’Thenbeginread(ch);P(T);P(E’)；

End;

elseifch=“)”Thenreturn;elseifch=‘#’Thenreturn;elseError;End;T→FT’P(T)BeginP(F)；P(T’)；End;T’→*FT’|P(E’)BeginIfch=‘*’Thenbeginread(ch);P(F)；P(T’)；

End;

//chFollow(E’)?End;例

E→TE’;E’→+TE’|;T→FT’;T’→*FT’|;F→(E)|i

FIRST(＋TE’)={+}FIRST(*FT’)={*}

FOLLOW(E’)={),$}FOLLOW(T’)={+,),$}FIRST((E))={(}FIRST(i)={i}F→(E)|i

P(F)

Beginifch=‘i’thenread(ch)elseifch=‘(’then

beginread(ch);P(E);ifch=‘)’then read(ch)elseErrorEndelseError;End;例E→TE’;E’→+TE’|;T→FT’;T’→*FT’|;F→(E)|i

FIRST(＋TE’)={+}FIRST(*FT’)={*}

FOLLOW(E’)={),$}FOLLOW(T’)={+,),$}FIRST((E))={(}FIRST(i)={i}例:產生Pascal類型子集的文法

type

simple |id |array[simple]oftype simpleinteger |char |numdotdotnum一個輔助過程voidmatch(terminalt){ if(lookahead==t)lookahead=nextToken(); elseerror();}Type過程voidtype(){ if((lookahead==integer)||(lookahead==char)|| (lookahead==num)) simple(); elseif(lookahead==){match();match(id);} elseif(lookahead==array){ match(array);match([);simple(); match(]);match(of);type(); } elseerror();}typesimple |id |array[simple]oftypeSimple過程voidsimple(){ if(lookahead==integer)match(integer); elseif(lookahead==char)match(char); elseif(lookahead==num){ match(num);match(dotdot);match(num); } elseerror();}simpleinteger |char |numdotdotnum

3.3.4非遞歸的預測分析遞歸下降分析器需要具有能夠實現遞歸過程的語言和編譯系統，使程序實現受到一定限制。如果顯示地維持一個棧，就可以構造非遞歸的預測分析程序,這是實現LL(1)分析的另一種有效方法。非遞歸預測分析程序的關鍵是如何選擇候選式，分析程序通常由三部分組成：

預測分析表（LL(1)分析表）、符號棧、總控程序

1、LL（1）分析表

若文法有m個非終結符n個終結符，則LL(1)分析表是一個(m+1)*(n+2)的矩陣M，行標題為文法非終結符，列標題為終結符號和輸入結束符$。M[A,a]為一條關于A的產生式，指出當A面臨a時，應使用的產生式或空格(出錯標志)例G:E→TE’E’→＋TE’│ε T→FT’T’→*FT’│ε F→(E)│ii+*()$EE→TE’E→TE’E’E’→＋TE’E’→εE’→εTT→ET’T→FT’T’T’→εT’→*FT’‘T’→εT’→ε

FF→i

F→(E)2、分析棧STACK:

放文法符號,初始放一個$號,

再放入開始符號S。3、總控程序:設棧頂為X，當前輸入符號為a，則對于任何（X，a）執行以下三種動作之一：若X=a=“#”則分析成功若X=a≠“#”

則把X從STACK棧中彈出,a指向下一輸入符號若X是非終結符,則按M[X,a]中的產生式進行推導(彈出X,將右部符號串反序入棧),或進行出錯處理。例:G:E→TE’E’→＋TE’│εT→FT’T’→*FT’│εF→(E)│ii+*()$EE→TE’E→TE’E’E‘→+TE’E’→εE’→εTT→FT’T→FT’T’T’→εT’→*FT’T’→εT’→εFF→iF→(E)輸入串:i+i*i的分析過程

步驟分析棧 輸入串 產生式或動作

1$E i+i*i$ E→TE’ 2 $E’T i+i*i$ T→FT’3 $E'T’Fi+i*i$ F→i4 $E'T’i i+i*i$ i退棧,輸入前進

5 $E'T’ +i*i$ T’退棧

6 $E' +i*i$ E’→+TE’7 $E'T+ +i*i$ +退棧,輸入前進

8 $E'Ti*i$ T→FT’9 .........17$ $ 成功3.3.5構造預測分析表（1）對文法的每個產生式A

，執行(2)和(3)（2）對FIRST()的每個終結符a， 把A

加入M[A,a]（3）如果在FIRST()中，對FOLLOW(A)的每個終結符b（包括$）,把A

加入M[A,b]（4）M中其它沒有定義的條目都是errorEE’TT’Fi+*()$E→TE’E→TE’T→FT’T→FT’T’→εT’→*FT’T’→εT’→εF→iF→(E)例

:對G構造分析表

E→TE’

E’→＋TE’│ε

T→FT’T’→*FT’│ε

F→(E)│iE’→+TE’E’→εE’→εFIRST(TE’)={(,i}FIRST（＋TE’）={+}FIRST(FT’)={（，i}FIRST(*FT’)={*}FIRST(（E）)={（}FOLLOW(E’)={$,)}FOLLOW(T’〕={+,$,)}

說明：

若文法G的分析表每一項M[A,a]，均不含有多重定義入口,當且僅當G為LL(1)文法。條件對任意A→α│βFIRST(α)∩FIRST(β)=Φ若β=>*ε,則FIRST(α)∩FOLLOW(A)=Φ

總控程序的形式化描述

BEGIN

＃及S進棧(push(‘#’);push(‘S’);)；

read(a)；

FLAG：＝TRUE；

WHILEFLAGDOBEGIN

把STACK棧頂彈出放在X中(X=pop())；

IFX∈VT

THEN IFX＝aTHENread(a)ELSEERROR

ELSEIFX=“＃”

THEN IFX=aTHENFLAG:=FALSEELSEERROR

ELSEIFM[X,a]={X→X1…Xk} THEN把Xk,Xk-1,…,X1逐一進棧

ELSEERRORENDOFWHILE；

END3.3.6LL（1）分析中的出錯處理出錯場合棧頂的終結符與當前的輸入符號不匹配棧頂的非終結符A與當前輸入符號a，分析表中M[A,a]為空。錯誤恢復的思路分析器檢測到一個錯誤時，暫時放棄分析并給出錯誤信息；如果分析器能到達一個狀態，從該狀態可以對剩余輸入繼續分析，則從該狀態恢復。3.3.6LL（1）分析中的出錯處理處理方法發現錯誤時，分析器跳過輸入串中的一些符號，直到輸入符號屬于某個“同步符號”為止。通過選擇適當的“同步符號”，可以使分析器迅速從錯誤中恢復過來。

A的同步符號集（synch）的選擇FOLLOW(A)

的所有終結符放入A的同步符號集合。即如果跳過一些符號直到看見FOLLOW(A)的元素，再把A彈出，分析一般可以繼續下去。3.3.6LL（1）分析中的出錯處理把高層構造的開始符號加到低層構造的同步記號集合中。如： a=expr;if… (語句的開始符號作為表達式的同步記號，以免表達式出錯又遺漏分號時忽略if語句等一大段程序)3.3.6LL（1）分析中的出錯處理把FIRST(A)的終結符加入A的同步記號集合。 如：a=expr;,if…（語句的開始符號作為語句的同步符號，以免多出一個逗號時會把if語句忽略了）如果非終結符可以產生空串，若出錯時棧頂是這樣的非終結符，則可以使用推出空串的產生式。如果終結符在棧頂而不能匹配，彈出此終結符例：加入同步符號集（FOLLOW集合元素）的LL(1)分析表i+*()$EE→TE’E→TE’synchsynchE’E’→＋TE’E’→εE’→εTT→FT’synchT→FT’synchsynchT’T’→εT’→*FT’T’→εT’→εFF→isynchsynchF→（E）synchsynch對輸入串+id*+id的語法分析與錯誤處理過程見P62表3.53.4自下而上分析3.4.1

歸約例:

S

aABe輸入串abbcde

的分析過程 A

Abc|b B

d

3.4.1歸約例:

S

aABe輸入串abbcde

的分析過程 A

Abc|b B

dab

bcde

（讀入ab）

ab3.4.1歸約例:

S

aABe輸入串abbcde

的分析過程 A

Abc|b B

dab

bcdeaAbcde（歸約）

abA3.4.1歸約例:

S

aABe輸入串abbcde

的分析過程 A

Abc|b B

dabbcdeaAbcde（再讀入bc）

abAbc3.4.1歸約例:

S

aABe

A

Abc|b B

dabbcdeaAbcdeaAde（歸約）

abAbAc3.4.1歸約例:

S

aABe

A

Abc|b B

dabbcdeaAbcdeaAde（再讀入d）

abAbdAc3.4.1歸約例:

S

aABe

A

Abc|b B

dabbcdeaAbcdeaAdeaABe（歸約）

abAbdAcB3.4.1歸約例:

S

aABe

A

Abc|b B

dabbcdeaAbcdeaAdeaABe(再讀入e)

eabAbdAcB

3.4.1歸約例： S

aABe

A

Abc|b B

dabbcdeaAbcdeaAdeaABeS（歸約）SeabAbdAcB3.4.1歸約例： S

aABe

A

Abc|b B

dabbcdeaAbcdeaAdeaABeSSrmaABermaAdermaAbcdermabbcdeSeabAbdAcB3.4.2句柄句型的句柄是和某產生式右部匹配的子串，并且，把它歸約成該產生式左部的非終結符時，恰是最右推導的逆過程的一步。

S

aABe

A

Abc|b B

dSrmaABe

rmaAdermaAbcdermabbcde句柄的右邊僅含終結符如果文法二義，那么句柄可能不唯一例：句柄不唯一

文法：EE+E|EE|(E)|id在句型EE+id3中，句柄不唯一ErmEE

E

rmE+ErmE

E+E

rmE+id3rmEE+id3

rmEE+id3rmE

id2

+id3

rmE

id2

+id3

rm

id1

id2+id3

rm

id1

id2+id3

3.4.2句柄3.4.3用棧實現移進歸約分析先通過移進歸約分析器在分析輸入串id1

id2+id3時的動作序列，來了解移進歸約分析的工作方式。棧輸入

動作

$

id1

id2

+id3$移進

$id1

id2

+id3$按E

id歸約

$E

id2

+id3$移進

$E

id2

+id3$ 移進

$Eid2

+id3$按E

id歸約

$EE

+id3$

移進

$EE+

id3$ 移進

$EE+id3

$ 按E

id歸約

$EE+E

$ 按E

E+E歸約

$EE

$ 按E

EE歸約

3.4.3用棧實現移進歸約分析要想很好地使用移進歸約方式，尚需解決一些問題如何決策移進還是歸約進行歸約時，如何確定右句型中將要歸約的子串進行歸約時，如何確定選擇哪一個產生式3.4.4移進歸約分析的沖突1、移進歸約沖突例 stmt

ifexprthenstmt |ifexprthenstmtelsestmt|other 如果移進歸約分析器處于格局 棧

輸入 …ifexprthenstmt else…$是移進還是歸約？-沖突！2、歸約歸約沖突stmtid(parameter_list)|expr=exprparameter_list

parameter_list,parameter|parameterparameter

idexpr

id(expr_list)|idexpr_list

expr_list,expr|expr分析由A(I,J)開始的語句 棧 輸入 …id(id ,id)…歸約成expr還是parameter?3.5

LR分析器本節介紹LR(k)分析技術特點適用于一大類上下文無關文法效率高主要介紹構造LR分析表的三種技術簡單的LR方法（簡稱SLR）規范的LR方法向前看的LR方法（簡稱LALR）

3.5.1LR分析算法輸入LR分析程序輸出棧LR分析器的模型actiongotosmXmsm-1Xm-1…s0…a1ai…an$L表示從左到右掃描輸入串；R表示構造一個最右推導的逆過程例

(1)E

E+T(2)E

T

(3)T

TF(4)

T

E

(5)F(E)(6)Fid(P70)狀態動

作(action

)轉

移(goto)

id

+()$

E

TF

0s5s41231s6acc

2

r2s7r2r23r4r4r4r44…

s5s4

…

…

823……

移進(Sj)把當前a和狀態j進棧歸約(rj)按第j個產生式歸約

接受(acc)成功結束出錯(空白或出錯處理）GOTO(S,X)狀態S面對文法符號X時,下一狀態是什么棧輸入

動作

0

id

id

+id$移進

0id5

id

+id$按F

id歸約

0F3

id

+id$按TF歸約

0T2

id

+id$ 移進

0T2*7

id+id$移進

0T2*7id5

+id$按F

id歸約

0T2*7F10

+id$ 按T

T*F歸約

0T2

+id$ 按E

T歸約

…