编译原理课后习题答案

第一章

1.典型的编译程序在逻辑功能上由哪几部分组成？

答：编译程序主要由以下几个部分组成：词法分析、语法分析、语义分析、中间代码生成、

中间代码优化、目标代码生成、错误处理、表格管理。

2.实现编译程序的主要方法有哪些？

答：主要有：转换法、移植法、自展法、自动生成法。

3.将用户使用高级语言编写的程序翻译为可直接执行的机器语言程序有哪几种主要的方

式？

答：编译法、解释法。

4.编译方式和解释方式的根本区别是什么？

答：编译方式：是将源程序经编译得到可执行文件后，就可脱离源程序和编译程序单独执

行，所以编译方式的效率高，执行速度快；

解释方式：在执行时，必须源程序和解释程序同时参与才能运行，其不产生可执行程序文

件，效率低，执行速度慢。

第二章

1.乔姆斯基文法体系中将文法分为哪几类？文法的分类同程序设计语言的设计与实现关

系如何？

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

2)

2,写一个文法，使其语言是偶整数的集合，每个偶整数不以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整除的无符号十进制整数。

答：

2|5|8

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

1|4|7

7,设计一个DFA,使其能够接受被4整除的一进制数.

答：

0

「1

8.写出表达下列各项的正则表达式。

（1）二进制数且为5的倍数。

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

（3）2={a,b,c},包含偶数个a的字符串。

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

答：

（1）

可以先画出相应的有限自动机：

添加新的开始状态S和终止状态T:

根据以上自动机，列出以下方程：

①

S=A

②

A=0A+1B+T

③

B=OC+1D

④

C=OE+1A

⑤

⑥D=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出现在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.词法分析器的功能是什么？

答：读源程序的字符序列，逐个拼出单词，并构造相应的内部表示TOKEN；同时检查源程

序中的词法错误。

2.试分析分隔符(空格、跳格及回车等)对词法分析的影响。

答：空格、跳格、回车等分隔符号对词法分析不起作用，可以删除。但是回车符号可以用

于错误定位，所以在删除回车符号前需要统计回车的个数。

3.给出识别C语言全部实型常数的自动机。

答：(+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)求每个产生式的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)={b}

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)

请按递归下降法构造该文法的语法分析程序。

答：求产生式的predict集合：

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

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

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

predict[9F)={i,(}

由于文法中非终极符号E和T对应的产生式的precict集合的交集都不为空，所以该文

法不满足自顶向下分析的条件，现对文法进行等价变换得到如下文法：

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))={(}

由于以上文法中任意非终极符号对应的产生式的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)={#}

对任意非终极符号对应的产生式的predict集合的交集都为空，所以该文法是LL(1)文

法。

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

A->aABe|a

B->Bb|d

(1)试给出与G［A］等价的LL⑴文法6［A］。

(2)构造G，［A］的LL⑴分析表并给出输入串aade#的分析过程。

答：⑴所求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)={d}

Prcdict(B'fbB')={b}

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

对任意非终极符号对应的产生式的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)归约活前缀状态机，并给出LR(O)分析表。

答：

(1)

ChO5-l-(l)有移入、规约冲突

⑵

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-⑶有移入、规约冲突

(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.试写出下列类型的内部表示：

□.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.设当前层数为I,可用区距为101,且有下列程序段：

CONSTmm=333；nn=444；

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

rtype=RECORDi,j:integerEND;

VARa,b:atype;

x,y:real

试写出各标识符的内部表示。

3.设当前层数和区距分别为I和。ff,且有函数说明首部：

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

其中atype的定义见题5,试写出f的内部表示。

4.要求在下面括号中写上相应。(层数)和区距(off)。

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

ARB：atype；0()

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

5.给出下面C程序扫描到语句c=a+b+x时相应的全局符号表(采用顺序表结构)。

6.给出题1中程序扫描到语句c=a+b+x时相应的全局符号表（采用外拉链的散列表结构）。

7.根据标识符的作用域规则，分别给出图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.假设有如下语句序列，写出常表达式优化前和优化后的四元式中间代码。

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

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

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

3.假设有如下语句序列或表达式，写出公共表达式优化前和优化后的四元式中间代码。

(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.写出如下循环语句不变式外提后的四元式中间代码。

whilei<=100do

beginu:=A*B;

m:=u*u;

S:=S+m*m;

i:=i+l;

end

5.写出下面循环语句不变式外提后的四元式中间代码，其中数组各卜标的类型为L.10。

whilei<=100do

beginj:=l;