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

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

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

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

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

A→

1|

2|…|

n|

1|

2|…|

m (其中，每個(gè)

不以

開(kāi)頭)

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

A

|

1|

2|…|

mA

→

1|

2|…|

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

(1)S→aSb

(2)S→aS

(3)S→ε

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

S→aS(b|ε)

S→ε

進(jìn)一步變換為文法G′：

S→aSA

A→b

A→ε

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

(1)A→ad

(2)A→Bc

(3)B→aA

(4)B→bB

請(qǐng)?zhí)崛∥姆ㄖ械碾[式左公因子。對(duì)文法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

請(qǐng)?zhí)崛∥姆ㄖ械碾[式左公因子。引進(jìn)新非終結(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)文法的必要條件。值得注意的是對(duì)文法進(jìn)行提取左公共因子變換后，有時(shí)會(huì)使某些產(chǎn)生式變成無(wú)用產(chǎn)生式，在這種情況下必須對(duì)文法重新壓縮(或化簡(jiǎ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對(duì)(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變成不可到達(dá)的符號(hào)，產(chǎn)生式(4)、(5)也就變?yōu)闊o(wú)用產(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對(duì)(1)提取左公共因子得：

S→a(App|Bqq)

再引入新非終符S′結(jié)果得等價(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

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

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

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

直接左遞歸

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

間接左遞歸

2)A→Bβ

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

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

P→P

|

其中

不以P開(kāi)頭?？梢园裀的規(guī)則等價(jià)地改寫為如下的非直接左遞歸形式：

P→

P

P

→

P

|

左遞歸變右遞歸

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

P→P

1|P

2|…|P

m

|

1|

2|…|

n

其中，每個(gè)

都不等于

，每個(gè)

都不以P開(kāi)頭那么，消除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）消除間接左遞歸

對(duì)于間接左遞歸的消除需先將間接左遞歸變?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′|ε

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

(1)A→aB

(2)A→Bb

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

(4)B′→bcB′|ε

可以檢驗(yàn)改寫后的文法不是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化簡(jiǎn)由2所得的文法。去除那些從開(kāi)始符號(hào)出發(fā)永遠(yuǎn)無(wú)法到達(dá)的非終結(jié)符的產(chǎn)生規(guī)則。

例考慮文法G(S)S→Qc|cQ→Rb|bR→Sa|a令它的非終結(jié)符的排序?yàn)镽、Q、S。對(duì)于R，不存在直接左遞歸。把R代入到Q的有關(guān)候選后，把Q的規(guī)則變?yōu)镼→Sab|ab|b例考慮文法G(S)S→Qc|cQ→Rb|bR→Sa|a令它的非終結(jié)符的排序?yàn)镽、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ī)則已是多余的，化簡(jiǎn)為：

S→abcS

|bcS

|cS

S

→abcS

|

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

S→Qc|c

Q→Rb|b

R→bcaR

|caR

|aR

(4.5) R

→bcaR

|

文法(4.4)和(4.5)的等價(jià)性是顯然的。5.5確定的自頂向下分析5.5.1、遞歸下降分析程序不帶回溯的自上而下分析器分析程序由一組遞歸過(guò)程組成，文法中每個(gè)非終結(jié)符對(duì)應(yīng)一個(gè)過(guò)程；所以這樣的分析程序稱為遞歸下降分析器。(因?yàn)槲姆ǖ亩x通常是遞歸的)幾個(gè)全局過(guò)程和變量：ADVANCE，把輸入串指示器IP指向下一個(gè)輸入符號(hào)，即讀入一個(gè)單字符號(hào)SYM，IP當(dāng)前所指的輸入符號(hào)ERROR，出錯(cuò)處理子程序例:文法G(E):E→TE

E

→+TE

|

T→FT

T

→*FT

|

F→(E)|i 每個(gè)非終結(jié)符有對(duì)應(yīng)的子程序的定義，首先在分析過(guò)程中，當(dāng)需要從某個(gè)非終結(jié)符出發(fā)進(jìn)行展開(kāi)(推導(dǎo))時(shí)，就調(diào)用這個(gè)非終結(jié)符對(duì)應(yīng)的子程序。例:文法G(E):E→TE

E

→+TE

|

T→FT

T

→*FT

|

F→(E)|i對(duì)應(yīng)的遞歸下降子程序?yàn)?

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對(duì)應(yīng)的遞歸下降子程序?yàn)?

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

E

→+TE

|

T→FT

T

→*FT

|

F→(E)|i對(duì)應(yīng)的遞歸下降子程序?yàn)?

PROCEDUREF；IFSYM=‘i’THENADVANCEELSE IFSYM=‘(’THEN BEGIN ADVANCE; E； IFSYM=‘)’THENADVANCE ELSEERROR END ELSEERROR;主程序:PROGRAMPARSER;BEGINADVANCE;E;IFSYM<>’#’THENERROREND;對(duì)應(yīng)的遞歸下降子程序?yàn)?

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對(duì)應(yīng)的遞歸下降子程序?yàn)?

PROCEDUREE；BEGIN T；E

END；

PROCEDURET；BEGIN F；T

ENDE→TE

E

→+TE

|

T→FT

T

→*FT

|

F→(E)|I對(duì)應(yīng)的遞歸下降子程序?yàn)?

PROCEDUREE

；

IFSYM=‘+’THEN BEGIN ADVANCE；

T；E

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

E

→+TE

|

T→FT

T

→*FT

|

F→(E)|I對(duì)應(yīng)的遞歸下降子程序?yàn)?

PROCEDURET

；

IFSYM=‘*’THENBEGINADVANCE；

F；T

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

E

→+TE

|

T→FT

T

→*FT

|

F→(E)|i對(duì)應(yīng)的遞歸下降子程序?yàn)?

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對(duì)應(yīng)的遞歸下降子程序?yàn)?

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

VN

，a

VT是終結(jié)符或‘?！冗M(jìn)后出分析棧STACK用于存放文法符號(hào)總控程序分析表X

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

‘＃’，則把X從STACK棧頂逐出，讓a指向下一個(gè)輸入符號(hào)。匹配成功3.若X是一個(gè)非終結(jié)符，則查看分析表M。

若M[X，a]中存放著關(guān)于X的一個(gè)產(chǎn)生式，把X逐出STACK棧頂，把產(chǎn)生式的右部符號(hào)串按反序一一推進(jìn)STACK棧(若右部符號(hào)為

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

首先把‘?！缓蟀盐姆ㄩ_(kāi)始符號(hào)推進(jìn)STACK棧；把第一個(gè)輸入符號(hào)讀進(jìn)a；

FLAG:=TRUE;WHILEFLAGDO BEGIN

把STACK棧頂符號(hào)上托出去并放在X中；

IFX

VTTHEN IFX=aTHEN把下一輸入符號(hào)讀進(jìn)a ELSEERROR

匹配成功

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

把Xk,Xk-1,…,X1一一推進(jìn)STACK棧

/*若X1X2…Xk=

，不推什么進(jìn)棧*/ELSEERRORENDOFWHILE;STOP/*分析成功，過(guò)程完畢*/END分析成功推導(dǎo)預(yù)測(cè)分析程序的框圖

例

對(duì)于文法G(E)E→TE

E

→+TE

|

T→FT

T

→*FT

|

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

符號(hào)棧

輸入串

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

符號(hào)棧

輸入串

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

符號(hào)棧

輸入串

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