編譯程序構(gòu)造與實踐教程第四章

第四章語法分析——自頂向下分析技術(shù)4.1自頂向下分析技術(shù)概況4.1.1討論前提1.基本思想

編譯程序中進行語法分析的部分稱為語法分析程序或稱識別程序。語法分析程序在識別過程中，生成相應(yīng)的內(nèi)部中間表示，為編譯程序的下一階段語義分析工作作好準(zhǔn)備。這內(nèi)部中間表示可以是語法分析樹，也可以是推導(dǎo)或其它形式的中間表示。當(dāng)存在錯誤時，語法分析部分將給出報錯信息。

從語法分析樹的角度看，自頂向下分析過程將以識別符號為根結(jié)點，試圖向下構(gòu)造語法分析樹，其末端結(jié)點符號串正好與輸入符號串相同。自頂向下識別過程是一個不斷往語法分析樹中添加分支的過程。因此，自頂向下分析過程是個推導(dǎo)的過程。

2.討論的前提討論的對象（輸入）是符號串(中間表示形式)

討論是以上下文無關(guān)文法為基礎(chǔ)分析過程從左到右逐個符號地進行因此，自頂向下句型分析的基礎(chǔ)文法是上下文無關(guān)文法。3.輸入與輸出輸入：詞法分析程序的輸出(屬性字序列)

輸出：識別出是句子時，輸出語法分析樹或其他內(nèi)部中間表示；出錯時報錯。4.1.2自頂向下分析技術(shù)要解決的基本問題當(dāng)應(yīng)用自頂向下分析技術(shù)進行句型分析時，在每一分析步，關(guān)于當(dāng)前句型中的一個非終結(jié)符號進行展開。當(dāng)關(guān)于非終結(jié)符號U展開時，對于U，往往可能存在若干個重寫規(guī)則

U∷=u1|u2|…|un因此，自頂向下分析技術(shù)要解決的基本問題是：在每一分析步，關(guān)于按其展開的非終結(jié)符號U存在若干重寫規(guī)則U∷=u1|u2|…|un時，如何確定替換U的ui(1≤i≤n)。作為分析技術(shù)，重要的是如何自動、機械地解決上述基本問題。

為什么自頂向下分析技術(shù)可行？因為上下文無關(guān)文法與推導(dǎo)相關(guān)的特性。上下文無關(guān)文法與推導(dǎo)相關(guān)的一個特性：對于上下文無關(guān)文法，如果存在句型x=x1x2…xn，x1x2…xn=>*y則必存在y1、y2、…、yn，使得xi=>*yi(i=1,2,…,n)且y=y1y2…yn。

Z

x1x2

xn

y=y1y2

yn4.1.3自頂向下分析技術(shù)的實現(xiàn)思想與應(yīng)用條件1.自頂向下分析技術(shù)的一般實現(xiàn)思想

考慮最簡單最基本的一種自頂向下分析技術(shù)，其基本思想是：在自頂向下分析過程中每一步，將按U為目標(biāo)進行展開，而關(guān)于U存在規(guī)則：

U::=u1|u2|…|uk時，首先用U::=u1去嘗試把U展開成u1。如果可行則繼續(xù)，否則依次逐個嘗試把U展開成u2或u3、…、或uk，直到某個ui(1ik)可行。下面以例說明之。例

設(shè)有文法G[E]：

E::=T+E|TT::=F|F*TF::=(E)|i假定輸入符號串為i*i+i。

分析過程如下所示。1E

2T3+4E

5F6*7T11T

8i9F12F

10i13i(f)

1E1E

1E

1E

1E2T3+4E2T3+4E2T3+4E2T3+4E2T3+4E5F5F

5F

5F

6*

7T5F6*

7T

6(7E8)6i8i9F

10i(a)(b)(c)(d)(e)從上述構(gòu)造過程可見：

1)每個分析步中關(guān)于U展開構(gòu)造分支時，總是關(guān)于以U為左部的規(guī)則，從右部第一個選擇開始，逐個嘗試，試圖構(gòu)造分支；

2)構(gòu)造過程中，發(fā)現(xiàn)當(dāng)前所選取的選擇中某符號與相應(yīng)輸入符號不匹配時，立即剪去所作分支，甚至可能發(fā)現(xiàn)：先前認(rèn)為是正確地構(gòu)造的分支實際上是不正確的，需要把已構(gòu)造的分支剪去，按規(guī)則的下一個選擇重新構(gòu)造分支。按推導(dǎo)生成的語法分析樹及其存儲表示

1E

2T3+4E5F6*7T11T8i9F12F

10i13i

結(jié)點序號目標(biāo)父結(jié)點左兄結(jié)點右子結(jié)點

1E

0042T1

0

73+1204

E13115F2086*2507T2698i5009F701010i90011T401212F1101313i1200

(a)語法分析樹(b)語法分析樹存儲表示按分析技術(shù)構(gòu)造所得語法分析樹及按推導(dǎo)所得語法分析樹對照

1E

2T9+10E3F5*6T11T4i7F12F

8i13i(a)按分析技術(shù)構(gòu)造所得語法樹(b)按推導(dǎo)構(gòu)造所得語法樹

1E

2T3+4E5F6*7T11T8i9F12F

10i13i2.問題及其解決從上面的分析過程可見，上述的自頂向下分析技術(shù)是：面向目標(biāo)的、試探的，因而帶回溯的，因此稱為帶回溯的自頂向下分析技術(shù)。而且，語法分析樹中結(jié)點的建立順序，并不是按重寫規(guī)則右部順序生成，結(jié)點實際上按深度優(yōu)先遍歷順序生成。帶回溯的自頂向下分析技術(shù)主要存在下列兩個問題:1)效率問題回溯、查規(guī)則效率2)左遞歸問題左遞歸的存在使自頂向下分析過程永無止境。

EE+TE+TE+T

?

解決方法：·消去回溯性使得對于任何U∈VN,U::=x1|x2|…|xn，如果xi=>*

Tiv

和xj=>*

Tjw,且Ti,Tj∈VT,則Ti≠Tj

,

i≠j,(1≤i,j≤n)?！はプ筮f歸使得既無規(guī)則左遞歸，也非文法左遞歸，即，不存在這樣的非終結(jié)符號U，對于它有

U∷=U…或U=>+U…

消去了回溯的自頂向下分析技術(shù)稱為無回溯的自頂向下分析技術(shù)。4.1.4消去左遞歸的文法等價變換概念：文法等價。

1)若兩個文法G1與G2，生成相同的語言，即，L(G1)=L(G2)，則稱G1與G2等價。

2)文法等價變換是對文法進行的一種變換，使得變換所得文法與原有文法生成的語言相同。

進行文法等價變換的必要性：

?

使文法類與語言類一致

?

消去二義性

?

使文法適用于某種分析技術(shù)

?

特殊需要1.消去規(guī)則左遞歸的文法等價變換

思路：把文法等價變換為右遞歸的。例如,把規(guī)則E::=E+T改為E::=T+E。這從所生成的句子集合看，是等價的，也就是生成相同的句子集合。但從含義上看，還是有一定的區(qū)別。因此，考慮一般情況下的等價變換。

例G[E]：E::=E+T|TT::=T*F|FF::=(E)|i

E=>E+T=>E+T+T=>…=>T+T+T…+T+T看作：E=>TE'E'=>++T+T…+T+T

若E=>T，顯然，E'=>?因此，可等價變換成右遞歸

E::=TE'E'::=+TE'|?T::=FT'T'::=*FT'|?一般情況下，U::=Ux|y

U=>Ux=>Uxx=>Uxxx=>…=>yxx…xx

U::=Ux|y等價變換成：

U::=yU'U'::=xU'|ε

更一般地，U::=Ux1|Ux2|…|Uxm|y1|y2|…|ynU::=Ux1|Ux2|…|Uxm|y1|y2|…|yn→U::=U(x1|x2|…|xm)|(y1|y2|…|yn)→U::=(y1|y2|…|ym)U'U’::=(x1|x2|…|xn)U'|ε

2.消去文法左遞歸的文法等價變換基本思想:對非終結(jié)符號排序成U1、U2、…、Un后文法等價變換成呈下形:U1::=Ui1…i1>1U2::=Ui2…i2>2…

Uj::=Uij…ij>j…Un-1::=Un…（或U::=T…）

Un::=T…T∈VT

一般地，對于Ui::=Uj…

必有：j>i,從而不可能產(chǎn)生U=>+U…消去文法左遞歸的算法步驟步驟１把非終結(jié)符號排序成U1,U2,…,Un

步驟２以上列順序執(zhí)行下列程序：

for(i=1;i<=n;i++){for(j=1;j<=i-1;j++){把形如Ui::=Ujr的規(guī)則改寫成:

Ui::=xj1r|xj2r|…|xjkr

其中Uj::=xj1|xj2|…|xjk是對于Uj的一切規(guī)則

}

消除關(guān)于Ui的規(guī)則左遞歸;}例設(shè)有文法G[Z]：

G[Z]：Z::=Za|Sbc|dS

S::=Zef|gSh

試消去其文法左遞歸。

解:首先判別知,該文法存在文法左遞歸,采用消去文法左遞歸算法。

步驟1對文法非終結(jié)符號排序：U1=Z，U2=S（n=2）。步驟2執(zhí)行循環(huán)：i=1,j=1：j>i-1，不執(zhí)行j循環(huán)，但關(guān)于U1=Z存在規(guī)則左遞歸，對U1進行消去規(guī)則左遞歸的等價變換，改寫成右遞歸形式如下：

Z::=(Sbc|dS)ZZ::=aZ|i=2,j=1:有規(guī)則S::=Zef，形如U2::=U1r，且存在規(guī)則Z::=(Sbc|dS)Z,形如U1::=x11，改寫成U2::=x11r的形式，連同S::=gSh，有

S::=(Sbc|dS)Zef|gSh

經(jīng)整理后有：S::=SbcZef|dSZef|gShi=2,j=2：j>i-1，關(guān)于j的循環(huán)結(jié)束，消去關(guān)于U2=S的規(guī)則左遞歸，應(yīng)用規(guī)則左遞歸消去的文法等價變換，改寫成右遞歸形式：

S::=(dSZef|gSh)SS::=bcZefS|

步驟3最后得到消去了左遞歸的等價文法G[Z]:Z::=(Sbc|dS)ZZ::=aZ|S::=(dSZef|gSh)SS::=bcZefS|最后得到文法G[Z]：

G[Z]：

Z::=Za|Sbc|dS

S::=Zef|gSh消去了左遞歸的等價文法G'[Z]：

G'[Z]：

Z::=(Sbc|dS)ZZ::=aZ|S::=(dSZef|gSh)SS::=bcZefS|注意：

?必須在關(guān)于j的循環(huán)結(jié)束時才進行關(guān)于Ui的規(guī)則左遞歸的消去,否則將引起錯誤；

?消去了文法左遞歸，同時也消去了規(guī)則左遞歸，不必要另行進行消去規(guī)則左遞歸的文法等價變換。例設(shè)有文法G[Z]：

Z::=Sa|Tb|cZ

S::=Tde|Zf|Sg

T::=Sh|jTk

試消去該文法的左遞歸。

解：首先判別知，該文法存在文法左遞歸,應(yīng)用消去文法左遞歸的算法。步驟1對文法非終結(jié)符號排序：U1=Z、U2=S、U3=T。步驟2執(zhí)行循環(huán)：i=1,j=1:j>i-1,不執(zhí)行關(guān)于j的循環(huán)，且關(guān)于U1=Z不存在規(guī)則左遞歸,不進行消去關(guān)于Z的規(guī)則左遞歸的等價變換。i=2,j=1:有規(guī)則S::=Zf,形如U2::=U1r,且Z::=Sa|Tb|cZ，形如U1::=x11|x12|x13,連同S::=Tde|Sg

有

S::=(Sa|Tb|cZ)f|Tde|Sg

或整理得

S::=S(af|g)|T(bf|de)|cZfi=2,j=2：j>i-1,關(guān)于j的循環(huán)結(jié)束,對U2=S消去規(guī)則左遞歸,得到

S::=(T(bf|de)|cZf)S

S::=(af|g)S|i=3,j=1:無形如U3::=U1r的規(guī)則，不進行代入。i=3,j=2:有規(guī)則T::=Sh，形如U3::=U1r，且規(guī)則

S::=(T(bf|de)|cZf)S,形如U2::=x21，進行代入，連同T::=jTk,有：

T::=(T(bf|de)|cZf)Sh|jTk

或整理得：T::=T(bf|de)Sh|cZfSh|jTk。i=3,j=3:j>i-1,關(guān)于j的循環(huán)結(jié)束,對U3=T消去規(guī)則左遞歸,

得到：

T::=(cZfSh|jTk)TT::=(bf|de)ShT|

步驟3最后得到消去了左遞歸的等價文法G[Z]如下:Z::=Sa|Tb|cZS::=(T(bf|de)|cZf)S

S::=(af|g)S|T::=(cZfSh|jTk)TT::=(bf|de)ShT|最后得到消去了左遞歸的等價文法

G[Z]:Z::=Sa|Tb|cZS::=(T(bf|de)|cZf)S

S::=(af|g)S|T::=(cZfSh|jTk)TT::=(bf|de)ShT|注意：消去了文法左遞歸，同時也消去了規(guī)則左遞歸。3.實現(xiàn)之考慮要點:·識別是否存在遞歸，存在時，識別是規(guī)則左遞歸還是文法左遞歸

·文法在計算機內(nèi)的存儲表示解題規(guī)范：步驟1識別是規(guī)則左遞歸還是文法左遞歸步驟2進行相應(yīng)的文法等價變換步驟3給出消去了左遞歸的等價文法4.2無回溯的自頂向下分析技術(shù)4.2.1應(yīng)用條件為應(yīng)用無回溯的自頂向下分析技術(shù)，文法必須滿足下列條件：1)無左遞歸性文法中關(guān)于任何非終結(jié)符號U，都不具有規(guī)則左遞歸和文法左遞歸，即，不存在形如U::=U…的規(guī)則，也不存在U=>+U…。

2)無回溯性

一個文法的任何UVN，存在U::=u1|u2|…|uk，若ui=>*Ti…與uj=>*Tj…，Ti、TjVT,ij，就有TiTj。從無回溯性條件可知，當(dāng)按某個選擇ui進行展開時，要末成功要末失敗，再無回溯的可能。。

注意：有回溯性，必定具有左遞歸，反之，沒有左遞歸，仍可能有回溯性。4.2.2遞歸下降分析技術(shù)1.實現(xiàn)思想遞歸下降分析技術(shù)是無回溯的自頂向下分析技術(shù)?；緦崿F(xiàn)思想：為每個非終結(jié)符號構(gòu)造一個子程序，它處理相應(yīng)句型中相對于該非終結(jié)符號的短語。遞歸下降識別程序=

總控程序+各個子程序

為什么稱為遞歸下降分析技術(shù)？

2.遞歸下降識別程序的例子G[E]：

E∷=E+T｜TT∷=T*F|FF∷=(E)｜i2.遞歸下降識別程序的例子文法G[E]：

E∷=E+T｜TT∷=T*F|FF∷=(E)｜i等價文法G[E]：

E∷=TEE∷=+TEE∷=εT∷=FTT∷=*FTT∷=εF∷=(E)F

∷=

i文法G[E]:

E::=TEE::=+TE|T::=FT

T::=*FT|F::=(E)|i

假定輸入符號串為i*i+i?？蔀樗鼧?gòu)造語法分析樹如圖所示。

1E2T3E4F5T

12+13T14E

6i7*8F9T

15F16T

1910i11

17i18由語法分析樹可見,當(dāng)關(guān)于E展開時，將按規(guī)則E::=TE

展開。當(dāng)關(guān)于E展開時，輸入符號是符號+，將按規(guī)則E::=+TE

展開，而在輸入符號不是符號+時，將按規(guī)則E::=展開。一般地，可如下地構(gòu)造遞歸下降識別程序。

ETE'

返回

E'+取符號TE'

返回NY

TFT'

返回

T'*取符號FT'

返回NY

總控取符號E出口NY

i取符號返回

F(取符號E)出錯

出錯NYNY關(guān)于文法G[E]的遞歸下降識別程序（控制流程圖）voidGetSymbol(){…}/*G'[E]的C型遞歸下降識別程序*/voidError(){…}voidE(){T()；E1();}voidE1(){if(sym==+){GetSymbol();T();E1();}}voidT(){F()；T1();}voidT1(){if(sym==*){GetSymbol();F();T1();}}voidF(){if(sym==i)GetSymbol();elseif(sym==(){GetSymbol();E();if(sym==))GetSymbol();elseError();}elseError();}voidmain(){GetSymbol();E();}構(gòu)造遞歸下降識別程序的步驟：步驟1首先檢查文法是否滿足應(yīng)用遞歸下降分析技術(shù)的條件，即，無左遞歸性與無回溯性。如果不滿足,則需進行文法等價變換，使之符合應(yīng)用條件。步驟2對符合條件的文法構(gòu)造遞歸下降識別程序的各個子程序，包括寫出識別程序的總控程序。

在構(gòu)造遞歸下降識別程序時需注意下列兩點,即,

?ε規(guī)則的處理

?

子程序構(gòu)造約定1.規(guī)則的處理

設(shè)正進入關(guān)于U的子程序，當(dāng)前輸入符號為T。

?當(dāng)關(guān)于U的規(guī)則僅U::=V,VVN,則立即調(diào)用關(guān)于V的子程序，由關(guān)于V的子程序查錯；

?當(dāng)關(guān)于U的規(guī)則呈U::=V|W形，則當(dāng)V=>*T…時，T與V匹配，調(diào)用關(guān)于V的子程序，或當(dāng)W=>*T…時，T與W匹配，調(diào)用關(guān)于W的子程序，否則報錯，當(dāng)前輸入符號T不匹配，可以不判別是否與W匹配，直接調(diào)用W，T不匹配時在W中報錯；

?當(dāng)關(guān)于U的規(guī)則呈U::=u|形，則當(dāng)u=>*T…時,T與u匹配,否則任何的輸入符號T都與匹配。即，在當(dāng)前輸入符號T不與u匹配時，便認(rèn)為按規(guī)則U::=展開。規(guī)則的存在，使得無需任何輸入符號便可以與當(dāng)前目標(biāo)(非終結(jié)符號)匹配，因此不出現(xiàn)出錯情況。

2.子程序構(gòu)造約定在進入一個子程序時，已取得當(dāng)前所處理短語的第一個符號（輸入符號），當(dāng)從子程序返回時，已取得該短語的后繼第一個輸入符號。因此，每當(dāng)一個終結(jié)符號與輸入符號匹配時就應(yīng)調(diào)用函數(shù)GetSymbol，掃描下一個當(dāng)前輸入符號。

例G[Ｃ]：Ｃ::=C;SC::=SS::=if(E)SelseSS::=if(E)SS::=A試為其構(gòu)造遞歸下降識別程序。首先檢查該文法是否滿足應(yīng)用遞歸下降分析技術(shù)的兩個條件，即，無左遞歸性與無回溯性。顯然，文法Ｇ[C]既有左遞歸性，又不滿足無回溯性。進行文法等價變換，得到等價文法Ｇ[C]如下。Ｃ::=SCC::=;SC|S::=if(E)SS|AS::=elseS|此文法既無左遞歸性，也無回溯性。關(guān)于文法G[C]構(gòu)造遞歸下降識別程序

CSC

返回

C

；

Y

取符號

SC

返回

N

SAY

取符號

返回

N

ifY

取符號

(

N

出錯

N

Y

出錯

取符號

E

)N出錯

Y

取符號SS

返回

SelseY

取符號

S返回

N

總控

取符號

C返回

3.2.3應(yīng)用遞歸下降分析技術(shù)進行句型識別

設(shè)輸入符號串是：i*i

mainGetSymbol

iETFif(sym==i)

GetSymbol

*

*

*

###T1if(sym==*)

GetSymbol#iE1if(sym==+)Fif(sym==i)###GetSymbol####T1if(sym==*)##

#iii*i##因此，識別出輸入符號串i*i是相應(yīng)文法的句子。當(dāng)識別出輸入符號串是相應(yīng)文法的句子時，需構(gòu)造語法分析樹?？梢栽谶M入關(guān)于某非終結(jié)符號U的子程序時為U生成相應(yīng)的結(jié)點，對于終結(jié)符號T，則在子程序中,當(dāng)T與輸入符號匹配時為T構(gòu)造結(jié)點。這樣，對函數(shù)定義可作如下的修改，如對于E與E1可改寫成：

voidE()

{MakeNode(E);T();E1();}

voidE1()

{MakeNode(E1);

if(sym==+)

{MakeNode(+);GetSymbol();T();E1();}

elseMakeNode();

}

概括

構(gòu)造遞歸下降識別程序的步驟：

步驟1首先檢查文法是否滿足應(yīng)用遞歸下降分析技術(shù)的條件，即，無左遞歸性與無回溯性。如果不滿足,則需進行文法等價變換，使之符合應(yīng)用條件。

步驟2對符合條件的文法構(gòu)造遞歸下降識別程序的各個子程序，包括寫出識別程序的總控程序。遞歸下降分析技術(shù)有如下優(yōu)點：１)實現(xiàn)思想簡單清晰明了，各個子程序的流程圖幾乎就是文法規(guī)則的圖解描述。２)能靈活地在各個子程序中添加語義處理工作，例如生成語法分析樹或推導(dǎo)，今后還將看到，可以采用遞歸下降分析技術(shù)生成表達式的逆波蘭表示。當(dāng)能用某種程序設(shè)計語言寫出所有這些子程序（包括遞歸子程序）時，可以用該語言的編譯系統(tǒng)來生成整個遞歸下降識別程序，而且如果遞歸子程序的實現(xiàn)功效是高的，則相應(yīng)的遞歸下降識別程序功效也是高的。遞歸下降分析技術(shù)的缺點也正是與實現(xiàn)語言密切相關(guān)。4.2.3預(yù)測分析技術(shù)1.預(yù)測分析技術(shù)的實現(xiàn)思想預(yù)測分析技術(shù)是一種無回溯的自頂向下分析技術(shù)，它使用一個稱為預(yù)測分析表的分析表和一個分析棧聯(lián)合進行控制地實現(xiàn)句型分析。輸入控制程序分析表

ZYX#輸出…abc…預(yù)測識別程序分析棧G'

[E]:E::=TE′E'::=

+TE′E'::=εT::=FT′

T'::=*FT′

T'::=εF::=(E)F::=i預(yù)測分析表

E::=TE′E::=TE′E::=+TE′E::=ε

E::=ε

T::=FT′T::=FT′T::=ε

T::=*FT′T::=εT::=ε

F::=(E)F::=i

EE′TT′F

+*()i#

輸入規(guī)則棧頂分析輸入符號串i+i*i2.應(yīng)用預(yù)測分析技術(shù)進行句型分析輸入符號串:i+i*i

分析過程用表列形式表示：步驟棧輸入輸出

0#Ei+i*i#E::=TE'1#E'Ti+i*i#T::=FT'2#E'T'F

i+i*i#F::=i3#E'T'i

i+i*i#

分析棧變化如下圖(a)~(d)所示，最終如圖(e)所示。

FiTT

T棧頂EE

E

E#####(a)(b)(c)(d)(e)步驟棧輸入輸出

0123456789#E#ET#ETF#ETi#ET#E#ET+#ET#ETF#ETi

i+i*i#i+i*i#i+i*i#i+i*i#+i*i#+i*i#+i*i#i*i#i*i#i*i#E∷=TE

T∷=FT

F∷=iT∷=εE∷=+TE

T∷=FT

F∷=i分析過程：步驟棧輸入輸出910111213141516#ETi#ET

#ETF*#ETF#ETi#ET

#E

#i*i#*i#*i#i#i####T∷=*FT

F∷=iT∷=εE∷=ε所以，輸入符號串i+i*i是該文法的句子。在任何分析時刻,分析棧頂符號X與當(dāng)前輸入符號T決定預(yù)測識別程序所應(yīng)執(zhí)行的分析動作。有四種可能的動作：如果XVT，且X=T=#，則分析成功而結(jié)束；如果XVT，X=T#，則從分析棧中上退去X，并把輸入指針推進到指向下一個輸入符號；如果XVN，且分析表A的元素A[X][T]=“X::=x1x2…xk”，則把分析棧頂?shù)姆朮上退去，把x1x2…xk依次下推入分析棧（注意：依逆序把x1x2…xk下推入分析棧，使x1在分析棧頂）；在其他情況下，即XVT，且XT，或XVN，且A[X][T]=ERROR（空白元素），識別失敗，調(diào)用出錯處理程序，使能繼續(xù)下去，或結(jié)束分析。voidmain(){push(#);push(Z);/*依次把#與識別符號Z下推入分析棧*/

T=下一輸入符號；Flag=true;while(Flag){X=top(S);if(XVT{#})if(X==T)if(T==#)Flag=false;else{pop(S);T=下一輸入符號；}elseerror()；

else/*XVN

*/if(A[X][T]==“X::=x1x2…xk”){pop(S);push(xkxk-1…x1);

打印輸出規(guī)則X::=x1x2…xk;}elseerror()；

}/*while*/STOP;/*

分析成功而結(jié)束

*/}/*預(yù)測識別程序控制程序(C型)*/

1E

1E

2T3E'

2T7E'

4F5T'

8+9T10E'

3F5T'

8+9T14E'6i7ε11F12T'

15ε4i6ε10F12T'

15ε

13i14ε11i13ε3.語法分析樹的生成

通過實例考察語法分析樹的生成。i+i的推導(dǎo)：

ETE'

FT'E'

iT'E'

iE'

i+TE'

i+FT'E'i+iT'E'

i+iE'

i+iT'E'

i+iE'

i+ii+i的語法分析樹：按推導(dǎo)生成的語法分析樹按預(yù)測分析法生成的語法分析樹按預(yù)測分析技術(shù)構(gòu)造語法分析樹思路：

1.設(shè)立分析棧，分析棧中元素是結(jié)點序號（既有文法符號，又有結(jié)點序號與實際生成順序）

2.逐步向下建立分支

·首先為識別符號建立（根）結(jié)點，序號為1；

·當(dāng)一個非終結(jié)符號出現(xiàn)在分析棧頂時，從該非終結(jié)符號相應(yīng)的結(jié)點處，關(guān)于按其展開的規(guī)則之右部，向下建立分支，同時建立父子兄弟關(guān)系。各結(jié)點給以結(jié)點序號。

·當(dāng)一個符號出現(xiàn)在分析棧頂時，為相應(yīng)結(jié)點確定實際建立順序。struct

語法樹結(jié)點類型{int

結(jié)點序號；

int

文法符號序號；

int

父結(jié)點序號；

int

左兄結(jié)點序號；

int

右子結(jié)點序號；

int

實際生成順序；}語法分析樹[MaxNodeNum]；如果要在分析過程中生成推導(dǎo)，該如何處理？

4.*

預(yù)測分析表的構(gòu)造從現(xiàn)有的預(yù)測分析表剖析如何確定分析表元素。輸入規(guī)則棧頂

+*()i#

EE′TT′F

E::=TE′E::=TE′

E::=+TE′E::=ε

E::=ε

T::=FT′T::=FT′

T::=ε

T::=*FT′T::=εT::=ε

F::=(E)F::=i

A[E][i]=“E::=TE”A[T][i]=“T::=FT”A[F][i]=“F::=i”A[E][+]=“E::=+TE”

A[T][+]=“T::=ε”A[F][*]=A[E][i]=“E::=TE”A[T][i]=“T::=FT”A[F][i]=“F::=i”A[E][+]=“E::=+TE”

A[T][+]=“T::=ε”A[F][+]=

ETE'FT'+TE'iεFT'

εiε

易見：E=>TE=>…=>i…，有A[E][i]=“E::=TE”

不可能E=>TE=>…=>+…，A[E][+]=空白。若存在U::=和推導(dǎo)Z=>*

…UT…=>…T…,TVT，則當(dāng)U出現(xiàn)在分析棧頂，且輸入符號是T時，將按規(guī)則U::=對U進行展開,因此，有分析表元素A[U][T]=“U::=”。

引進First集合與Follow集合

First(u)=｛T｜u=>*T…，T∈VT｝

Follow(U)={T｜Z=>*…UT…，T∈VT∪{#}}例如，F(xiàn)irst(TE)={(，i}First(E)={+,}Follow(E)={),#}Follow(T)={+,),#}為文法G構(gòu)造預(yù)測分析表的步驟如下。首先，對各規(guī)則U::=u計算First集合與Follow集合。然后填預(yù)測分析表A：步驟1對每個規(guī)則U∷=u，執(zhí)行步驟2與步驟3；步驟2對每個T∈VT，若T∈First(u)，

則置A[U][T]=“U∷=u”；

步驟3若ε∈First(u)，則對每個T∈Follow(U),

置A[U][T]=“U∷=u”；若#∈Follow(U)，則置A[U][#]=“U∷=u”；

步驟4把分析表A中每個未定義元素置為ERROR(用空白表示)。最后結(jié)束時所得的A便是所求的預(yù)測分析表。注意：無需一開始便計算全部Follow集合，可以僅當(dāng)需要時再計算Follow集合。試為文法G[S]:

S::=AS::=CA::=V=EC::=if(E)SV::=i

E::=VEE::=+VEE::=VEE::=

構(gòu)造下列預(yù)測分析表。=if()i+-#SS::=CS::=AAA::=V=ECC::=if(E)BVV::=iEE::=VE′E′E′::=εE′::=+VE′E′::=-VE′E′::=ε輸入規(guī)則棧頂對于分析表元素均唯一的文法引進LL(1)文法。

如果對于某文法，其預(yù)測分析表元素的值都是唯一的，則該文法稱為LL(1)文法。一個LL(1)文法是無二義性的文法，它所定義的語言正是利用它的預(yù)測分析表所能識別的所有句子。

LL（1）文法判別條件：

一個文法G是LL(1)的，當(dāng)且僅當(dāng)對于G的每個非終結(jié)符號U的任何兩個不同的重寫規(guī)則U∷=x與U∷=y，下面的條件成立。條件1First(x)∩First(y)=?

條件2x=>*ε與y=>*ε不能同時成立條件3如果y=>*ε,則First(x)∩Follow(U)=?例設(shè)有文法Ｇ[S]:S::=if(C)SS|AS::=elseS|

C::=B

if

A

else

B

#

SS::=if(C)SS

S::=A

S

S::=elseSS::=

S::=

C

C::=B

棧頂規(guī)則輸入對于規(guī)則S::=elseS因elseFirst(S),有A[S][else]=“S::=elseS”,對于規(guī)則S::=,因elseFollow(S),又有A[S][else]=“S::=”,因此,A[S][else]包含兩個值，即，“S::=elseS”與“S::=”。

結(jié)論：文法G[S]不是LL(1)文法，事實上它是二義性文法。4.3預(yù)測識別程序句型分析的計算機實現(xiàn)

應(yīng)用預(yù)測識別程序進行句型分析的實現(xiàn)，關(guān)鍵是解決兩方面問題，即，預(yù)測分析表的存放與語法分析樹的構(gòu)造。4.3.1預(yù)測分析表的存儲表示

預(yù)測分析表在概念上與實踐上反差甚大，必須解決預(yù)測分析表在計算機內(nèi)的存放問題。預(yù)測分析表是一個表格，明顯的是它將用二維數(shù)組來實現(xiàn)，符號用序號代替，文法規(guī)則也用序號代替。

預(yù)測分析表的給出：自動生成，而且更可以用賦初值方式給出分析表。例如,下列文法及其分析表都可以如此。G[E]:E::=TEE::=+TEE::=εT::=FT

T::=*FTT::=εF::=(E)F::=iintA[5+1][6]=/*

符號#的序號是0*/{{0},{0,0,0,1,0,1},/*E*/{3,2,0,0,3,0},/*E'*/{0,0,0,4,0,4},/*T*/{6,6,5,0,6,0},/*T'*/{0,0,0,7,0,8}/*F*/}；

E::=TE′E::=TE′E::=+TE′E::=ε

E::=ε

T::=FTT::=FTT::=ε

T::=*FT′T::=εT::=ε

F::=(E)F::=i

EE′TT′F

+*()i#

輸入