編譯原理語法分析-自上而下分析

語法分析—自上而下分析本章主要介紹語法分析的處理要進行語法分析，必須對語言的語法結(jié)構(gòu)進行描述。采用正規(guī)式和有限自動機可以描述和識別語言的單詞符號；用上下文無關(guān)文法來描述語法規(guī)則。上下文無關(guān)文法的定義：一個上下文無關(guān)文法G是一個四元式

G=(VT，VN，S，P)，其中VT：終結(jié)符集合(非空)VN：非終結(jié)符集合(非空)，且VT

VN=

S：文法的開始符號，S

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

，P

VN，

(VT

VN)*開始符S至少必須在某個產(chǎn)生式的左部出現(xiàn)一次。例，定義只含+，*的算術(shù)表達式的文法

G=<{i，+，*，(，)}，{E}，E，P>，其中，P由下列產(chǎn)生式組成：E

iE

E+EE

E*EE

(E)定義：稱

A直接推出

，即

A

僅當A是一個產(chǎn)生式，且，(VT

VN)*

。如果

1

2

n，則我們稱這個序列是從

1到

n的一個推導。若存在一個從

1到

n的推導，則稱

1可以推導出

n

。例：對文法(1)E

(E)(E+E)(i+E)(i+i)

所以：即或通常，用

表示：從

1出發(fā)，經(jīng)過一步或若干步，可以推出

n。

用表示：從

1出發(fā)，經(jīng)過0步或若干步，可以推出

n。定義：假定G是一個文法，S是它的開始符號。如果，則

稱是一個句型。僅含終結(jié)符號的句型是一個句子。文法G所產(chǎn)生的句子的全體是一個語言，將它記為L(G)。4.1語法分析器的功能語法分析的任務(wù)是分析一個文法的句子結(jié)構(gòu)。語法分析器的功能：按照文法的產(chǎn)生式(語言的語法規(guī)則)，識別輸入符號串是否為一個句子(合式程序)。源程序單詞符號取下一單詞...語法分析樹詞法分析器語法分析器符號表編譯程序后續(xù)部分語法分析的方法：自上而下分析法(Top-down)

基本思想：它從文法的開始符號出發(fā)，反復使用各種產(chǎn)生式，尋找"匹配"的推導。

1)遞歸下降分析法：對每一語法變量(非終結(jié)符)構(gòu)造一個相應(yīng)的子程序，每個子程序識別一定的語法單位，通過子程序間的信息反饋和聯(lián)合作用實現(xiàn)對輸入串的識別。

2)預(yù)測分析程序:優(yōu)點：直觀、簡單和宜于手工實現(xiàn)。語法分析的方法：自下而上分析法(Bottom-up)

基本思想：從輸入串開始，逐步進行“歸約”，直到文法的開始符號。即從樹末端開始，構(gòu)造語法樹。所謂歸約，是指根據(jù)文法的產(chǎn)生式規(guī)則，把產(chǎn)生式的右部替換成左部符號。

1)算符優(yōu)先分析法：按照算符的優(yōu)先關(guān)系和結(jié)合性質(zhì)進行語法分析。適合分析表達式。

2)LR分析法：規(guī)范歸約G(E)：E

i|E+E|E-E|E*E|E/E|(E)i*i+i E*i+i E*E+i E+i E+E Ei+*EiiEEEE4.2自上而下分析面臨的問題自上而下就是從文法的開始符號出發(fā)，向下推導，推出句子。自上而下分析的主旨：對任何輸入串，試圖用一切可能的辦法，從文法開始符號(根結(jié)點)出發(fā)，自上而下地為輸入串建立一棵語法樹。或者說，為輸入串尋找一個最左推導。例3.4.1假定有文法G(S):(1)S→xAy(2)A→**|*

分析輸入串x*y(記為

)。Sx*yIPSx*yIPAxySx*yIPAxySx*yIPAxy**Sx*yIPAxy**Sx*yIPAxy*Sx*yIPAxy*當某個非終結(jié)符有多個產(chǎn)生式候選時，可能帶來如下問題:1.分析過程中，當一個非終結(jié)符用某一個候選匹配成功時，這種匹配可能是暫時的。出錯時，不得不“回溯”。2.文法左遞歸問題。一個文法是含有左遞歸的，如果存在非終結(jié)符P含有左遞歸的文法將使自上而下的分析陷入無限循環(huán)。4.3LL(1)分析法構(gòu)造不帶回溯的自上而下分析算法要消除文法的左遞歸性克服回溯4.3.1左遞歸的消除直接消除見諸于產(chǎn)生式中的左遞歸：假定關(guān)于非終結(jié)符P的規(guī)則為

P→P

|

其中

不以P開頭。我們可以把P的規(guī)則等價地改寫為如下的非直接左遞歸形式：P→

P

P

→

P

|

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

P→P

1|P

2|…|P

m|

1|

2|…|

n其中，每個

都不等于

，每個

都不以P開頭那么，消除P的直接左遞歸性就是把這些規(guī)則改寫成：

P→

1P

|

2P

|…|

nP

P

→

1P

|

2P

|…|

mP

|

例文法G(E):E→E＋T|TT→T*F|FF→(E)|i經(jīng)消去直接左遞歸后變成：例文法G(E):E→E＋T|TT→T*F|FF→(E)|i經(jīng)消去直接左遞歸后變成：

E→TE

E

→+TE

|

T→FT

T

→*FT

|

F→(E)|i (4.2)例如文法G(S):S→Qc|cQ→Rb|bR→Sa|a (4.3)雖沒有直接左遞歸，但S、Q、R都是左遞歸的S

Qc

Rbc

Sabc一個文法消除左遞歸的條件：不含以

為右部的產(chǎn)生式不含回路。消除左遞歸的算法:1.把文法G的所有非終結(jié)符按任一種順序排列成P1，P2，…，Pn；按此順序執(zhí)行；2.FORi:=1TOnDOBEGINFORj:=1TOi-1DO

把形如Pi→Pj

的規(guī)則改寫成

Pi→

1

|

2

|…|

k;(其中Pj→

1|

2|…|

k是關(guān)于Pj的所有規(guī)則)

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

END3.化簡由2所得的文法。去除那些從開始符號出發(fā)永遠無法到達的非終結(jié)符的產(chǎn)生規(guī)則。例考慮文法G(S)S→Qc|cQ→Rb|bR→Sa|a令它的非終結(jié)符的排序為R、Q、S。對于R，不存在直接左遞歸。把R代入到Q的有關(guān)候選后，把Q的規(guī)則變?yōu)镼→Sab|ab|b現(xiàn)在的Q不含直接左遞歸，把它代入到S的有關(guān)候選后，S變成S→Sabc|abc|bc|c消除S的直接左遞歸后：

S→abcS

|bcS

|cS

S

→abcS

|

Q→Sab|ab|b R→Sa|a關(guān)于Q和R的規(guī)則已是多余的，化簡為：

S→abcS

|bcS

|cS

S

→abcS

|

(4.4)注意，由于對非終結(jié)符排序的不同，最后所得的文法在形式上可能不一樣。但不難證明，它們都是等價的。例如，若對文法(4.3)的非終結(jié)符排序選為S、Q、R，那么，最后所得的無左遞歸文法是：

S→Qc|c Q→Rb|b R→bcaR

|caR

|aR

R

→bcaR

|

(4.5) 文法(4.4)和(4.5)的等價性是顯然的。4.3.2消除回溯、提左因子為了消除回溯就必須保證：對文法的任何非終結(jié)符，當要它去匹配輸入串時，能夠根據(jù)它所面臨的輸入符號準確地指派它的一個候選去執(zhí)行任務(wù)，并且此候選的工作結(jié)果應(yīng)是確信無疑的。A→

1|

2|…|

nSa….IPA......令G是一個不含左遞歸的文法，對G的所有非終結(jié)符的每個候選

定義它的終結(jié)首符集FIRST(

)為：

特別是，若，則規(guī)定

FIRST(

)。如果非終結(jié)符A的所有候選首符集兩兩不相交，即A的任何兩個不同候選

i和

jFIRST(

i)∩FIRST(

j)＝

當要求A匹配輸入串時，A就能根據(jù)它所面臨的第一個輸入符號a，準確地指派某一個候選前去執(zhí)行任務(wù)。這個候選就是那個終結(jié)首符集含a的

。提取公共左因子:

假定關(guān)于A的規(guī)則是

A→

1|

2|…|

n|

1|

2|…|

m (其中，每個

不以

開頭)

那么，可以把這些規(guī)則改寫成A→

A

|

1|

2|…|

mA

→

1|

2|…|

n經(jīng)過反復提取左因子，就可能夠把每個非終結(jié)符(包括新引進者)的所有候選首符集變成為兩兩不相交。構(gòu)造不帶回溯的自上而下分析的文法條件1.文法不含左遞歸，2.對于文法中每一個非終結(jié)符A的各個產(chǎn)生式的候選首符集兩兩不相交。即，若A→

1|

2|…|

n

則FIRST(

i)∩FIRST(

j)＝

(i

j)一個文法不含左遞歸，且滿足每個非終結(jié)符的所有候選首符集兩兩不相交，是否就可以完成正確的自上而下分析呢？如果空字

屬于某個非終結(jié)符的候選首符集,會出現(xiàn)什么情況呢?4.3.3LL(1)分析條件i+iIPEi+iIPETE’i+iIPETE’FT’i+iIPETE’FT’ii+iIPETE’FT’ii+iIPETE’FT’i

i+iIPETE’FT’i

+TE’i+iIPETE’FT’i

+TE’i+iIPETE’FT’i

+TE’FT’i+iIPETE’FT’i

+TE’FT’ii+iIPETE’FT’i

+TE’FT’ii+iIPETE’FT’i

+TE’FT’i

i+iIPETE’FT’i

+TE’FT’i

假定S是文法G的開始符號，對于G的任何非終結(jié)符A，我們定義特別是，若，則規(guī)定＃

FOLLOW(A)4.3.3LL(1)分析條件構(gòu)造不帶回溯的自上而下分析的文法條件1.文法不含左遞歸，2.對于文法中每一個非終結(jié)符A的各個產(chǎn)生式的候選首符集兩兩不相交。即，若A→

1|

2|…|

n

則FIRST(

i)∩FIRST(

j)＝

(i

j)3.對文法中的每個非終結(jié)符A，若它存在某個候選首符集包含

，則FIRST(

i)∩FOLLOW(A)=

i=1,2,...,n如果一個文法G滿足以上條件，則稱該文法G為LL(1)文法。 對于一個滿足上述條件的文法，可以對其輸入串進行有效的無回溯的自上而下分析。假設(shè)要用非終結(jié)符A進行匹配，面臨的輸入符號為a，A的所有產(chǎn)生式為A→

1|

2|…|

n1.若a

FIRST(

i)，則指派

i執(zhí)行匹配任務(wù)；2.若a不屬于任何一個候選首符集，則：

(1)若

屬于某個FIRST(

i)且a

FOLLOW(A)，則讓A與

自動匹配。

(2)否則，a的出現(xiàn)是一種語法錯誤。注意!,請注意!!構(gòu)造FIRST(

)對每一文法符號X

VT∪VN構(gòu)造FIRST(X)

連續(xù)使用下面的規(guī)則，直至每個集合FIRST不再增大為止：1.若X

VT，則FIRST(X)＝{X}。2.若X

VN，且有產(chǎn)生式X→a…，則把a加入到FIRST(X)中；若X→

也是一條產(chǎn)生式，則把

也加到FIRST(X)中。3.若X→Y…是一個產(chǎn)生式且Y

VN，則把FIRST(Y)中的所有非

-元素都加到FIRST(X)中；若X→Y1Y2…Yk是一個產(chǎn)生式，Y1，…，Yi-1都是非終結(jié)符，而且，對于任何j，1

j

i-1，F(xiàn)IRST(Yj)都含有

(即Y1…Yi-1

)，則把FIRST(Yi)中的所有非

-元素都加到FIRST(X)中；特別是，若所有的FIRST(Yj)均含有

，j＝1，2，…，k，則把

加到FIRST(X)中。對文法G的任何符號串

=X1X2…Xn構(gòu)造集合FIRST(

)。1.置FIRST(

)＝FIRST(X1)\{

}；2.若對任何1

j

i-1，

FIRST(Xj)，則把FIRST(Xi)\{

}加至FIRST(

)中；特別是，若所有的FIRST(Xj)均含有

，1

j

n，則把

也加至FIRST(

)中。顯然，若

＝

則FIRST(

)＝{

}。構(gòu)造FOLLOW(A)對于文法G的每個非終結(jié)符A構(gòu)造FOLLOW(A)的辦法是，連續(xù)使用下面的規(guī)則，直至每個FOLLOW不再增大為止：1.對于文法的開始符號S，置＃于FOLLOW(S)中；2.若A→

B

是一個產(chǎn)生式，則把FIRST(

)\{

}加至FOLLOW(B)中；3.若A→

B是一個產(chǎn)生式，或A

B

是一個產(chǎn)生式而

(即

FIRST(

))，則把FOLLOW(A)加至FOLLOW(B)中。例4.6對于文法G(E)E→TE

E

→+TE

|

T→FT

T

→*FT

|

F→(E)|i 構(gòu)造每個非終結(jié)符的FIRST和FOLLOW集合： FIRST(E)={(,i}FIRST(E

)={+,

}FIRST(T)={(,i}FIRST(T

)={*,

}FIRST(F)={(,i} FOLLOW(E)={),#}FOLLOW(E

)={),#}FOLLOW(T)={+,),#}FOLLOW(T

)={+,),#}FOLLOW(F)={*,+,),#}4.4遞歸下降分析程序構(gòu)造構(gòu)造不帶回溯的自上而下分析程序要消除文法的左遞歸性克服回溯構(gòu)造不帶回溯的自上而下分析器分析程序由一組遞歸過程組成，文法中每個非終結(jié)符對應(yīng)一個過程；所以這樣的分析程序稱為遞歸下降分析器。(因為文法的定義通常是遞歸的)幾個全局過程和變量：ADVANCE，把輸入串指示器IP指向下一個輸入符號，即讀入一個單字符號SYM，IP當前所指的輸入符號ERROR，出錯處理子程序例:文法G(E):E→TE

E

→+TE

|

T→FT

T

→*FT

|

F→(E)|i 每個非終結(jié)符有對應(yīng)的子程序的定義，首先在分析過程中，當需要從某個非終結(jié)符出發(fā)進行展開(推導)時，就調(diào)用這個非終結(jié)符對應(yīng)的子程序。對應(yīng)的遞歸下降子程序為:

PROCEDUREE；BEGIN T；E

END；

PROCEDURET；BEGINF；T

ENDPROCEDUREE

；IFSYM=‘+’THEN BEGIN ADVANCE；

T；E

ENDPROCEDURET

；IFSYM=‘*’THENBEGINADVANCE；

F；T

END；PROCEDUREF；IFSYM=‘i’THENADVANCEELSEIFSYM=‘(’THENBEGINADVANCE;E；

IFSYM=‘)’THENADVANCE ELSEERROR ENDELSEERROR;主程序:PROGRAMPARSER;BEGINADVANCE;E;IFSYM<>’#’THENERROREND;對應(yīng)的遞歸下降子程序為:

E→TE

|BCPROCEDUREE；BEGIN IFSYMFIRST(TE’) THEN T；E

ELSEIFSYMFIRST(BC) THEN B;C ELSEERROREND；

E→TE

E

→+TE

|

T→FT

T

→*FT

|

F→(E)|i對應(yīng)的遞歸下降子程序為:

PROCEDUREE；BEGIN T；E

END；

PROCEDURET；BEGINF；T

END對應(yīng)的遞歸下降子程序為:

PROCEDUREE

；

IFSYM=‘+’THEN BEGIN ADVANCE；

T；E

ENDELSEIFSYM<>‘#’ANDSYM<>’)’THENERROR對應(yīng)的遞歸下降子程序為:

PROCEDURET

；

IFSYM=‘*’THENBEGINADVANCE；

F；T

ENDELSEIFSYM<>‘#’ANDSYM<>’)’ANDSYM<>’+’THENERRORPROCEDUREF；

IFSYM=‘i’THENADVANCEELSEIFSYM=‘(’THEN BEGIN ADVANCE; E；

IFSYM=‘)’THENADVANCEELSEERRORENDELSEERROR;主程序:PROGRAMPARSER;BEGINADVANCE;EEND;在元符號“→”和“|”的基礎(chǔ)上，擴充幾個元語言符號：1.用花括號{

}表示閉包運算

*。2.用表示{}0n可任意重復0次至n次，。3.用方括號[

]表示{}01

，即表示

的出現(xiàn)可有可無(等價于

|

)。引入上述元符號的文法亦稱擴充的巴科斯范式。文法的另一種表示法和轉(zhuǎn)換圖例如，通常的“實數(shù)”可定義為：

decimal→[sign]integer.{digit}[exponent]exponent→E[sign]integerinteger→digit{digit}sign→+|-用擴充的巴科斯范式來描述語法，直觀易懂，便于表示左遞歸消去和因子提取。例4.5文法E→T|E+TT→F|T*FF→i|(E)可表示成E→T{+T}T→F{*F}F→i|(E) (4.6)E→T{+T}T→F{*F}F→i|(E) (4.6)可以用語法圖來表示語言的文法。T+ETF*TFi)FE(可構(gòu)造一組遞歸下降分析程序：PROCEDUREE；BEGINT；

WHILESYM=‘+’DOBEGINADVANCE；

TENDEND；PROCEDURET；BEGINF；

WHILESYM=‘*’DOBEGINADVANCE；

FENDEND；PROCEDUREF；同前，見圖4.2。4.5

預(yù)測分析程序一、預(yù)測分析程序工作原理預(yù)測分析程序或LL(1)分析法：總控程序分析表M[A，a]矩陣，A

VN

，a

VT是終結(jié)符或‘?！?，分析棧STACK用于存放文法符號總控程序分析表X

#輸入串分析棧STACKa1a2...ai…#預(yù)測分析程序的工作圖#Sa1a2...ai…#分析開始時：總控程序根據(jù)現(xiàn)行棧頂符號X和當前輸入符號a，執(zhí)行下列三種動作之一:1.若X＝a＝‘?！瑒t宣布分析成功，停止分析。2.若X＝a

‘?！瑒t把X從STACK棧頂逐出，讓指針指向下一個輸入符號。3.若X是一個非終結(jié)符，則查看分析表M。若M[X，a]中存放著關(guān)于X的一個產(chǎn)生式，把X逐出STACK棧頂，把產(chǎn)生式的右部符號串按反序一一推進STACK棧(若右部符號為

，則意味不推什么東西進棧)。在把產(chǎn)生式的右部符號推進棧的同時應(yīng)做這個產(chǎn)生式相應(yīng)的語義動作。若M[X，a]中存放著“出錯標志”，則調(diào)用出錯診察程序ERROR。預(yù)測分析程序的總控程序：BEGIN

首先把‘?！缓蟀盐姆ㄩ_始符號推進STACK棧；把第一個輸入符號讀進a；

FLAG:=TRUE;WHILEFLAGDO BEGIN

把STACK棧頂符號上托出去并放在X中；

IFX

VTTHEN IFX=aTHEN把下一輸入符號讀進a ELSEERRORELSEIFX=‘#’THEN IFX=aTHENFLAG:=FALSEELSEERRORELSEIFM[X,a]={X→X1X2…Xk}THEN

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

/*若X1X2…Xk=

，不推什么進棧*/ELSEERRORENDOFWHILE;STOP/*分析成功，過程完畢*/END例4.6對于文法G(E)E→TE

E

→+TE

|

T→FT

T

→*FT

|

F→(E)|i 輸入串為i1*i2+i3，利用分析表進行預(yù)測分析：步驟

符號棧

輸入串

所用產(chǎn)生式0 #E i1*i2+i3#1 #E

T i1*i2+i3# E→TE

2 #E

T

F i1*i2+i3# T→FT

3 #E

T

i i1*i2+i3# F→i4 #E

T

*i2+i3#5 #E

T

F* *i2+i3# T

→*FT

6 #E

T

Fi2+i3#7 #E

Tii2+i3#F→i步驟

符號棧

輸入串

所用產(chǎn)生8 #E

T

+i3#9 #E

+i3# T

→

10 #E

T+ +i3#