第4章 語(yǔ)法分析-自頂向下

第4章語(yǔ)法分析(一)-自頂向下1/24/20241莆田學(xué)院許振和

語(yǔ)法分析常用的方法有自頂向下分析和自底向上分析兩大類(lèi)。

自頂向下的分析法:確定的自頂向下的分析法和不確定的自頂向下的分析法，常見(jiàn)確定的自頂向下的分析法有遞歸下降法和預(yù)測(cè)分析法（如LL(1)分析法），不確定的分析法即帶回溯的分析法。自底向上分析法：算符優(yōu)先分析法和LR分析法。其中，LR分析方法是目前編譯程序中應(yīng)用最廣泛，按分析能力從弱到強(qiáng)分別為：LR(0)分析法、SLR(1)分析法、LALR(1)分析法和LR(1)分析法等。語(yǔ)法分析主要內(nèi)容1/24/20242莆田學(xué)院許振和第4章自頂向下語(yǔ)法分析一、語(yǔ)法分析概述二、確定的自頂向下語(yǔ)法分析三、LL(1)文法的判別四、非LL(1)文法到LL(1)文法等價(jià)變換五、不確定的自頂向下分析思想六、確定的自頂向下分析方法1/24/20243莆田學(xué)院許振和一、語(yǔ)法分析概述詞法分析器語(yǔ)法分析器語(yǔ)義分析符號(hào)表源程序單詞符號(hào)語(yǔ)法樹(shù)中間表示

主要任務(wù)：

①對(duì)詞法分析器產(chǎn)生的單詞符號(hào)進(jìn)行處理，輸出分析樹(shù)

②與單詞相關(guān)的信息記錄到符號(hào)表中③類(lèi)型檢查④錯(cuò)誤處理1/24/20244莆田學(xué)院許振和自頂向下的語(yǔ)法分析是從文法的起始符號(hào)出發(fā)，反復(fù)使用文法中各種產(chǎn)生式，推導(dǎo)出句型，并一個(gè)符號(hào)地與給定終結(jié)符號(hào)串進(jìn)行匹配，尋找匹配于輸入串的推導(dǎo)。1、自頂向下的語(yǔ)法分析結(jié)果：1）利用推倒產(chǎn)生句子1/24/20245莆田學(xué)院許振和2）利用語(yǔ)法樹(shù)產(chǎn)生句子形成語(yǔ)法樹(shù)過(guò)程1/24/20246莆田學(xué)院許振和自底向上的語(yǔ)法分析就是從輸入串開(kāi)始，采用逐步進(jìn)行歸約的思想，直至歸約到文法的起始符號(hào)。2、自底向上的語(yǔ)法分析[例4-3]對(duì)于文法（4-1）G(Z)來(lái)說(shuō)，終結(jié)符號(hào)串a(chǎn)bbbdb的一棵語(yǔ)法樹(shù)如圖4-3所示，用自底向上分析法判斷終結(jié)符號(hào)串a(chǎn)bbbdb是否為文法（4-1）的一個(gè)句子。1/24/20247莆田學(xué)院許振和相反，符號(hào)串a(chǎn)bbbdb根據(jù)文法（4-1）G(Z)的自頂向下的推導(dǎo)過(guò)程為：ZaBbabDb

abbBbabbbDbabbbdb

=>=>=>=>=>串a(chǎn)bbbdb的推導(dǎo)過(guò)程1/24/20248莆田學(xué)院許振和3、推導(dǎo)推導(dǎo)就是從文法的開(kāi)始符號(hào)開(kāi)始，反復(fù)使用產(chǎn)生式，將產(chǎn)生式左部的非終結(jié)符替換為右部的文法符號(hào)序列，直到得到一個(gè)終結(jié)符(和非終結(jié)符)的序列。1/24/20249莆田學(xué)院許振和句型與句子最左推導(dǎo)與最右推導(dǎo)在推導(dǎo)過(guò)程中，若每次直接推導(dǎo)均替換句型中最左邊的非終結(jié)符，則稱(chēng)為最左推導(dǎo)，由最左推導(dǎo)產(chǎn)生的句型被稱(chēng)為左句型。若每次直接推導(dǎo)均替換句型中最右邊的非終結(jié)符，則稱(chēng)為最右推導(dǎo)，由最右推導(dǎo)產(chǎn)生的句型被稱(chēng)為右句型。

最右推導(dǎo)也被稱(chēng)為規(guī)范推導(dǎo)，其逆過(guò)程最左歸約稱(chēng)為規(guī)范歸約。1/24/202410莆田學(xué)院許振和分析樹(shù)亦稱(chēng)推導(dǎo)樹(shù)（語(yǔ)法樹(shù)），用來(lái)表示一個(gè)句型的推導(dǎo)。

4、推導(dǎo)過(guò)程的表示——分析樹(shù)對(duì)文法G的句型，分析樹(shù)的特點(diǎn)：（1）根由開(kāi)始符號(hào)所標(biāo)記；（2）每個(gè)葉子由一個(gè)終結(jié)符、非終結(jié)符或ε標(biāo)記，它們從左到右一個(gè)句型，稱(chēng)為樹(shù)的邊界或果實(shí)；（3）每個(gè)內(nèi)部結(jié)點(diǎn)由一個(gè)非終結(jié)符標(biāo)記；（4）若A→X1X2...Xn是一個(gè)產(chǎn)生式，則X1、X2、...、Xn是標(biāo)記為A的內(nèi)部結(jié)點(diǎn)從左到右所有孩子的標(biāo)記。1/24/202411莆田學(xué)院許振和分析樹(shù)與文法、語(yǔ)言的關(guān)系（1）每一直接推導(dǎo)（或者每個(gè)產(chǎn)生式），對(duì)應(yīng)一棵僅有父子關(guān)系的子樹(shù)，即產(chǎn)生式左部非終結(jié)符“長(zhǎng)出”右部的孩子。（2）分析樹(shù)的葉子從左到右，構(gòu)成G的一個(gè)句型。若葉子僅由終結(jié)符構(gòu)成，則構(gòu)成一個(gè)句子。1/24/202412莆田學(xué)院許振和基本目標(biāo)：（1）清楚而準(zhǔn)確地報(bào)告發(fā)現(xiàn)的錯(cuò)誤，地點(diǎn)正確、不漏報(bào)、不錯(cuò)報(bào)也不多報(bào)；（2）迅速地從每個(gè)錯(cuò)誤中恢復(fù)過(guò)來(lái)，以便分析繼續(xù)進(jìn)行；（3）對(duì)語(yǔ)法正確的源程序的分析速度不應(yīng)降低太多。5、語(yǔ)法分析的錯(cuò)誤處理1/24/202413莆田學(xué)院許振和6、錯(cuò)誤恢復(fù)策略1）緊急方式恢復(fù)（Panic-moderecovery）2）短語(yǔ)級(jí)恢復(fù)（Phrase-levelrecovery）3）出錯(cuò)產(chǎn)生式（Error-productions）4）全局糾正（Globalcorrection）1/24/202414莆田學(xué)院許振和二、確定的自頂向下分析思想自頂而下分析的基本思想：對(duì)于任何一個(gè)輸入序列，從文法的開(kāi)始符號(hào)開(kāi)始，進(jìn)行最左推導(dǎo)，直到得到一個(gè)合法句子或者發(fā)現(xiàn)一個(gè)非法結(jié)構(gòu)。在推導(dǎo)的過(guò)程中試圖用一切可能的方法，自上而下、從左到右為輸入序列建立分析樹(shù)。整個(gè)分析是一種試探的過(guò)程，是反復(fù)使用不同產(chǎn)生式謀求與輸入序列匹配的過(guò)程。1/24/202415莆田學(xué)院許振和語(yǔ)法分析是編譯程序的核心部分語(yǔ)法分析作用：識(shí)別由詞法分析給出的單詞符號(hào)序列是否是給定文法的正確句子（程序）語(yǔ)法分析的方法：自頂向下分析：確定分析、不確定分析

自底向上分析：算符優(yōu)先分析、LR分析二、確定的自頂向下分析思想1/24/202416莆田學(xué)院許振和例5

若有文法G1[S]:S→pA|qBA→cAd|aB→dB|c識(shí)別輸入串w=pccadd是否是G1[S]的句子試探推導(dǎo)過(guò)程：S

pA

pcAd

pccAdd

pccadd試探成功

1、確定的自頂向下分析文法：它是從文法的開(kāi)始符號(hào)出發(fā)，考慮如何根據(jù)當(dāng)前的輸入符號(hào)（單詞符號(hào)）唯一地確定選用哪個(gè)產(chǎn)生式替換相應(yīng)非終結(jié)符以往下推導(dǎo)，或如何構(gòu)造一棵相應(yīng)的語(yǔ)法樹(shù)。1/24/202417莆田學(xué)院許振和相應(yīng)的語(yǔ)法樹(shù)如圖5.1圖

5.1確定的自頂向下語(yǔ)法分析樹(shù)這個(gè)文法的特點(diǎn)：每個(gè)產(chǎn)生式的右部都由終結(jié)符號(hào)開(kāi)始如果兩個(gè)產(chǎn)生式有相同的左部，那么它們的右部由不同的終結(jié)符開(kāi)始1/24/202418莆田學(xué)院許振和例2：文法G(S)為：S→Ap∣BqA→a∣cAB→b∣dB當(dāng)輸入W=ccap推導(dǎo)：自頂向下的推導(dǎo)過(guò)程為：

S

Ap

cAp

ccAp

ccap這個(gè)文法的特點(diǎn)：產(chǎn)生式的右部不全是由終結(jié)符開(kāi)始如果兩個(gè)產(chǎn)生式有相同的左部，它們的右部是由不同的終結(jié)符或非終結(jié)符開(kāi)始文法中無(wú)空產(chǎn)生式1/24/202419莆田學(xué)院許振和相應(yīng)語(yǔ)法樹(shù)為圖5.2

：圖

5.2確定的自頂向下語(yǔ)法分析樹(shù)1/24/202420莆田學(xué)院許振和在上述2個(gè)例子推導(dǎo)過(guò)程中，如何根據(jù)輸入串的第1個(gè)符號(hào)來(lái)確定產(chǎn)生式呢？2、開(kāi)始符號(hào)集合(首終結(jié)符號(hào)集)的定義：

設(shè)G=（VT，VN，P，S）是上下文無(wú)關(guān)文法，開(kāi)始符號(hào)集合為First()={a|

aβ，a∈VT，

、β∈V*}

若

ε，則規(guī)定

∈First(

)。**1/24/202421莆田學(xué)院許振和例3：上例中文法是：S

Ap|BqA

a|cAB

b|dB則：FIRST(Ap)={a，c}

FIRST(Bq)={b，d}1/24/202422莆田學(xué)院許振和SaA

SaAbAS

SaAbAS

d例4：文法G[S]：

S

aA|dA

bAS|ε

若輸入W=abd，則推導(dǎo)過(guò)程為：

S

aA

abAS

abS

abd語(yǔ)法樹(shù)為：1/24/202423莆田學(xué)院許振和

從上例可以看出：每步推導(dǎo)的產(chǎn)生式該如何確定呢？如何知道非終結(jié)符后跟什么，為此引入后跟符號(hào)的集合定義：3、后跟符號(hào)集合的定義：

設(shè)G=（VT，VN，P，S）是上下文無(wú)關(guān)文法，A∈VN，S是開(kāi)始符號(hào)，F(xiàn)ollow(A)={a|S

uAβ且a∈VT，a∈First(β)，u∈VT*，β∈V+}。若S

uAβ，且β

ε，則#∈Follow(A)（#表示輸入串的結(jié)束符，或句子括號(hào)）***1/24/202424莆田學(xué)院許振和換句話說(shuō)：

Follow(A)是所有句型中出現(xiàn)在緊接A之后的終結(jié)符或“#”?？蓪?xiě)成為：Follow(A)＝｛a|S…Aa…，a∈VT｝若S…A，則#∈Follow(A)。1/24/202425莆田學(xué)院許振和例5：在例2中文法G[S]為：S

Ap|BqA

a|cAB

b|dB求Follow集。解：Follow(S)={#}Follow(A)={p}Follow(B)={q}1/24/202426莆田學(xué)院許振和4、選擇集合的定義給定上下文無(wú)關(guān)文法的產(chǎn)生式A

，A

VN，

V*，若

ε，則Select(A)=First(

)，若

ε,則Select(A

)=(First(

)-{ε})∪Follow(A)5、LL(1)文法的定義：(自頂向下分析技術(shù))一個(gè)上下文無(wú)關(guān)文法是LL(1)文法的充分必要條件是對(duì)每個(gè)非終結(jié)符A的兩個(gè)不同產(chǎn)生式：A

，A

β滿足Select(A)∩Select(A

β)=

，其中、β不同時(shí)推出

**1/24/202427莆田學(xué)院許振和根據(jù)前面的討論容易看出：能夠使用自頂向下分析技術(shù)的文法正是LL（1）文法：第一個(gè)L表明自頂向下分析是從左向右掃描輸入串第二個(gè)L表明分析過(guò)程中將用最左推導(dǎo)1表明只需向右看一個(gè)符號(hào)便可決定如何推導(dǎo)即選擇哪個(gè)產(chǎn)生式（規(guī)則）進(jìn)行推導(dǎo)LL（k）文法，也就是需向前查看k個(gè)符號(hào)才可確定選用哪個(gè)產(chǎn)生式1/24/202428莆田學(xué)院許振和例5：上例3文法：S

aA|d

A

bAS|ε不難看出：Select(S

aA)=First(aA)＝{a}Select(S

d)=First(d)=8uqamcySelect(A

bAS)=Select(A

ε)=(first(ε)-{ε})∪f(wàn)ollow(A)={a,d,#}Select(S

aA)∩Select(S

d)＝{a}∩osoik06=

Select(A

bAS)∩Select(A

ε)=∩{a,d,#}=

所以上述文法是LL(1)文法。

S

AaaA

ε*SaA

abAS

abAdSaA

abAS

abAaA所以Follow(A)={a,d,#}1/24/202429莆田學(xué)院許振和例：設(shè)文法G[S]為：

S

aAS

|bA

bA

|ε判別是否是LL(1)文法。解：Select(S

aAS)=first(aAS)={a}Select(S

b)=Select(A

bA)=Select(A

ε)=(first(ε)-{ε})∪f(wàn)ollow(A)={a,b}S

aAS

aAbSaAS

aAaAS1/24/202430莆田學(xué)院許振和Select(S

aAS)∩Select(S

b)＝{a}∩=

Select(A

bA)∩Select(A

ε)＝∩{a,b}

因此，該文法不是LL（1）文法，因而也就不能用確定的自頂向下分析。1/24/202431莆田學(xué)院許振和判別文法是否是LL（1）文法，對(duì)任何文法計(jì)算需計(jì)算FIRST、FOLLOW和SELECT集合，進(jìn)而判別文法是否為L(zhǎng)L（1）文法。舉例說(shuō)明判斷LL（1）文法的步驟。三、LL(1)文法的判別1/24/202432莆田學(xué)院許振和例：若文法G[S]為：S

AB|bCA

ε|bB

ε|aDC

AD|bD

aS

|c判別文法是否是LL(1)文法。解：(1)計(jì)算first集：方法一：計(jì)算first集合的算法：對(duì)于每一個(gè)文法符號(hào)xV，計(jì)算first(x)的方法如下：1/24/202433莆田學(xué)院許振和若xVT，則first(x)＝{x}若xVN，且有xa…，aVT，則a

first(x)若xVN，x

，則

first(x)若x

VN，y1，y2，…，yi都

VN，產(chǎn)生式xy1y2…yn，當(dāng)y1，y2，…yi-1都

時(shí)(1≤i≤n)，

則first(y1)－{

}，first(y2)－{

}，…，first(yi－1)－{

}，first(yi)都包含在first(x)中。e)當(dāng)上式中所有yi

(1≤i≤n)，則first(x)＝first(y1)∪f(wàn)irst(y2)∪…∪f(wàn)irst(yn)∪{

}**1/24/202434莆田學(xué)院許振和first(S)={first(A)}∪{first(B)}∪{}∪={a,b,}first(A)=∪{}={b,}first(B)={}∪{a}={a,}first(C)={first(A)-{}}∪f(wàn)irst(D)∪f(wàn)irst(b)={a,b,c}first(D)={a}∪{c}={a,c}S

AB|bCA

ε|bB

ε|aDC

AD|bD

aS

|c按上面的規(guī)則可得上例文法中每個(gè)文法符號(hào)的first集合如下：1/24/202435莆田學(xué)院許振和方法二：由關(guān)系圖法求文法符號(hào)的first集合1、每個(gè)文法符號(hào)對(duì)應(yīng)圖中的一個(gè)結(jié)點(diǎn)，終結(jié)符結(jié)點(diǎn)用符號(hào)本身標(biāo)記，非終結(jié)符結(jié)點(diǎn)用first(A)標(biāo)記。2、若文法中有AX，ε，則從對(duì)應(yīng)A的結(jié)點(diǎn)到對(duì)應(yīng)X結(jié)點(diǎn)連一條箭弧。3、凡是從first(A)結(jié)點(diǎn)有路徑可到達(dá)的終結(jié)符結(jié)點(diǎn)所標(biāo)記的終結(jié)符都為first(A)的成員。4、由判別1確定ε是否為某非終結(jié)符first的成員，若是則將ε加入該非終結(jié)符的first集中。*1/24/202436莆田學(xué)院許振和bac文法為：S

AB|bCA

ε|bB

ε|aDC

AD|bD

aS

|c(1)規(guī)則1：終結(jié)符結(jié)點(diǎn)用符號(hào)本身標(biāo)記，本文法中有a,b,c。1/24/202437莆田學(xué)院許振和first(S)first(B)first(C)first(A)first(D)bac文法為：S

AB|bCA

ε|bB

ε|aDC

AD|bD

aS

|c(2)規(guī)則1：非終結(jié)符結(jié)點(diǎn)用first(A)標(biāo)記。本文法中有S,A,B,C,D。1/24/202438莆田學(xué)院許振和first(S)first(B)first(C)first(A)first(D)bac文法為：S

AB|bCA

ε|bB

ε|aDC

AD|bD

aS

|c(3)規(guī)則2：AX，ε，則A到X畫(huà)一條箭弧。S

AB看成＝ε，X＝A,=B因此從S到A畫(huà)一條弧。1/24/202439莆田學(xué)院許振和first(S)first(B)first(C)first(A)first(D)bac文法為：S

AB|bCA

ε|bB

ε|aDC

AD|bD

aS

|c(3)規(guī)則2：AX，ε，則A到X畫(huà)一條箭弧。S

AB看成＝A，X＝B,=εA

ε,因此從S到B畫(huà)一條弧。1/24/202440莆田學(xué)院許振和first(S)first(B)first(C)first(A)first(D)bac文法為：S

AB|bCA

ε|bB

ε|aDC

AD|bD

aS

|c(3)規(guī)則2：AX，ε，則A到X畫(huà)一條箭弧。S

bC看成

＝ε，X＝b,

=C因此從S到b畫(huà)一條弧。1/24/202441莆田學(xué)院許振和first(S)first(B)first(C)first(A)first(D)bac文法為：S

AB|bCA

ε|bB

ε|aDC

AD|bD

aS

|c(3)規(guī)則2：AX，ε，則A到X畫(huà)一條箭弧。同理：從A到b，從B到a，從C到A、D、b，從D到a、c畫(huà)一條弧。1/24/202442莆田學(xué)院許振和(4)規(guī)則3：first(A)結(jié)點(diǎn)有路徑可到達(dá)的終結(jié)符結(jié)點(diǎn)所標(biāo)記的終結(jié)符都為first(A)的成員。所以，first(S)＝｛a,b｝first(A)＝｛b｝first(B)＝｛a｝first(C)＝｛a,b,c｝first(D)＝｛a,c｝(5)規(guī)則4：若ε是某非終結(jié)符first的成員，則將ε加入該非終結(jié)符的first集中。所以，first(S)＝｛a,b,ε｝first(A)＝｛b,ε｝first(B)＝｛a,ε｝first(C)＝｛a,b,c｝first(D)＝｛a,c｝first(S)first(B)first(C)first(A)first(D)bac1/24/202443莆田學(xué)院許振和計(jì)算Follow集：方法一：根據(jù)Follow定義計(jì)算：①求follow集的算法：對(duì)文法中每一A∈VN

計(jì)算FOLLOW(A)(a)設(shè)S為文法中開(kāi)始符號(hào)，把{#}加入FOLLOW(S)中(這里“#”為句子括號(hào))(b)若A→αBβ是一個(gè)產(chǎn)生式，則把FIRST(β)的非空元素加入FOLLOW(B)中。如果β

ε則把FOLLOW(A)也加入FOLLOW(B)中(c)反復(fù)使用(b)直到每個(gè)非終結(jié)符的FOLLOW集不再增大為止*簡(jiǎn)單法：(1)設(shè)S為開(kāi)始符號(hào)，則#follow(S);(2)Follow(A)是所有句型中出現(xiàn)在緊接A之后的終結(jié)符或“#”。1/24/202444莆田學(xué)院許振和SAB

BBbA

AaDFollow(S)={#}Follow(A)={a，#，c}Follow(B)={#}Follow(C)={#}Follow(D)={#}文法為：S

AB|bCA

ε|bB

ε|aDC

AD|bD

aS

|cS為開(kāi)始符號(hào)，#加入follow(S)中。SABA

AABAaD

bC

bADbAc1/24/202445莆田學(xué)院許振和方法二：根據(jù)關(guān)系圖法求非終結(jié)符Follow集。步驟如下：文法G中的每個(gè)符號(hào)和“#”對(duì)應(yīng)圖中的一個(gè)結(jié)點(diǎn)，對(duì)應(yīng)終結(jié)符和“#”的結(jié)點(diǎn)用符號(hào)本身標(biāo)記。對(duì)應(yīng)非終結(jié)符的結(jié)點(diǎn)(如A

Vn)，則用Follow(A)或first(A)標(biāo)記。從開(kāi)始符號(hào)S的Follow(S)結(jié)點(diǎn)到“#”號(hào)的結(jié)點(diǎn)連一條箭弧。如果文法中有產(chǎn)生式ABX，且ε，則從Follow(B)結(jié)點(diǎn)到first(X)結(jié)點(diǎn)連一條箭弧，當(dāng)X

Vt時(shí)，則與X相連。*1/24/202446莆田學(xué)院許振和(4)如果文法中有產(chǎn)生式AB，且ε，則從Follow(B)結(jié)點(diǎn)到Follow(A)結(jié)點(diǎn)連一條箭弧。(5)對(duì)每一first(A)結(jié)點(diǎn)如果有產(chǎn)生式A

X

，且

ε，則從first(A)到first(X)連一條箭弧。(6)凡是從Follow(A)結(jié)點(diǎn)有路徑可以到達(dá)的終結(jié)符或“#”號(hào)的結(jié)點(diǎn)，其所標(biāo)記的終結(jié)符或“#”號(hào)即為Follow(A)的成員。**1/24/202447莆田學(xué)院許振和first(B)#first(D)Follow(S)Follow(B)Follow(D)Follow(C)Follow(A)ac(1)文法G中的每個(gè)符號(hào)和“#”對(duì)應(yīng)圖中的一個(gè)結(jié)點(diǎn)，對(duì)應(yīng)終結(jié)符和“#”的結(jié)點(diǎn)用符合本身標(biāo)記。對(duì)應(yīng)非終結(jié)符的結(jié)點(diǎn)(如A

Vn)，則用Follow(A)或first(A)標(biāo)記。S

AB|bCA

ε|bB

ε|aDC

AD|bD

aS

|c1/24/202448莆田學(xué)院許振和(2)從開(kāi)始符號(hào)S的Follow(S)結(jié)點(diǎn)到“#”號(hào)的結(jié)點(diǎn)連一條箭弧。first(B)#first(D)Follow(S)Follow(B)Follow(D)Follow(C)Follow(A)acS

AB|bCA

ε|bB

ε|aDC

AD|bD

aS

|c1/24/202449莆田學(xué)院許振和(3)如果文法中有產(chǎn)生式A

B

X,且

ε，則從Follow(B)結(jié)點(diǎn)到first(X)結(jié)點(diǎn)連一條箭弧，當(dāng)X

Vt時(shí)，則與X相連。S

AB看成＝ε,

＝ε則從Follow(A)結(jié)點(diǎn)到first(B)結(jié)點(diǎn)連一條箭弧。C

AD看成＝ε,

＝ε則從Follow(A)結(jié)點(diǎn)到first(D)結(jié)點(diǎn)連一條箭弧。first(B)#first(D)Follow(S)Follow(B)Follow(D)Follow(C)Follow(A)acS

AB|bCA

ε|bB

ε|aDC

AD|bD

aS

|c1/24/202450莆田學(xué)院許振和(4)如果文法中有產(chǎn)生式A

B

，且

ε，則從Follow(B)結(jié)點(diǎn)到Follow(A)結(jié)點(diǎn)連一條箭弧。S

AB

看成＝A,

＝ε則從Follow(B)到Follow(S)連一條弧。S

AB看成＝ε,

＝B,B

ε則從Follow(A)到Follow(S)連弧。S

bC

看成＝b,

＝ε則從Follow(C)到Follow(S)連一條弧。B

aD

看成＝a,

＝ε則從Follow(D)到Follow(B)連一條弧。C

AD

看成＝A,

＝ε則從Follow(D)到Follow(C)連一條弧。D

aS

看成＝a,

＝ε則從Follow(S)到Follow(D)連一條弧。first(B)#first(D)Follow(S)Follow(B)Follow(D)Follow(C)Follow(A)acS

AB|bCA

ε|bB

ε|aDC

AD|bD

aS

|c1/24/202451莆田學(xué)院許振和(5)對(duì)每一first(A)結(jié)點(diǎn)如果有產(chǎn)生式A

X

，且

ε，則從first(A)到first(X)連一條箭弧。對(duì)于first(B)結(jié)點(diǎn)：BaD,a

為

不

ε,不存在first(B)到first(D)箭弧。BaD,看成=ε,=D,X=a,從first(B)到a連一條箭弧。對(duì)于first(D)結(jié)點(diǎn)：DaS,a

為

不

ε,不存在first(D)到first(S)連一條箭弧。DaS,看成=ε,=S,X=a,從first(D)到a連一條箭弧。Dc,看成=ε,=ε,X=c,從first(D)到c連一條箭弧。first(B)#first(D)Follow(S)Follow(B)Follow(D)Follow(C)Follow(A)acS

AB|bCA

ε|bB

ε|aDC

AD|bD

aS

|c1/24/202452莆田學(xué)院許振和(6)凡是從Follow(A)結(jié)點(diǎn)有路徑可以到達(dá)的終結(jié)符或“#”號(hào)的結(jié)點(diǎn)，其所標(biāo)記的終結(jié)符或“#”號(hào)即為Follow(A)的成員。#first(B)Follow(S)Follow(B)Follow(D)Follow(A)first(D)Follow(C)aaFollow(S)={#}Follow(A)={a，#，c}Follow(B)={#}Follow(C)={#}Follow(D)={#}1/24/202453莆田學(xué)院許振和(3)計(jì)算Select集：每個(gè)產(chǎn)生式的Select集合計(jì)算為:Select(S

AB)=first(AB)∪Follow(S)={b,a,#}Select(S

bC)=first(bC)=Select(A

ε)=(first(ε)-{})

∪Follow(A)={c,a,#}Select(A

b)=first(b)=Select(B

ε)=(first(ε)-{})

∪Follow(B)={#}Select(B

aD)=first(aD)={a}Select(C

AD)=first(AD)={b,a,c}因?yàn)锳

B

1/24/202454莆田學(xué)院許振和Select(C

b)=first(C)=Select(D

aS)=first(aS)={a}Select(D

c)=first(c)={c}所以select的交集為：Select(S

AB)∩Select(S

bC)=≠

Select(A

ε)∩Select(A

b)=

Select(B

ε)∩Select(B

aD)=

Select(C

AD)∩Select(C

b)=

Select(D

aS)∩Select(D

c)=

因此該文法不是LL(1)文法。1/24/202455莆田學(xué)院許振和四、非LL(1)文法到LL(1)文法的等價(jià)變換

若文法中含有直接或間接左遞歸，含有左公共因子，該文法肯定不是LL(1)文法，要進(jìn)行變換。

1、

提取左公共因子提取左因子是一種對(duì)產(chǎn)生適合預(yù)測(cè)分析的文法非常有用的文法變換?？梢杂脕?lái)消除回溯。若文法中含有形如A

|

的產(chǎn)生式，這導(dǎo)致了對(duì)相同左部的產(chǎn)生式其右部的First集相交,也就是Select(A

)∩Select(A

)

，不滿足LL(1)文法的充分必要條件.則須進(jìn)行提取左公共因子的等價(jià)變換:A

(

|

)寫(xiě)成一般形式：AA’

A’

1/24/202456莆田學(xué)院許振和例1：若文法G1的產(chǎn)生式為：S

aSbS

aSS

ε提取左公因子后得：S

aS(b|ε)

S

ε進(jìn)一步變換：S

aSAA

bA

ε

S

ε1/24/202457莆田學(xué)院許振和例2：若文法G2的產(chǎn)生式：Aad

ABc

BaA

BbB

解：A

adA

aAcA

bBcB

aAB

bBAa(d|Ac)AaA’A’dA’Ac1/24/202458莆田學(xué)院許振和A

aA’

A

bBcA’

dA’AcB

aAB

bB最后變換為：不難驗(yàn)證經(jīng)提取左公共因子后文法仍不是LL(1)文法。1/24/202459莆田學(xué)院許振和經(jīng)過(guò)文法提取左公共因子后的文法不一定是LL(1)文法。文法中不含左公共因子只是LL(1)文法的必要條件，而不是充分條件。經(jīng)過(guò)文法提取左公共因子后的文法，若有多余的產(chǎn)生式，則必須進(jìn)行化簡(jiǎn)。

不一定每個(gè)文法的左公共因子都能在有限的步驟內(nèi)替換成無(wú)左公共因子的文法。一個(gè)文法提取了左公共因子后，只解決了相同左部產(chǎn)生式右部的FIRST集不相交問(wèn)題，當(dāng)改寫(xiě)后的文法不含空產(chǎn)生式，且無(wú)左遞歸時(shí)，則改寫(xiě)后的文法才有可能是LL(1)文法。否則還需用LL(1)文法的判別方式進(jìn)行判斷才能確定是否為L(zhǎng)L(1)文法。1/24/202460莆田學(xué)院許振和2、消除左遞歸1.

一個(gè)文法含有下列形式的產(chǎn)生式時(shí)，

a)A

A

A

VN,

V*b)A

B

B

A

A,B

VN,

，

V*

稱(chēng)為左遞歸文法。其中a)是直接遞歸，b)是間接遞歸。例1：文法SSaSb是直接左遞歸所產(chǎn)生的語(yǔ)言是：L＝{ban|n≥0}1/24/202461莆田學(xué)院許振和例2：文法為：AaBABbBAcBd是間接左遞歸※消除左遞歸的變換方法：

(1)

消除直接左遞歸，把直接遞歸改寫(xiě)為右遞歸：方法：改為右遞歸。如

S

Sa

改寫(xiě)為：S

bS

S

bS

aS

|ε1/24/202462莆田學(xué)院許振和(2)消除間接左遞歸：方法：間接左遞歸直接左遞歸右遞歸

化簡(jiǎn)文法例3：文法G6為:A

aBA

BbB

AcB

d

A

aBA

Bb

B

aBc

BBbcB

d

B

aBc|d

BBbc

B(aBc|d)B'

B'bcB'|

1/24/202463莆田學(xué)院許振和A

aBA

BbB(aBc|d)B

B

bcB

|ε對(duì)文法中一切左遞歸的消除要求文法中不含回路，即無(wú)A

A的推導(dǎo)。滿足該文法的充分條件是：文法中不包含形如A

A的有害規(guī)則和A

ε的產(chǎn)生式。＋1/24/202464莆田學(xué)院許振和【例4-10】考慮下面的算術(shù)表達(dá)式文法：產(chǎn)生式E→E+T和T→T*F存在直接左遞歸，則消除直接左遞歸，可以得到：1/24/202465莆田學(xué)院許振和五、不確定的自頂向下分析思想當(dāng)文法不滿足LL(1)時(shí)，則不能用確定的自頂向下分析，只能用不確定的自頂向下分析法，也就是帶回溯的自頂向下分析法。在文法中當(dāng)關(guān)于某個(gè)非終結(jié)符的產(chǎn)生式有多個(gè)候選時(shí)，而面臨當(dāng)前的輸入符無(wú)法確定選用唯一的產(chǎn)生式，從而引起回溯。確定的自頂向下分析法－LL(1)文法不確定的自頂向下分析法－帶回溯的自頂向下分析法1、由于相同左部的產(chǎn)生式的右部First集交集不為空而引起回溯。1/24/202466莆田學(xué)院許振和例：文法SxAy

Aab|a求輸入串為xay語(yǔ)法樹(shù)。first(ab)與first(a)的交集不為空SxAySxAyabSxAya回溯SxAy若選擇Aab，就于xay不匹配回溯，用Aa就匹配1/24/202467莆田學(xué)院許振和2、由于相同左部非終結(jié)符的右部能，且該非終結(jié)符Follow集中含有其右部First集的元素而引起回溯。例：S

aAS

|bAbAS

|求對(duì)輸入串a(chǎn)b#的推導(dǎo)樹(shù)。A

Follow(A)={a,b}first(bAs)=SaASSaASbAS回溯SaASb

*1/24/202468莆田學(xué)院許振和3、由于文法含有左遞歸而引起回溯。例：SSaSb若推導(dǎo)baa#Sb回溯SSaSSab回溯SSaSaSSaSab1/24/202469莆田學(xué)院許振和由以上例子可知：帶回溯的自頂向下分析是是一個(gè)試探過(guò)程，當(dāng)分析不成功時(shí)則推翻分析退回到適當(dāng)位置再重新試探其余候選可能的推導(dǎo)，這樣需要記錄已選過(guò)的產(chǎn)生式，直到把所有可能的推導(dǎo)序列都試完仍不成功才能確認(rèn)輸入串不是該文法的句子而報(bào)錯(cuò)。由于在編譯程序真正實(shí)現(xiàn)時(shí)往往是邊分析邊插入語(yǔ)義動(dòng)作，因而帶回溯分析代價(jià)很高，效率很低，在實(shí)用編譯程序中幾乎不用，因此對(duì)它實(shí)現(xiàn)的詳細(xì)算法不做介紹1/24/202470莆田學(xué)院許振和六、確定的自頂向下分析方法1、遞歸下降分析技術(shù)：實(shí)現(xiàn)思想：識(shí)別程序由一組過(guò)程組成。每個(gè)過(guò)程對(duì)應(yīng)于一個(gè)非終結(jié)符號(hào)。每一個(gè)過(guò)程的功能是：選擇正確的右部，掃描完相應(yīng)的字。在右部中有非終結(jié)符號(hào)時(shí)，調(diào)用該終結(jié)符號(hào)對(duì)應(yīng)的過(guò)程來(lái)完成。1/24/202471莆田學(xué)院許振和遞歸下降技術(shù)（實(shí)例）文法GE::=E+T|T T::=T*F F::=(E)|i消左遞歸得到

E::=TE’ E’::=+TE’|

T::=FT’ T’::=*FT’| F::=(E)|i1/24/202472莆田學(xué)院許振和遞歸下降技術(shù)（實(shí)例續(xù)）對(duì)應(yīng)于文法G中的每個(gè)非終結(jié)符號(hào)，都有一個(gè)過(guò)程。E(){if(當(dāng)前符號(hào)可能是T的開(kāi)始符號(hào)) {T();E1();}else error();}1/24/202473莆田學(xué)院許振和遞歸下降技術(shù)（實(shí)例續(xù)）E1(){

if(ch=‘+’) {

getnextchar();T();E1()；

} else return;}因?yàn)镋1對(duì)應(yīng)有空規(guī)則，所以其處理中，不做錯(cuò)誤處理，而是直接return。實(shí)際表示它沒(méi)有讀入任何字符。1/24/202474莆田學(xué)院許振和文法G[E]:

E→TE?PROCEDUREE;//相對(duì)應(yīng)于開(kāi)始符號(hào)，

BEGIN//它收養(yǎng)兩個(gè)兒子

T;E?ENDE?→+TE?∣εPROCEDUREE?;IFSYM=‘+’THENBEGIN

ADVANCE;T;E?;END

把輸入指示器IP調(diào)向下一個(gè)輸入符號(hào)/*遇到+則匹配，選用第一候選；若面臨其他字符就自動(dòng)認(rèn)為獲得了匹配，但當(dāng)前IP并不前進(jìn)。*/SYM是指輸入串指示器IP當(dāng)前所指的那個(gè)輸入符號(hào)1/24/202475莆田學(xué)院許振和遞歸分析程序的優(yōu)缺點(diǎn)優(yōu)點(diǎn)：實(shí)現(xiàn)思想簡(jiǎn)單明了。程序結(jié)構(gòu)和語(yǔ)法規(guī)則有直接的對(duì)應(yīng)關(guān)系。因?yàn)槊總€(gè)過(guò)程表示一個(gè)非終結(jié)符號(hào)的處理，添加語(yǔ)義加工工作比較方便。需要書(shū)寫(xiě)程序的語(yǔ)言支持遞歸調(diào)用。如果遞歸調(diào)用機(jī)制是高效的，那么分析程序也是高效的。缺點(diǎn)：對(duì)文法要求高，必須滿足LL（1）文法，個(gè)別LL（2）例外速度慢占用空間多1/24/202476莆田學(xué)院許振和2、預(yù)測(cè)分析方法自頂向下分析的另一種方法預(yù)測(cè)分析器的組成：預(yù)測(cè)分析程序先進(jìn)后出棧預(yù)測(cè)分析表－與文法有關(guān)預(yù)測(cè)分析表：用矩陣M[A,a]表示，A表示非終結(jié)符，a為終結(jié)符或句子括號(hào)#，矩陣M[A,a]中的內(nèi)容是一條關(guān)于A的產(chǎn)生式，表明當(dāng)用非終結(jié)符A向下推導(dǎo)時(shí)，面臨輸入符a時(shí)，所應(yīng)采取的候選產(chǎn)生式，當(dāng)元素內(nèi)容無(wú)產(chǎn)生時(shí)，則表明用A為左部向下推導(dǎo)時(shí)遇到了不該出現(xiàn)的符號(hào)，因此元素內(nèi)容為轉(zhuǎn)向出錯(cuò)處理的信息。1/24/202477莆田學(xué)院許振和＃句子括號(hào)即輸入串的括號(hào)，S文法的開(kāi)始符號(hào)X存放當(dāng)前棧頂符號(hào)的工作單元，a存放當(dāng)前輸入符號(hào)a的工作單元（2）預(yù)測(cè)分析程序工作過(guò)程示意圖：1/24/202478莆田學(xué)院許振和

SSaS

bS'SbS'aS'|E

E+TE

T(3)構(gòu)造預(yù)測(cè)分析表：例：文法為：E

E+T|TT

T*F|FF

i|(E)構(gòu)造步驟有：

判斷文法是否為L(zhǎng)L(1)文法。

由于文法中含有左遞歸，所以必須先消除左遞歸：

E

E+T|TE

TE

E

+TE

|ε

1/24/202479莆田學(xué)院許振和T

T*F|FT

FT

T

*FT

|εE

TE

E

+TE

|εT

FT

T

*FT

|εF

i|(E)

文法變?yōu)椋?/24/202480莆田學(xué)院許振和

求First集合：First(E)={(，i}First(E)={+，ε}First(T)={(，i}First(T)={*，ε}First(F)={(，i}∵E

TE

T不，E'不

∴First(E)=first(T)=first(F)={(,i}

求Follow集：

Follow(E)={

，#}Follow(E)={

，#}Follow(T)={+，

，#}Follow(T)={+，

，#}Follow(F)={*，+，

，#}

ETE'FT'E'(E)T'E'ETE'FT'E'

(E)T'E‘(TE')T'E'E

TE'

T+T'E'

T+TT+FT'T+(E)T'T+(TE')T'

T+(T)T'E

TE'

FT'E'

FT'F*FT'F*(E)T‘F*(TE')T'F*(FT'E')T‘F*(FT')T'1/24/202481莆田學(xué)院許振和求Select集：Select(E

TE)={(，i}Select(E

+TE)={+}Select(E

ε)={

，#}Select(T

FT)={(，i}Select(T

*FT)={*}Select(T

ε)={+，

，#}Select(F

i)={i}Select(F

(E))={(}由上可知有相同左部產(chǎn)生式的Select集合的交集為空，所以文法是LL(1)1/24/202482莆田學(xué)院許振和構(gòu)造預(yù)測(cè)分析表：

方法：對(duì)每個(gè)終結(jié)符或#用a表示。若aSelect(Aa)，則Aa放入M[A,a]中。i+*()#ETE'TE'E'

+TE'

TFT'FT'T'

*FT'

Fi

(E)1