第3章 語法分析

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

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

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

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

α，β為符號串箭頭左邊稱為產(chǎn)生式左部箭頭右邊稱為產(chǎn)生式右部

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

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

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

VN∩VT=φ

S：開始符號，至少在某個產(chǎn)生式左部出現(xiàn)一次

P：產(chǎn)生式集合（有限），每個產(chǎn)生式的形式為：

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

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

expr

op

exprop+expr(expr)op

expr

exprexpr

id}

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

expr

op

expr |

(expr)|

expr|idop+|習(xí)慣上，常用大寫字母表示非終結(jié)符，小寫字母表示終結(jié)符。上例簡化表示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}

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

E

EAE|0E0|a

A

b|c

也是上下文無關(guān)文法

G(S)=（VT,

VN,

S,

P)

VT:{id,

+,*,

(

,

),

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

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

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

E+E|E

E|(E)|

E|idE

E

(E)

(E+E)

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

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

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

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

(經(jīng)一步或若干步推導(dǎo)）或α1=>*αn

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

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

E+E|E

E|(E)|

E|id最左推導(dǎo) E lm

Elm

(E)lm

(E

+E)

lm

(id+E)lm(id+id)最右推導(dǎo)（規(guī)范推導(dǎo)） E rm

Erm

(E)rm

(E+E)

rm

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

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

E+E|E

E|(E)|

E|id

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

例：E

E+E|E

E|(E)|

E|id

句子idid+id的最左推導(dǎo)如下

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如果一個文法存在某個句子對應(yīng)兩棵不同的語法樹,則稱這個文法是二義的。文法二義不代表語言一定是二義的。當(dāng)產(chǎn)生一個語言的所有文法都是二義時,這個語言才稱為二義的。有些語法分析器希望處理的文法是無二義的，則要構(gòu)造無二義文法；出于某些需要，也可以構(gòu)造允許二義文法的分析器，不過文法要附帶消除二義性的規(guī)則。如對文法G(E)，規(guī)定“*”的優(yōu)先級高于“+”，并服從左結(jié)合，文法改寫為 E→T|E+T

T→F|T*F

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

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

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

a

A0|bA0|a

A1A1

b

A2A2

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

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

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

歸納假設(shè)：少于n步的推導(dǎo)都產(chǎn)生配對的括號串歸納步驟：n步的最左推導(dǎo)如下：

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

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

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

1)的w=(x)y

S(S)S*(x)S*(x)y3.2.4適當(dāng)?shù)谋磉_式文法

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

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適當(dāng)?shù)谋磉_式文法

3.2.5消除二義性stmt

ifexprthenstmt |ifexprthenstmtelsestmt |other句型：ifexprthenifexprthenstmt

elsestmt兩個最左推導(dǎo)：

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可以例外短語文法、上下文有關(guān)文法3.2.6形式語言鳥瞰文法G=(VT

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

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

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

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

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

短語文法、上下文有關(guān)文法、上下文無關(guān)文法、正規(guī)文法上下文有關(guān)文法舉例例 L3＝{anbncn|n1}的上下文有關(guān)文法S

aSBC

S

aBC

CB

BCaB

ab

bB

bb bC

bccC

ccanbncn的推導(dǎo)過程如下：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自上而下分析的一般方法對任何的輸入串(單詞記號流),試圖用一切可能的辦法,從文法的開始符號出發(fā),為輸入串尋找一個最左推導(dǎo),也就是自上而下地為輸入串建立一棵語法樹。這是一種帶回溯的試探過程。

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

SxAySxAyS**用S→xAy

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

xAy

A→**│*

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

Pα，稱它是含有左遞歸的。文法的左遞歸使分析過程陷入無限循環(huán)?；厮菔狗治鲎叽蠖五e路。存在虛假匹配現(xiàn)象。報告分析不成功時，難于知道輸入串中出錯的確切位置。效率低，代價高，有理論意義，實踐價值不大。自上而下分析面臨的問題3.3.2LL(1)文法對于LL(1)文法，可以進行不帶回溯的自上而下的LL(1)分析。LL(1)是指從左(Left)到右掃描輸入串；構(gòu)造句子的最左(Leftmost)推導(dǎo)；分析時每步向前看一個字符。消除左遞歸消除回溯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)消除間接左遞歸例:設(shè)文法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γ的規(guī)則改寫為：

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

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

消除關(guān)于Pi規(guī)則的直接左遞歸

END3）化簡:刪除永不使用的產(chǎn)生式

解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例:為文法消除間接左遞歸在分析過程中，對任非終結(jié)符A,用它匹配輸入串時要求能夠根據(jù)當(dāng)前輸入，準確地指派一個候選式,若匹配成功,則不虛假,若匹配不成功,則其它的候選式也不會成功。即當(dāng)A執(zhí)行匹配時,A→α1│α2│…│αn

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

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

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

設(shè)A→δβ1│δβ2│…│δβn│

γ1│γ2│…│γm

（其中γ1、

γ2、

…、

γm不以δ開頭） 改寫:

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

B→β1│β2│…│βn例1：文法G：S→aSb|aS|ε解：提?。篠→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一般地，經(jīng)過反復(fù)提取左因子可把每一個非終結(jié)符的所有候選首符集變成兩兩不相交。結(jié)論當(dāng)文法滿足：（1）消除了左遞歸（2）FIRST(αi)∩FIRST(αj)=Φ，i≠j）對某個輸入符號a，及待匹配的非終結(jié)符A，若a∈FIRST（αi），則對A選用αi候選式工作。這種選擇是唯一、確定和無虛假匹配的。3.

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

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

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

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

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

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

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

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

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

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

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

2）若X∈VN，且有產(chǎn)生式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求每個非終結(jié)符號的FIRST集合解：

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

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

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

解

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

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

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

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

4）反復(fù)使用以上規(guī)則,直至FOLLOW(A)不再增大為止FOLLOW(A)構(gòu)造例

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

求每個非終結(jié)符號的FOLLOW集合解

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

={$,)}

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

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

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相應(yīng)的子程序P(

α)為：

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

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

γi)為非終結(jié)符相應(yīng)的子程序程序構(gòu)造例

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}例:產(chǎn)生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非遞歸的預(yù)測分析遞歸下降分析器需要具有能夠?qū)崿F(xiàn)遞歸過程的語言和編譯系統(tǒng)，使程序?qū)崿F(xiàn)受到一定限制。如果顯示地維持一個棧，就可以構(gòu)造非遞歸的預(yù)測分析程序,這是實現(xiàn)LL(1)分析的另一種有效方法。非遞歸預(yù)測分析程序的關(guān)鍵是如何選擇候選式，分析程序通常由三部分組成：

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

1、LL（1）分析表

若文法有m個非終結(jié)符n個終結(jié)符，則LL(1)分析表是一個(m+1)*(n+2)的矩陣M，行標(biāo)題為文法非終結(jié)符，列標(biāo)題為終結(jié)符號和輸入結(jié)束符$。M[A,a]為一條關(guān)于A的產(chǎn)生式，指出當(dāng)A面臨a時，應(yīng)使用的產(chǎn)生式或空格(出錯標(biāo)志)例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、總控程序:設(shè)棧頂為X，當(dāng)前輸入符號為a，則對于任何（X，a）執(zhí)行以下三種動作之一：若X=a=“#”則分析成功若X=a≠“#”

則把X從STACK棧中彈出,a指向下一輸入符號若X是非終結(jié)符,則按M[X,a]中的產(chǎn)生式進行推導(dǎo)(彈出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的分析過程

步驟分析棧 輸入串 產(chǎn)生式或動作

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構(gòu)造預(yù)測分析表（1）對文法的每個產(chǎn)生式A

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

加入M[A,a]（3）如果在FIRST()中，對FOLLOW(A)的每個終結(jié)符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構(gòu)造分析表

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]，均不含有多重定義入口,當(dāng)且僅當(dāng)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=“?！?/p>

THEN IFX=aTHENFLAG:=FALSEELSEERROR

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

ELSEERRORENDOFWHILE；

END3.3.6LL（1）分析中的出錯處理出錯場合棧頂?shù)慕K結(jié)符與當(dāng)前的輸入符號不匹配棧頂?shù)姆墙K結(jié)符A與當(dāng)前輸入符號a，分析表中M[A,a]為空。錯誤恢復(fù)的思路分析器檢測到一個錯誤時，暫時放棄分析并給出錯誤信息；如果分析器能到達一個狀態(tài)，從該狀態(tài)可以對剩余輸入繼續(xù)分析，則從該狀態(tài)恢復(fù)。3.3.6LL（1）分析中的出錯處理處理方法發(fā)現(xiàn)錯誤時，分析器跳過輸入串中的一些符號，直到輸入符號屬于某個“同步符號”為止。通過選擇適當(dāng)?shù)摹巴椒枴?，可以使分析器迅速從錯誤中恢復(fù)過來。

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

的所有終結(jié)符放入A的同步符號集合。即如果跳過一些符號直到看見FOLLOW(A)的元素，再把A彈出，分析一般可以繼續(xù)下去。3.3.6LL（1）分析中的出錯處理把高層構(gòu)造的開始符號加到低層構(gòu)造的同步記號集合中。如： a=expr;if… (語句的開始符號作為表達式的同步記號，以免表達式出錯又遺漏分號時忽略if語句等一大段程序)3.3.6LL（1）分析中的出錯處理把FIRST(A)的終結(jié)符加入A的同步記號集合。 如：a=expr;,if…（語句的開始符號作為語句的同步符號，以免多出一個逗號時會把if語句忽略了）如果非終結(jié)符可以產(chǎn)生空串，若出錯時棧頂是這樣的非終結(jié)符，則可以使用推出空串的產(chǎn)生式。如果終結(jié)符在棧頂而不能匹配，彈出此終結(jié)符例：加入同步符號集（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輸入串a(chǎn)bbcde

的分析過程 A

Abc|b B

d

3.4.1歸約例:

S

aABe輸入串a(chǎn)bbcde

的分析過程 A

Abc|b B

dab

bcde

（讀入ab）

ab3.4.1歸約例:

S

aABe輸入串a(chǎn)bbcde

的分析過程 A

Abc|b B

dab

bcdeaAbcde（歸約）

abA3.4.1歸約例:

S

aABe輸入串a(chǎn)bbcde

的分析過程 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句柄句型的句柄是和某產(chǎn)生式右部匹配的子串，并且，把它歸約成該產(chǎn)生式左部的非終結(jié)符時，恰是最右推導(dǎo)的逆過程的一步。

S

aABe

A

Abc|b B

dSrmaABe

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

文法：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用棧實現(xiàn)移進歸約分析先通過移進歸約分析器在分析輸入串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用棧實現(xiàn)移進歸約分析要想很好地使用移進歸約方式，尚需解決一些問題如何決策移進還是歸約進行歸約時，如何確定右句型中將要歸約的子串進行歸約時，如何確定選擇哪一個產(chǎn)生式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分析器本節(jié)介紹LR(k)分析技術(shù)特點適用于一大類上下文無關(guān)文法效率高主要介紹構(gòu)造LR分析表的三種技術(shù)簡單的LR方法（簡稱SLR）規(guī)范的LR方法向前看的LR方法（簡稱LALR）

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

(1)E

E+T(2)E

T

(3)T

TF(4)

T

E

(5)F(E)(6)Fid(P70)狀態(tài)動

作(action

)轉(zhuǎn)

移(goto)

id

+()$

E

TF

0s5s41231s6acc

2

r2s7r2r23r4r4r4r44…

s5s4

…

…

823……

移進(Sj)把當(dāng)前a和狀態(tài)j進棧歸約(rj)按第j個產(chǎn)生式歸約

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

動作

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歸約

…