編譯原理第四章：語法分析-自上而下分析

第四章語法分析——自上而下分析4.1語法分析器的功能4.2自上而下分析面臨的問題4.3LL（1）分析法4.4遞歸下降分析程序構(gòu)造4.5預測分析程序4.6LL（1）分析中的錯誤處理

復習題4.1語法分析器的功能語法分析是編譯過程的核心部分，它的任務(wù)是在詞法分析識別出單詞符號串的基礎(chǔ)上，分析并判定程序的語法結(jié)構(gòu)是否符合語法規(guī)則。語法分析器工作本質(zhì)：按文法的產(chǎn)生式，識別輸入符號串是否為一個句子，判斷是否能從文法的開始符號出發(fā)推導出這個輸入串。語法分析方法種類

（按語法分析樹建立方法）

自上而下分析

遞歸下降分析、預測分析

自下而上分析

算符優(yōu)先分析、LR分析4.2自上而下分析面臨的問題一.自上而下分析開始符號句子

從文法的開始符號出發(fā)，向下推導，推出句子；即對任何輸入串，試圖用一切可能的辦法，從文法開始符號出發(fā)，自上而下地為輸入串建立一棵語法樹。

或者說，為輸入串尋找一個最左推導。自上而下分析過程，本質(zhì)是一種試探過程，是反復使用不同產(chǎn)生式，謀求匹配輸入串的過程。

二．引例例4.1假定有文法（1）S→xAy

（2）A→**|*以及輸入串x*y（記為α）自上而下構(gòu)造α的語法樹

SS

xAyxAy

**注銷A的第一個候選所發(fā)展的子樹

S

xAy試探用第二個候選

*

實現(xiàn)這種自上而下的帶回溯試探法的一個簡單途徑是讓每個非終結(jié)符對應(yīng)一個遞歸子程序，每個這種子程序作為一個布爾過程。三．自上而下分析法存在的困難和缺點

1.文法的左遞歸問題（消除文法的左遞歸）

2.回溯問題（消除回溯）

3.當一個非終結(jié)符用某一候選式匹配成功時，這種成功可能僅是暫時的（從最長候選開始匹配，虛假現(xiàn)象會減少）

4.當最終報告分析不成功時，難于知道輸入串出錯的確切位置。

5.窮盡試探法，效率低，代價高。4.3LL（1）分析法一.左遞歸的消除1.直接左遞歸假定關(guān)于非終結(jié)符P的規(guī)則為P→Pα|?,其中?不以P開頭可改寫為P→?P’，P’→αP’|ε(ε為空字)

一般而言，假定關(guān)于P的全部產(chǎn)生式是

P→Pα1|Pα2|…|Pαm|β1|β2|…βn

其中α都不等于ε

，且每個β不以P開頭。則改寫后為P→β1P′|β2P′|…|βnP′

P′→α1P′|α2P′|…|αmP′|ε例4.2文法E→E+T|T消去直接左遞歸。

T→T*F|FF→（E）|i解：

E→TE′E′→+TE′|εT→FT′T′→*FT′|εF→（E）|i

2．間接左遞歸例4.3文法S→Qc|cQ→Rb|bR→Sa|a在該文法中

有S

Qc

Rbc

Sabc3．消除左遞歸算法如果一個文法不含回路,也不含以ε為右部的產(chǎn)生式。1o排序把文法G的所有非終結(jié)符按任一種順序排列P1、P2、…、Pn按序執(zhí)行。2o代入及消除左遞歸

for(i=1;i<=n;i++)

for(j=1;j<=i－1;j++)把形如Pi→Pjγ的規(guī)則改寫為

Pi→δ1

γ

|δ

2

γ|…|δ

k

γ

(其中Pj→δ

1|δ

2|…|δ

k

是關(guān)于Pj的所有規(guī)則)消除關(guān)于Pi規(guī)則的直接左遞歸性3o化簡化簡由2o所得文法，即去除那些從開始符號出發(fā)永遠無法到達的非終結(jié)符的產(chǎn)生式規(guī)則。例4.3考慮文法S→Qc|c

Q→Rb|b

R→Sa|a

解:令它的非終結(jié)符排序為R，Q，S，對于R不存在直接左遞歸，把R代入Q則得Q→Sab|ab|b

再把Q代入S則得S→Sabc|abc|bc|c

經(jīng)除去S直接左遞歸后，得

S→abcS′|bcS′|cS′

S′→abcS′|ε

Q→Sab|ab|b

R→Sa|a

其中關(guān)于Q和R的規(guī)則多余,

刪除之若對文法排序S，Q，R，則得

S→Qc|c

Q→Rb|b

R→Sa|a將S代入到R，R→Sa|a

R→Qca|ca|a將Q代入到R，R→Rbca|bca|ca|a則得R→bcaR’|caR’|aR’R’→bcaR’|ε二．消除回溯（提公共左因子）

假定關(guān)于A的規(guī)則是A→δβ1|δβ2|……|δβn|γ1|γ2|……|γm(其中γi不以δ開頭)提取公共左因子,改寫為

A→δA′|γ1|γ2|……|γmA′→β1|β2|……|βn三.LL(1)分析條件第一個L表示從左到右掃描,第二個L表示最左推導,1表示分析時,每步只需向前查看一個符號。First(α)和Follow(A)定義(1)First(α)

令G是一個不含左遞歸的文法,對G的所有非終結(jié)符的每個候選α定義它的終結(jié)首符集First(α)為

First(α)={a|…,a∈VT}

若,規(guī)定ε∈First(α)(2)Follow(A)

假定S是文法G的開始符號,對于G的任何非終結(jié)符A.

定義:Follow(A)={a|S

…Aa…,a∈VT

}.

若S…A,則規(guī)定#∈Follow(A)

即Follow(A)是所有句型中出現(xiàn)在緊接A之后的終結(jié)符或”#”2.LL(1)文法三個條件:（1）文法不含左遞歸（2）對于文法中每一個非終結(jié)符A的各個產(chǎn)生式的候選首符集兩兩不相交,若A→α1|α2|…|αn，則

First(αi)∩First(αj)=(其中i不等于j)（3）對文法中每個非終結(jié)符A,若它存在某個候選首符集包含εFirst(αi)∩Follow(A)=1≤i≤n

如果一個文法G滿足以上條件，則稱該文法G為LL（1）文法3.LL（1）分析假設(shè)要用非終結(jié)符A進行匹配，面臨的輸入符號為a,A的所有產(chǎn)生式為A→α1|α2|…|αn(1)若a∈First(αi),則指派αi去執(zhí)行匹配任務(wù)(2)若a不屬于First(αi)（i=1,2,…,n）,則若ε∈First(αi)且a∈Follow(A)，則讓A與ε自動匹配否則，a的出現(xiàn)是一種語法錯誤4.4遞歸下降分析程序構(gòu)造當一個文法滿足LL（1）條件時，可為它構(gòu)造一個不帶回溯的自上而下分析程序，這個分析程序由一組遞歸過程組成，每個過程對應(yīng)文法的一個非終結(jié)符，這樣的分析程序為遞歸下降分析器。

ADVANCE指輸入串指示器IP調(diào)至指向下一個輸入符號

SYM指IP當前所指的那個輸入符號

ERROR出錯診察處理程序文法E→TE′

E′→+TE′|εT→FT′T′→*FT′|ε

F→(E)|i遞歸子程序PROCEDUREE;PROCEDURE

T;BEGINBEGIN

T;

E′F;

T′END;END;PROCEDURE

E′;PROCEDURET′IFSYM=’+’THEN

IFSYM=’*’THENBEGIN

BEGINADVANCE;

ADVANCET;

E′

F;

T′END;

END;PROCEDUREF;IFSYM=’i’THENADVANCEELSEIFSYM=’(‘THEN

BEGIN

ADVANCE;

E;

IFSYM=’)’THENADVANCE

ELSEERRORENDELSEERROR;4.5預測分析程序一、預測分析程序思想二、First(α)和Follow(A)的求法三、預測分析表的構(gòu)造四、預測分析程序的總控程序五、實例4.5預測分析程序使用一張分析表和一個棧進行聯(lián)合控制一.預測分析程序思想

輸入串．．．a(chǎn)．．．#

Ｘ總控程序輸出

預測分析表M

#STACK匹配推導成功報錯

棧STACK用于存放文法符號，分析開始時，棧底先放一個“#”，后放進文法開始符號，假定輸入串后總有一個“#”，標志輸入串結(jié)束。當棧頂元素為X，a為當前輸入符號

X∈VT①X=a=’#’成功

②X=a≠’#’X退棧，a指向下一個輸入符號匹配

X∈VN①查看分析表M。M（X,a）中的X→α,X退棧，α反序入棧，對X→ε,X退棧，無符號進棧，a保持推導

②當M(X,a)不存在，出錯標志報錯二.First(α)和Follow(A)的求法1.FIRST（α）的求法定義：假定α是文法G的任一符號串，α∈（VT∪VN）*，則FIRST(α)={a|αa……,a∈VT},若αε,則ε∈FIRST（α）FIRST(X)求法X∈(VT∪VN)1’若X∈VT,則FIRST(X)＝｛X｝2’若X∈VN,且有產(chǎn)生式X→a…,則a加入FIRST（X）,若X→ε，則ε加入FIRST（X）3’若X→Y…

是一產(chǎn)生式且Y∈VN,則把FIRST（Y）中所有的非

ε元素加到FIRST(X)中；若X→Y1Y2…YK是一個產(chǎn)生式，Y1,Y2,…,Yi-1∈VN,且對于,,FIRST(Yj)都含有ε(Y1…Yi-1ε),則把FIRST(Yi)中所有非ε元素都加到

FIRST(X)中；若所有FIRST(Yi)均含有ε,j=1,2,…,k,則把ε加到FIRST(X)中。4’重復2’,3’直到所有FIRST(X)不再擴大為止。2．FOLLOW(A)的求法定義：假定S是文法G的開始符號，對于G的任何非終結(jié)符AFOLLOW(A)={a|S

…

Aa…,a∈VT}

若S…A,規(guī)定#∈FOLLOW(A)。即：FOLLOW(A)是所有句型中出現(xiàn)在緊接A之后的終結(jié)符或“#”。

FOLLOW(B)的求法1’對于文法的開始符號S，置#于FOLLOW(S)中2’若A→αBβ是一個產(chǎn)生式，則把FIRST(β)\{ε}加到FOLLOW(B)中。3’若A→αB是一個產(chǎn)生式，或A→αBβ且βε時（即ε∈FIRST(β)）則把FOLLOW(A)加到FOLLOW(B)中。4’重復2’,3’直到FOLLOW集不再增大為止。例：對于文法G:E→E+T|T,T→T*F|F,F→(E)|i求FIRST(α)和FOLLOW(A)解:消除左遞歸得G’:E→TE’E’→+TE’|εT→FT’T’→*FT’|εF→(E)|iRFIRST(R)FOLLOW(R)E(,i#,)T(,i#,),+E’+,ε#,)T’*,ε#,),+F(,i#,),+,*三．預測分析表的構(gòu)造1.對文法G的每個產(chǎn)生式A→α

執(zhí)行2，32.對任意a∈FIRST(α),把A→α加至M[A,a]中3.若ε∈FIRST(α),則對任意b∈FOLLOW(A),把A→α加至M[A,b]中4.把所有無定義的M[A,a]標上“出錯標志”結(jié)論:一個文法G的預測分析表M不含多重定義入口,當且僅當該文法為LL(1)的。四．預測分析程序的總控程序BEGIN

首先把“#”然后把文法的開始符號推進STACK棧；把第一個輸入符號讀進a;FLAG:=TURE;WHILEFLAGDOBEGIN

把STACK棧頂符號上托出去并放在X中;IFX∈VTTHENIFX=aTHEN把下一個輸入符號讀進aELSEERRORELSEIFX=‘#’THENIFX=aTHENFLAG:=FALSEELSEERRORELSEIFM[X,a]={X→X1X2…XK}THEN

把XK,XK-1,…X1一一推進STACK棧

ELSEERRORENDOFWHILESTOP/*分析成功,過程完畢*/END．例.對于文法G’輸入串為i1*i2+i3,利用分析表進行預測分析步驟符號棧輸入串所用產(chǎn)生式0#Ei1*i2+i3#E面臨i1#EˊTi1*i2+i3#E→TEˊ2#EˊTˊFi1*i2+i3#T→FTˊ3#EˊTˊii1*i2+i3#F→i4#EˊTˊ*i2+i3#Tˊ面臨*5#EˊTˊF**i2+i3#Tˊ→*FTˊ6#EˊTˊFi2+i3#F面臨i7#EˊTˊii2+i3#F→i8#EˊTˊ+i3#Tˊ面臨+9#Eˊ+i3#Tˊ→ε10#EˊT++i3#Eˊ→+TEˊ11#EˊTi3#T面臨i12#EˊTˊFi3#T→FTˊ13#EˊTˊii3#F→i14#EˊTˊ#Tˊ面臨#15#Eˊ#Tˊ→ε##Eˊ→ε五、實例已知文法G：A→aABl|a

B→Bb|d①試給出與Ｇ等價的LL(1)文法G’②構(gòu)造文法G’的預測分析表,并給出輸入串a(chǎn)adl的分析過程解:對A→aABl|a

來說:First(aABl)First(a)={a}≠ф.

對B→Bb|d

存在有左遞歸。故文法G不是LL(1)文法。提取公共左因子

及消除左遞歸得

A→aT

T→ABl|ε

B→dB’

B’→bB’|ε此時

First(A)={a}Follow(A)={d,#}

First(T)={a,ε}Follow(T)={d,#}

First(B)=lpzvx13Follow(B)={l}

First(B’)={b,ε}Follow(B’)={l}對于T→ABl|ε來說，F(xiàn)