編譯原理課后習(xí)題答案

第2章參考答案:

1,2,3；解答：略！

4.解答：

A：①B：③C：①D：②

5.解答：

用E表示〈表達(dá)式,，T表示v項(xiàng)〉，F(xiàn)表示〈因子〉，上述文法可以寫(xiě)為:

E一T|E+T

T—F|T*F

F-(E)|i

最左推導(dǎo)：

E=>E+T=>E+T+T=>T+T+T=>F+T+T=>i+T+T=>i+F+T=>i+i+T

=>i+i+F=>i+i+i

E=>E+T=>T+T=>F+T=>i+T=>i+T*F=>i+F*F=>i+i*F=>i+i*i

最右推導(dǎo)：

E=>E+T=>E+F=>E+i=>E+T+i=>E4-F+i=>E+i+i=>T+i+i

=>F+i+i=>i+i+i

E=>E+T=>E+T*F=>E+T*i=>E+F*i=>E+i*i=>T+i*i=>F+i*i=>i+i*i

i+i+i和i+i*i的語(yǔ)法樹(shù)如下圖所示。

DTT

/—

?\—

E+TF

^

11^-

T

F1FF

n.

1^

F1-

^11

i—

i+i+i、i+i*i的語(yǔ)法樹(shù)

6.解答：

(1)終結(jié)符號(hào)為：{or,and,not,(,),true,false}

非終結(jié)符號(hào)為：{bexpr,bterm,bfactor}

開(kāi)始符號(hào)為：bexpr

(2)句子not(trueorfalse)的語(yǔ)法樹(shù)為:

bexpr

I

bterm

bfactor

bexprorbterm

II

btermbfactor

II

bfactorfalse

I

true

7.解答：

(1)把a(bǔ)%"分成a%11和J兩部分，分別由兩個(gè)非終結(jié)符號(hào)生成，因此，生成此文法的

產(chǎn)生式為：

S—AB

A—>aAb|ab

B一CB|E

(2)令S為開(kāi)始符號(hào)，產(chǎn)生的w中a的個(gè)數(shù)恰好比b多一個(gè)，令E為一個(gè)非終結(jié)符號(hào)，

產(chǎn)生含相同個(gè)數(shù)的a和b的所有串，則產(chǎn)生式如下：

S^aE|Ea|bSS|SbS|SSb

E—>aEbE|bEaE|c

(3)設(shè)文法開(kāi)始符號(hào)為S,產(chǎn)生的w中滿足lalWlblW2lal。因此，可想到S有如下的產(chǎn)生

式(其中B產(chǎn)生1到2個(gè)b)：

S-aSBS|BSaS

B—b|bb

(4)解法一：

S一〈奇數(shù)頭〉〈整數(shù)〉〈奇數(shù)尾〉

I〈奇數(shù)頭〉〈奇數(shù)尾〉

I〈奇數(shù)尾〉

〈奇數(shù)尾〉-1|3|5|7|9

〈奇數(shù)頭〉一2|4|6|8|〈奇數(shù)尾〉

〈整數(shù)〉一〈整數(shù)〉〈數(shù)字〉I〈數(shù)字〉

〈數(shù)字〉->0|〈奇數(shù)頭〉

解法二：文法G=({S,A,B,C,D},{0,1,2,3,4,5,6,7,8,9},P,S)

S—ABIB

A—ACID

BT113151719

D—2I4I6I8IB

C—OID

(5)文法G=({N,S,N,M,D},{0,l,2,3,4,5,6,7,8,9},S,P)

S—NO|N5

N一MD歸

M->1|2|3|4|5|6|7|8|9

D-DO|DM|E

(6)G[S]：S->aSaIbSbIcScIaIbIcIs

8.解答：

(1)句子abab有如下兩個(gè)不同的最左推導(dǎo)：

S=>aSbS=>abS=>abaSbS=>ababS=>abab

S=>aSbS=>abSaSbS=>abaSbS=>ababS=>abab

所以此文法是二義性的。

(2)句子abab的兩個(gè)相應(yīng)的最右推導(dǎo)：

S=>aSbS=>aSbaSbS=>aSbaSb=>aSbab=>abab

S=>aSbS=>aSb=>abSaSb=>abSab=>abab

(3)句子abab的兩棵分析樹(shù)：

(4)此文法產(chǎn)生的語(yǔ)言是：在｛a,b｝上由相同個(gè)數(shù)的a和b組成的字符串。

9,10：解答:略！

第3章習(xí)題解答:

i.解答：

(1)V(2)V(3)X(4)X(5)V(6)V

2.［分析］

有限自動(dòng)機(jī)分為確定有限自動(dòng)機(jī)和非確定有限自動(dòng)機(jī)。確定有限自動(dòng)機(jī)的確定性表現(xiàn)

在映射6：QXVT—>q是單值函數(shù)，也就是說(shuō)，對(duì)任何狀態(tài)qGQ和輸入字符串a(chǎn)GV”8(q,a)

唯一確定下一個(gè)狀態(tài)。顯然，本題給出的是一個(gè)確定的有限自動(dòng)機(jī)，它的狀態(tài)轉(zhuǎn)換圖是C

中的②。

它所接受的語(yǔ)言可以用正則表達(dá)式表示為00(01D*,表示的含義為由兩個(gè)0開(kāi)始的

后跟任意個(gè)(包含0個(gè))0或1組成的符號(hào)串的集合。

2.解答：A:④B:③C:②D:②E:④

3,4.解答：略！

5.解答：

Starr

other;

6.解答：

(1)(011),01

(2)((1121...19)(011121...19)*1￡)(015)

(3)(011)*(011)(011)*

(4)1*11*0(0110)*(lie)

(5)ab"c\..z"

(6)(0110,1)*1

(7)(00111)*((01110)(00111)*(01110)(00111)*)*

(8)［分析］

設(shè)S是符合要求的串,|S|=2k+l(k-0)。

則S-SOSzl,Sl=2k(k>0),IS21=2k(k20)。

且Si是｛0,1｝上的串，含有奇數(shù)個(gè)。和奇數(shù)個(gè)1。

Sz是｛0,1｝上的串，含有偶數(shù)個(gè)0和偶數(shù)個(gè)1。

考慮有一個(gè)自動(dòng)機(jī)小接受那么自動(dòng)機(jī)曲如下:

和L(MJ等價(jià)的正規(guī)式,即，為：

((00111)|(0110)(00111)*(01110))*(01110)(00|11),

類(lèi)似的考慮有一個(gè)自動(dòng)機(jī)比接受$2,那么自動(dòng)機(jī)Mz如下:

和L(岫)等價(jià)的正規(guī)式，即S為：

((00|11)|(01|10)(0011)-(01110))*

因此，S為：

((00|11)|(01|10)(00|11)*(01110))*(01110)(00111)*0!

((0011)|(01|10)(00|11)*(01|10))*1

7.解答：

(1)以0開(kāi)頭并且以0結(jié)尾的，由0和1組成的符號(hào)串。

(2){alaG{0,l}*}

(3)由0和1組成的符號(hào)串，且從右邊開(kāi)始數(shù)第3位為0。

(4)含3個(gè)1的由0和1組成的符號(hào)串。{alaG{01}+,且a中含有3個(gè)1}

(5)包含偶數(shù)個(gè)0和1的二進(jìn)制串，即{alaW{0,l}*,且a中有偶數(shù)個(gè)0和1}

8.解答：口

Q。*可

QiQ3Q。

Q2Q。Q3

&Q1Q2

9.解答:

(1)DFAM=({0,1},{q(),qI,q2},qo>3},3)

其中3定義如下：

8(q0，0)=q(8(q()>l)=qo

8(qi，0)=q28(qi>l)=qo

5(q2.0)=q2S(q2>l)=qo

狀態(tài)轉(zhuǎn)換圖為：

(2)正規(guī)式

DFAM=({0,1),{q。，q”q2，q?}，q()，{q3)>8),其中B定義如下:

8(q()，O)=qi8(q(),l)=q()

8(qP0)=q28(qi，l)=qi

S(q2>0)=q3§(q2>l)=q2

8(q3-l)=q3

狀態(tài)轉(zhuǎn)換圖為：

10.解答：

(1)DFAM=({0,1}>{qo>qi>q2>qs}>qo，{q3},8),其中6定義如下:

8(qo<0)=qi8(qo-l)=q2

6(qi>0)=qi8(qi，l)=q3

8(q2，0)=q38(q2>l)=qi

狀態(tài)轉(zhuǎn)換圖為：

(2)DFAM=({0,1},{q0}.q0.{q0}?8),其中3定義如下:

8(q0，0)=qo8(q0.l)=q0

狀態(tài)轉(zhuǎn)換圖為：

11解答：

(1)(alb)*a(alb)

①求出NFAM:

②確定化，得到DFAM:

③化簡(jiǎn):在第②步中求出的DFAM中沒(méi)有等價(jià)狀態(tài),因此它就是最小化的DFAMo

⑵(a)b)*a(alb)(alb)

①求NFAM：

②確定化，得到DFAM：

③化簡(jiǎn)，在第②步中求出的DFAM中沒(méi)有等價(jià)狀態(tài)，因此它已經(jīng)是最小化的DFAM了。

12.解答：

對(duì)應(yīng)的NFA為：

增加狀態(tài)X、Y,再確定化:

ILlb

{x,5}{A.T.Y}(}

{A,T,Y){A,T,Y}{B}

{B}{){B,T,Y}

{B,T,Y}{){T.Y}

{T.Y)(}{}

得到的DFA為:

最小化：該自動(dòng)機(jī)已經(jīng)是最小化的DFA了。

13.解答：

14.解答：

正規(guī)式為：(011)*(00101)化簡(jiǎn)：(011)*0(011)

確定化，并最小化得到:

正規(guī)文法為：

S-1SIOA

A-OB1011CI1

B-0B1011CI1

C-1SI0A

15.解答：

①正規(guī)式：(dd*:l￡)dd"(.dd*l￡),d代表a?z的字母

②NFA為：

③DFA為:

16.解答：

詞法分析器對(duì)源程序采取非常局部的觀點(diǎn)，因此象C語(yǔ)言的語(yǔ)句

fi(a==f(x))...

中，詞法分析器把fi當(dāng)作一個(gè)普通的標(biāo)識(shí)符交給編譯的后續(xù)階段，而不會(huì)把它看成是關(guān)鍵

字if的拼寫(xiě)錯(cuò)。

PASCAL語(yǔ)言要求作為實(shí)型常量的小數(shù)點(diǎn)后面必須有數(shù)字，如果程序中出現(xiàn)小數(shù)點(diǎn)后面

沒(méi)有數(shù)字情況，它由詞法分析器報(bào)錯(cuò)。

17.解答：

此時(shí)編譯器認(rèn)為

/*thenpart

returnq

else

/*elsepart7

是程序的注釋?zhuān)虼怂豢赡茉侔l(fā)現(xiàn)else前面的語(yǔ)法錯(cuò)誤。

分析這是注釋用配對(duì)括號(hào)表示時(shí)的一個(gè)問(wèn)題。注釋是在詞法分析時(shí)忽略的，而詞法分

析器對(duì)程序采取非常局部的觀點(diǎn)。當(dāng)進(jìn)入第一個(gè)注釋后，詞法分析器忽略輸入符號(hào)，一直到

出現(xiàn)注釋的右括號(hào)為止，由于第一個(gè)注釋缺少右括號(hào)，所以詞法分析器在讀到第二個(gè)注釋的

右括號(hào)時(shí)，才認(rèn)為第一個(gè)注釋處理結(jié)束。

為克服這個(gè)問(wèn)題，后來(lái)的語(yǔ)言一般都不用配對(duì)括號(hào)來(lái)表示注釋。例如Ada語(yǔ)言的注釋

始于雙連字符（-），隨行的結(jié)束而終止。如果用Ada語(yǔ)言的注釋格式，那么上面函數(shù)應(yīng)寫(xiě)

成

longgcd(p,q)

longp,q;

(

if(p%q==0)

-thenpart

returnq

else

-elsepart

returngcd(q,p%q);

)

18.解答：略！

第4章習(xí)題解答:

1,2,3,4解答略！

5.解答：

(1)X(2)V(3)X(4)V(5)V(6)V⑺X(8)X

6.解答：

(DA：④B：③C：③D：@E：②

(2)A：④B：④C：③D：③E：②

7.解答:

(1)消除給定文法中的左遞歸，并提取公因子:

bexpr—>bterm{orbterm}

bterm—>bfactor{andbfactor}

bfacto—notbfactor|(bexpr)|true|false

(2)用類(lèi)C語(yǔ)言寫(xiě)出其遞歸分析程序：

voidbexpr();voidbfactor();

((

bterm();if(llokahead=="nof)then(

WHILE(lookahead=='or'){match('not');

match('or');bfactor();

bterm();1

)elseif(lookahead=V)then{

)match(*(');

bexpr();

voidbterm();match(')');

1\

\I

bfactor();elseif(lookahead='true')

WHILE(lookahead=='and'){thenmatch('true)

match('and');elseif(lookahead=false')

bfactor();thenmatch('false');

)elseerror;

)

8.解答：

消除所給文法的左遞歸，得G：

S一(L)|a

L-SL'

,SL'|e

實(shí)現(xiàn)預(yù)測(cè)分析器的不含遞歸調(diào)用的一種有效方法是使用一張分析表和一個(gè)棧進(jìn)行聯(lián)合

控制，下面構(gòu)造預(yù)測(cè)分析表:

根據(jù)文法G有：

First(S)={(,a)Follow(S)={),,,#}

First(L)={(,a)Follow(L)={)}

First(L')={,}Follow(L1)={)}

按以上結(jié)果，構(gòu)造預(yù)測(cè)分析表M如下:

輸入符號(hào)

m留結(jié)符

()?a#

SSa

LL^SL'L->SU

UU3,su

文法G是LL(1)的，因?yàn)樗腖L(D分析表不含多重定義入口。

預(yù)測(cè)分析器對(duì)輸入符號(hào)串(a,(a,a))做出的分析動(dòng)作如下：

步驟棧剩余輸入串輸出

1#s(a,(a,a))##

2#)L(a,(a,a))#s-(L)

3#)La,(a,a))#

4#)L*Sa,(a,a))#L—SU

5#)L'aa,(a,a))#S—>a

6#)L',(a?a))#

7#)L'S,,(a,a))#U1,SL'

8#)L'S(a,a))#

9#)L')L((a,a))#S-(L)

10#)L*)La,a))#

11#)L)LSa,a))#L—SU

12#)L)L'aa,a))#S—a

13#)L)L',a))#

14#)L)US,,a))#L'T,SL,

15#)L)LSa))#

16#)L)L'aa))#S—a

17#)L)U))#

18#)L)))#

19#)L,)#

20#))#L'f

21##

9.解答：

各非終結(jié)符的First集:

First(S)={First(A)\{￡}}U{First(B)\{s}}U{s}U={a,b,￡}

First(A)=U{￡}={b,E}

First(B)={￡)U{a}={a,E)

First(C)={First(A)\{s}}UFirst(D)UFirst(b)={a,b,c}

First(D)={a}U{c}={a,c}

各個(gè)候選式的First集為：

First(AB)={a,b,￡)First(bC)=

First(E)z={￡}First(b)=

First(aD)={a}First(AD)={a,b,c}

First(b)={b)First(aS)={aJ

First(c)={c}

各非終結(jié)符的Follow集的計(jì)算:

Follow(S)={#}UFollow(D)={#}

Follow(A)=(First(B)\{￡})UFollow(S)UFirst(D)={a,#,c}

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

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

Follow(D)=Follow(B)UFollow(C)={#}

10.解答：

(1)求First和Follow集

First(E)=First(T)={(,a,b,Al⑦

First(E')={+,￡}⑥

First(T)=First(F)={(,a,b,A)④

First(T')={(,a,b,A,8)⑤

First(F)=First(P)={(,a,b,A)③

First(F*)={*,8)②

First(P)={(,a,b,Al①（計(jì)算順序）

Follow(E)={#,)}

Follow(E')=FolIow(E)={#,)}(1)(使用的產(chǎn)生式)

Follow(T)=First(E')\{c}UFollow(T')(1,2)

={+}U{),#}={+,),#)

Follow(T')=Follow(T)={+,},#}(3)

Follow(F)=First(T')\{s}UFollow(T)(3,4)

={(,a,b,A,+.),#)

Follow(F')=Follow(F)(5)

={(,a,b,A,+.),#}

Follow(P)=First(F')\{s}UFollow(F)(5,6)

={*,(,a,b.A,+.),#}

⑵證明：

?「a文法不含左遞歸；

b.每個(gè)非終結(jié)符的各個(gè)侯選式的First集不相交;

c.First(E,)nFollow(E')={+,e}n{#,),}=①

First(T')AFollow(T')={(,a,b,A,e}n{+,)}=①

First(F')nFollow(F')={*,s}n{,a,(A,+,},#}=①

改造后的文法滿足LL(1)文法的三個(gè)條件，是LL(1)文法。

(3)預(yù)測(cè)分析表如下所示。

ab*+A()#

EE-TFE一TE，E->TE

E*EJ+EE'fE'f

TJFTT-FTT—FFTTFT

T'T'TTT—TT'->TT—Tr->8Tf

FF-PFF—PFF—PFF-PF

FFT￡FTF—*FF-￡F'fFfFfF'->￡

PP-?aP-bP—AP-(E)

11.解答：

(1)

a.文法不含左遞歸；

S—>/be

b.S,A,B各候選式的First集不相交；

A—a|s

c.First(A)AFollow(A)={a,s}A{b)=<I>

B—>b|s

First(B)AFolk)w(B)={b,￡}A?=<t>

...該文法為L(zhǎng)L(1)文法。

(2)

a.文法不含左遞歸；

b.S,A,B各候選式的First集不相交；

c.First(A)DFollow(A)={a,b,E}A={b厚中

該文法不是LL(1)文法。

12.解答：

①最右推導(dǎo)：

E=>T=>F=>(E)=>(E+T)=>(E+F)=>(E+i)=>(T+i)=>(T*F+i)

語(yǔ)法樹(shù)：

b

—

T

—

圖4.1句型(T*F+i)的語(yǔ)法樹(shù)

②短語(yǔ)：(T*F+i),T*F+i,T*F,i

素短語(yǔ)：T*F,i

最左素短語(yǔ)：T*F

③由于E=>E+T=>E+T*F,故E+T*F為該文法的句型

短語(yǔ)：T*F、E+T*F

直接短語(yǔ)：T*F

句柄：T*F

13.解答：

最左推導(dǎo)：

S=>(T)=>(T,S)=>(S,S)->(a,S)->(a,(T))=>(a,(T,S))

=>(a,(S,S))=>(a,(a,S))=>(a,(a,a))

最右推導(dǎo)：

S=>(T)=>(T,S)=>(T,(T))=>(T,(T.S))=>(T,(T,a))

=>(T,(T,a))=>(T,(a,a))=>(S,(a,a))=>(a,(a,a))

文法中S和T的FirstVT和LastVT集為：

FirstVT(S)={a,(}FirstVT(T)={,,a,()

lastVT(S)={a,)}lastVT(T)={,,a,)}

文法G[S]的算符優(yōu)先關(guān)系表：

a()t#

a?>?>?>

(<?<?

)?>■>■>

1<??>?>

#<?工

根據(jù)優(yōu)先關(guān)系表，對(duì)每個(gè)終結(jié)符或#建立符號(hào)f與g,把f（和g）分成一組。根據(jù)G|S］的算

符優(yōu)先關(guān)系表，畫(huà)出如下的有向圖。

優(yōu)先函數(shù)如下:

a()#

f20220

933010

用算符優(yōu)先分析法分析句子（a,（a,a））。

棧輸入動(dòng)作

u(a.(a.a))#初始

#(a,(a,a))#移進(jìn)

#(a,(a.a))#移進(jìn)

#(N,(a.a))#歸約

#(N.(a.a))#移進(jìn)

#(N,(a.a))#移進(jìn)

#(N,(a.a))#移進(jìn)

#(N.(N.a))#歸約

#(N,(N,a))#移進(jìn)

#(N,(N.a))#移進(jìn)

#(N,(N.N))#歸約

#(N.(N))#歸約

U(N,(N)沖移進(jìn)

#(N,N)#歸約

津歸約

#(N)移進(jìn)

#N歸約，接受

給定的輸入符號(hào)串是文法的一個(gè)句子。

14.解答：

(1)該文法的拓廣文法3為

0,S'-S

1.S-aSAB

2.S-BA

3.AaA

4.AfB

5.B-b

其LR(0)項(xiàng)目集規(guī)范族和識(shí)別活前綴的DFA如下：

I()={S'—SS—aSAB,STBA,B—b}

L={S'TS.}

I2={B->b)

I3={S-aSAB,S—aSAB,S—BA,B—b}

I4={S-B,A,A-，aA,A—>>B,B—>,b}

I5={S—>aS-AB,A—>-aA,A—>B,B—b}

I6={S->aSAB,B->b}

I7={A-aA,A一aA,A—>B,B—>b}

I8={A^B}

b={S—BA}

Iio={S—>aSAB-)

In={A—aA。}

顯然，上述狀態(tài)中沒(méi)有出現(xiàn)沖突。顯然，該文法是LR(O)的文法，因此也是SLR(l)的。

求各個(gè)非終結(jié)符的Follow集，以便構(gòu)造分析表：

Follow(S*)={#}Follow(S)={a,b,#}

Follow(A)={a,b,#}Follow(B)={a,b,#}

構(gòu)造的SLR(l)分析表如下：

actiongoto

ab#sAB

0S3S214

1acc

2巧r5r5

3S3S254

4S7S298

5S7S268

6S210

7S7S2118

8r4r4r4

9已r2r2

10r1r1r1

11r3r3r3

(2)該文法的拓廣文法G為

0.S，fS

1.SfSab

2.S-bR

3.R-S

4.R-a

其LR(0)項(xiàng)目集規(guī)范族和識(shí)別活前綴的DFA如下：

一一

Io={S'—SSSab,SbR}

Ii={S'-S?，S-S?ab}

【2={S-bR,R-S,R—*a,S-Sab,S—>bR}

{S—Sab}

I4={S->bR}

k二{R—S,S一Sab}

k={R-a?}

L={S一Sab?}

顯然，h和I5存在移進(jìn)-歸約沖突。求S和R的Follow集：

Follow(S')={#)

Follow(R)=Follow(S)={a,#}

在b中,出現(xiàn)的移進(jìn)一歸約沖突，且Follow(R)n{a}={a},不能用SLR(l)方法解決。

因此，此文法不是SLR(l)文法。

15.解答：

(1)構(gòu)造其拓廣文法G'的產(chǎn)生式為

0.S'fS

1.S-A

2.A—BA

3.A-*8

4.BfaB

5.Bfb

構(gòu)造其LR(0)項(xiàng)目集規(guī)范族和goto函數(shù)(識(shí)別活前綴的DFA)如下:

Io={[S—S,#],[ST,A,#],[A--BA,#,[A--,#],

[B——aB,a/b/#|,|B-^b,a/b/#]}

Ii={[SJS?，知

I2={[S^A-,#]}

h={[ATB-A,#],[A^-BA,#],[Af,#],

[B—?aB,a/b/#],[B-?-b,a/b/#]}

L={[BTr,a/b/#]}

I5={[B->aB,a/b/#],[B-^aB,a/b/#],

[Bfb,a/b/#]}

I6={[A^BA-,#]}

I7=|[B^aB-,a/b/#]}

該文法的LR(1)項(xiàng)目集規(guī)范族中沒(méi)有沖突，所以該文法是LR(1)文法。

構(gòu)造LR(1)分析表如下：

actiongoto

狀態(tài)

ab#sAB

0S5S4r3123

1acc

2r1

3S5S4r363

4r5巧r57

5S5S4

6r2

7r4r4r4

以上分析表無(wú)多的定義入口，所以該文法為L(zhǎng)R(1)文法。

(3)對(duì)于輸入串a(chǎn)bab,其分析過(guò)程如下：

步驟狀態(tài)棧輸入動(dòng)作

(i)0abab#移進(jìn)

(2)0a5bab#移進(jìn)

(3)0a5b4ab#用B-b歸約

(4)0a5B7ab#用BfaB進(jìn)行歸約

(5)0B3ab#移進(jìn)

(6)OB3a5b#移進(jìn)

(7)OB3a5b4用B-b歸約

(8)0B3a5B7#用B-aB進(jìn)行歸約

(9)0B3B3#用A-￡進(jìn)行歸約

(10)0B3B3A6#用A-BA進(jìn)行歸約

(11)0B3A6*用A-BA進(jìn)行歸約

(12)0A2#用S-A進(jìn)行歸約

(13)0S1#接受

16.解答:

(1)對(duì)于產(chǎn)生式S—AaAb|BbBa來(lái)說(shuō)

First(AaAb)nFirst(BbBa)={a}n=(D

A,BGVN僅有一條候選式。

因此，這個(gè)文法是LL(1)的。

(2)下面構(gòu)造這個(gè)文法的識(shí)別活前綴的DFA。

Io={S'->S,S——AaAb,S—BbBa,A—?，B——}

L={S'—S-}

I2={S_AaAb}

【3={S-BbBa}

I4={S—>Aa,Ab,A—*,}

I5={S->BbBa,Bf}

k={S—>AaAb}

L={S—BbBa}

h={S_AaAb}

k={S—BbBa}

下D?

由于Follow(A)=Follow(B)={a,b},因此項(xiàng)目集Io中存在歸約-歸約沖突。在I。狀態(tài)下，當(dāng)

輸入符號(hào)是a或是b時(shí)，不知用ATE還是BTE進(jìn)行歸約。故此文法不是SLR(l)的。但是,

此文法時(shí)LR⑴的。

17.解答：

該文法的拓廣文法G為

0.S'TS

1.ST(SR

2.S—?a

3.R一,SR

4.R一)

構(gòu)造其LR(O)項(xiàng)目集規(guī)范族和goto函數(shù)(識(shí)別活前綴的DFA)如下：

Io={S-S,S一(SR,S—a}

!

II={S->S-}

b={S—(SR,S1(SR,S->a}

h={S—a,}

k={S一(SR,RfSR,R—)}

k={S_(SR}

I6={RT)}

b={RT,SR,SI(SR,S—a}

[8={RfSR,R—,SR,R—?)}

b={R一,SR}

,R

每個(gè)LR(O)項(xiàng)目集中沒(méi)有沖突。因此，此文法是LR(O)文法。其分析表如下:

actiongoto

狀態(tài)

a()9#5R

0S3S21

1acc

2S3S24

3r2r2r2r2r2

4S6S75

5r1r1r1r1r1

6r5r5r5r5r5

7S2S28

8S6S79

9r4r4r4r4r4

18.解答：略!

第5章習(xí)題解答:

1,2,3解答：略!

4.解答：

(1)設(shè)S,L,B的值的屬性用val表示：

S'-S{printf(S.val)}

S->L'.L2{S.val:=L、Val+L2.val/2UJen8th)

STL{S.val:=L.val}

L->L'B{L.val:=L1.val*2+B.val,

L.length=L'.length+l}

L—B{L.val:=B.val),

L.length:=l}

B—0{B.val:=0}

BT1{B.val:=l}

(2)為S,L引入屬性h,用來(lái)記錄配對(duì)的括號(hào)個(gè)數(shù)：

S'—S{printf(S.h)}

S—a{S.h:=0}

S—(L){S.h:=S.h+l}

L—L⑴,S{L.h:=L?).h+S.h}

L—S{L.h:=S.h)}

(3)為D引入一個(gè)綜合屬性h,用來(lái)記錄D中含id的個(gè)數(shù)

P—>D{printf(D.h)}

D^DI;D2{D.h:=D'.h+D2.h}

D—id:T{D.h:=1}

D-^procid;D';S{D.h:=D'.h+l}

5.解答：

輸入率為bcccaadadadb時(shí)的語(yǔ)法樹(shù)為:

采用修剪語(yǔ)法樹(shù)的方法，按句柄方式自下而上歸約該語(yǔ)法樹(shù)，在歸約時(shí)調(diào)用相應(yīng)的語(yǔ)義

規(guī)則，由此得到最終的翻譯結(jié)果為：34242421.

6.解答：

(a+b)+(c+d/(e-3))*8

7.解答：

(1)ab-c+*

(2)AnotCDnotornotor

(3)abcde/+*+

(4)ABandCnotDoror

(5)a-bc-d+*+

(6)ABorCDnotEandorand

8.解答：

三元式四元式

①(+,a,b)1.(+,a,b,Ti)

②(-,1,-)2.(-,T,T2)