第5自頂向下語(yǔ)法分析方法

第5自頂向下語(yǔ)法分析方法自頂向下分析法也就是從文法的開(kāi)始符號(hào)出發(fā)企圖推導(dǎo)出與輸入的單詞串完全相匹配的句子，若輸入串是給定文法的句子，則必能推出，反之必然出錯(cuò)。回顧在“文法和語(yǔ)言”一章中介紹的關(guān)于句子、句型和語(yǔ)言的定義及什么叫最左推導(dǎo)、最右推導(dǎo)和規(guī)范推導(dǎo)的基本概念。句型、句子、語(yǔ)言的定義

句型:

有文法G[S]，若S

x，且x∈V*則稱(chēng)x是文法G[S]的句型。

符號(hào)

表示經(jīng)過(guò)0步或若干步的推導(dǎo)。

句子:

有文法G[S]，若S

x，且x∈VT*，則稱(chēng)x是文法G[S]的句子。

例：G[S]：S→0S1，S→01

可有推導(dǎo)S

0S1

00S11

000S111

00001111

說(shuō)明是G[S]的句子。

句型的分析

句型分析就是識(shí)別一個(gè)符號(hào)串是否為某文法的句型，是某個(gè)推導(dǎo)的構(gòu)造過(guò)程。

最左（最右）推導(dǎo)：在推導(dǎo)的任何一步α

β，都是對(duì)α中的最左（右）非終結(jié)符進(jìn)行替換。

最右推導(dǎo)被稱(chēng)為規(guī)范推導(dǎo)。

由規(guī)范推導(dǎo)所得的句型稱(chēng)為規(guī)范句型。句型分析的有關(guān)問(wèn)題

①如何選擇使用哪個(gè)產(chǎn)生式進(jìn)行推導(dǎo)？

假定要被替換的最左非終結(jié)符號(hào)是V，且左部為V的規(guī)則有n條：V→A1|A2|…|An，那么如何確定用哪個(gè)右部去替換V呢？

②如何識(shí)別可歸約的串？

在自下而上的分析方法中，在分析程序工作的每一步，都是從當(dāng)前串中尋找一個(gè)子串，看它是否能歸約到文法的某個(gè)非終結(jié)符號(hào)，該子串稱(chēng)為“可歸約串”。5.1確定的自頂向下分析思想確定的自頂向下分析方法:首先要解決從某文法的開(kāi)始符號(hào)出發(fā)，對(duì)給定的輸入符號(hào)串如何根據(jù)當(dāng)前的輸入符號(hào)(單詞符號(hào))唯一地確定選用哪個(gè)產(chǎn)生式替換相應(yīng)非終結(jié)符往下推導(dǎo).

例5.1若有文法G1[S]:

S→pA|qB

A→cAd|a

B→dB|c

識(shí)別輸入串w=pccadd是否是G1[S]的句子

試探推導(dǎo)過(guò)程：

S

pA

pcAd

pccAdd

pccadd

試探成功。

這個(gè)文法有以下兩個(gè)特點(diǎn)：

①每個(gè)產(chǎn)生式的右部都由終結(jié)符號(hào)開(kāi)始。

②如果兩個(gè)產(chǎn)生式有相同的左部，那么它們的右部由不同的終結(jié)符開(kāi)始。即每個(gè)產(chǎn)生式的右部的開(kāi)始終結(jié)符不同。

對(duì)于這樣的文法顯然在推導(dǎo)過(guò)程中完全可以根據(jù)當(dāng)前的輸入符號(hào)決定選擇哪個(gè)產(chǎn)生式往下推導(dǎo)，因此分析過(guò)程是唯一確定的。

例5.2若有文法G2[S]:

S→Ap|Bq

A→a|cA

B→b|dB

識(shí)別輸入串w=ccap是否是G2[S]的句子，那么試探推出輸入串的推導(dǎo)過(guò)程為：

S

Ap

cAp

ccAp

ccap

試探推導(dǎo)成功。文法的特點(diǎn)是：

①產(chǎn)生式的右部不全是由終結(jié)符開(kāi)始。

②如果兩個(gè)產(chǎn)生式有相同的左部，它們的右部是由不同的終結(jié)符或非終結(jié)符開(kāi)始。

③文法中無(wú)空產(chǎn)生式。對(duì)于產(chǎn)生式中相同左部含有非終結(jié)符開(kāi)始的產(chǎn)生式時(shí)，在推導(dǎo)過(guò)程中選用哪個(gè)產(chǎn)生式不像例5.1文法那樣直觀(guān)，對(duì)于W=ccap為輸入串時(shí)，其第一個(gè)符號(hào)是c，這時(shí)從S出發(fā)選擇S→Ap還是選擇S→Bq，需要知道，Ap或Bq它們的開(kāi)始終結(jié)符號(hào)集合是什么？因?yàn)閏是包含在A(yíng)p的開(kāi)始終結(jié)符號(hào)集合中，且不包含在Bq的開(kāi)始終結(jié)符號(hào)集合中，則選擇S→Ap往下進(jìn)行推導(dǎo)。S→Ap|Bq

A→a|cA

B→b|dB

一個(gè)文法符號(hào)串的終結(jié)符的首符集定義如下：

定義5.1

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

FIRST(α)={a|α

aβ,a∈VT，α,β∈V*}

若α

ε,則規(guī)定ε∈FIRST(α)．

不難求出在例5.2文法G2中

FIRST(Ap)={a,c}

FIRST(Bq)={b,d}

因此有FIRST(Ap)∩(FIRST(Bq)=?

這樣文法G中，兩個(gè)產(chǎn)生式有相同的左部，它們的右部是由不同的終結(jié)符或非終結(jié)符開(kāi)始。但它們右部的符號(hào)串可能推導(dǎo)出的First集不相交，因而可以根據(jù)當(dāng)前的輸入符號(hào)是屬于哪個(gè)產(chǎn)生式的FIRST集而決定選擇相應(yīng)產(chǎn)生式進(jìn)行推導(dǎo)，因此仍能構(gòu)造確定的自頂向下分析。G2：S→Ap|Bq

A→a|cAB→b|dB

例5.3若有文法G3[S]:

S→aA|d

A→bAS|ε

識(shí)別輸入串w=abd是否是G3[S]的句子

試探推導(dǎo)出abd的推導(dǎo)過(guò)程為：

S

aA

abAS

abS

abd

試探推導(dǎo)成功。文法的特點(diǎn)是：

文法中含有空產(chǎn)生式。從以上推導(dǎo)過(guò)程中我們可以看到在第2步到第3步的推導(dǎo)中，因當(dāng)前面臨輸入符號(hào)為d，而最左非終結(jié)符A的產(chǎn)生式右部的開(kāi)始符號(hào)集合都不包含d，但有ε，因此對(duì)于d的匹配自然認(rèn)為只能依賴(lài)于在可能的推導(dǎo)過(guò)程中A的后面的符號(hào)，所以這時(shí)選用產(chǎn)生式A→ε往下推導(dǎo)，而當(dāng)前A后面的符號(hào)為S，S產(chǎn)生式右部的開(kāi)始的終結(jié)符號(hào)集合包含了d，所以可匹配。

當(dāng)一個(gè)文法中相同左部非終結(jié)符的右部存在能

ε的情況則必須知道該非終結(jié)符的后跟符號(hào)的集合中的符號(hào)是否可以唯一地確定選擇哪個(gè)產(chǎn)生式。為此，我們定義一個(gè)文法非終結(jié)符的后跟符號(hào)的集合如下：

定義5.2：設(shè)

G=(VT，VN，S，P)是上下文無(wú)關(guān)文法，A∈VN，S是開(kāi)始符號(hào)

FOLLOW(A)=｛a|S

μAβ,且a∈VT，a∈FIRST(β),μ∈VT*,β∈V+｝

若S

μAβ,且β

ε,則#∈FOLLOW(A)。

也可定義為：FOLLOW(A)={a|S

…Aa…,a∈VT}

若有S

…A，則規(guī)定#∈FOLLOW(A)

這里我們用'#'作為輸入串的結(jié)束符，或稱(chēng)為句子括號(hào)，如：#輸入串#。

因此當(dāng)文法中含有形如：

A→α

A→β

的產(chǎn)生式時(shí)，其中A∈VN，α,β∈V*，當(dāng)α,β不同時(shí)推導(dǎo)出空時(shí)，設(shè)α

ε,β

ε,則當(dāng)FIRST(α)∩(FIRST(β)∪FOLLOW(A))=

時(shí)，對(duì)于非終結(jié)符A的替換仍可唯一地確定候選。

綜合以上情況可定義選擇集合SELECT如下：

定義5.3給定上下文無(wú)關(guān)文法的產(chǎn)生式A→α,A∈VN,α∈V*,

若α

ε,則SELECT(A→α)=FIRST(α)

如果α

ε則：

SELECT(A→α)=（FIRST(α)–{ε}）∪FOLLOW(A)是否所有的文法都能采用確定的自上而下的分析該文法的特點(diǎn)是：

關(guān)于A(yíng)的產(chǎn)生式的不同右部開(kāi)始符號(hào)集合都含有a，因此要替換非終結(jié)符A時(shí)，對(duì)當(dāng)前輸入符為a的情況，不能確定用產(chǎn)生式A→ab的右部還是用A→a的右部去替換。所以導(dǎo)致必須用帶回溯的自頂向下分析，這是一個(gè)不確定的分析文法含有左遞歸，可見(jiàn)一個(gè)文法含有左遞歸時(shí)不能用確定的自頂向下分析文法含有左遞歸，一個(gè)文法含有左遞歸時(shí)不能用確定的自頂向下分析。由以上例子可以看出，例5.4～例5.6的文法不能用確定的自頂向下分析,可用帶回溯的自頂向下分析。5.2LL(1)文法的定義和判別由5.1的例1～例6可知，一個(gè)文法能否用確定的自頂向下分析與文法中相同左部的每個(gè)產(chǎn)生式右部的開(kāi)始符號(hào)集合有關(guān)，當(dāng)某個(gè)非終結(jié)符能推出ε時(shí)則與該非終結(jié)符的后跟符號(hào)集合也有關(guān)。綜合以上兩點(diǎn)，即一個(gè)文法能否用確定的自頂向下分析與產(chǎn)生式的Select集有關(guān)。此外在產(chǎn)生式中不存在左遞歸。定義5.4

一個(gè)上下文無(wú)關(guān)文法是LL(1)文法的充分必要條件是：對(duì)每個(gè)非終結(jié)符A的兩個(gè)不同產(chǎn)生式，A→α,A→β,滿(mǎn)足SELECT(A→α)∩SELECT(A→β)=?

其中α，β不同時(shí)能εLL(1)文法的定義LL(1)文法的含義：第一個(gè)L從左到右掃描輸入串第二個(gè)L生成的是最左推導(dǎo)

1向右看一個(gè)輸入符號(hào)便可決定選擇哪個(gè)產(chǎn)生式。例：判斷下列文法是否是LL(1)文法G：S→aAS→dA→bASA→ε解：select(S→aA)={a}select(S→d)=mbgojjsselect(S→aA)∩select(S→d)=?select(A→bAS)=select(A→ε)={First(ε)-{ε}}∪Follow(A)=Follow(A)={a,d,#}select(A→bAS)∩select(A→ε)=?所以，該文法是LL（1）文法。例：判斷下列文法是否是LL(1)文法

文法G[S]為：

S→aAS

S→b

A→bA

A→ε

例文法G[S]為：

S→aAS

S→b

A→bA

A→ε

則SELECT(S→aAS)={a}

SELECT(S→b)=

SELECT(A→bA)=

SELECT(A→ε)={a,b}

所以SELECT(S→aAS)∩SELECT(S→b)={a}∩=

SELECT(A→bA)∩SELECT(A→ε)=∩{a,b}≠

因此，該文法不是LL(1)文法，因而也就不可能用確定的自頂向下分析。LL(1)文法的判別當(dāng)我們需選用自頂向下分析技術(shù)時(shí)，首先必須判別所給文法是否是LL(1)文法。因而我們對(duì)任給文法需計(jì)算FIRST、FOLLOW、SELECT集合，進(jìn)而判別文法是否為L(zhǎng)L(1)文法。

4、若X∈VN；Y1，Y2，…，Yi∈VN，且有產(chǎn)生式X→Y1Y2…Yn；當(dāng)Y1Y2…Yi-1都

ε時(shí)，(其中1≤i≤n)，則FIRST(Y1)、FIRST(Y2)、…、FIRST(Yi-1)的所有非空元素和FIRST(Yi)都包含在FIRST(X)中。5、當(dāng)(4)中所有Yi

ε,(i=1,2,…n)，則

FIRST(X)=(FIRST(Y1)－{ε}）∪（FIRST(Y2)－{ε}）∪

…∪（FIRST(Yn)－{ε}）∪{ε}反復(fù)使用上述(2)～(5)步直到每個(gè)符號(hào)的FIRST集合不再增大為止。

例文法G[S]為：

S→AB

S→bC

A→ε

A→b

B→ε

B→aD

C→AD

C→b

D→aS

D→c

求每個(gè)終結(jié)符的First集。例文法G[S]為：

S→AB

S→bC

A→ε

A→b

B→ε

B→aD

C→AD

C→b

D→aS

D→c

FIRST(S)={FIRST(A)－{ε}}∪{FIRST(B)－{ε}}∪{ε}∪={b,a,ε}

FIRST(A)=∪{ε}={b,ε}

FIRST(B)＝{ε}∪{a}＝{a,ε}

FIRST(C)={FIRST(A)－{ε}}∪FIRST(D)∪FIRST(b)={b,a,c}

FIRST(D)={a}∪{c}={a,c}也可以由關(guān)系圖法求文法符號(hào)的FIRST集，可作為一種驗(yàn)證。其方法為：

(a)每個(gè)文法符號(hào)對(duì)應(yīng)圖中一個(gè)結(jié)點(diǎn)，對(duì)應(yīng)終結(jié)符的結(jié)點(diǎn)時(shí)用符號(hào)本身標(biāo)記，對(duì)應(yīng)非終結(jié)符的結(jié)點(diǎn)用FIRST(A)標(biāo)記。這里A表示非終結(jié)符。

(b)如果文法中有產(chǎn)生式A→αXβ，且α

ε,則從對(duì)應(yīng)A的結(jié)點(diǎn)到對(duì)應(yīng)X的結(jié)點(diǎn)連一條箭弧。

(c)凡是從FIRST(A)結(jié)點(diǎn)有路徑可到達(dá)的終結(jié)符結(jié)點(diǎn)所標(biāo)記的終結(jié)符都為FIRST(A)的成員。

(d)由ε是否為某非終結(jié)符FIRST集的成員，若是則將ε加入該非終結(jié)符的FIRST集中。

文法G[S]為：

S→AB

S→bC

A→ε

A→b

B→ε

B→aD

C→AD

C→b

D→aS

D→c

FIRST(S)={b,a,ε}

FIRST(A)={b,ε}

FIRST(B)={a,ε}

FIRST(C)={a,b,c}

FIRST(D)={a,c}

計(jì)算FOLLOW集

根據(jù)定義計(jì)算

對(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集不再增大為止。

例：文法G[S]為：

S→AB

S→bC

A→ε

A→b

B→ε

B→aD

C→AD

C→b

D→aS

D→c

求每個(gè)非終結(jié)符的Follow集。文法G[S]為：

S→AB

S→bC

A→ε

A→b

B→ε

B→aD

C→AD

C→b

D→aS

D→c

解：

FOLLOW(S)={#}∪FOLLOW(D)＝{#}

FOLLOW(A)=(FIRST(B)－{ε})∪FOLLOW(S)∪FIRST(D)

＝{a,#,c}

FOLLOW(B)=FOLLOW(S)={#}

FOLLOW(C)=FOLLOW(S)={#}

FOLLOW(D)={#}

判斷它是否是LL(1)文法文法G[S]為：

S→AB

S→bC

A→ε

A→bB→ε

B→aD

C→AD

C→b

D→aS

D→c每個(gè)產(chǎn)生式的SELECT集合計(jì)算為：

SELECT(S→AB)=（FIRST(AB)-{ε})∪FOLLOW(S)={b,a,#}

SELECT(S→bC)=FIRST(bC)=

SELECT(A→ε)=(FIRST(ε)-{ε})∪FOLLOW(A)={a,c,#}

SELECT(A→b)=FIRST(b)=

SELECT(B→ε)=(FIRST(ε)-{ε})∪FOLLOW(B)={#}

SELECT(B→aD)=FIRST(aD)={a}

SELECT(C→AD)=FIRST(AD)={a,b,c}

SELECT(C→b)=FIRST(b)=

SELECT(D→aS)=FIRST(aS)={a}

SELECT(D→c)=FIRST(c)={c}

文法G[S]為：

S→AB

S→bC

A→ε

A→bB→ε

B→aD

C→AD

C→b

D→aS

D→c由以上計(jì)算結(jié)果可得相同左部產(chǎn)生式的SELECT交集為：

SELECT(S→AB)∩SELECT(S→bC)={b,a,#}∩=≠

SELECT(A→ε)∩SELECT(A→b)={a,c,#}∩=

SELECT(B→ε)∩SELECT(B→aD)={#}∩{a}=

SELECT(C→AD)∩SELECT(C→b)＝{b,a,c}∩＝≠

SELECT(D→aS)∩SELECT(D→c)={a}∩{c}＝

由LL(1)文法定義知該文法不是LL(1)文法，因?yàn)殛P(guān)于S和C的相同左部其產(chǎn)生式的SELECT集的交集不為空。非LL(1)文法到LL(1)文法的等價(jià)轉(zhuǎn)換由前面可知：確定的自頂向下分析要求對(duì)給定語(yǔ)言的文法必須是LL(1)形式。然而，不一定每個(gè)語(yǔ)言都有LL(1)文法。對(duì)一個(gè)語(yǔ)言的非LL(1)文法是否能變換為等價(jià)的LL(1)形式以及如何變換是本節(jié)討論的主要問(wèn)題。若文法中含有直接或間接左遞歸，或含有左公共因子則該文法肯定不是LL(1)文法。因而，我們?cè)O(shè)法消除文法中的左遞歸，提取左公共因子對(duì)文法進(jìn)行等價(jià)變換，在某些特殊情況下可能使其變?yōu)長(zhǎng)L(1)文法。1．提取左公共因子

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

，不滿(mǎn)足LL(1)文法的充分必要條件。

現(xiàn)將產(chǎn)生式A→αβ|αγ進(jìn)行等價(jià)變換為：

A→α（β|γ）

使產(chǎn)生式變換為：

A→αA′

A′→β|γ寫(xiě)成一般形式為：

A→αβ1|αβ2|…|αβn，提取左公共因子后變?yōu)椋?/p>

A→α（β1|β2|…|βn），再引進(jìn)非終結(jié)符A′，變?yōu)椋?/p>

A→αA′

A′→β1|β2|…|βn

若在βi、βj、βk…(其中1≤i，j，k≤n)中仍含有左公共因子，這時(shí)可再次提取，這樣反復(fù)進(jìn)行提取直到引進(jìn)新非終結(jié)符的有關(guān)產(chǎn)生式再無(wú)左公共因子為止。例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í)崛∥姆ㄖ械碾[式左公因子。

產(chǎn)生式(2)的右部以非終結(jié)符開(kāi)始，因此左公共因子可能是隱式的，所以這種情況下對(duì)右部以非終結(jié)符開(kāi)始的產(chǎn)生式，用其相同左部而右部以終結(jié)符開(kāi)始的產(chǎn)生式進(jìn)行相應(yīng)替換，對(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

引進(jìn)新非終結(jié)符A′，去掉'('，')'后得G′為：

(1)A→aA′

(2)A→bBc

(3)A′→d

(4)A′→Ac

(5)B→aA

(6)B→bB

不難驗(yàn)證經(jīng)提取左公共因子后文法例1中的G′仍不是LL(1)文法。而文法例2中的G′變成LL(1)文法，因此文法中不含左公共因子只是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′后變?yōu)椋?/p>

(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)改寫(xiě)后的文法不含空產(chǎn)生式，且無(wú)左遞歸時(shí)，則改寫(xiě)后的文法是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*

可稱(chēng)含1)中產(chǎn)生式的文法為含有直接左遞歸。含2)中產(chǎn)生式的文法有A

A…則稱(chēng)文法中含有間接左遞歸，文法中只要含有1)或含有2)的產(chǎn)生式或二者皆有，均認(rèn)為文法是左遞歸的，然而，一個(gè)文法是左遞歸時(shí)不能采用自頂向下分析法。為了使某些含有左遞歸的文法經(jīng)過(guò)等價(jià)變換消除左遞歸后可能變?yōu)長(zhǎng)L(1)文法，可采取下列變換公式：

a)消除直接左遞歸，把直接左遞歸改寫(xiě)為右遞歸，如對(duì)文法G：

S→Sa

S→b

可改寫(xiě)為：

S→bS′

S′→aS′|ε

一般情況下，假定關(guān)于A(yíng)的全部產(chǎn)生式是：

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

其中，αi(1≤i≤m)不等于ε,βj(1≤j≤n)不以A開(kāi)頭，

消除直接左遞歸后改寫(xiě)為：

A→β1A′|β2A′|…|βnA′

A′→α1A′|α2A′|…|αmA′|ε

b)消除間接左遞歸。

對(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)改寫(xiě)后的文法不是LL(1)文法。例：文法：E→E+T|TT→T*F|FF→(E)|i

試消除它的左遞歸E→TE’E’→+TE’|ε

T→FT’T’→*FT’|εF→(E)|ic)消除文法中一切左遞歸的算法。步驟(P83－P84算法步驟）

1)把文法的所有非終結(jié)符按某一順序排序；

如A1，A2,…,An

2)A1產(chǎn)生式右部用A2，…,An表示，

A2產(chǎn)生式右部用A3，…,An表示，

A3產(chǎn)生式右部用A4，…,An表示，

……,An產(chǎn)生式右部用An表示。消除An中的直接左遞歸。

3)去掉無(wú)用產(chǎn)生式。

把上述算法歸結(jié)為：

若非終結(jié)符的排序?yàn)锳1，A2，…，An。

for(i=1;i<=n;i++){for(j=1;j<=i-1;j++){將規(guī)則Ai→Ajr改寫(xiě)：

//若Aj→δ1|δ2|…|δk

//則：替換產(chǎn)生式變?yōu)椋?/p>

Ai→δ1r|δ2r|…|δkr}

消除規(guī)則中的直接左遞歸}

例如，有文法的產(chǎn)生式為：

(1)S→Qc|c

(2)Q→Rb|b

(3)R→Sa|a

該文法為間接左遞歸，按上述方法消除該文法的一切左遞歸。

若非終結(jié)符排序?yàn)镾、Q、R,

（1）式左部為S的產(chǎn)生式是用后面的符號(hào)表示，不用修改

(2)號(hào)產(chǎn)生式中右部是用后面的符號(hào)表示，不用修改，

(3)式中R是用前面的S表示，所以把(1)右部代入(3)得：

(4)R→Qca|ca|a

再將(2)的右部代入(4)得：

(5)R→Rbca|bca|ca|a對(duì)(5)消除直接左遞歸得：

R→(bca|ca|a)R′

R′→bcaR′|ε最終文法變?yōu)椋?/p>

S→Qc|c

Q→Rb|b

R→(bca|ca|a)R′

R′→bcaR′|ε若非終結(jié)符的排序?yàn)镽、Q、S,則把(3)代入(2)得：

Q→Sab|ab|b

再將此代入(1)得：

S→Sabc|abc|bc|c

消除該產(chǎn)生式的左遞歸后，最終文法變?yōu)椋?/p>

S→(abc|bc|c)S′

S′→abcS′|ε

Q→Rb|b

R→Sa|a

由于Q、R為不可到達(dá)的非終結(jié)符，所以以Q、R為左部及包含Q、R的產(chǎn)生式應(yīng)刪除。當(dāng)非終結(jié)符的排序不同時(shí)，最后結(jié)果的產(chǎn)生式形式不同，但它們是等價(jià)的。(1)S→Qc|c

(2)Q→Rb|b

(3)R→Sa|a

例：G：E→TE’E’→+TE’|εT→FT’T’→*FT’|εF→(E)|i寫(xiě)出它的遞歸子程序。ProcedureEBeginT;E’End;ProcedureTBeginF;T’End;ProcedureE’Beginifsym=‘+’thenBegingetsymT;E’;EndEnd;ProcedureT’Beginifsym=‘*’thenBegingetsym;F;T’;EndEndProcedureFBeginifsym<>‘i’thenBeginifsym=‘(‘thenBegingetsym;E;ifsym=‘)’thengetsym;elseErrorEndelseErrorEndEndF→(E)|i（見(jiàn)附錄）遞歸子程序要求文法必須是LL(1)文法。預(yù)測(cè)分析方法

預(yù)測(cè)分析方法是自頂向下分析的另一種方法，一個(gè)預(yù)測(cè)分析器是由三個(gè)部分組成。

·預(yù)測(cè)分析程序(總控程序)

·先進(jìn)后出棧(stack)

·預(yù)測(cè)分析表

表驅(qū)動(dòng)予測(cè)分析程序模型

Input#總控程序預(yù)測(cè)分析表stack其中只有預(yù)測(cè)分析表與文法有關(guān)，而分析表又可用一個(gè)矩陣M(或稱(chēng)二維數(shù)組)表示。矩陣的元素M[A，a]中的下標(biāo)A表示非終結(jié)符，a為終結(jié)符或句子括號(hào)“#”，矩陣元素M[A,a]中的內(nèi)容為存放著一條關(guān)于A(yíng)的產(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ò)處理的信息AaA→αA遇到輸入符a，選用哪個(gè)產(chǎn)生式，如果A→α，αε，

a∈Frist(α)

。如果A→α，α→εa∈Follow(A),即如果a∈select(A→α)則把A→α加入到M(A,a)中。

解：(1)判斷它是否是LL（1）文法因?yàn)樵撐姆ê凶筮f歸，所以不是LL（1）文法，必須改寫(xiě)成LL(1)文法：

G’[E]:(1)E–>TE’(2)E’

–>+TE’(3)E’

–>

(4)T–>FT’(5)T’

–>*FT’(6)T’

–>

(7)F–>(E)(8)F–>a

例：為文法G(E):E–>E+T|TT–>T*F|FF–>a|(E)構(gòu)造預(yù)測(cè)分析表。Select(E–>TE’)=First(T)=First(F)={a,(}Select(E’

–>+TE’)={+}Select(E’

–>

)=Follow(E’)=Follow(E)=(#,)}Select(T–>FT’)=First(F)={(,a}Select(T’

–>*FT’)={*}Select(T’

–>

)=Follow(T’)=Follow(T)=(First（E’)-{})∪Follow(E’)=(First（E’)-{})∪Follow(E)={+,#,)}Select(F–>(E))={(}Select(F–>a)=