編譯原理課后習題答案

第一章

1.典型的編譯程序在邏輯功能上由哪幾部分組成？

答：編譯程序主要由以下幾個部分組成：詞法分析、語法分析、語義分析、中間代碼生成、

中間代碼優(yōu)化、目標代碼生成、錯誤處理、表格管理。

2.實現(xiàn)編譯程序的主要方法有哪些？

答：主要有：轉(zhuǎn)換法、移植法、自展法、自動生成法。

3.將用戶使用高級語言編寫的程序翻譯為可直接執(zhí)行的機器語言程序有哪幾種主要的方

式？

答：編譯法、解釋法。

4.編譯方式和解釋方式的根本區(qū)別是什么？

答：編譯方式：是將源程序經(jīng)編譯得到可執(zhí)行文件后，就可脫離源程序和編譯程序單獨執(zhí)

行，所以編譯方式的效率高，執(zhí)行速度快；

解釋方式：在執(zhí)行時，必須源程序和解釋程序同時參與才能運行，其不產(chǎn)生可執(zhí)行程序文

件，效率低，執(zhí)行速度慢。

第二章

1.喬姆斯基文法體系中將文法分為哪幾類？文法的分類同程序設計語言的設計與實現(xiàn)關

系如何？

答：1)。型文法、1型文法、2型文法、3型文法。

2)

2,寫一個文法，使其語言是偶整數(shù)的集合，每個偶整數(shù)不以0為前導。

答：

Z今SME|B

S^l|2|3|4|5|6|7|8|9

IDIMD

D->O|S

B->2|4|6|8

F->O|R

3.設文法G為：

D|ND

D^0|l|2|3|4|5|6|7|8|9

請給出句子123、301和75431的最右推導和最左推導。

答：NnNDnN3nND3nN23nD23nl23

N=>ND=>NDD=>DDD=>1DD=>12D=>123

NnNDnNlnNDl=N01nD01n301

N=>ND=>NDD=>DDD=>3DD=>30D=>301

NnNDnNlnNDl=N31nND31=N431nND431=N5431nD5431n75431

N=ND=NDDnNDDDnNDDDDnDDDDDn7DDDD=75DDD=754DDn7543Dn75431

4.證明文法S^iSeS|iS|i是二義性文法。

答：對于句型iiSeS存在兩個不同的最左推導：

S=>iSeS=>iiSes

SniSniiSeS

所以該文法是二義性文法。

S.給出描述下面語言的上下文無關文法。

(1)Ll={anbnc'|n>=lj>=0}

(2)L2={ab|j>=i>=l}

nmmn

(3)L3={abcd|mzn>=0}

答：

(1)STAB

A->aAb|ab

B->cB|￡

(2)S^ASb|ab

A->a|c

（3）S->aSd|A|E

A^bAc|￡

6.設計一個最簡的DFAM,使其能夠識別所有的被3整除的無符號十進制整數(shù)。

答：

2|5|8

2|5|82|5|810|3|6|9

1|4|7

7,設計一個DFA,使其能夠接受被4整除的一進制數(shù).

答：

0

「1

8.寫出表達下列各項的正則表達式。

（1）二進制數(shù)且為5的倍數(shù)。

（2）Z={a,b,c},第一個a位于第一個b之前的字符串。

（3）2={a,b,c},包含偶數(shù)個a的字符串。

4）2={0,1},不包含11子串的字符串。

答：

（1）

可以先畫出相應的有限自動機：

添加新的開始狀態(tài)S和終止狀態(tài)T:

根據(jù)以上自動機，列出以下方程：

①

S=A

②

A=0A+1B+T

③

B=OC+1D

④

C=OE+1A

⑤

⑥D(zhuǎn)=OB+1C

E=OD+1E

解以上方程組：

⑥E=1*OD

②A=O+1B+OT

⑥代入④c=oroD+iA

⑤代入④oo1'ooB+oroic+iA

C=xB+yA

其中x=(01-01)*01*00y=(01*01)*l

⑤代入③B=OC+10B+11C

B=(O|11)C+1OB

B=(1O)*(O|11)C

將C=xB+yA代入上式B=uB+vA

B=u'vA

其中u=(10)*(0|ll)xv=(10)*(0|ll)y

將B-u*vA代入②A-O」u*vA+O*T

A=(O*lu*v)4O*T

將A代入①S=(O*lu*v)*OT

串(O*lu*v)*O*即為所求。

(2)該題目理解為：至少有一個a和一個b,且a出現(xiàn)在b的前面(可以有間

隔)，則答案為：

c*a(a|c)*b(a|b|c)*

(3)((b|c)*a(b|c)*a)*(b|c)*(a(b|c)*a|b|c)*

(4)(0|10)*(1|s)

第三章

1.詞法分析器的功能是什么？

答：讀源程序的字符序列，逐個拼出單詞，并構造相應的內(nèi)部表示TOKEN；同時檢查源程

序中的詞法錯誤。

2.試分析分隔符(空格、跳格及回車等)對詞法分析的影響。

答：空格、跳格、回車等分隔符號對詞法分析不起作用，可以刪除。但是回車符號可以用

于錯誤定位，所以在刪除回車符號前需要統(tǒng)計回車的個數(shù)。

3.給出識別C語言全部實型常數(shù)的自動機。

答：(+H)([1-9][0-9]*|0)(.[0-9][0-9]*|)(E(+|-|)[0-9][0-9]*)

4.寫出識別C語言中所有單詞的LEX程序。

答：

L=[A-Z]|[a-z]

D=[0-9]

D1=[1-9]

%%

(L|J(L|D|J*{return(1);)

D1D*{return(2);}

+{return(3);}

第四章

1.設有如下文法G[S]:

S->aABbcd|8

A^ASd|e

B->SAh|eC|8

C->SfICg|￡

(1)求每個產(chǎn)生式的Predict集。

(2)該文法是否為LL⑴文法？為什么？

答：⑴

Predict(S->aABbcd)={a}

Predict(S->￡)={#,d,f,a,h}

Predict(A->ASd)={azd}

Predict(A->E)={h,a,d,b,e}

Predict(R->SAh)={a,d,h}

Predict(B->eC)={e}

Predict(B->8)=

Predict(C->Sf)={a,f}

Predict(C->Cg)={a/f/g)

Predict(C->e)={g,b}

(2)由于Predict(A->ASd)nPredict(A->￡)w0,所以該文法不是LL⑴文法。

2.下列描述括號匹配的文法中，哪些是LL⑴文法？

(1)ST(SS」c

S'力I￡

(2)ST(S)S|￡

(3)S^S(S)S|8

(4)S-|S，

S'T(S，)|￡

答：(1)不是，(2)是，(3)不是，(4)不是

3.已知文法G舊：

E->E+T|T

T->T*F|F

TI(E)

請按遞歸下降法構造該文法的語法分析程序。

答：求產(chǎn)生式的predict集合：

predict(E->E+T)={i,(}

predict(E->T)={i,(}

predict(T^T*F)={i,(}

predict[9F)={i,(}

由于文法中非終極符號E和T對應的產(chǎn)生式的precict集合的交集都不為空，所以該文

法不滿足自頂向下分析的條件，現(xiàn)對文法進行等價變換得到如下文法：

ETTE'

E>TE'|8

TfFT'

T'今*FT'|￡

F->i

F今(E)

求新文法的predict集合：

Predict(E->TE')={(,i}

Predict(E,->+TE/)={+}

Predict(E,->￡)={#,)}

Predict-FT)={i,(}

Predict(T'玲*FT')={*}

Predict(T/->c)={+,),#}

Predict(F->i)={i}

Predict(F^(E))={(}

由于以上文法中任意非終極符號對應的產(chǎn)生式的predict集合的交集都為空，所以滿足

自頂向下分析的條件，所以可以寫出如下的遞歸下降語法分析偽代碼：

VoidE()

{if(tokenw{(,i}){T();E'();}

elseError();}

voidEz()

{if(tokenc{,}){Match(*);T();E，();}

elseif(token€{#,)}){;}

elseErrorf);}

voidT()

{if(tokenw{i,(}){F();T();}

elseError();}

voidr()

{if(token￡{*}){Match('*');F();T'();}

elseif(token€{?/)/#}){;}

elseError();}

voidF()

{if(tokene{i}){Matchfr);}

elseif(token€{{}){Match(z(/)；E();Match(z)/)；}

elseError();}

4.構造一個LL⑴文法G,它能識別語言L:

L={co|⑴為字母表E上不包括兩個相鄰的1的非空串},其中E={0，l}o

并證明你所構造的文法是LL(1)文法。

答：A-?OE|IF

B->OE|IF

CTOE

E->B|E

F->C|￡

Predict(A->OE)={O}

Predict(A->lF)={l}

Predict(B->OE)={O}

Predict-1F)={1}

Predict(E->B)={04}

Predict(E->s)={#}

Predict(F->C)={0}

Predict(F->s)={#}

對任意非終極符號對應的產(chǎn)生式的predict集合的交集都為空，所以該文法是LL(1)文

法。

5.已知文法G［A］為:

A->aABe|a

B->Bb|d

(1)試給出與G［A］等價的LL⑴文法6［A］。

(2)構造G，［A］的LL⑴分析表并給出輸入串a(chǎn)ade#的分析過程。

答：⑴所求G1A］為：

A->aAz(1)

A'TABe(2)

Nfe(3)

BfdB，(4)

B'lbB，(5)

B;->￡(6)

Rredict(A->aA*)={a}

Predict(Az^ABe)={a}

Predict(A'f￡)={#,d}

Predict(B->dBz)=wfdmuim

Prcdict(B'fbB')=

Predict(B/->￡)={e}

對任意非終極符號對應的產(chǎn)生式的predict集合的交集都為空，所以該文法是LL(1)文

法。

(3)分析表如下:

abde#

A(1)

A，(2)⑶⑶

B⑷

B，(5)(6)

aade#的分析過程如下

分析棧輸入流動作

A#aade#替換⑴

aA'#aade#匹配

A'#□de#替換(2)

ABe#ade#替換⑴

aA'Be#ade#匹配

A'Be#de#替換⑶

Be#de#替換⑷

dB'e#de#匹配

B'e#e#替換

e#e#匹配

##成功

第五章(這章答案是錯的)

1.設有下列文法：

(1)S^aA

A->Ab

A->b

(2)S-^aSSb

S->aSSS

S->c

(3)S->AS

STb

A->SA

A玲a

(4)S->cA

S->ccR

B->ccB

B->b

A->cA

A->a

構造上述文法的LR(O)歸約活前綴狀態(tài)機，并給出LR(O)分析表。

答：

(1)

ChO5-l-(l)有移入、規(guī)約沖突

⑵

Ch05-l-(2)

actiongoto

abc#S

SOs2s51

/\

(1)

Z-.SX/SIAcc

/2\

()

S-*.aSSbX/

/\S2s2s53

(3

S-*.aSSSX7

z\

(41S3s2s54

S—.cx7

S4s2s6s57

S5R4R4R4R4

S6R2R2R2R2

S7R3R3R3R3

⑶

ChO5-1-⑶有移入、規(guī)約沖突

(4)

/1\

()actiongoto

z-s\/

z2\

(7abc#ABS

S-cA\

/3\

(7SOsi2

S—ccB\

z4\

(7

B-*ccB\SIs3s54

z5\

(7

Bfb\S2Acc

/6\

(1

A-*cA\/S3R7R7R7R7

z

(7

A-*a\S4R6R6R6R6

S5s3s9s876

S6R3R3R3R3

S7R2R2R2R2

S8s3slO7

S9R5R5R5R5

S10s3s9s8711

SliR4R4R4R4

2.設有下列文法:

(1)S->SASIh

(2)STbSb|cSc|b|c

⑶S^bSb|bSc|d

(4)S->aSb|bSa|ab

(5)S-?Sab|bR

R->S|a

(6)S玲SAB|BA

B9b

A今aA|B

⑺S->AaAb|BbBa

BTg

A->8

(8)A^aABe|Ba

BTdB|￡

說明上述文法是否為SLR(l)文法。若是，請構造SLR(l)分析表；若不是，請說明理由,

答：

(1)

ChO5-2-(l)不是SLR(1)

FoIlow(S)={#,a}

S-*Sa.S

S-SaS.

S-*.SaSS-*.SaS

ST.aSST.aS

S-.bS-.h

b

b

S~b.

(2)

Ch05-2-⑵不是SLR(1)

Follow(S)={#,b,c}

0

Z-.S

S-*.bSb

S-*.cSc

S—.b

S->.c

⑶

ChO5-2-⑶是SLR(1)

actiongoto

bcd#S

z-.sSOs2s31

Sf.bSbSIAcc

S-*.bScS2s2s34

S-*.dS3R4R4R4

S4s5s6

S5R2R2R2

S6R3R3R3

(4)

Ch05-2-(4)不是SLR(1)

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

234

S_*a.Sb-STS-aS.bS-*aSb.

S-*a.b5

S—aSbS-*ab.

S-*.bSaS-*b.Sa

S-*.abS-*.aSb

S-*.bSa

4S—.ab

S-*b.Sa

S—*.aSb

S—.bSa

S-*.ab

⑸

Ch05-2-⑸不是SLR(1)

Follow(R)={#.a}

1

z-*s.23

-a-2

S_*S.abS—Sa.bS-*Sab.

0

Z-.S

S-*.Sab-b—J

S-*.bR

(6)

actiongoto

ab#ABS

SOs231

?1\

X(7J

z-*sz2\SIs6s2Acc85

\f7|

STAB/\S2R6R6R6

f37

S-BA\s24

(/4n\S3s65

A-*aAX/

A/5\S4R3R3R3

X(7|

B/6\S5R5R5R5

XI/—

S6s6s275

S7R4R4R4

S8s29

S9R2R2R2

(7)

Ch05-2-(7)不是SLR(I)

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

(8)

ChO5-2-(8)不是SLR(1)Follow(B)={a,e}

3.設有下列文法：

STaAd|bBd|aBe|bAe

A->g

B->g

說明該文法是LR⑴文法，但不是LALR⑴文法。

答：

ChO5-3是LR(I)文法

ChO5-3不是LALR⑴文法

2小S—aA.d

S—>a.Ad#

S->a.Be#煙5

S-?aB.c

Afgd

Zfs#-a-3

S—>.aAd#g

SfbBd#

S—?.aBc#

S—.bAe￡T

S—b.Bd#

Z9

S->b.Ae#LATS-?bA.e#

Afg

S—bB.d

4.設有下列文法:

(1)E->E+TIT

T->TF|T

F今(E)|F*|a|b

⑵S->Aa|bAc|de|bda

A->d

說明上述文法是否為SLR(l)文法？是否為LALR⑴文法？并構造相應的分析表。

答：⑴

ChO5-4-(l)不是SLR(l)文法Follow(T)={#,(,a,b,+,))

F

Ch05-4-(l)不是LALR(1)文法

F-F*.#+(ab*

34

ETE+T.#+T-?TF.#+(ab

T—T.F#+(abF->F*#+(ab*

T—T.#+(ab

2Ff(E)#+(ab*F—a.#+(ab*

1E—E+.T#+(ab*)FfF*#+(ab*

T->.TF#+(ab-TT

Z->E.#_Fra#+(ab*F->b.#+(ab*

E—E.+T#+T->.T#+(abFrb#+(ab*

1E

611

#+(ab*)

ZfE#FfE)#+(ab*)F-(.E)#+(ab*)KETT.

T—T.F#+(ab*)

E—.E+T#+E—E.+T#+(ab*)E—.E+T#+(ab*)

(E-

ErT#+E-.T#+(ab*-T-T.#+(ab*)

(Ff(E)#+(ab*)

TfTF#+(ab10TfTF#+(ab*>

#+(ab*)

T-?.T#+(abF—>(E).#+(ab*)T—.T#+(ab*)卜T~)尸

Ffa#?(ub*)

F—.b#+(ab*)

(2)

Ch05-4-⑵不是SLR(l)文法Follow(A)={a,c}

ChO54⑵是LALR(l)文法

actiongoto

abcd#AS

SOs6s241

Z-.S(1)

S-*.Aa(2)SIAcc

SfbAc(3)S2R6s3

ST.de(4)S3R4

S—>.bda(5)S4s5

Afd(6)S5R2

S6s79

S7s8R6

S8R5

S9slO

S10R3

5.設有下列文法：

LfMlb|a

說明上述文法是否為LR⑴文法，若不是，請說明理由。

答：

Ch05-5是LR(1)文法

第六章

1.試寫出下列類型的內(nèi)部表示：

□.integer

b.ARRAY[1..5]ofRECORDinteger;b:booleanEND

c.ARRAY[1..5]ofRECORDa:ARRAY[1..10];r:RECORDij:integerENDEND

d.RECORDr:RECORDx,y:realEND;a:ARRAY[1..10]ofirtegerEND

2.設當前層數(shù)為I,可用區(qū)距為101,且有下列程序段：

CONSTmm=333；nn=444；

TYPEatype=ARRAY[1..1O]OFreal;

rtype=RECORDi,j:integerEND;

VARa,b:atype;

x,y:real

試寫出各標識符的內(nèi)部表示。

3.設當前層數(shù)和區(qū)距分別為I和。ff,且有函數(shù)說明首部：

FUNCTIONf(A：atype：VARB：atype；VARX：real)：integer

其中atype的定義見題5,試寫出f的內(nèi)部表示。

4.要求在下面括號中寫上相應。(層數(shù))和區(qū)距(off)。

()()PROCEDUREg(A：atype；()()

ARB：atype；0()

ARX：real()())()().

5.給出下面C程序掃描到語句c=a+b+x時相應的全局符號表(采用順序表結(jié)構)。

6.給出題1中程序掃描到語句c=a+b+x時相應的全局符號表（采用外拉鏈的散列表結(jié)構）。

7.根據(jù)標識符的作用域規(guī)則，分別給出圖6.5的程序中，過程P、Q、R、S中有效的標識

符。

第七章

1.將算術表達式(a+b)*(c+d)-(a+b+c)翻譯成四元式序列。

2.將下列語句翻譯成四元式序列：

a.IFx>0THENx:=0ELSEx:=l

b.WHILEx>0DOx:=x-l

C.IFx>0THENx:=x+lELSE

IFx<0THENx:=x+lELSEx:=x+l

d.WHILEx>0DO

WHILEy>0DO

BEGINy:=y-x;x:=x-lEND

3.給出如下程序段的四元式序列。(四元式的操作符可用自身代替)。其中A：Array

ofintegero

a:=l;

whilea<=10do

beginifaobthen

A[a]:=A[b]+2;

elsea:=a+l;

b:=b+l;

end

4.試將FOR語句翻譯成川元式序列。

5.試將UNTIL語句翻譯成四元式序列。

6.試將CASE語句翻譯成四元式序列.

7.試給出4、5、6題中翻譯過程的語法制導程序。

第八章

1.將下面的程序段劃分為基本塊并畫出其程序流圖。

read(A);

read(B);

F:=l;

C:=A*A;

D:=B*B;

ifC<DgotoLI;

E:=A*A;

F:=F+1;

E:=E+F;

write(E);

gotoL3;

LI:E:=B*B;

F:=F+2;

write(E);

ifE>100gotoL2;

gotoL3;

L2:F:=F-1;

gotoLI;

L3:write(E);

2.假設有如下語句序列，寫出常表達式優(yōu)化前和優(yōu)化后的四元式中間代碼。

(1)i:=l;(2)a:=20;

j:=i*(i+l);b:=a*(a+10);

k:=2*(i+j);c:=a*b;

3.假設有如下語句序列或表達式，寫出公共表達式優(yōu)化前和優(yōu)化后的四元式中間代碼。

(1)x:=x*y+z;y:=x*y+z;z:=x*y+z;

(2)(a*b+c)/(a*b-c)+(c*b+a-d)/(a*b+c)

4.寫出如下循環(huán)語句不變式外提后的四元式中間代碼。

whilei<=100do

beginu:=A*B;

m:=u*u;

S:=S+m*m;

i:=i+l;

end

5.寫出下面循環(huán)語句不變式外提后的四元式中間代碼，其中數(shù)組各卜標的類型為L.10。

whilei<=100do

beginj:=l;