第三章習(xí)題解答-0課件

第三章語(yǔ)法分析

下述文法描述了C語(yǔ)言整數(shù)變量的聲明語(yǔ)句：

G[D]:D→TLT→int|long|shortL→id|L,id改造上述文法，使其接受相同的輸入序列，但文法是右遞歸的；分別用上述文法G[D]和改造后的文法G[D′]為輸入序列int

a,b,c構(gòu)造分析樹(shù)。第三章語(yǔ)法分析【解答】(1)消除左遞歸后，文法G[D′]如下：D→TLT→int|long|shortL→idL′L′

→,id

L′

|ε第三章語(yǔ)法分析圖3-6兩種文法為int

a,b,c構(gòu)造的分析樹(shù)(a)文法G(D)；(b)文法G′(D)第三章語(yǔ)法分析3.11

將下述文法改造為L(zhǎng)L(1)文法：

G[V]:V→N

|

N[E]E→V

|

V+EN→I【解答】LL(1)文法的基本條件是不含左遞歸和回溯(公共左因子)，而文法G[V]中含有回溯，所以先提取公共左因子，以消除回溯，得到文法G[V′]：G

[V′]：V→NV′V′→ε

|

[E]E→VE′E′→ε

|

+EN→i第三章語(yǔ)法分析一個(gè)LL(1)文法的充要條件是：對(duì)每一個(gè)終結(jié)符A的任何兩個(gè)不同產(chǎn)生式A→α|β有下面的條件成立：FIRST(α)∩FIRST(β)=Φ；假若β→ε,則有FIRST(α)∩FOLLOW(A)=Φ。即求出G[V′]的FIRST集合和LAST集合如下：

FIRST(N)=FIRST(V)=FIRST(E)={i}FIRST(V′)={[,ε}FIRST(E′)={+,

ε}第三章語(yǔ)法分析FOLLOW(V)=FIRST(E)\{ε}∪FOLLOW(E)FOLLOW(V∪{#}={+,],#})=

FOLLOW(V)={+,],#}FOLLOW(E)={]}

∪FOLLOW(E

)={]}FOLLOW(E

)=FOLLOW(E)

={]}FOLLOW(N)=FIRST(V)\{ε}

∪FOLLOW(V)={[,+,

],#}第三章語(yǔ)法分析對(duì)產(chǎn)生式V′→ε

|[E]有：FIRST(ε)∩FIRST(‘[’]=Φ；FIRST(‘[’)∩FOLLOW(V′)={[}∩{#,+,]}=Φ；對(duì)E′→ε

|+E有：FIRST(ε)∩FIRST(‘+’)=Φ；FIRST(‘+’)∩FOLLOW(E′)={+}∩{]}=Φ。故文法G[V′]為L(zhǎng)L(1)文法。第三章語(yǔ)法分析3.14在算符優(yōu)先分析法中，為什么要在找到最左素短語(yǔ)的尾時(shí)才返回來(lái)確定其對(duì)應(yīng)的頭，能否按掃描順序先找到頭后再找到對(duì)應(yīng)的尾，為什么？【解答】設(shè)句型的一般形式為N1a1N2a2…NnanNn+1。其中，每個(gè)ai都是終結(jié)符，而Ni則是可有可無(wú)的非終結(jié)符。對(duì)上述句型可以找出該句型中的所有素短語(yǔ)，每個(gè)素短語(yǔ)都具有如下形式：…aj-1?aj≡aj+1≡…≡ai?ai+1…第三章語(yǔ)法分析如果某句型得到的優(yōu)先關(guān)系如下：…?…?……?…?則當(dāng)從左至右掃描到第一個(gè)“?”時(shí)，再由此從右至左掃描到第一個(gè)“?”時(shí)，它們之間(當(dāng)然不包含第一個(gè)“?”前一個(gè)終結(jié)符和第二個(gè)“?”后一個(gè)終結(jié)符)即為最左素短語(yǔ)。第三章語(yǔ)法分析3.16

給出文法G[S]:S→aSb∣PP→bPc∣bQcQ→Qa∣a它是Chomsky哪一型文法？它生成的語(yǔ)言是什么？它是不是算符優(yōu)先文法？請(qǐng)構(gòu)造算符優(yōu)先關(guān)系表證實(shí)之；文法G[S]消除左遞歸、提取公共左因子后是不是LL(1)文法？請(qǐng)證實(shí)。第三章語(yǔ)法分析【解答】(1)根據(jù)Chomsky的定義，對(duì)任何形如A→β的產(chǎn)生式，有A∈VN，β∈(VT∪VN)*時(shí)為2型文法。而文法G[S]恰好滿(mǎn)足這一要求，故為Chomsky

2型文法。(2)

由文法G[S]可以看出：S推出串的形式是ai

Pbi(i≥0)，P推出串的形式是bjQcj(j≥1)，Q推出串的形式是ak(k≥1)。因此，文法G[S]生成的語(yǔ)言是L={aibjakcjbi|i≥0,

j≥1,

k≥1}。第三章語(yǔ)法分析(3)求出文法G[S]的FIRSTVT集和LASTVT集：FIRSTVT(S)={a,b}FIRSTVT(Q)={a}LASTVT(S)={b,c}LASTVT(Q)={a}FIRSTVT(P)=LASTVT(P)={c}根據(jù)優(yōu)先關(guān)系構(gòu)造規(guī)則有：a<·

FIRSTVT(S)LASTVT(S)

·>ba≡bb<·

FIRSTVT(P)LASTVT(P)

·>cb≡cb<·

FIRSTVT(Q)LASTVT(Q)

·>cLASTVT(Q)

·>a構(gòu)造優(yōu)先關(guān)系表如表3-8所示。第三章語(yǔ)法分析表3-8優(yōu)先關(guān)系表由于表中的優(yōu)先關(guān)系不唯一，故文法G[S]不是算符優(yōu)先文法。第三章語(yǔ)法分析(4)消除文法G[S]的左遞歸：

S→aSb

|

PP→bPc

|

bQcQ→aQ′Q′→aQ′|

ε提取公共左因子后得到文法G′[S]:S→aSb

|

PP→bP′P′→Pc

|

QcQ→aQ′Q′→aQ′|

ε第三章語(yǔ)法分析求每個(gè)非終結(jié)符的FIRST集和FOLLOW集如下：FIRST(P)=FIRST(Q)={a}FIRST(S)={a,b}FIRST(P′)={a,b}FIRST(Q′)={a,

ε}FOLLOW(S)={b,#}FOLLOW(P′)={b,c,#}FOLLOW(Q′)={c}FOLLOW(P)={b,c,#}FOLLOW(Q)={c}第三章語(yǔ)法分析對(duì)于P′→Pc|Qc，有：FIRST(P)

∩FIRST(Q)=

∩{a}=?對(duì)于Q′→a

Q′|ε，有：

FIRST(“aQ′”)∩{ε}=?FIRST

(“aQ′”)

∩FOLLOW(Q′)={a}

∩{c}=

?所以，該文法是LL(1)文法。第三章語(yǔ)法分析3.22

文法G(S)的產(chǎn)生式集為

S→(EtSeS)|(EtS)|

i=E

E→+EF

|

FF→*Fi

|

i構(gòu)造文法G(S)的SLR(1)分析表，要求先畫(huà)出相應(yīng)的DFA。第三章語(yǔ)法分析【解答】第一步，將文法G拓廣為文法G[S′]：(0)S′→SS→(EtSeS)S→(EtS)S→i=EE→+EFE→FF→*FiF→i第三章語(yǔ)法分析第二步，列出LR(0)的所有項(xiàng)目：S′→·SS′→S·S→·(EtSeS)S→

(·EtSeS)S→

(E·tSeS)S→

(Et·SeS)S→

(EtS·eS)S→

(EtSe·S)S→

(EtSeS·)S→

(EtSeS)·第三章語(yǔ)法分析S→·(EtS)S→

(·EtS)S→

(E·tS)S→

(Et·S)S→

(EtS·)S→

(EtS)·S→·i=ES→i·=ES→i=·ES→i=E·第三章語(yǔ)法分析E→·+EFE→+·EF29.

F→*F·i30.F→*Fi·23.

E→+E·F31.F→·i24.E→+EF·32.F→i·25.

E→·F26.

E→F·27.

F→·*Fi28.

F→*·Fi第三章語(yǔ)法分析第三步，用ε_(tái)CLOSURE方法構(gòu)造文法G[S′]的LR(0)項(xiàng)目集規(guī)范族：I0:

S′→·SS→·(EtSeS)S→·(EtS)S→·i=EI1:

S′→S

·第三章語(yǔ)法分析I2:

S→

(·EtSeS)S→

(·EtS)E→·+EFE→·FF

→·*FiF

→·iI3:

S→(E·tSeS)S→(E·tS)第三章語(yǔ)法分析I4:

S→

(Et·SeS)S→

(Et·S)S→·(EtSeS)S→·(EtS)S→·i=EI5:

S→

(EtS·eS)S→

(EtS·)第三章語(yǔ)法分析I6:

S→

(EtSe·S)S→·(EtSeS)S→·(EtS)S→·i=EI7:

S→

(EtSeS·)I8:

S→

(EtSeS)·I9:

S→

(EtS)·第三章語(yǔ)法分析I10:

S→i·=EI11:

S→i=·EE→·+EFE→·FI15:

E→+EF·I16:

E→F·I17:

F→*·FiF→·*FiF→·iI18:

F→*F·iI19:

F→*Fi·I20:

F→·iI12:

S→i=E·I13:

E→+·EFE→·+EFE→·FI14:

E→+E·FF→·*FiF→·i第三章語(yǔ)法分析第四步，構(gòu)造文法G[S′]的DFA如圖3-13所示。圖3-13習(xí)題3.22的DFA第三章語(yǔ)法分析第五步，構(gòu)造SLR(1)分析表。首先求出所有形如“A→α·”的FOLLOW(A)，即由FOLLOW集的構(gòu)造方法求得G[S′]的FOLLOW集如下：FOLLOW(S′)={#}；FOLLOW(S)={e}

∪{)}

∪{#}={e,),#}FOLLOW(E)=FIRST(F)\{ε}

∪{t}

∪FOLLOW(S)={*,i,t,e,),#}FOLLOW(F)={i}

∪

FOLLOW(E)=

{*,i,t,e,),#}最后,構(gòu)造SLR(1)分析表如表3-10所示。第三章語(yǔ)法分析表3-10習(xí)題3.22的SLR(1)分析表第三章語(yǔ)法分析3.24

文法G[T]及其SLR(1)分析表(見(jiàn)表3-12)如下，給出串bibi的分析過(guò)程。G[T]:(1)

T→EbHE→dE→εH→iH→HbiH→ε第三章語(yǔ)法分析表3-12習(xí)題3.24的SLR(1)分析表第三章語(yǔ)法分析序狀態(tài)符號(hào)產(chǎn)生輸入說(shuō)明1號(hào)0

棧#棧E→式bi串bi#歸約r3202#Eεbibi#移進(jìn)3024#Ebibi#移進(jìn)40246#EbiH

→ibi#歸約r450245#EbHbi#移進(jìn)60245#EbHi#移進(jìn)770245b#EbHH

→Hbi#歸約r58708245b#iEbHT

→

EbH#歸約r1901#T#acc第三章語(yǔ)法分析3.32

給出文法G[S]:S→SaS∣SbS∣cSd∣eS∣f。請(qǐng)證實(shí)這是一個(gè)二義文法；給出什么樣的約束條件可構(gòu)造無(wú)沖突的LR分析表？請(qǐng)證實(shí)你的論點(diǎn)。【解答】

(1)

對(duì)于語(yǔ)句fafbf，該文法存在兩棵不同的語(yǔ)法樹(shù)，如圖3-20所示。第三章語(yǔ)法分析圖3-20語(yǔ)句fafbf的兩棵不同語(yǔ)法樹(shù)第三章語(yǔ)法分析因此，G[S]是二義文法。(2)首先將文法G[S]拓廣為G[S′]：(0)S′→SS→SaSS→SbSS→cSdS→eSS→f該文法G[S′]的DFA如圖3-21所示。第三章語(yǔ)法分析圖3-21習(xí)題3.32中G[S′]的DFA第三章語(yǔ)法分析狀態(tài)I1、I8、I9和I10存在“移進(jìn)”/“歸約”沖突。計(jì)算G[S′]中所有非終結(jié)符的FOLLOW集：

FOLLOW(S′)={#}FOLLOW(S)={a,b,d,#}①對(duì)于I1：S′→S