编译原理作业答案

《编译原理》习题解答：

第一次作业：

P142、何谓源程序、目标程序、翻译程序、汇编程序、编译程序和解释程序？它们之间

可能有何种关系？

答：被翻译的程序称为源程序；

翻译出来的程序称为目标程序或目标代码；

将汇编语言和高级语言编写的程序翻译成等价的机器语言，实现此功能的程序称为翻

译程序；

把汇编语言写的源程序翻译成机器语言的目标程序称为汇编程序；

解释程序不是直接将高级语言的源程序翻译成目标程序后再执行，而是一个个语句读

入源程序，即边解释边执行；

编译程序是将高级语言写的源程序翻译成目标语言的程序。

关系：汇编程序、解释程序和编译程序都是翻译程序，具体见P4图1.3。

P143、编译程序是由哪些部分组成？试述各部分的功能？

答：编译程序主要由8个部分组成：（1）词法分析程序；（2）语法分析程序；（3）语义分

析程序；（4）中间代码生成；（5）代码优化程序；（6）目标代码生成程序；（7）错误检查

和处理程序；（8）信息表管理程序。具体功能见P7-9。

P144、语法分析和语义分析有什么不同？试举例说明。

答：语法分析是将单词流分析如何组成句子而句子又如何组成程序，看句子乃至程序是否

符合语法规则，例如：对变量x：=y符合语法规则就通过。语义分析是对语句意义进行检

查，如赋值语句中x与y类型要一致，否则语法分析正确，语义分析则错误。

补充：为什么要对单词进行内部编码？其原则是什么？对标识符是如何进行内部编码的？

答：内部编码从''源字符串”中识别单词并确定单词的类型和值；原则：长度统一，即刻

画了单词本身，也刻画了它所具有的属性，以供其它部分分析使用。对于标识符编码，先

判断出该单词是标识符，然后在类别编码中写入相关信息，以表示为标识符，再根据具体

标识符的含义编码该单词的值。

第二次作业：

+

P381、设%={11,010},T2={0,01,1001},计算：T2TpT/，T2»

T2Tl={011,0010,0111,01010,100111,1001010}

T/={e,11,010,1111,11010,01011,010010........}

+

T2={0,01,1001,00,001,01001,010,0101........}

P38-398、设有文法G网：

S：：=aAb

A：：=BcA|B

B：：=idt|e

试问下列符号串(1)aidtcBcAb(2)aidtccb(4)abidt是否为该文法的句型或句子。

(1)S=>aAbaBcAb=>aidtcAb=>aidtcBcAb句型但不是句子；

(2)S=>aAb=>aBcAb=>aidtcAb=>aidtcBcAb=>aidtccAb=>aidtccBb=>aidtccb；是句

型也是句子；

(4)该文法的句子或句型的最后一个字符串一定是字符“b”；

第三次作业：

P3911、试分别描述下列文法所产生的语言(文法开始符号为S)：

(1)S：：=OSI01

(2)S：：=aaS|bc

n

(1)L(G)={0l|n^l};{解题思路：将文法转换为正规表达式}

(2)L(G)={a2nbc|n^0}»

P3912、试分别构造产生下列语言的文法：

(1){abna|n=0,1,2,3........}

(3){aban|n^l)

(5){anbmcp|n,m,p》0}

(1)G={VN，VT，P，S},VN={S,A},VT={a,b},

P：S：：=aAa

A：：=bA|£

(3)G={VN,VT,P,S},VN={S,A},VT={a,b},

P：S：：=abA

A：：=aA|a

(5)®G={VN,VT,P,S},VN={S,A,B,C},VT={a,b,c},

P：S：：=ABC

A：：=aA|£

B：：=bB|£

C：：=cC|e

®G={VN,VT,P,S},VN={S},VT={a,b,c},

P：S：：=aS|bS|cS|e

P3915.设文法G规则为：

S：：=AB

B：：=a|Sb

A：：=Aa|bB

对下列句型给出推导语法树，并求出其句型短语，简单短语和句柄。

(2)baabaab(3)bBABb

句型baabaab的短语a,ba,baa,baab,baabaab,简单短语a,句柄

(3)

短语bB,AB,ABb,bBABb

简单短语bB,AB,

句柄bB

第四次作业

P4124.下面文法那些是短语结构文法,上下文有关文法，上下文无关文法，及正规文法?

l.S::=aBB::=cBB::=bC::=c

2.S::=aBB::=bCC::=cC：：=E

3.S::=aAbaA::=aBaA::=aaAB::=bA::=a

4.S::=aCdaC::=BaC::=aaAB::=b

5.S::=ABA::=aB::=bCB::=bC::=c

6.S::=ABA::=aB::=bCC::=cC：：=£

7.S::=aAS::=£A::=aAA::=aBA::=aB:::

8.S::=aAS::=EA::=bAbA::=a

短语结构文法（0）4

上下文有关文法（1）3

上下文无关文法（2）568或者25678

正规文法(3)127或者1

P4229.用扩充的BNF表示以下文法规则:

1.Z::=AB|AC|A

2.A::=BC|BCD|AXZ|AXY

3.S::=aABb|ab

4.A::=Aab|c

解:

1.Z::=A(B|C|E)::=A[B|C]

2.A::=BC(E|D)|{X(Z|Y)}::=BC[D]|{X(Z|Y)}

3.A::=a((AB|c)b)::=a[AB]b

4.A::={ab|c}::={ab}

第五次作业：

P744.画出下列文法的状态图：

Z：：=Be

B：：=Af

A：：=e|Ae并使用该状态图检查下列句子是否该文法的合法句子：f,eeff,eefe。

由状态图可知只有eefe是该文法的合法句子。

P745.设右线性文法G=({S,A,B}9{a,b},S,P),其中P组成如下：

S：：=bAA：：=bBA：：=aAA：：=bB：：=a

画出该文法的状态转换图。

P746.构造下述文法G[Z]的自动机，该自动机是确定的吗？它相应的语言是什么？

Z：：=A0A：：=AO|Z1|O

解1：将左线性文法转换为右线性文法，由于在规则中出现了识别符号出现在规则右

部的情形，因此不能直接使用书上的左右线性文法对应规则，可以引入非终结符号B,将

左线性文法变为Z：：=A0A：：=AO|B1|OB：：=A0,具体为：

rA：=Z1rA：=B1

-I--------A:=A01I------------

、Z:=AOLB:=A0

将所得的新左线性文法转换成右线性文法：

此时利用书上规则，其对应的右线性文法为：A：：=OA|OB|OZ：：=0AB：：=1A

解2：先画出该文法状态转换图：

NFA=({S,A,Z},{0,1},M,{S},{Z})

其中M：M(S,0)={A}M(S,1)=0

M(A,0)={A,Z}M(A,1)=0

M(Z,0)=0M(Z,1)={A}

显然该文法的自动机是非确定的；它相应的语言为：｛0,1｝上所有满足以00开头以0

结尾且每个1必有0直接跟在其后的字符串的集合;那么如何构造其相应的有穷自动机呢？

根据其转换系统可得状态转换集、状态子集转换矩阵如下表所示:

IIolis01

{S',S}{A}01①

{A}{A,Z,7?}12①

{A,Z,Z){A,Z,7?}{A}221

则其相应的DFA为:

P748.设(NFA)M=({A,B},{a,b},M,{A},{B}),其中M定义如下：

M(A,a)={A,B}M(A,b)={B}M(B,a)=0M(B,b)={A,B}

请构造相应确定有穷自动机(DFA)M，o

解：构造一个如下的自动机(DFA)M，，(DFA)M9={K,{a,b},S,Z}

K的元素是[A][B][A,B]

由于M(A,a)={A,B}>故有([A],a)=[A,B]

同样M5([A],b)=[B]

AT([B],a)=0

([B],b)=[A,B]

由于M({A,B},a)=M(A,a)UM(B,a)={A,B}U0={A,B}

故M,([A,B],a)=[A,B]

由于M({A,B},b)=M(A,b)UM(B,b)={B}U{A,B}={A,B}

故M,([A,B],b)=[A,B]

S=[A],终态集Z={[A,B],[B]}

重新定义：令0=[A]1=[B]2=[A,B],则DFA如下所示:

可以进一步化简，把的状态分成终态组{1,2}和非终态组{0}

由于{1,2£={1,2}b={2}u{l,2},不能再划分。至此，整个划分含有两组{1,2}{0}

令状态1代表{1,2},化简如图：

第六次作业：

P7411(1)(0|11*0)*0

解：先构造该正规式的转换系统:

由上述转换系统可得状态转换集K={S,1,2,3,4,Z},

状态子集转换矩阵如下表所示：

IIoIiK01

{S,1,Z){1,Z}{2,3,4}012

{1,Z}{1,Z}{2,3,4)112

{2,3,4}{1,Z}{3,4}213

{3,4}{1,Z}{3,4}313

由状态子集转换矩阵可知，

状态0和1是等价的，而状态2

和3是等价的，因此，合并等价

状态之后只剩下2个状态，也即

是最少状态的DFA。

P7412.将图3.24非确定有穷自动机NFA确定化和最少化。

a

图3.24NFA状态转换图

解：设(DFA)M={K,VT,M,S,Z},其中,K={[0],[0,1],[1]},VT={a,b},M：

11

M([1],a)=[0]M([l],b)=①M([0,1],a)=[0,1]M([0,1],b)=[1]

M([0],a)=|0,1]M(|0],b)=[l]

S=[lbZ={[0],[0,1]}

令[0,1]=2,则其相应的状态转换图为：

现在对该DFA进行化简，先把状态分为两组：

终态组｛0,2｝和非终态组｛1｝,易于发现｛0,2｝

不可以继续划分，因此化简后的状态转换图如下:

P7418.根据下面正规文法构造等价的正规表达式:

S::=cC|a........①

A::=cA|aB........②

B::=aB|c........(3)

C::=aS|aA|bB|cC|a.......④

解：由③式可得B=aB+c—B=a*c

由②式可得A=cA+aBfA=c*aa*c

由①式可得S=cC+a

由④式可得C=aS+aA+bB+cC+aC=c*(aS+aA+bB+a)

C=c*(aS+ac*aa*c+ba*c+a)-S=cc*(aS+ac*aa*c+ba*c+a)+a=cc*aS+

cc*(ac*aa*c+ba*c+a)+a=(cc*a)*(cc*(ac*aa*c+ba*c+a)+a)=(cc*a)*(cc*(ac*aa*c|

ba*c|a)|a)另一种答案是S=c(ac|c)*(ac*aa*c|ba*c|aa|a)|a

第七次作业：

P1421.试分别消除下列文法的直接左递归(采用两种方法一一重复法和改写法)

(1)G[E]:

E::=T|EAT........①

T::=F|TMF........②

F::=(E)|i........(3)

A::=+|-........④

/.......⑤

解：先采用“重复法”：再采用“改写法一

E::=T{AT}E::=TE'

T::=F{MF}E，::=ATE，|e

F::=(E)|iT::=FT9

A::=+|-TF=MFF|e

M::=*|/F::=(E)|i

A::=+|-

M::=*|/

P1422.试分别消除下列文法的间接左递归

(2)G[Z]:

Z::=AZ|b①.

A::=ZA|a........②

解：将②式代入①式可得，Z::=ZAZ|aZ|b消除左递归后得到:

Z::=(aZ|b)Z'

Z，::=AZZ，|£

A::=ZA|a

P1435.对下面的文法G[E]:

E::=TE9

E，::=+E|£

T::=FT'

T9::=T|e

F::=PF'

F'::=*F'|£

P：：=(E)|a|b|A

(1)计算这个文法的每个非终结符号的FIRST和FOLLOW；

(2)证明这个文法是LL(1)文法；

(3)构造它的LL(1)分析表并分析符号串a*b+b;

解：(1)构造FIRST集：

FIRST(E,)={+,e}

FIRST(F，)={*,e}

FIRST(E)=FIRST(T)=FIRST(F)=FIRST(P)={(,a,b,A}

FIRST(T5)={(,a,b,e,A}

构造FOLLOW集：

规则一

#eFOLLOW(E)FOLLOW(E)={#}

规则二

)GFOLLOW®FOLLOE(E)={),#}

FIRST(E){e}^FOLLOW(T)FOLLOW(T)={+}

FIRST(T){e}^FOLLOW(F)FOLLOW(F)={(,a,b,A}

FIRST(F,)-{e}^FOLLOW(P)FOLLOW(P)={*}

规则三

FOLLOW(E)^FOLLOW(E,)FOLLOW(E,)={#,)}

FOLLOW(E)qFOLLOWfT)FOLLOW(T)={+,#,)}

FOLLOW(T)GFOLLOWCT)FOLLOWfT尸{+,#,)}

FOLLOW(T)^FOLLOW(F)FOLLOW(F)={(,),a,b,+,#,A)

FOLLOW(F)^FOLLOW(F,)FOLLOW(F,)={(,),a,b,+,#,A}

FOLLOW(F)^FOLLOW(P)FOLLOW(P)={(,),a,b,+,#,A,*}

最后结果为：

FIRST(E,)={+,e}

FIRST(F,)={*,e}

FIRST(E)=FIRST(T)=FIRST(F)=FIRST(P)={(,a,b,A}

FIRST(T5)={(,a,b,e,A)

FOLLOE(E)={),#}

FOLLOW(E,)={#,)}

FOLLOW(T)={+,#,))

FOLLOWfT尸{+,#,))

FOLLOW(F)={(,),a,b,+,#,A}

FOLLOW(F,)={(,),a,b,+,#,A}

FOLLOW(P)={(,),a,b,+,#,A,*)

(2)证明该文法是LL(1)文法：

证明：对于规则E，::=+E|e,T，::=T|e,F,::=*F,|e(仅有一边能推出空串)

有FIRST(+E)={+}AFIRST(e)=0,FIRST(T尸{(,a,b,八}nFIRST(e)=0

FIRST(*F,)={*}AFIRST(e)=0,FIRST(+E)={+}AFOLLOW(E,)={#,)}=o

FIRST(T)={(,a,b,A}HFOLLOW(T,)={+,#,)}=0

FIRST(*F,)={*}AFOLLOW(F,)={(,),a,b,+,#,A}=0

所以该文法是LL(1)文法。

(3)构造文法分析表

*

ab+()A#

EE—TE，E-TE'E-TE，EfTE，

E，E'f+EE'feE'—e

TT—FT，T-FT，T—FT'TfFT，

T，T，-TT，-TT'—£T，-TT'—eT，->Trf

e

FF—PFF—PF'F—PFF—PP

F9F，一£F'—£F，-eF'_*F'F'—eF'—£F'—£F，一

e

PPfaP—bP-(E)P-A

下面分析符号串a*b+b

步骤分析栈余留输入串所用的产生式

1#Ea*b+b#ETE'

2#E5Ta*b+b#T—FT'

3#ETFa*b+b#F—PF'

4#ETFPa*b+b#Pfa

5#ETFaa*b+b#

6#ETF*b+b#F，—

7#ETP**b+b#

8#ETF，b+b#F，一£

9#ETb+b#T，T

10#E，Tb+b#T—FT'

11#ETFb+b#F—PF'

12#ETF，Pb+b#Pfb

13#ETPbb+b#

14#ETF，+b#F，一£

15#ET+b#T，-e

16#E'+b#E'f+E

17#E++b#

18#Eb#EfTE'

19#E，Tb#T—FT'

20#ETFb#F—PF'

21#ETF，Pb#Pfb

22#ETF，bb#

23#ETF#F，一£

24#ET#T，一£

25#E'#E'f£

26##成功

所以符号串a*b+b是该文法的句子；

P1446.对下列文法，构造相应的FIRST和FOLLOW：

(1)S：：=aAd

A：：=BC

B：：=b|e

(2)A：：=BCc|gDB

B：：=e|bCDE

C：：=DaB|ca

D：：=€|dD

E：：=gAf|c

解：⑴

构造FIRST集

FIRST(S)={a}

FIRST(B)={b,e}

FIRST(C)={c,e}

FIRST(A)={b,c,£}

构造FOLLOW集

规则一

#GFOLLOW(S)FOLLOW(S)={#}

规则二

deFOLLOW(A)FOLLOE(A)={d}

FIRST(C)-{e}^FOLLOW(B)FOLLOW(B)={c}

规则三

FOLLOW(A)GFOLLOW(B)FOLLOW(B)={d,c}

FOLLOW(A)^FOLLOW(C)FOLLOW(C)={d}

最后结果为：

FIRST(S)={a}

FIRST(A)={b,c,e)

FIRST(B)={b,e}

FIRST(C)={c,e}

FOLLOW(S)={#}

FOLLOW(A)={d}

FOLLOW(B)={d,c}

FOLLOW(C)={d}

(2)

构造FIRST集

规则二

FIRST(A)={g},

FIRST(B)={b,e},

FIRST(C)={c},

FIRST(D)={d,e},

FIRST(E)={g,c}.

规则三

FIRST(A)={g,b,c},

FIRST(C)={a,c,d},

FIRST(A)={a,b,c,d,g}.

构造FOLLOW集

规则一

#eFOLLOW(A)FOLLOW(A)={#}

规则二

fGFOLLOW(A)FOLLOE(A)={f,#}

ceFOLLOW(C)FOLLOE(C)={c}

aeFOLLOW(D)FOLLOE(D)={a}

FIRST(Cc)-{e}^FOLLOW(B)FOLLOW(B)={c,d,a}

FIRST(B)-{e}^FOLLOW(D)FOLLOW(D)={b,a}

FIRST(DE)-{e}^FOLLOW(C)FOLLOW(C)={d,g,c}

FIRST(E)^FOLLOW(D)FOLLOW(D)={b,c,a,g}

规则三

FOLLOW(A)^FOLLOW(B)FOLLOW(B)={a,c,d,f,#}

FOLLOW(A)^FOLLOW(D)FOLLOW(D)={a,b,c,f,g,#}

FOLLOW(B)GFOLLOW®FOLLOW(E)={a,c,d,f,#}

FOLLOW(C)GFOLLOW(B)FOLLOW(B)={a,c,d,g,f,#)

FOLLOW(B)GFOLLOW®FOLLOW(E)={a,c,d,g,f,#}

最后结果为：

FIRST(A)={a,b,c,d,g},

FIRST(B)={b,e},

FIRST(C)={a,c,d},

FIRST(D)={d,e},

FIRST(E)={g,c},

FOLLOE(A)={f,#}

FOLLOW(B)={a,c,d,g,f,机

FOLLOW(C)={d,g,c},

FOLLOW(D)={a,b,c,f,g,#},

FOLLOW(E)={a,c,d,g,f,#}.

P1449.设已给文法G[S]:

S：：=SaB|bB

A：：=Sa

B：：=Ac

(1)将此文法改写为LL(1)文法

(4)构造LL(1)分析表

解：此题消除左递归之后，构造LL(1)分析表存在“多重入口”问题，故采用以下方法:

(1)改写为LL(1)文法:

S：：=bB{aB}

A：：=Sa

B：：=Ac

(4)

FIRST(S)={b},

FIRST(A)={b},

FIRST(B)={b},

FOLLOE(S)={a,#},

FOLLOW(A)={c},

FOLLOW(B)={a,#}.

abc#

sS：：=bB{aB}

AA：：=Sa

BB：：=Ac

P14410.证明下述文法不是简单优先文法：

(1)S：：=bEb

E：：=E+T|T

(2)S：：=bEb

E：：=F|F+T|T|i

T：：=i|(E)

证明：

(1)画语法树：S

/I\

bEb

/I\

E+T

可以得出b=E和b〈E,因此该文法不是简单优先文法。

⑵因该文法中含

E：：=i

T：：=i

右部两个产生式相同，故该文法不是简单优先文法.

P14511.构造下述文法的优先关系矩阵，它们是简单优先文法吗？

S：：=M|U

M：：=iEtMeM|a

U：：=iEtS|iEtMeU

E：：=b

解:

SMUEiteabSMUEiteab

s^OOOOOOOO'xsx-011000000-x

M000000100M000010010

U000000000u000010000

Br二E000001000BL二E000000001

i000100000i000000000

t110000000t000000000

e011000000e000000000

a000000000a000000000

00000000)

b\oooooooo)b

SMUEiteabSMUEiteab

SZ0OOOOOOOO-^S「011010010、

M000000100M000010010

U000000000u000010000

BL2=E000001000BL=E000000001

i000100000i000000000

t110000000t000000000

e011000000e000000000

a000000000a000000000

00000000)

b%oooooooo-^b

+

B<=BrxBL

SMUEiteabSMUEiteab

s/00000000、S「011000000、

M000000000M010000010

U000000000U101000000

B<«=E000000000BR=E000000001

i000000001i000000000

t011010010t000000000

e000010010e000000000

a000000000a000000000

00000000)

b%oooooooo-^b

SMUEiteabSMUEiteab

s11000010-xsz-111000010

M010000010M010000010

u111000000u111000010

BR2二E000000000BR3二E000000000

i000000000i000000000

t000000000t000000000

JJ

A

00I000000

000000000a

000000000

000000000I

000000000a

000000000n

00I000000w

00000000rs

qgeiianws

10000000(kqX-O00I0000(Kq

010000000p001000000p

00I000II0a000000000a

0001000II000000000

0000I0000I000000000T

T0000I000ax000000000a=JHxHHx[(+x)H=气

0000I0I00n000000000n

0100I00I0w001000000w

【0IIJ

0T00s0000000(Ks

quaq.TanKsq13anws

00T00000xq厂10000000名q

001000000T3010000000p

000000000d0010000000

000000000000T000004-

000000000T000010000T

000000000aI0000T0003=*^9

000000000n二节x(x)8000010100n

001000000w0I00I00I0w

lo00J

00000siooioiirs

qpa4-T9flws

「00000I000、q厂00000000名q

000000IT

00000000000000000000

000000000]0000000004-

000000000T000000000T

a=工(+N)H

000000000100000000a二十阻

000000I0In0I0000IIIn

000000IIIw010000010w

I00000J^-oiooooiTr

00Iss

qgajianwsqga—anws

000000000q000000000q

000000000000000000g

000000000d0000000000

b000001000

优先关系矩阵如下:

SMUiEteab

S

M=>

U

i=<­

E=

t==<<<<

e==<<

a>

b

其中含多重定义的表项，因而该文法不是简单优先文法。

P14512.根据图4.25的语法树，确定全部优先关系:

(a)E=++=TT=**二F(=EE=)

*<(+<F+<iF>*i>*)>+T>+F>+

(b)〈说明表＞=；BEGIN=＜说明表＞REAL=v标识符表》

〈变量＞=：=;=＜语句表＞:==i

BEGINw说明〉BEGIN＜REALREAL<i

;«语句〉；《变量〉；＜i

〈说明＞＞；＜标识符表》；i＞；i>:=

P14513.利用表4.6文法G[E]的优先关系矩阵，来分析符号串#b(((aa)a)a)b#和#((aa)a)#。

(1)

步骤符号栈关系输入串规则

1#<b(((aa)a)a)b#

2#b<(((aa)a)a)b#

3#b(<((aa)a)a)b#

4#b((<(aa)a)a)b#

5#b(((<aa)a)a)b#

6#b(((a>a)a)a)b#

7#b(((M=a)a)a)b#M：：=a

8#b(((Ma=)a)a)b#

9#b(((Ma)>a)a)b#

10#b(((L>a)a)b#L：：=Ma)

11#b((M=a)a)b#M：：=(L

12#b((Ma=)a)b#

13#b((Ma)>a)b#

14#b((L>a)b#L：：=Ma)

15#b(M=a)b#M：：=(L

16#b(Ma=)b#

17#b(Ma)>b#

18#b(L>b#L：：=Ma)

19#bM=b#M：：=(L

20#bMb>#

21#Z>#Z：：=bMb

⑵

步骤符号栈关系输入串规则

1#<((aa)a)#

2#(<(aa)a)#

3#((<aa)a)#

4#((a>a)a)#

5#((M=a)a)#M：：=a

6#((Ma=