第三章習題解答-0課件

第三章語法分析

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

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

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

→,id

L′

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

a,b,c構造的分析樹(a)文法G(D)；(b)文法G′(D)第三章語法分析3.11

將下述文法改造為LL(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第三章語法分析一個LL(1)文法的充要條件是：對每一個終結符A的任何兩個不同產(chǎn)生式A→α|β有下面的條件成立：FIRST(α)∩FIRST(β)=Φ；假若β→ε,則有FIRST(α)∩FOLLOW(A)=Φ。即求出G[V′]的FIRST集合和LAST集合如下：

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

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

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

∪FOLLOW(E

)={]}FOLLOW(E

)=FOLLOW(E)

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

∪FOLLOW(V)={[,+,

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

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

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

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

2型文法。(2)

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

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

j≥1,

k≥1}。第三章語法分析(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ī)則有：a<·

FIRSTVT(S)LASTVT(S)

·>ba≡bb<·

FIRSTVT(P)LASTVT(P)

·>cb≡cb<·

FIRSTVT(Q)LASTVT(Q)

·>cLASTVT(Q)

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

S→aSb

|

PP→bPc

|

bQcQ→aQ′Q′→aQ′|

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

|

PP→bP′P′→Pc

|

QcQ→aQ′Q′→aQ′|

ε第三章語法分析求每個非終結符的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}第三章語法分析對于P′→Pc|Qc，有：FIRST(P)

∩FIRST(Q)=

∩{a}=?對于Q′→a

Q′|ε，有：

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

(“aQ′”)

∩FOLLOW(Q′)={a}

∩{c}=

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

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

S→(EtSeS)|(EtS)|

i=E

E→+EF

|

FF→*Fi

|

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

(·EtSeS)S→

(E·tSeS)S→

(Et·SeS)S→

(EtS·eS)S→

(EtSe·S)S→

(EtSeS·)S→

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

(·EtS)S→

(E·tS)S→

(Et·S)S→

(EtS·)S→

(EtS)·S→·i=ES→i·=ES→i=·ES→i=E·第三章語法分析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第三章語法分析第三步，用ε_CLOSURE方法構造文法G[S′]的LR(0)項目集規(guī)范族：I0:

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

S′→S

·第三章語法分析I2:

S→

(·EtSeS)S→

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

→·*FiF

→·iI3:

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

S→

(Et·SeS)S→

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

S→

(EtS·eS)S→

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

S→

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

S→

(EtSeS·)I8:

S→

(EtSeS)·I9:

S→

(EtS)·第三章語法分析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第三章語法分析第四步，構造文法G[S′]的DFA如圖3-13所示。圖3-13習題3.22的DFA第三章語法分析第五步，構造SLR(1)分析表。首先求出所有形如“A→α·”的FOLLOW(A)，即由FOLLOW集的構造方法求得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,),#}最后,構造SLR(1)分析表如表3-10所示。第三章語法分析表3-10習題3.22的SLR(1)分析表第三章語法分析3.24

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

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

棧#棧E→式bi串bi#歸約r3202#Eεbibi#移進3024#Ebibi#移進40246#EbiH

→ibi#歸約r450245#EbHbi#移進60245#EbHi#移進770245b#EbHH

→Hbi#歸約r58708245b#iEbHT

→

EbH#歸約r1901#T#acc第三章語法分析3.32

給出文法G[S]:S→SaS∣SbS∣cSd∣eS∣f。請證實這是一個二義文法；給出什么樣的約束條件可構造無沖突的LR分析表？請證實你的論點?！窘獯稹?/p>

(1)

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

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