第3章 語(yǔ)法分析

第3章語(yǔ)法分析本章要點(diǎn)上下文無(wú)關(guān)文法自上而下語(yǔ)法分析自下而上語(yǔ)法分析語(yǔ)法分析器的自動(dòng)生成

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

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

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

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

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

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

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

VN∩VT=φ

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

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

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

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

expr

op

exprop+expr(expr)op

expr

exprexpr

id}

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

expr

op

expr |

(expr)|

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

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

E

EAE|0E0|a

A

b|c

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

G(S)=（VT,

VN,

S,

P)

VT:{id,

+,*,

(

,

),

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

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

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

E+E|E

E|(E)|

E|idE

E

(E)

(E+E)

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

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

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

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

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

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

如：(i×i+i),(i+i)都是G（E）的句子。語(yǔ)言文法G所產(chǎn)生句子的全體,即:L(G)={α|S=>+α，α∈VT*}概念最左(右)推導(dǎo)若某推導(dǎo)中任何一步直接推出α=>β都是對(duì)α中的最左（最右）非終結(jié)符進(jìn)行替換，則稱其為最左（最右）推導(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)的樹形表示即語(yǔ)法分析樹，簡(jiǎn)稱分析樹。分析樹的構(gòu)造

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

E+E|E

E|(E)|

E|id

(id+id)的分析樹EE()EEE+idid在一棵語(yǔ)法樹生長(zhǎng)過(guò)程中的任何時(shí)刻，所有那些沒(méi)有后代的端末結(jié)點(diǎn)自左到右排列起來(lái)就是一個(gè)句型。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如果一個(gè)文法存在某個(gè)句子對(duì)應(yīng)兩棵不同的語(yǔ)法樹,則稱這個(gè)文法是二義的。文法二義不代表語(yǔ)言一定是二義的。當(dāng)產(chǎn)生一個(gè)語(yǔ)言的所有文法都是二義時(shí),這個(gè)語(yǔ)言才稱為二義的。有些語(yǔ)法分析器希望處理的文法是無(wú)二義的，則要構(gòu)造無(wú)二義文法；出于某些需要，也可以構(gòu)造允許二義文法的分析器，不過(guò)文法要附帶消除二義性的規(guī)則。如對(duì)文法G(E)，規(guī)定“*”的優(yōu)先級(jí)高于“+”，并服從左結(jié)合，文法改寫為 E→T|E+T

T→F|T*F

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

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

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

a

A0|bA0|a

A1A1

b

A2A2

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

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

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

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

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

(S)S|L(G)：配對(duì)的括號(hào)串的集合按串長(zhǎng)進(jìn)行歸納：配對(duì)括號(hào)串可由S推出歸納基礎(chǔ)：S

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

1)的w=(x)y

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

用一種層次觀點(diǎn)看待表達(dá)式

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ù)谋磉_(dá)式文法

3.2.5消除二義性stmt

ifexprthenstmt |ifexprthenstmtelsestmt |other句型：ifexprthenifexprthenstmt

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

stmtifexprthenstmt

ifexprthenifexprthenstmtelsestmt

stmtifexprthenstmtelsestmt

ifexprthenifexprthenstmt

elsestmt

無(wú)二義的文法stmt

matched_stmt

|unmatched_stmtmatched_stmt

ifexprthenmatched_stmt

elsematched_stmt

|otherunmatched_stmt

ifexprthenstmt |ifexprthenmatched_stmt

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

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

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

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

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

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

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

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

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

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

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

aSBC

S

aBC

CB

BCaB

ab

bB

bb bC

bccC

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

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

SxAySxAyS**用S→xAy

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

xAy

A→**│*

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

Pα，稱它是含有左遞歸的。文法的左遞歸使分析過(guò)程陷入無(wú)限循環(huán)?；厮菔狗治鲎叽蠖五e(cuò)路。存在虛假匹配現(xiàn)象。報(bào)告分析不成功時(shí)，難于知道輸入串中出錯(cuò)的確切位置。效率低，代價(jià)高，有理論意義，實(shí)踐價(jià)值不大。自上而下分析面臨的問(wèn)題3.3.2LL(1)文法對(duì)于LL(1)文法，可以進(jìn)行不帶回溯的自上而下的LL(1)分析。LL(1)是指從左(Left)到右掃描輸入串；構(gòu)造句子的最左(Leftmost)推導(dǎo)；分析時(shí)每步向前看一個(gè)字符。消除左遞歸消除回溯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）化簡(jiǎn):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）化簡(jiǎn):刪除永不使用的產(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例:為文法消除間接左遞歸在分析過(guò)程中，對(duì)任非終結(jié)符A,用它匹配輸入串時(shí)要求能夠根據(jù)當(dāng)前輸入，準(zhǔn)確地指派一個(gè)候選式,若匹配成功,則不虛假,若匹配不成功,則其它的候選式也不會(huì)成功。即當(dāng)A執(zhí)行匹配時(shí),A→α1│α2│…│αn

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

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

若要準(zhǔn)確地指派候選式，則應(yīng)滿足FIRST(αi)∩FIRST(αj)=Φ，i≠j通過(guò)提取公共左因子，將文法改造成任何非終結(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：對(duì)文法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)過(guò)反復(fù)提取左因子可把每一個(gè)非終結(jié)符的所有候選首符集變成兩兩不相交。結(jié)論當(dāng)文法滿足：（1）消除了左遞歸（2）FIRST(αi)∩FIRST(αj)=Φ，i≠j）對(duì)某個(gè)輸入符號(hào)a，及待匹配的非終結(jié)符A，若a∈FIRST（αi），則對(duì)A選用αi候選式工作。這種選擇是唯一、確定和無(wú)虛假匹配的。3.

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

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

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

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

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

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

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

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

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

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

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

2）若X∈VN，且有產(chǎn)生式X→a…,a∈VT，則把a(bǔ)加入到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求每個(gè)非終結(jié)符號(hào)的FIRST集合解：

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

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

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

解

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

對(duì)于文法G的每個(gè)非終結(jié)符，構(gòu)造FOLLOW(A)的方法是:1）若A為文法開始符號(hào)，置$于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

求每個(gè)非終結(jié)符號(hào)的FOLLOW集合解

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

={$,)}

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

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

IFchINFIRST(α1)THENP(α1)

ELSEIFch

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

∈

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

ELSEERROR對(duì)于符號(hào)串α=γ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一個(gè)輔助過(guò)程voidmatch(terminalt){ if(lookahead==t)lookahead=nextToken(); elseerror();}Type過(guò)程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過(guò)程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ù)測(cè)分析遞歸下降分析器需要具有能夠?qū)崿F(xiàn)遞歸過(guò)程的語(yǔ)言和編譯系統(tǒng)，使程序?qū)崿F(xiàn)受到一定限制。如果顯示地維持一個(gè)棧，就可以構(gòu)造非遞歸的預(yù)測(cè)分析程序,這是實(shí)現(xiàn)LL(1)分析的另一種有效方法。非遞歸預(yù)測(cè)分析程序的關(guān)鍵是如何選擇候選式，分析程序通常由三部分組成：

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

1、LL（1）分析表

若文法有m個(gè)非終結(jié)符n個(gè)終結(jié)符，則LL(1)分析表是一個(gè)(m+1)*(n+2)的矩陣M，行標(biāo)題為文法非終結(jié)符，列標(biāo)題為終結(jié)符號(hào)和輸入結(jié)束符$。M[A,a]為一條關(guān)于A的產(chǎn)生式，指出當(dāng)A面臨a時(shí)，應(yīng)使用的產(chǎn)生式或空格(出錯(cuò)標(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:

放文法符號(hào),初始放一個(gè)$號(hào),

再放入開始符號(hào)S。3、總控程序:設(shè)棧頂為X，當(dāng)前輸入符號(hào)為a，則對(duì)于任何（X，a）執(zhí)行以下三種動(dòng)作之一：若X=a=“#”則分析成功若X=a≠“#”

則把X從STACK棧中彈出,a指向下一輸入符號(hào)若X是非終結(jié)符,則按M[X,a]中的產(chǎn)生式進(jìn)行推導(dǎo)(彈出X,將右部符號(hào)串反序入棧),或進(jìn)行出錯(cuò)處理。例: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的分析過(guò)程

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

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退棧,輸入前進(jìn)

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

6 $E' +i*i$ E’→+TE’7 $E'T+ +i*i$ +退棧,輸入前進(jìn)

8 $E'Ti*i$ T→FT’9 .........17$ $ 成功3.3.5構(gòu)造預(yù)測(cè)分析表（1）對(duì)文法的每個(gè)產(chǎn)生式A

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

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

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

:對(duì)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’〕={+,$,)}

說(shuō)明：

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

總控程序的形式化描述

BEGIN

＃及S進(jìn)棧(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逐一進(jìn)棧

ELSEERRORENDOFWHILE；

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

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

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

歸約例:

S

aABe輸入串a(chǎn)bbcde

的分析過(guò)程 A

Abc|b B

d

3.4.1歸約例:

S

aABe輸入串a(chǎn)bbcde

的分析過(guò)程 A

Abc|b B

dab

bcde

（讀入ab）

ab3.4.1歸約例:

S

aABe輸入串a(chǎn)bbcde

的分析過(guò)程 A

Abc|b B

dab

bcdeaAbcde（歸約）

abA3.4.1歸約例:

S

aABe輸入串a(chǎn)bbcde

的分析過(guò)程 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é)符時(shí)，恰是最右推導(dǎo)的逆過(guò)程的一步。

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用棧實(shí)現(xiàn)移進(jìn)歸約分析先通過(guò)移進(jìn)歸約分析器在分析輸入串id1

id2+id3時(shí)的動(dòng)作序列，來(lái)了解移進(jìn)歸約分析的工作方式。棧輸入

動(dòng)作

$

id1

id2

+id3$移進(jìn)

$id1

id2

+id3$按E

id歸約

$E

id2

+id3$移進(jìn)

$E

id2

+id3$ 移進(jìn)

$Eid2

+id3$按E

id歸約

$EE

+id3$

移進(jìn)

$EE+

id3$ 移進(jìn)

$EE+id3

$ 按E

id歸約

$EE+E

$ 按E

E+E歸約

$EE

$ 按E

EE歸約

3.4.3用棧實(shí)現(xiàn)移進(jìn)歸約分析要想很好地使用移進(jìn)歸約方式，尚需解決一些問(wèn)題如何決策移進(jìn)還是歸約進(jìn)行歸約時(shí)，如何確定右句型中將要?dú)w約的子串進(jìn)行歸約時(shí)，如何確定選擇哪一個(gè)產(chǎn)生式3.4.4移進(jìn)歸約分析的沖突1、移進(jìn)歸約沖突例 stmt

ifexprthenstmt |ifexprthenstmtelsestmt|other 如果移進(jìn)歸約分析器處于格局 棧

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

parameter_list,parameter|parameterparameter

idexpr

id(expr_list)|idexpr_list

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

LR分析器本節(jié)介紹LR(k)分析技術(shù)特點(diǎn)適用于一大類上下文無(wú)關(guān)文法效率高主要介紹構(gòu)造LR分析表的三種技術(shù)簡(jiǎn)單的LR方法（簡(jiǎn)稱SLR）規(guī)范的LR方法向前看的LR方法（簡(jiǎn)稱LALR）

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

(1)E

E+T(2)E

T

(3)T

TF(4)

T

E

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

作(action

)轉(zhuǎn)

移(goto)

id

+()$

E

TF

0s5s41231s6acc

2

r2s7r2r23r4r4r4r44…

s5s4

…

…

823……

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

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

動(dòng)作

0

id

id

+id$移進(jìn)

0id5

id

+id$按F

id歸約

0F3

id

+id$按TF歸約

0T2

id

+id$ 移進(jìn)

0T2*7

id+id$移進(jìn)

0T2*7id5

+id$按F

id歸約

0T2*7F10

+id$ 按T

T*F歸約

0T2

+id$ 按E

T歸約

…