第4章自頂向下的語法分析方法

第4章自頂向下的語法分析方法

語法分析的作用是識別由詞法分析給出的單詞符號序列是否是給定文法的正確句子(程序)。目前語法分析常用的方法有:1、自頂向下（自上而下）分析2、自底向上（自下而上）分析

自頂向下分析法也就是從文法的開始符號出發(fā)企圖推導出與輸入的單詞串完全相匹配的句子，若輸入串是給定文法的句子，則必能推出，反之必然出錯。

回顧在“文法和語言”一章中介紹的關(guān)于句子、句型和語言的定義及什么叫最左推導、最右推導和規(guī)范推導的基本概念。句型:

有文法G[S]，若S

x，且x∈V*則稱x是文法G[S]的句型。

符號

表示經(jīng)過0步或若干步的推導。句子:

有文法G[S]，若S

x，且x∈VT*，則稱x是文法G[S]的句子。

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

可有推導S

0S1

00S11

000S111

00001111

說明00001111是G[S]的句子。

句型的分析

句型分析就是識別一個符號串是否為某文法的句型，是某個推導的構(gòu)造過程。

最左（最右）推導：在推導的任何一步α

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

最右推導被稱為規(guī)范推導。

由規(guī)范推導所得的句型稱為規(guī)范句型。句型分析的有關(guān)問題

①如何選擇使用哪個產(chǎn)生式進行推導？

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

②如何識別可歸約的串？

在自下而上的分析方法中，在分析程序工作的每一步，都是從當前串中尋找一個子串，看它是否能歸約到文法的某個非終結(jié)符號，該子串稱為“可歸約串”。4.1確定的自頂向下分析思想

確定的自頂向下分析方法:從某文法的開始符號出發(fā)，對給定的輸入符號串如何根據(jù)當前的輸入符號(單詞符號)唯一地確定選用哪個產(chǎn)生式替換相應(yīng)非終結(jié)符以往下推導。

例4.1

若有文法G1[S]:

S→pA|qB

A→cAd|a

B→dB|c

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

試探推導過程：

S

pA

pcAd

pccAdd

pccadd

試探成功。

例4.1

若有文法G1[S]:

S→pA|qB

A→cAd|a

B→dB|c

這個文法有以下兩個特點：

①每個產(chǎn)生式的右部都由終結(jié)符號開始。

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

對于這樣的文法顯然在推導過程中完全可以根據(jù)當前的輸入符號決定選擇哪個產(chǎn)生式往下推導，因此分析過程是唯一確定的。例4.2

若有文法G2[S]:

S→Ap|Bq

A→a|cA

B→b|dB

識別輸入串w=ccap是否是G2[S]的句子，那么試探推出輸入串的推導過程為：

S

Ap

cAp

ccAp

ccap

試探推導成功。例4.2

若有文法G2[S]:

S→Ap|Bq

A→a|cA

B→b|dB

此文法的特點是：①產(chǎn)生式的右部不全是由終結(jié)符開始。

②如果兩個產(chǎn)生式有相同的左部，它們的右部是由不同的終結(jié)符或非終結(jié)符開始。③文法中無空產(chǎn)生式。例4.2

若有文法G2[S]:

S→Ap|Bq

A→a|cA

B→b|dB

對于產(chǎn)生式中相同左部含有非終結(jié)符開始的產(chǎn)生式時，在推導過程中選用哪個產(chǎn)生式不像例4.1文法那樣直觀，對于W=ccap為輸入串時，其第一個符號是c，這時從S出發(fā)選擇S→Ap還是選擇S→Bq，需要知道，Ap或Bq它們的開始終結(jié)符號集合是什么？因為c是包含在Ap的開始終結(jié)符號集合中，且不包含在Bq的開始終結(jié)符號集合中，則選擇S→Ap往下進行推導。一個文法符號串的終結(jié)符的首符集定義如下：

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

FIRST(α)={a|α

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

若α

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

FIRST(Ap)={a,c}

FIRST(Bq)={b,d}

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

此時可以根據(jù)當前的輸入符號是屬于哪個產(chǎn)生式的FIRST集而決定選擇相應(yīng)產(chǎn)生式進行推導，因此仍能構(gòu)造確定的自頂向下分析。例4.2G2：S→Ap|Bq

A→a|cAB→b|dB例4.3

若有文法G3[S]:

S→aA|d

A→bAS|ε

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

試探推導出abd的推導過程為：

S

aA

abAS

abS

abd

試探推導成功。當一個文法中相同左部非終結(jié)符的右部存在能

ε的情況則必須知道該非終結(jié)符的后跟符號的集合中的符號是否可以唯一地確定選擇哪個產(chǎn)生式。

一個文法非終結(jié)符的后跟符號的集合如下：定義4.2：設(shè)G=(VT，VN，S，P)是上下文無關(guān)文法，A∈VN，S是開始符號

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é)束符，或稱為句子括號，如：#輸入串#。因此當文法中含有形如：

A→α

A→β

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

ε,β

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

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

?

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

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

若α

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

如果α

ε則：

SELECT(A→α)=（FIRST(α)–{ε}）∪FOLLOW(A)4.2LL(1)文法的定義和判別

一個文法能否用確定的自頂向下分析與文法中相同左部的每個產(chǎn)生式右部的開始符號集合有關(guān)，當某個非終結(jié)符能推出ε時則與該非終結(jié)符的后跟符號集合也有關(guān)。綜合以上兩點，即一個文法能否用確定的自頂向下分析與產(chǎn)生式的Select集有關(guān)。此外在產(chǎn)生式中不存在左遞歸。1、LL(1)文法的定義定義4.4

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

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

1向右看一個輸入符號便可決定選擇哪個產(chǎn)生式。例：判斷下列文法是否是LL(1)文法G：S→aAS→dA→bASA→ε解：select(S→aA)={a}select(S→d)=hlpqsvwselect(S→aA)∩select(S→d)=?select(A→bAS)=select(A→ε)={First(ε)-{ε}}∪Follow(A)=Follow(A)={a,d,#}select(A→bAS)∩select(A→ε)=?所以，該文法是LL（1）文法。2、LL(1)文法的判別當我們需選用自頂向下分析技術(shù)時，首先必須判別所給文法是否是LL(1)文法。因而我們對任給文法需計算FIRST、FOLLOW、SELECT集合，進而判別文法是否為LL(1)文法。

（1）計算FIRST集1.若X

VT，則FIRST(X)＝{X}。2.若X

VN，且有產(chǎn)生式X→a…，a

VT則把a加入到FIRST(X)中；3.若X→

是一條產(chǎn)生式，則把

加到FIRST(X)中。4.若X→Y…是一個產(chǎn)生式且Y

VN，則把FIRST(Y)中的所有非

-元素都加到FIRST(X)中；5.若X→Y1Y2…Yk是一個產(chǎn)生式，Y1，…，Yi-1都是非終結(jié)符，而且，對于任何j，1

j

i-1，F(xiàn)IRST(Yj)都含有

(即Y1…Yi-1

)，則把FIRST(Yi)中的所有非

-元素都加到FIRST(X)中；特別是，若所有的FIRST(Yj)均含有

，j＝1，2，…，k，則把

加到FIRST(X)中。反復使用上述(2)～(5)步直到每個符號的FIRST集合不再增大為止。例4.5若文法G[S]為：

S→ABS→bCA→εA→b

B→ε

B→aD

C→AD

C→b

D→aS

D→c

求每個終結(jié)符的First集。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}（2）計算FOLLOW集對于文法G的每個非終結(jié)符A構(gòu)造FOLLOW(A)的辦法是，連續(xù)使用下面的規(guī)則，直至每個FOLLOW不再增大為止：1.對于文法的開始符號S，置＃于FOLLOW(S)中；2.若A→

B

是一個產(chǎn)生式，則把FIRST(

)-{

}加至FOLLOW(B)中；3.若A→

B是一個產(chǎn)生式，或A

B

是一個產(chǎn)生式而

(即

FIRST(

))，則把FOLLOW(A)加至FOLLOW(B)中。例4.5若文法G[S]為：

S→ABS→bCA→εA→b

B→ε

B→aD

C→AD

C→b

D→aS

D→c

求每個終結(jié)符的Follow集。FOLLOW(S)={#}∪FOLLOW(D)＝{#}FOLLOW(A)=(FIRST(B)－{ε})∪FOLLOW(S)∪FIRST(D)

＝{a,#,c}

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

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

FOLLOW(D)=FOLLOW(C)∪FOLLOW(B)={#}

例4.5若文法G[S]為：

S→ABS→bCA→εA→b

B→ε

B→aD

C→AD

C→b

D→aS

D→c

判斷它是否是LL(1)文法。每個產(chǎn)生式的SELECT集合計算為：

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→ε)=(FIR