第5章自頂向下語(yǔ)法分析方法完教材課程

第5章自頂向下語(yǔ)法分析方法2025/1/11第5章自頂向下語(yǔ)法分析方法Page2第五章

自頂向下語(yǔ)法分析方法學(xué)習(xí)目標(biāo):掌握：LL(1)文法的判別，預(yù)測(cè)分析法，遞歸子程序的構(gòu)造方法理解：LL(1)文法了解：不確定的自頂向下分析2025/1/11Page3第5章自頂向下語(yǔ)法分析方法語(yǔ)法分析的作用是識(shí)別由詞法分析給出的單詞序列是否是給定文法的正確句子.分類:語(yǔ)法分析自頂向下分析（第五章）自底向上分析確定的不確定的算符優(yōu)先分析（第六章）LR分析（第七章）自頂向下的基本思想:

從文法的開(kāi)始符出發(fā)企圖推導(dǎo)出與輸入的單詞串完全相匹配的句子。2025/1/11第5章自頂向下語(yǔ)法分析方法Page45.1 確定的自頂向下分析思想5.2 LL(1)文法的判別5.3 某些非LL(1)文法到LL(1)文法的等價(jià)變換5.4 不確定的自頂向下分析思想5.5 確定的自頂向下分析方法第五章自頂向下語(yǔ)法分析方法2025/1/11Page6第5章自頂向下語(yǔ)法分析方法1確定分析的條件

從文法的開(kāi)始符出發(fā)，如能根據(jù)當(dāng)前的輸入符號(hào)（單詞符號(hào)）唯一地確定選用哪個(gè)產(chǎn)生式進(jìn)行推導(dǎo)，則分析是確定的。2025/1/11Page7第5章自頂向下語(yǔ)法分析方法例1設(shè)有文法G1[S]: S→pA|qB A→cAd|a B→dB|b

若輸入串W=pccadd。自頂向下的推導(dǎo)過(guò)程為:SSApcAdcAda=>pA=>pcAd=>pccAdd=>pccaddG1[S]有如下特點(diǎn)：

(1)每個(gè)產(chǎn)生式的右部由終結(jié)符開(kāi)頭;(2)同一非終結(jié)符的不同產(chǎn)生式的右部由不同的終結(jié)符開(kāi)頭。對(duì)于這種文法，在推導(dǎo)過(guò)程可以根據(jù)當(dāng)前的輸入符號(hào)唯一確定選哪個(gè)產(chǎn)生式往下推導(dǎo)，即分析過(guò)程是確定的。2025/1/11Page8第5章自頂向下語(yǔ)法分析方法例2：設(shè)有文法G2[S]為:S→Ap|BqA→a|cAB→b|dBpAScAcAa=>ccapS=>cAp=>ccAp=>Ap該例說(shuō)明，當(dāng)(1)產(chǎn)生式右部以終結(jié)符或非終結(jié)符開(kāi)頭（無(wú)空產(chǎn)生式）；(2)同一非終結(jié)符的不同產(chǎn)生式的右部由不同的符號(hào)開(kāi)頭。對(duì)于這種文法，在推導(dǎo)過(guò)程選用哪個(gè)產(chǎn)生式不直觀，關(guān)鍵是判斷產(chǎn)生式右部推出的開(kāi)始符號(hào)（集）——First集，分析過(guò)程可能是確定的。若輸入串W=ccap,自頂向下的推導(dǎo)過(guò)程為：2025/1/11Page9第5章自頂向下語(yǔ)法分析方法例3：設(shè)有文法G3[S]S→aA|dA→bAS|ε若輸入串W=abd，自頂向下的推導(dǎo)過(guò)程為：AaSbSAεd=>abd

S=>abAS=>abS文法的特點(diǎn)是：包含空產(chǎn)生式對(duì)于空產(chǎn)生式左部的非終結(jié)符，關(guān)鍵是判斷該非終結(jié)符的后跟符號(hào)（集）——Follow集，分析過(guò)程可能是確定的。=>aA2025/1/11Page10第5章自頂向下語(yǔ)法分析方法1確定分析的條件要進(jìn)行確定的自頂向下的分析，文法要滿足一定的限制——即文法是LL(1)文法。先研究三個(gè)定義開(kāi)始符號(hào)集FIRST集后跟符號(hào)集FOLLOW集選擇集合SELECT集2025/1/11Page11第5章自頂向下語(yǔ)法分析方法2

開(kāi)始符號(hào)集FIRST(α)的定義定義:

設(shè)G=(VN,VT,P,S)是上下文無(wú)關(guān)文法，

(VN

VT)*

FIRST(

)={a

VT|

*a}

若

*ε

則規(guī)定ε∈FIRST(

)

直觀上說(shuō)，文法符號(hào)串

的開(kāi)始符號(hào)集是由

推導(dǎo)出的開(kāi)頭的終結(jié)符（包括ε）組成。2025/1/11Page12第5章自頂向下語(yǔ)法分析方法例文法G2[S]:S→ApS→BqA→aA→cAB→bB→dBFIRST(Ap)=FIRST(Bq)=FIRST(a)=FIRST(cA)=FIRST(b)=FIRST(dB)=由于同一非終結(jié)符的兩個(gè)產(chǎn)生式的右部推導(dǎo)出來(lái)的開(kāi)始符號(hào)集不相交，因此可根據(jù)當(dāng)前輸入符屬于哪個(gè)產(chǎn)生式右部的開(kāi)始符號(hào)集而決定選哪個(gè)產(chǎn)生式進(jìn)行推導(dǎo)，可以進(jìn)行確定的自頂向下分析{a,c}{b,d}{a}{c}q4ehyfnFirst:開(kāi)始符號(hào)集2025/1/11Page13第5章自頂向下語(yǔ)法分析方法例2：設(shè)有文法G2[S]為:S→Ap|BqA→a|cAB→b|dBpAScAcAa=>ccapS=>cAp=>ccAp=>ApS→ApFIRST(Ap)={a,c}S→BqFIRST(Bq)={b,d}A→aFIRST(a)={a}A→cAFIRST(cA)={c}B→bFIRST(b)=B→dBFIRST(dB)=dr6zzns若輸入串W=ccap,自頂向下的推導(dǎo)過(guò)程為：2025/1/11Page14第5章自頂向下語(yǔ)法分析方法3

后跟符號(hào)集FOLLOW(A)的定義定義： 設(shè)G=(VT,VN,P,S)是上下文無(wú)關(guān)文法，A∈VN

，

FOLLOW(A)={a|S=>*…Aa…，a∈VT}， 若有S=>*…A，則規(guī)定#∈FOLLOW(A)

（注：#輸入串#，‘#’做為輸入串的結(jié)束符） 直觀上說(shuō)，非終結(jié)符A的后跟符號(hào)集是由句型中緊跟A后的那些終結(jié)符（包括#）組成。2025/1/11Page15第5章自頂向下語(yǔ)法分析方法例文法G3[S]: S→aA|dA→bAS|ε由S=>*S

得#∈FOLLOW(S)

由S=>aA=>abAS=>abbASS=>abbASaA

…=>abbASd

FOLLOW(S)={#,a,d}由S=>*aA得#∈FOLLOW(A)

由S=>*abAS=>*abAaA得a∈FOLLOW(A)

…=>*abAd

得d∈FOLLOW(A)

FOLLOW(A)={#,a,d}2025/1/11Page16第5章自頂向下語(yǔ)法分析方法3

后跟符號(hào)集FOLLOW(A)的定義說(shuō)明：對(duì)于非終結(jié)符A的兩個(gè)產(chǎn)生式A→bAS和A→ε：當(dāng)輸入符號(hào)∈FIRST(bAS)=時(shí)，選A→bAS推導(dǎo)，當(dāng)輸入符號(hào)∈FOLLOW(A)={#,a,d}時(shí)，選A→ε推導(dǎo)。由于FIRST(bAS)∩FOLLOW(A)=ф，所以可進(jìn)行確定的自頂向下分析。2025/1/11Page17第5章自頂向下語(yǔ)法分析方法例3：設(shè)有文法G3[S]S→aA|dA→bAS|ε若輸入串W=abd，自頂向下的推導(dǎo)過(guò)程為：AaSbSAεd=>abd

S=>abAS=>abS文法的特點(diǎn)是:包含空產(chǎn)生式對(duì)于空產(chǎn)生式左部的非終結(jié)符，關(guān)鍵是判斷該非終結(jié)符的后跟符號(hào)（集），分析過(guò)程可能是確定的。=>aAFIRST(bAS)=FOLLOW(A)={#,a,d}2025/1/11Page18第5章自頂向下語(yǔ)法分析方法4

選擇集合SELECT(A→α)的定義定義 對(duì)給定的上下文無(wú)關(guān)文法的產(chǎn)生式A→α，A∈VN，α∈V*，若α≠>*ε,則

SELECT(A→α)=FIRST(α)若α=>*ε,則

SELECT(A→α) =(FIRST(α)-{ε})∪FOLLOW(A)2025/1/11Page19第5章自頂向下語(yǔ)法分析方法4

選擇集合SELECT(A→α)的定義解釋 當(dāng)A面對(duì)應(yīng)輸入符a，若First(α)中包含a，在自頂向下的分析中應(yīng)選擇產(chǎn)生式A→α進(jìn)行推導(dǎo)； 此外若α可能導(dǎo)出空串，A自動(dòng)獲得匹配，輸入符a有可能與A后的一個(gè)符號(hào)匹配，所以當(dāng)a屬于Follow(A)時(shí)，選擇產(chǎn)生式A→α也是可以的。

直觀上說(shuō)某產(chǎn)生式A→α的SELECT集是指遇到哪些輸入符號(hào)（包括#）時(shí)選用該產(chǎn)生式向下推導(dǎo)。SELECT(A→α)={a,b,c}2025/1/11Page20第5章自頂向下語(yǔ)法分析方法4

選擇集合SELECT(A→α)的定義即：若α≠>*ε,則是否選擇A→α這條產(chǎn)生式進(jìn)行推導(dǎo)，主要是看當(dāng)時(shí)輸入字符是否屬于FIRST(α)，若是，則選它。若α=>*ε,則是否選擇A→α這條產(chǎn)生式進(jìn)行推導(dǎo)，除了看當(dāng)時(shí)輸入字符是否屬于FIRST(α)，還可以看當(dāng)時(shí)輸入字符是否屬于FOLLOW(A)，若屬于其中一個(gè)集合，則選它。若α≠>*ε,則SELECT(A→α)=FIRST(α)若α=>*ε,則SELECT(A→α) =(FIRST(α)-{ε})∪FOLLOW(A)2025/1/11Page21第5章自頂向下語(yǔ)法分析方法例G3[S]:S→aAS→dA→bASA→εSELECT(S→aA)=SELECT(S→d)=SELECT(A→bAS)=SELECT(A→ε)=若α≠>*ε,則SELECT(A→α)=FIRST(α)若α=>*ε,則SELECT(A→α) =(FIRST(α)-{ε})∪FOLLOW(A)FIRST(aA)=FIRST(d)=FIRST(bAS)=FOLLOW(A)={#,a,b}2cojcjs{a}2025/1/11Page22第5章自頂向下語(yǔ)法分析方法4選擇集合SELECT(A→α)的定義說(shuō)明： 同一非終結(jié)符的不同產(chǎn)生式A→α與A→β，若SELECT(A→α)∩SELECT(A→β)=Φ，則一定可以進(jìn)行確定的自頂向下分析。SELECT(A→α)={a,b}SELECT(A→β)={c,d}SELECT(A→α)={a,b}SELECT(A→β)={a,d}可確定不可確定2025/1/11Page23第5章自頂向下語(yǔ)法分析方法5LL(1)文法的定義定義:

一個(gè)上下文無(wú)關(guān)文法是LL(1)文法的充分必要條件是，對(duì)每個(gè)非終結(jié)符A的兩個(gè)不同產(chǎn)生式A→α與A→β，滿足SELECT(A→α)∩SELECT(A→β)=Φ（無(wú)交集）。LL(1)文法的含義是：第一個(gè)L表示從左到右掃描輸入串第二個(gè)L表示分析過(guò)程用最左推導(dǎo)1表明只需向前看一個(gè)符號(hào)便可以決定選哪個(gè)產(chǎn)生式進(jìn)行推導(dǎo)，類似地LL(k)文法需要向前看K個(gè)符號(hào)才可以確定選用哪個(gè)產(chǎn)生式。2025/1/11Page24第5章自頂向下語(yǔ)法分析方法例有文法G[S]為：

S→aAS S→b A→bA A→εSELECT(S→aAS)={a}由于SELECT(A→bA)∩SELECT(A→ε)=≠Φ，所以文法G[S]不是LL(1)文法，當(dāng)A遇輸入符b時(shí)，不能確定選A→bA還是A→ε去推導(dǎo)。SELECT(S→b)=SELECT(A→bA)=SELECT(A→ε)=Follow(A)={a,b}2025/1/11第5章自頂向下語(yǔ)法分析方法Page25§5.2LL(1)文法的判別要判別一個(gè)上下文無(wú)關(guān)文法是否是LL(1)文法分為五步：

1.

求出能推出ε的非終結(jié)符集

2.

計(jì)算每個(gè)產(chǎn)生式右部α的FIRST(α)集

3.

計(jì)算每個(gè)非終結(jié)符A的FOLLOW(A)集

4.

計(jì)算每個(gè)產(chǎn)生式A→α的SELECT(A→α)集

5.

按LL(1)文法的定義判別2025/1/11Page26第5章自頂向下語(yǔ)法分析方法1.

求出能推出ε的非終結(jié)符集步驟：(1)第1次掃描——掃描文法中的產(chǎn)生式對(duì)能直接推出ε的產(chǎn)生式左部的終結(jié)符標(biāo)“是”。刪除所有右部含有終結(jié)符的產(chǎn)生式。若以某一非終結(jié)符為左部的所有產(chǎn)生式都被刪除，則該非終結(jié)符不能推出ε，將其標(biāo)為“否”。2025/1/11Page27第5章自頂向下語(yǔ)法分析方法1.

求出能推出ε的非終結(jié)符集例G[S]：S→AB|bCA→b|εB→aD|εC→AD|bD→aS|cS→ABS→bCA→bA→εB→aDB→εC→ADC→bD→aSD→c非終結(jié)符SABCD第1次掃描第2次掃描是是否2025/1/11Page28第5章自頂向下語(yǔ)法分析方法1.

求出能推出ε的非終結(jié)符集(2)第2次掃描——掃描產(chǎn)生式右部的符號(hào)對(duì)每個(gè)產(chǎn)生式p:A→X1Xn，如果X1,…,Xn都被標(biāo)為“是”(即X1,…,Xn都能推出ε)，則A也能推出ε，將其標(biāo)為“是”。如果A→Y1Yn中，Y1Yn中任一個(gè)已被標(biāo)為“否”，則刪掉該產(chǎn)生式，若這么做使得A的所有產(chǎn)生式都被刪去，則A不能推出ε，將其標(biāo)為“否”。2025/1/11Page29第5章自頂向下語(yǔ)法分析方法1.

求出能推出ε的非終結(jié)符集例G[S]：S→AB|bCA→b|εB→aD|εC→AD|bD→aS|cS→ABS→bCA→bA→εB→aDB→εC→ADC→bD→aSD→c非終結(jié)符SABCD第1次掃描第2次掃描是是否是否能推出ε的非終結(jié)符集為{A,B,S}2025/1/11Page30第5章自頂向下語(yǔ)法分析方法2.

計(jì)算每個(gè)產(chǎn)生式右部α的FIRST(α)集首先對(duì)每一文法符號(hào)X

(X

VT

VN)，求FIRST(X)的算法:對(duì)每個(gè)a

VT

：FIRST(a)={a}對(duì)每個(gè)A

VN

：若

A

*ε

，則ε

FIRST(A)對(duì)每個(gè)A

VN

：若A→a···,a

VT

，則a

FIRST(A)2025/1/11Page31第5章自頂向下語(yǔ)法分析方法2.

計(jì)算每個(gè)產(chǎn)生式右部α的FIRST(α)集若X,Y1,Y2,…,Yn都

VN,有產(chǎn)生式X→Y1Y2…Yn.當(dāng)Y1,Y2,…,Yn-1都

*ε時(shí)，F(xiàn)IRST(Y1)-{ε},FIRST(Y2)-{ε},…,FIRST(Yn-1)-{ε},FIRST(Yn)都包含在FIRST(X)中。當(dāng)4中所有Yi

*ε，則FIRST(X)=FIRST(Y1)

FIRST(Y2)…FIRST(Yn){ε}2025/1/11Page32第5章自頂向下語(yǔ)法分析方法例G[S]： S→AB S→

bC A→b A→

ε B→aD B→

ε C→AD C→

b D→aS D→

cbaacbacεaεbεbaFirst集(3)baacbεaεb

εbFirst集(2)ba

εεεFirst集(1)ABCDabSabFirst集(0)已求出能推出ε的非終結(jié)符集為{A,B,S}babacaacεεεb2025/1/11Page33第5章自頂向下語(yǔ)法分析方法利用求出每個(gè)文法符號(hào)的FIRST集求符號(hào)串的FIRST集設(shè)α=X1X2…Xn當(dāng)X1不能=>*ε，則FIRST(α)=FIRST(X1)若對(duì)任何j(1≤j＜n）都有ε∈FIRST(Xj),

則FIRST(α) =(FIRST(X1)-{ε})∪…∪(FIRST(Xj)-{ε}) ∪FIRST(Xj+1)若對(duì)所有i(1≤i≤n)，都有ε∈FIRST(Xi)，

則

FIRST(α)=FIRST(X1)∪…∪FIRST(Xn)∪{ε}2025/1/11Page34第5章自頂向下語(yǔ)法分析方法例G[S] S→AB|bC A→b|ε B→aD|ε C→AD|b D→aS|c已求出非終結(jié)符的First集合如下:First(S)={a,b,ε}First(A)={b,ε}First(B)={a,ε}First(C)={a,b,c}First(D)={a,c}產(chǎn)生式右部符號(hào)串的開(kāi)始符集合為:S→ABFIRST(AB)=

S→bCFIRST(bC)=

A→εFIRST(ε)=

A→b FIRST(b)=

C→ADFIRST(AD)=

D→aSFIRST(aS)=

FIRST(A)∪FIRST(B)∪{ε}={a,b,ε}(FIRST(A)-{ε})∪FIRST(D)={b,a,c}{a}{ε}2025/1/11Page35第5章自頂向下語(yǔ)法分析方法3．計(jì)算每個(gè)非終結(jié)符A的FOLLOW(A)集1.對(duì)所有A

VN令Follow(A)={};對(duì)開(kāi)始符S，令Follow(S)={#}因?yàn)镾=>*S，顯然#∈FOLLOW(S)2.

對(duì)每條產(chǎn)生式A→xBy，考察產(chǎn)生式右部的每一非終結(jié)符B，x,y∈V*，如果y不能推出ε

Follow(B)=Follow(B)

First(y),否則,若y

*ε，

Follow(B)=Follow(B)

(First(y)-{ε})

Follow(A)3.

重復(fù)2，直至對(duì)所有A

VN，F(xiàn)ollow(A)收斂為止。若a∈FOLLOW(A),則表明S=>*…Aa…，由于A→xBy，且y=>*ε,則有

S=>*…Aa…=>…xBya=>…xBa…，即S=>*…xBa…,所以a∈FOLLOW(B)2025/1/11Page36第5章自頂向下語(yǔ)法分析方法例G[S]：[1]S→AB[2]S→bC[3]A→b[4]A→ε[5]B→aD[6]B→ε[7]C→AD[8]C→b[9]D→aS[10]D→c已求出非終結(jié)符的First集合如下:First(S)={a,b,ε}First(A)={b,ε}First(B)={a,ε} First(C)={a,b,c}First(D)={a,c}#D#C#Ba#A###a#c＃＃＃SFollow集(2)Follow集(1)Follow集(0)c2025/1/11Page37第5章自頂向下語(yǔ)法分析方法4．計(jì)算每個(gè)產(chǎn)生式A→α的SELECT(A→α)集按定義計(jì)算SELECT(A→α)：若α≠>*ε，則

SELECT(A→α)=FIRST(α)若α=>*ε，則

SELECT(A→α)=(FIRST(α)-{ε})∪FOLLOW(A)2025/1/11Page38第5章自頂向下語(yǔ)法分析方法例G[S]：

S→AB|bCA→b|εB→aD|εC→AD|bD→aS|c是否=>*εFirst集Follow集S是{a,b,ε}{#}A是{b,ε}{a,c,#}B是{a,ε}{#}C否{a,b,c}{#}D否{a,c}{#}部分產(chǎn)生式的select集合SELECT(S→AB)=SELECT(S→bC)=SELECT(A→ε)=SELECT(A→b)=SELECT(B→aD)=SELECT(C→AD)=(FIRST(AB)-{ε})∪FOLLOW(S)={b,a,#}FIRST(bC)=FIRST(b)=FIRST(aD)={a}FIRST(AD)={b,a,c}(FIRST(ε)-{ε})∪FOLLOW(A)={a,c,#}2025/1/11Page39第5章自頂向下語(yǔ)法分析方法5.

按LL(1)文法的定義判別產(chǎn)生式的select集如下:SELECT(S→AB)={b,a,#} SELECT(S→bC)==SELECT(A→ε)={a,c,#} SELECT(A→b)=SELECT(B→ε)={#} SELECT(B→aD)={a}SELECT(C→AD)={b,a,c} SELECT(C→b)=SELECT(D→aS)={a} SELECT(D→c)={c}由于

SELECT(S→AB)∩SELECT(S→bC)=≠ф SELECT(C→AD)∩SELECT(C→b)=≠ф所以文法G[S]不是LL(1)文法一個(gè)上下文無(wú)關(guān)文法是LL(1)文法的充分必要條件是，對(duì)每個(gè)非終結(jié)符A的兩個(gè)不同產(chǎn)生式A→α與A→β，滿足SELECT(A→α)∩SELECT(A→β)=Φ2025/1/11第5章自頂向下語(yǔ)法分析方法Page40非LL(1)文法含有左公共因子的文法

若文法中含有形如：A→αβ|αr的產(chǎn)生式，稱文法含有左公共因子。 顯然, SELECT(A→αβ)∩SELECT(A→αr)≠ф,文法不是LL(1)文法5.3某些非LL(1)文法到

LL(1)文法的等價(jià)變換2025/1/11第5章自頂向下語(yǔ)法分析方法Page41含有左遞歸的文法

文法中只要含有下列形式的產(chǎn)生式（含有①或含有②或二者皆有），則稱文法含有左遞歸:A→AβA→Bβ B→Aα

在①中含有左遞歸的產(chǎn)生式，稱為直接左遞歸；

在②中雖然沒(méi)有含左遞歸的產(chǎn)生式，

但A=>Bβ=>Aαβ即A=>+

A…,稱為間接左遞歸.5.3某些非LL(1)文法到

LL(1)文法的等價(jià)變換2025/1/11第5章自頂向下語(yǔ)法分析方法Page42以直接左遞歸為例，若有如下產(chǎn)生式

A→A

|

A→其中和

為任意語(yǔ)法符號(hào)串。不難證明有下面關(guān)系式：

Select(A→A

))

First(A

)

First(

) Select(A→

))

First(

)故A→A

和A→的Select集相交，不是LL(1)文法5.3某些非LL(1)文法到

LL(1)文法的等價(jià)變換A

A

A

A

…不知何時(shí)結(jié)束不確定若α≠>*ε,則SELECT(A→α)=FIRST(α)若α=>*ε,則SELECT(A→α) =(FIRST(α)-{ε})∪FOLLOW(A)2025/1/11第5章自頂向下語(yǔ)法分析方法Page43對(duì)非LL(1)文法進(jìn)行等價(jià)變換提取左公共因子消除左遞歸 注意：變換后的文法不一定是LL(1)文法，文法不含左遞歸和左公共因子只是LL(1)文法的必要條件。5.3某些非LL(1)文法到

LL(1)文法的等價(jià)變換2025/1/11Page44第5章自頂向下語(yǔ)法分析方法將產(chǎn)生式A→αβ|αr等價(jià)變換為: A→α(β|r)， 將括號(hào)內(nèi)用一新引入的非終結(jié)符A’表示,得 A→αA’，A’→β|r一般形式：若A→αβ1|αβ2|…|αβn,

提取左公共因子后變?yōu)? A→α(β1|β2|…|βn)，引進(jìn)新的非終結(jié)符A’，得：

A→αA’，A’→β1|β2|…|βn

若在βi中仍含有左公共因子,可再次提取.1、提取左公因子2025/1/11Page45第5章自頂向下語(yǔ)法分析方法例文法G1：

S→aSb|aS|ε

提左因子得:S→aS(b|ε)|ε

引進(jìn)新的非終結(jié)符S’得: S→aSS’|ε S’→b|ε1、提取左公因子2025/1/11Page46第5章自頂向下語(yǔ)法分析方法1)消除直接左遞歸文法G:S→Sa|b

可改寫(xiě)成 S→bS’

S’→aS’|ε一般情形:

含直接左遞歸的文法G：

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

消除左遞歸后改寫(xiě)成：

A→β1A’|β2A’|…|βnA’ A’→α1A’|α2A’|…|αmA’|ε

2、消除左遞歸不難驗(yàn)證，改寫(xiě)前和改寫(xiě)后的文法都產(chǎn)生語(yǔ)言{ban|n≥0}

2025/1/11Page47第5章自頂向下語(yǔ)法分析方法2)消除間接左遞歸將間接左遞歸變成直接左遞歸，再加以消除。算法步驟：把文法的所有非終結(jié)符按任一順序排列，

如：A1，A2，…，An從A1開(kāi)始，按以下順序處理Ai。首先，消除左部為Ai的產(chǎn)生式的直接左遞歸；然后，若左部為Ai的產(chǎn)生式的右部為非終結(jié)符Aj(j<i)開(kāi)頭，即Ai→Aj…，則用左部為Aj的所有產(chǎn)生式的右部分別代替Ai→Aj…

中的Aj；最后，得到的左部為Ai的產(chǎn)生式若有直接左遞歸，則消除之。去掉無(wú)用產(chǎn)生式。2025/1/11Page48第5章自頂向下語(yǔ)法分析方法例文法G：(1)S→Qc|c (2)Q→Rb|b(3)R→Sa|a將非終結(jié)符排序：R，Q，S對(duì)R：產(chǎn)生式(3)不含直接左遞歸，所以保持不變

對(duì)Q：把(3)代入(2)得(2’)Q→Sab|ab|b，無(wú)直接左遞歸

對(duì)S：把(2’)代入(1)得(1’)S→Sabc|abc|bc|c，有直接左遞歸，消除直接左遞歸得

S→abcS’|bcS’|cS’ S’→abcS’|ε

處理結(jié)果為：R→Sa|a Q→Sab|ab|b S→abcS’|bcS’|cS’

S’→abcS’|ε由于Q，R是不可到達(dá)的非終結(jié)符，其產(chǎn)生式應(yīng)刪除。最終得文法G’：S→abcS’|bcS’|cS’

S’→abcS’|ε2025/1/11Page49第5章自頂向下語(yǔ)法分析方法示例說(shuō)明：當(dāng)非終結(jié)符順序?yàn)镽，Q，S，消除左遞歸的最終結(jié)果為：

S→abcS’|bcS’|cS’ S’→abcS’|ε若非終結(jié)符順序?yàn)镾，Q，R，則消除左遞歸的最終結(jié)果為：

S→Qc|c Q→Rb|bR→bcaR’|caR’|aR’R’→bcaR’|ε結(jié)論：當(dāng)非終結(jié)符的排序不同時(shí)，結(jié)果的產(chǎn)生式形式不同，但它們是等價(jià)的。2025/1/11第5章自頂向下語(yǔ)法分析方法Page50不確定的自頂向下分析也稱帶回溯的自頂向下分析定義：

不確定是指某個(gè)非終結(jié)符有多條產(chǎn)生式，而面臨當(dāng)前輸入符無(wú)法唯一確定選用哪條產(chǎn)生式進(jìn)行推導(dǎo)，只好逐個(gè)試探。當(dāng)分析不成功時(shí)，則推翻分析退回到適當(dāng)位置重新試探其余候選可能的推導(dǎo)，直到把所有可能的推導(dǎo)序列都試完仍不成功，才能確認(rèn)輸入串不是該文法的句子。5.4不確定的自頂向下分析思想2025/1/11Page51第5章自頂向下語(yǔ)法分析方法例1

設(shè)有文法

S→xAyA→ab|a，對(duì)輸入串w=xay，推導(dǎo)樹(shù)為SxAySxAybaSxAy回溯aSxAy由于A的兩條產(chǎn)生式：A→ab和A→a右部First集交集不為空，從而引起回溯2025/1/11Page52第5章自頂向下語(yǔ)法分析方法例2

文法G：S→aAS

S→b A→bAS A→ε

輸入串w=ab，推導(dǎo)樹(shù)為:SaAS回溯SaASSaASSbASaASεb由于A的產(chǎn)生式A→ε右部能=>*ε，且Follow(A)∩First(bAS)=≠ф

，從而引起回溯2025/1/11Page53第5章自頂向下語(yǔ)法分析方法例3

文法G：S→Sa S→b

輸入串w=baa，推導(dǎo)樹(shù)為:SSabSbSSa回溯回溯SSaSaSSaSab由于文法含有左遞歸而引起回溯2025/1/11第5章自頂向下語(yǔ)法分析方法Page545.5確定的自頂向下分析方法確定的自頂向下分析方法有：遞歸子程序法(recursive-descentparser)預(yù)測(cè)分析法(predictiveparser)兩種方法都要求文法是LL(1)文法。2025/1/11第5章自頂向下語(yǔ)法分析方法Page55實(shí)現(xiàn)思想： 對(duì)應(yīng)文法中每個(gè)非終結(jié)符編寫(xiě)一個(gè)遞歸過(guò)程，識(shí)別由該非終結(jié)符推出的串。當(dāng)非終結(jié)符有多條產(chǎn)生式時(shí)，按當(dāng)前輸入符屬于哪條產(chǎn)生式的SELECT集可唯一確定選擇哪個(gè)產(chǎn)生式進(jìn)行匹配。當(dāng)識(shí)別到終結(jié)符時(shí)，與當(dāng)前輸入符號(hào)匹配，并讀取下一輸入符；當(dāng)識(shí)別到非終結(jié)符時(shí)，則調(diào)用該非終結(jié)符相應(yīng)的過(guò)程。5.5.1遞歸子程序法2025/1/11第5章自頂向下語(yǔ)法分析方法Page565.5.1遞歸子程序法由于遞歸子程序法對(duì)每個(gè)過(guò)程可能存在直接或間接遞歸調(diào)用，所以對(duì)某個(gè)過(guò)程在退出之前可能又被調(diào)用，因此有些信息需要保留，通常在入口時(shí)需保留某些信息，出口時(shí)需恢復(fù)——先進(jìn)后出棧。優(yōu)點(diǎn)：簡(jiǎn)單直觀、易于構(gòu)造缺點(diǎn)：對(duì)文法要求高，必須是LL(1)文法遞歸調(diào)用多，速度慢，占用空間多2025/1/11第5章自頂向下語(yǔ)法分析方法Page575.5.2預(yù)測(cè)分析方法一個(gè)預(yù)測(cè)分析器由三個(gè)部分組成：預(yù)測(cè)分析程序：控制分析過(guò)程的進(jìn)行。分析棧：存放從文法開(kāi)始符號(hào)出發(fā)的自頂向下推導(dǎo)過(guò)程中等待匹配的文法符號(hào)。開(kāi)始時(shí)放入‘#’和文法開(kāi)始符，結(jié)束時(shí)棧應(yīng)是空的。預(yù)測(cè)分析表：是一張二維表，元素M[A,a]的內(nèi)容是當(dāng)非終結(jié)符A面臨輸入符號(hào)a(終結(jié)符或句子括號(hào)＃)時(shí)應(yīng)選取的產(chǎn)生式，當(dāng)無(wú)產(chǎn)生式時(shí)，元素內(nèi)容為轉(zhuǎn)向出錯(cuò)處理。2025/1/11Page58第5章自頂向下語(yǔ)法分析方法構(gòu)造預(yù)測(cè)分析表步驟：

(1)把文法轉(zhuǎn)變?yōu)長(zhǎng)L(1)文法

(2)求出每條產(chǎn)生式的SELECT集

(3)依照SELECT集把產(chǎn)生式填入分析表對(duì)每個(gè)終結(jié)符或‘＃’用a表示若a

SELECT(A→

)，則把A→

放入M[A,a]中，把所有無(wú)定義的M[A,a]標(biāo)上出錯(cuò)標(biāo)記。2025/1/11Page59第5章自頂向下語(yǔ)法分析方法例算術(shù)表達(dá)式文法G

E→E+T│T T→T*F│F F→(E)│i（1）消除G的左遞歸得到文法

G‘ E→TE' E'→+TE'│ε T→FT' T'→*FT'│ε F→(E)│i 2025/1/11Page60第5章自頂向下語(yǔ)法分析方法（2）求出每個(gè)產(chǎn)生式的select集,G’是LL(1)文法

SELECT(E→TE')={(,i} SELECT(E'→+TE')={+}SELECT(E'→ε)={),#} SELECT(T→FT')={(,i}SELECT(T'→*FT')={*} SELECT(T'→ε)={+,),#}SELECT(F→(E))={(} SELECT(F→i)={i}F→(E)F→iFT'→εT'→εT'→*FT'T'→εT'T→FT’T→FT’TE'→εE'→εE'→+TE’E'E#）（*+iE→TE’E→TE’（3）依照選擇集合把產(chǎn)生式填入分析表注：表中空白處為出錯(cuò)2025/1/11Page61第5章自頂向下語(yǔ)法分析方法上托棧頂符放入XNYYNNNNYYY把’#’和文法開(kāi)始符壓入分析棧；當(dāng)前輸入符送a把產(chǎn)生式右部反序進(jìn)棧X∈VT?X=’#’?X=a?X=a?讀下一輸入符到aM[X,a]有產(chǎn)生式？出錯(cuò)結(jié)束出錯(cuò)預(yù)測(cè)分析程序工作過(guò)程預(yù)測(cè)分析程序2025/1/11Page62第5章自頂向下語(yǔ)法分析方法輸入串i+i*i#的分析過(guò)程i+*（）#EE→TE’E→TE’E'E'→+TE’E'→εE'→εTT→FT’T→FT’T'T'→εT'→*FT'T'→εT'→εFF→iF→(E)+匹配+i*i##E’T+7E’→+TE’+i*i##E’6T’→ε+i*i##E’T’5i匹配i+i*i##E’T’i4F→ii+i*i##E’T’F3T→FT’i+i*i##E’T2E→TE’i+i*i##E1所用產(chǎn)生式剩余輸入串分析棧步驟反序壓棧!2025/1/11Page63第5章自頂向下語(yǔ)法分析方法T→FT’ i*i##E’T8F→i i##E’T’F13i匹配 i##E’T’i14T’→ε ##E’T’15E’→ε ##E’16接受 ##17*匹配 *i##E’T’F*12T’→*FT’ *i##E’T’11i匹配 i*i##E’T’i10F→i i*i##E’T’F9i+*（）#EE→TE’E→TE’E'E'→+TE’E'→εE'→εTT→FT’T→FT’T'T'→εT'→*FT'T'→εT'→εFF→iF→(E)2025/1/11Page64第5章自頂向下語(yǔ)法分析方法P96例1已知文法G[S]: SaH HaMd|d MAb|ε AaM|e1.判斷G[S]是否為L(zhǎng)L(1