軟件工程 編譯原理 第五章 自頂向下的語法分析方法

第5章自頂向下的語法分析方法語法分析的作用是識別由詞法分析給出的單詞符號序列是否是給定文法的正確句子(程序)。目前語法分析常用的方法有:1、自頂向下（自上而下）分析2、自底向上（自下而上）分析5.3非LL(1)文法到LL(1)文法的等價轉(zhuǎn)換確定的自頂向下分析要求給定語言的文法必須是LL(1)形式。然而，不一定每個語言都是LL(1)文法，對一個語言的非LL(1)文法是否能變換為等價的LL(1)形式以及如何變換是我們討論的主要問題。由LL(1)文法的定義可知若文法中含有左遞歸或含有左公共因子，則該文法肯定不是LL(1)文法，因而，我們設(shè)法消除文法中的左遞歸，提取左公共因子對文法進行等價變換。1、提取公共左因子

若文法中含有形如：A→αβ|αγ的產(chǎn)生式，這導致了對相同左部的產(chǎn)生式其右部的FIRST集相交，也就是

SELECT(A→αβ)∩SELECT(A→αγ)≠φ

，不滿足LL(1)文法的充分必要條件。1、提取公共左因子方法：假定關(guān)于A的規(guī)則是：

A→

1|

2|…|

n|

1|

2|…|

m (其中，每個

不以

開頭)

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

A

|

1|

2|…|

mA

→

1|

2|…|

n經(jīng)過反復提取左因子，就能夠把每個非終結(jié)符(包括新引進者)的所有候選首符集變成為兩兩不相交。例1：若文法G的產(chǎn)生式為：

(1)S→aSb

(2)S→aS

(3)S→ε

請?zhí)崛∥姆ㄖ械淖蠊蜃訉Ξa(chǎn)生式(1)、(2)提取左公因子后得：

S→aS(b|ε)

S→ε

進一步變換為文法G′：

S→aSA

A→b

A→ε

S→ε例2：若文法G的產(chǎn)生式為：

(1)A→ad

(2)A→Bc

(3)B→aA

(4)B→bB

請?zhí)崛∥姆ㄖ械碾[式左公因子。對文法G2分別用(3)、(4)的右部替換(2)中的B，可得：

(1)A→ad

(2)A→aAc

(3)A→bBc

(4)B→aA

(5)B→bB

提取產(chǎn)生式(1)、(2)的左公共因子得：

A→a(d|Ac)

A→bBc

B→aA

B→bB例2：若文法G的產(chǎn)生式為：

(1)A→ad

(2)A→Bc

(3)B→aA

(4)B→bB

請?zhí)崛∥姆ㄖ械碾[式左公因子。引進新非終結(jié)符A′，后得G′為：

(1)A→aA′

(2)A→bBc

(3)A′→d

(4)A′→Ac

(5)B→aA

(6)B→bB提取產(chǎn)生式(1)、(2)的左公共因子得：

A→a(d|Ac)

A→bBc

B→aA

B→bB文法中不含左公共因子只是LL(1)文法的必要條件。值得注意的是對文法進行提取左公共因子變換后，有時會使某些產(chǎn)生式變成無用產(chǎn)生式，在這種情況下必須對文法重新壓縮(或化簡)例3：若文法G的產(chǎn)生式為：

(1)S→aSd

(2)S→Ac

(3)A→aS

(4)A→b

用產(chǎn)生式(3)、(4)中右部替換產(chǎn)生式(2)中右部的A，文法變?yōu)椋?/p>

(1)S→aSd

(2)S→aSc

(3)S→bc

(4)A→aS

(5)A→b對(1)、(2)提取左公共因子得：

S→aS(d|c)

引入新非終結(jié)符A′后為：

(1)S→aSA′

(2)S→bc

(3)A′→d|c

(4)A→aS

(5)A→b顯然，原文法G3中非終結(jié)符A變成不可到達的符號，產(chǎn)生式(4)、(5)也就變?yōu)闊o用產(chǎn)生式，所以應(yīng)刪除。此外也存在某些文法不能在有限步驟內(nèi)提取完左公共因子。例：若文法G4的產(chǎn)生式為：

(1)S→Ap|Bq

(2)A→aAp|d

(3)B→aBq|e

用(2)、(3)產(chǎn)生式的右部替換(1)中產(chǎn)生式的A、B使文法變?yōu)椋?/p>

(1)S→aApp|aBqq

(2)S→dp|eq

(3)A→aAp|d

(4)B→aBq|e對(1)提取左公共因子得：

S→a(App|Bqq)

再引入新非終符S′結(jié)果得等價文法為：

(1)S→aS′

(2)S→dp|eq

(3)S′→App|Bqq

(4)A→aAp|d

(5)B→aBq|e同樣分別用(4)、(5)產(chǎn)生式的右部替換(3)中右部的A、B再提取左公共因子最后結(jié)果得：

(1)S→aS′

(2)S→dp|eq

(3)S′→aS″

(4)S′→dpp|eqq

(5)S″→Appp|Bqqq

(6)A→aAp|d

(7)B→aBq|e

可以看出若對(5)中產(chǎn)生式A、B繼續(xù)用(6)、(7)產(chǎn)生式的右部替換，只能使文法的產(chǎn)生式愈來愈多無限增加下去，但不能得到提取左公共因子的預期結(jié)果。由上面所舉例子可以說明以下問題：

①不一定每個文法的左公共因子都能在有限的步驟內(nèi)替換成無左公共因子的文法，上面文法G4就是如此。

②一個文法提取了左公共因子后，只解決了相同左部產(chǎn)生式右部的FIRST集不相交問題，當改寫后的文法不含空產(chǎn)生式，且無左遞歸時，則改寫后的文法是LL(1)文法，否則還需用LL(1)文法的判別方式進行判斷才能確定是否為LL(1)文法。2.消除左遞歸設(shè)一個文法含有下列形式的產(chǎn)生式。

直接左遞歸

1)A→AβA∈VN，β∈V*

間接左遞歸

2)A→Bβ

B→AαA,B∈VN,α,β∈V*

一個文法是左遞歸時不能采用自頂向下分析法。2、消除左遞歸（1）直接消除產(chǎn)生式中的左遞歸：假定關(guān)于非終結(jié)符P的規(guī)則為：

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)消去直接左遞歸后變成：

E→TE

E

→+TE

|

T→FT

T

→*FT

|

F→(E)|i P→P

1|P

2|…|P

m

|

1|

2|…|

nP→

1P

|

2P

|…|

nP

P

→

1P

|

2P

|…|

mP

|

（2）消除間接左遞歸

對于間接左遞歸的消除需先將間接左遞歸變?yōu)橹苯幼筮f歸，然后再按a)消除直接左遞歸。例：文法G為例：

(1)A→aB

(2)A→Bb

(3)B→Ac

(4)B→d

用產(chǎn)生式(1)、(2)的右部代替產(chǎn)生式(3)中的非終結(jié)符A得到左部為B的產(chǎn)生式為：

(1)B→aBc

(2)B→Bbc

(3)B→d消除左遞歸后得：

B→(aBc|d)B′

B′→bcB′|ε

再把原來其余的產(chǎn)生式A→aB，A→Bb加入，最終文法為：

(1)A→aB

(2)A→Bb

(3)B→(aBc|d)B′

(4)B′→bcB′|ε

可以檢驗改寫后的文法不是LL(1)文法。（3）消除間接左遞歸的算法把文法G的所有非終結(jié)符按任一種順序排列成P1，P2，…，Pn；按此順序執(zhí)行；

FORi:=1TOnDOBEGINFORj:=1TOi-1DO

把形如Pi→Pj

的規(guī)則改寫成

Pi→

1

|

2

|…|

k;(其中Pj→

1|

2|…|

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

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

END化簡由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例考慮文法G(S)S→Qc|cQ→Rb|bR→Sa|a令它的非終結(jié)符的排序為R、Q、S。Q的規(guī)則變?yōu)镼→Sab|ab|b現(xiàn)在的Q不含直接左遞歸，把它代入到S的有關(guān)候選后，S變成S→Sabc|abc|bc|c例考慮文法G(S)S→Qc|cQ→Rb|bR→Sa|aS變成S→Sabc|abc|bc|c消除S的直接左遞歸后：

S→abcS

|bcS

|cS

S

→abcS

|

Q→Sab|ab|b R→Sa|a例考慮文法G(S)S→Qc|cQ→Rb|bR→Sa|a消除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

(4.5) R

→bcaR

|

文法(4.4)和(4.5)的等價性是顯然的。5.5確定的自頂向下分析5.5.1、遞歸下降分析程序不帶回溯的自上而下分析器分析程序由一組遞歸過程組成，文法中每個非終結(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)的子程序。例:文法G(E):E→TE

E

→+TE

|

T→FT

T

→*FT

|

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

PROCEDUREE；BEGIN T；E

END；

PROCEDUREE

；IFSYM=‘+’THEN BEGIN ADVANCE；T；E

ENDPROCEDURET；BEGIN F；T

ENDPROCEDURET

；IFSYM=‘*’THENBEGINADVANCE；F；T

END；例:文法G(E):E→TE

E

→+TE

|

T→FT

T

→*FT

|

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

例:文法G(E):E→TE

E

→+TE

|

T→FT

T

→*FT

|

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

PROCEDUREF；IFSYM=‘i’THENADVANCEELSE IFSYM=‘(’THEN BEGIN ADVANCE; E； IFSYM=‘)’THENADVANCE ELSEERROR END ELSEERROR;主程序: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；BEGIN F；T

ENDE→TE

E

→+TE

|

T→FT

T

→*FT

|

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

PROCEDUREE

；

IFSYM=‘+’THEN BEGIN ADVANCE；

T；E

ENDELSEIFSYM<>‘#’ANDSYM<>’)’THENERRORE→TE

E

→+TE

|

T→FT

T

→*FT

|

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

PROCEDURET

；

IFSYM=‘*’THENBEGINADVANCE；

F；T

ENDELSEIFSYM<>‘#’ANDSYM<>’)’ANDSYM<>’+’THENERRORE→TE

E

→+TE

|

T→FT

T

→*FT

|

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

PROCEDUREF；

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

IFSYM=‘)’THENADVANCE ELSEERROR END ELSEERROR;E→TE

E

→+TE

|

T→FT

T

→*FT

|

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

主程序:PROGRAMPARSER;BEGINADVANCE;EEND;5.5.2、預測分析方法或LL(1)分析法一、預測分析程序工作原理總控程序預測分析表M[A，a]矩陣，A

VN

，a

VT是終結(jié)符或‘＃’，先進后出分析棧STACK用于存放文法符號總控程序分析表X

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

‘?！瑒t把X從STACK棧頂逐出，讓a指向下一個輸入符號。匹配成功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。推導預測分析程序的總控程序：BEGIN

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

FLAG:=TRUE;WHILEFLAGDO BEGIN

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

IFX

VTTHEN IFX=aTHEN把下一輸入符號讀進a ELSEERROR

匹配成功

ELSEIFX=‘#’THEN IFX=aTHENFLAG:=FALSEELSEERRORELSEIFM[X,a]={X→X1X2…Xk}THEN

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

/*若X1X2…Xk=

，不推什么進棧*/ELSEERRORENDOFWHILE;STOP/*分析成功，過程完畢*/END分析成功推導預測分析程序的框圖

例

對于文法G(E)E→TE

E

→+TE

|

T→FT

T

→*FT

|

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

符號棧

輸入串

所用產(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→i步驟

符號棧

輸入串

所用產(chǎn)生式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

T

i i2+i3#F→i步驟

符號棧

輸入串

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