编译原理-练习参考

程序设计语言

Chapter2.高级语言及其语法描述编译原理参考答案2023/2/5CH.2.练习题6(P36.)6.令文法G6为:

N→D|NDD→0|1|2|3|4|5|6|7|8|9(1)G6的语言L(G6)是什么?注意：集合的写法不正确解：L(G6)={0,1,2,3,4,5,6,7,8,9}+

={09数字构成的所有数字串，可以0开头}(2)给出句子0127、34和568的最左和最右推导。注意：1)步骤，和的区别；2)不能写为→解：0127的最左推导：NNDNDDNDDDDDDD0DDD01DD012D01270127的最右推导：NNDN7ND7N27ND27

N127D1270127+CH.2.练习题8(P36.)8.令文法为

E→T|E+T|E-TT→F|T*F|T/FF→(E)|i

(1)给出i+i*i、i*(i+i)的最左推导和最右推导。解：此处仅以i*(i+i)为例给出答案最左推导ETT*FF*F

i*Fi*(E)i*(E+T)

i*(T+T)

i*(F+T)

i*(i+T)

i*(i+F)

i*(i+i)

最右推导ETT*FT*(E)T*(E+T)T*(E+F)T*(E+i)T*(T+i)T*(F+i)

T*(i+i)

F*(i+i)

i*(i+i)

CH.2.练习题8(P36.)8.令文法为

E→T|E+T|E-T

T→F|T*F|T/FF→(E)|iEE-TE-TTFFiFiii-i-i

的语法树(2)给出i+i+i、i+i*i和i-i-i的语法树。EE+TE+TTFFiFiii+i+i

的语法树i+i*i的语法树EE+TTTFFiFii*注意：树枝和符号均不可随意增减！CH.2.练习题9(P36.)9.证明下面的文法是二义的：

S→iSeS|iS|i证明:因为存在句子iiiei，它对应两棵不同的语法树,如右图:

所以该文法是二义文法。说明：按定义只要能给出一个反例即可，iiiei不是唯一的反例。SiSiSeSiiiSiSeSiSi2023/2/5程序设计语言

Chapter3.词法分析编译原理参考答案2023/2/5CH.3.练习题8(P64.)8.给出下面的正规表达式。(1)以01结尾的二进制数串;正规式(0|1)*01(2)能被5整除的十进制整数;允许任意0开头：

(0|1|2|3|4|5|6|7|8|9)*(0|5)不允许0开头（0本身除外）：(0|5)|(1|2|3|…|9)(0|1|2|3|…|9)*(0|5)2023/2/5CH.3.练习题7(P64.)7.构造下列正规式相应的DFA。(1)1(0|1)*101

解2:正规式对应的NFA:04123110110

I

I0I1{0}初0{1}1{1}1{1}1{1,2}2{1,2}2{1,3}3{1,2}2{1,3}3{1}1{1,2,4}4{1,2,4}终4{1,3}3{1,2}210423110110010DFA:2023/2/57.构造下列正规式相应的NFA。(P64.)(2)1(1010*|1(010)*1)*0XY20ε113ε1010*1(010)*1XY20ε113ε6451100*7811(010)*2023/2/57.构造下列正规式相应的NFA。(P64.)(2)1(1010*|1(010)*1)*0XY20ε113ε645110078119εε10010εεXY20ε113ε645110078119εε100εε1211017.

(2)1(1010*|1(010)*1)*0的NFA。2023/2/5CH.3.练习题14(P64.)(1)正规式:(10|0)*

(2)NFA:确定化:YX10ε0ε1201001012

I

I0I1{X,1,Y}{1,Y}{2}

{1,Y}{1,Y}{2}{2}{1,Y}

I

I0I1初终0

12

终11

2

2

1

DFA:2023/2/5CH.3.练习题14(P64.)(1)正规式:(10|0)*

(2)NFA:YX10ε0ε1201001012DFA:构造一个DFA，它接受S＝{0,1}上所有满足如下条件的字符串：每个1都有0直接跟在右边。10010DFA:(最简)2023/2/5编译原理参考答案程序设计语言

Chapter4.自上而下语法分析2023/2/5CH.4.练习题1(P81.)1.考虑下面文法G1:

S→a|^|(T)T→T，S|S(1)消去G1的左递归。然后对每个非终结符,写出不带回溯的递归子程序。解(1)消左后的文法G1’:S→a|^|(T)T→ST’T’→,ST’|ε2023/2/5CH.4.练习题1(P81.)解(1)不带回溯的递归子程序:S→a|^|(T)ProcedureS;Beginifsym=‘a’orsym=‘^’thenadvanceelseifsym=‘(‘thenbeginadvance;T;ifsym=‘)’thenadvance

elseerrorendelseerrorEnd;CH.4.练习题1(P81.)解(1)不带回溯的递归子程序:T→ST’ProcedureT;BeginS;T’end;

解(1)不带回溯的递归子程序:T’→,ST’|εprocedureT’;beginifsym=‘,’thenbeginadvance;

S;T’endEnd;CH.4.练习题1(P81.)(2)经改写后的文法是否是LL(1)的?给出它的预测分析表。消左后的文法G1’:S→a|^|(T)T→ST’T’→,ST’|ε(2)因为G1’

:①文法不含左递归;②对S→a|^|(T)

FIRST(a)={a},FIRST(^)={^},FIRST((T))={(},集合互不相交且不含ε;③对T’→,ST’|εFIRST(,ST’)={,},FIRST(ε)={ε},其交集为空。

但ε∈FIRST(T’)=FIRST(,ST’)∩FIRST(ε)={，,ε},

然而，FOLLOW(T’)={)}FIRST(T’)={，,ε}，两者不相交。所以，G1’是LL(1)文法。CH.4.练习题1(P81.)(2)构造G1’的预测分析表:①对S→a|^|(T)②对T→ST’

FIRST(a)={a}FIRST(ST’)={a,^,(}FIRST(^)={^}③对T’→,ST’|εFIRST((T))={(}FIRST(,ST’)={,}预测分析表:

FOLLOW(T’)={)}

a^(),#

SS→aS→^S→(T)

TT→ST’T→ST’T→ST’

T’T’→εT’→,ST’2023/2/5CH4.1.(3)给出对符号串(a，^)的分析过程步骤符号栈输入串动作,所用产生式.0#S(a,^)#初始；用S,(查表1#)T((a,^)#S→(T),展开S2#)Ta,^)#匹配(；用T,a查表3#)T’Sa,^)#T→ST’,展开T;用S,a查表4#)T’aa,^)#S→a,展开S5#)T’,^)#匹配a;用T’,,查表6#)T’S,,^)#T’→,ST’,展开T’7#)T’S^)#匹配,；用S,^查表8#)T’^^)#S→^,展开S9#)T’)#匹配^；用T’,)查表10#))#T’→ε,展开T’11##匹配)12##分析成功,结束分析CH.4.练习题3(P82.)3.下面文法中,哪些是LL(1)的,说明理由。(1)

S→ABcA→a|εB→b|ε。解，因为FOLLOW(S)={#}

①文法不含左递归;FIRST(S)={a,b,c}

②对A→a|ε

候选式的FIRST集合互不相交;ε∈

FIRST(A)

但,FOLLOW(A)={b,c}FIRST(A)={a,ε}两者不相交。③B→b|ε其候选式的FIRST集合互不相交;ε∈

FIRST(B)

但，FOLLOW(B)={c}FIRST(B)={b,ε}两者也不相交。

所以，文法是LL(1)文法。CH.4.练习题3(P82.)3.下面文法中,哪些是LL(1)的,说明理由。(2)

S→AbA→a|B|εB→b|ε。解(1)

因为FOLLOW(S)={#}

对A→a|B|ε

;FIRST(S)={a,b}

FIRST(B)={b,ε}与FIRST(ε)={ε}相交;所以文法不是LL(1)文法。解(2)对A→a|ε因为ε∈FIRST(A)={a,b,ε}，FOLLOW(A)={b},FOLLOW和FIRST两者相交。所以文法不是LL(1)文法。CH.4.练习题3(P82.)3.下面文法中,哪些是LL(1)的,说明理由。(3)

S→ABBAA→a|εB→b|ε。解，虽然FOLLOW(S)={#}

①文法不含左递归;FIRST(S)={a,b,ε}

②对A→a|ε，其候选式的FIRST集合不相交;对B→b|ε，其候选式的FIRST集合也不相交;但对A→a|ε（由B→b|ε出发证明也可）FOLLOW(A)={a,b,#},FIRST(A)={a,ε}

两者相交。所以，文法不是LL(1)文法。CH.4.练习题3(P82.)3.下面文法中,哪些是LL(1)的,说明理由。(4)

S→aSe|B

B→bBe|C

C→cCe|d。解，

因为

①文法不含左递归;②对S→aSe|B、B→bBe|C

和C→cCe|d

各产生式的候选式的FIRST集合均不相交;即

FIRST(aSe)∩FIRST(B)=

；

FIRST(bBe)∩FIRST(C)=

；

FIRST(cCe)∩FIRST(d)=

；

③FIRST(S)={a,b,c,d}，FIRST(B)={b,c,d}FIRST(C)={c,d}均不含ε。所以，文法是LL(1)文法。编译原理参考答案程序设计语言

Chapter5.自下而上语法分析2023/2/5CH.5.练习题1(P133.)1.令文法G1为：E→E+T|TT→T*F|FF→(E)|i

证明E+T*F是它的一个句型,指出这个句型的所有短语、直接短语和句柄。证明1:∵存在从开始符号E出发到E+T*F的推导：EE+TE+T*F∴E+T*F是G1的一个句型。短语:E+T*F是句型相对于非终结符E的短语;T*F是句型相对于非终结符T的短语。直接短语:T*F是句型相对于规则T→T*F的直接短语句柄:T*FEE+TT*F语法树2023/2/5CH.5.练习题1(P133.)1.令文法G1为：E→E+T|TT→T*F|FF→(E)|i

证明E+T*F是它的一个句型,指出这个句型的所有短语、直接短语和句柄。证明2:∵可构造出E+T*F的语法树，如右图所示，∴E+T*F是G1的一个句型。证明3:(也可用归约来证明)（概念熟悉后，短语、直接短语和句柄可直接列出而不用说明）短语:E+T*F，T*F直接短语:T*F句柄:T*FEE+TT*F语法树2023/2/5CH.5.练习题2(P133.)2.考虑下面的表格结构文法G2：S→a||(T)T→T,S|S

(1)给出(a,(a,a))的最左和最右推导。(1)解:(a,(a,a))的最左推导：S(T)

(T,S)(S,S)

(a,S)(a,(T))

(a,(T,S))

(a,(S,S))

(a,(a,S))(a,(a,a))

最右推导：S(T)

(T,S)(T,(T))

(T,(T,S))(T,(T,a))(T,(S,a))(T,(a,a))

(S,(a,a))(a,(a,a))

2023/2/5CH.5.练习题2(P133.)2.(2)指出(a,(a,a))的规范归约及每一步的句柄。根据这个规范归约，给出“移进-归约”的过程，并给出它的语法树自下而上的构造过程。(2)解:(a,(a,a))的规范归约及每一步的句柄:

(a,(a,a))(S,(a,a))(T,(a,a))(T,(S,a))(T,(T,a))(T,(T,S))(T,(T))

(T,S)(T)

S.........2023/2/5CH.5.练习题2(P133.)2.(2).给出(a,(a,a))“移进-归约”的过程。(2)解:(a,(a,a))的“移进-归约”过程:步骤符号栈输入串动作句柄1#

(a,(a,a))#a2#(a,(a,a))#移进(3#(a

,(a,a))#移进a4#(S,(a,a))#归约S→aS5#(T,(a,a))#归约T→Sa6#(T,(a,a))#移进,7#(T,(a,a))#

移进(8#(T,(a

,a))#移进a2023/2/5CH.5.练习题2(P133.)2.(2).给出(a,(a,a))“移进-归约”的过程。(2)解:(a,(a,a))的“移进-归约”过程:步骤符号栈输入串动作句柄9#(T,(S

,a))#归约S→aS10#(T,(T,a))#归约T→Sa

11#(T,(T,a))#移进,12#(T,(T,a))#

移进a13#(T,(T,S))#归约S→aT,S14#(T,(T

))#归约T→T,S(T)15#(T,(T))#

移进)16#(T,S

)#归约S→(T)T,S2023/2/5CH.5.练习题2(P133.)2.(2).给出(a,(a,a))“移进-归约”的过程。(2)解:(a,(a,a))的“移进-归约”过程:步骤符号栈输入串动作句柄

17#(T

)#归约T→T,S(T)18#(T)#

移进)19#S#归约S→(T)20成功,分析结束,接受输入串2023/2/5CH.5.练习题2(P133.)2.(2).给出(a,(a,a))的语法树自下而上构造过程。(2)解:

(a,(a,a))的语法树自下而上构造过程:用序号表示S(T)T,S①(T)T,SSaSaa②③④⑤⑥⑦⑧⑨2023/2/5CH.5.练习题3(P133.)3.(1)计算练习2文法G2的FIRSTVT和LASTVT。S→a||(T)T→T,S|S(1)解:（执行相应的算法可求得）

FIRSTVT(S)={a,∧,(}FIRSTVT(T)={,

a,∧,(}LASTVT(S)={a,∧,)}LASTVT(T)={,,a,∧,)},2023/2/5CH.5.练习题3(P133.)3.(2)计算文法G2的优先关系,G2是一个算符优先文法吗?S→a||(T)T→T,S|S(2)解:

FIRSTVT(S)={a,∧,(}FIRSTVT(T)={,,a,∧,(}LASTVT(S)={a,∧,)}LASTVT(T)={,,a,∧,)}逐一考察S→(T)

和T→T,S

两两相邻的符号，得到算符优先关系,如右图；G2是算符优先文法。

a∧(),#

a>>>∧

>>>(<<<=<)>>>,<<<>>#<<<=.......................2023/2/53.(4)给出输入串(a,(a,a))的算符优先分析过程。S→a||(T)T→T,S|S序号符号栈输入串优先关系下一步的动作0#(a,(a,a))##<(移进(1#(

a,(a,a))#(<a移进a2#(a,(a,a))#(<aa>,归约S→a3#(S,(a,a))#(<,移进,4#(S,(a,a))#,<(移进(5#(S,(

a,a))#(<a移进a6#(S,(a,a))#(<aa>,归约S→a7#(S,(S,a))#(<,移进,8#(S,(S,

a))#,<a移进a

a∧(),#

a>>>∧

>>>(<<<=<)>>>,<<<>>#<<<=最左素短语..................................2023/2/5序号符号栈输入串优先关系下一步的动作9#(S,(S,a))#,<(a>)归约S→a10#(S,(S,S

))#(<,,>)归约T→S,S11#(S,(T))#(=)移进)12#(S,(T)

)#,<()>)归约S→(T)13#(S,S

)#(<,,>)归约T→S,S14#(T

)#(=)移进)15#(T)

#*<()>#归约S→(T)16#S

##=#接受17#S

#停.............3.(4)给出输入串(a,(a,a))的算符优先分析过程。S→a||(T)T→T,S|S

a∧(),#

a>>>∧

>>>(<<<=<)>>>,<<<>>#<<<=最左素短语.......................2023/2/55.(1)考虑文法S→AS|bA→SA|a

列出这个文法的所有LR(0)项目。CH.5.练习题5(P134.)解(1):拓广文法，加入S’→S

拓广文法的LR(0)项目有:

S’→.SS’→S.

S→.ASS→A.SS→AS.S→.bS→b.A→.SAA→S.AA→SA.A→.aA→a.2023/2/55.(2)构造文法S→AS|bA→SA|a的LR(0)项目集规范族及识别活前缀的DFA。1）拓广文法，加入S’→S2）画出DFA2023/2/55.(2)构造文法S→AS|bA→SA|a的LR(0)项目集规范族及识别活前缀的DFA。0:S’→.S

S→.ASS→.bA→.SAA→.a5:A→SA.S→A.SS→.ASS→.bA→.SAA→.a 7:S→AS.A→S.AA→.SAA→.aS→.ASS→.b 1:S’→S.A→S.AA→.SAA→.aS→.ASS→.b 3:S→b.4:A→a.2:S→A.S

S→.ASS→.bA→.SAA→.a6:A→S.A

A→.SAA→.aS→.ASS→.bSbaAASbaASabSabASAbaSabA2023/2/55.(3)

文法S→AS|bA→SA|a

是LR(0)文法吗？0:S’→.S

S→.ASS→.bA→.SAA→.a5:A→SA.S→A.SS→.ASS→.bA→.SAA→.a 7:S→AS.A→S.AA→.SAA→.aS→.ASS→.b 1:S’→S.A→S.AA→.SAA→.aS→.ASS→.b 3:S→b.4:A→a.2:S→A.S

S→.ASS→.bA→.SAA→.a6:A→S.A

A→.SAA→.aS→.ASS→.bSbaAASbaASabSabASAbaSabA不是LR(0)文法！因为存在冲突，例如状态1、状态52023/2/5编译原理参考答案程序设计语言

Chapter7.语义分析和中间代码产生2023/2/5P217-1a*（-b+c）后缀式：ab-c+*a+b*（c+d/e）后缀式：abcde/+*+-a+b*（-c+d）后缀式：a-bc-d+*+notAornot（CornotD）后缀式：AnotCDnotornotor（AandB）or（notCorD）后缀式：ABandCnotDoror2023/2/5P217-3-（a+b）*（c+d）-（a+b+c）

的四元式序列：（1）(+，a，b，T1)（2）(-，T1，-，T2)（3）(+，c，d，T3)（4）(*，T2，T3，T4)（5）(+，a，b，T5)（6）(+，T5，c，T6)（7）(-，T4，T6，T7)2023/2/5P218-4自下而上分析过程中把赋值语句A:=B*（-C+D）翻译成三地址码的步骤：

（参看p179的语义子程序）2023/2/5语法分析 翻译过程：A:=B*(-C+D)A:=E1*(-C+D) E1.place=k2A:=E1*(-E2+D) E2.place=k3A:=E1*(E3+D)A:=E1*(E3+E4)A:=E1*(E5)A:=E1*E6A:=E7

S........产生一个新的中间变量T1E3.place=k5产生代码

k5:=uminusk3……名字属性地址ABCDT1T2T3……k1K2k3k4k5k6k7符号表2023/2/5A:=B*(-C+D)的三地址码k5:=uminusk3k6:=k5+k4k7:=k2*k6k1:=k7名字属性地址ABCDT1T2T3……k1K2k3k4k5k6k7符号表（参看p179的语义子程序）2023/2/5P218-6：用7.4.2节的办法，把Aor（Bandnot（CorD））翻译成四元式序列100：（jnz，A，-，0）101：（j，-，-，102）102：（jnz，B，-，104）103：（j，-，-，0）104：（jnz，C，-，.）105：（j，-，-，106）106：（jnz，D，-，.）107：（j，-，-，.）TCFC2023/2/5P218-7100：（j<，A，C，102）101：（j，-，-，115）102：（j<，B，D，104）103：（j，-，-，115）104：（j=，A，‘1’，106）105：（j，-，-，109）106：（+，C，‘1’，T1）107：（:=，T1，-，C）108：（j，-，-，100）109：（j≤，A，D，111）110：（j，-，-，100）111：（+，A，‘2’，T2）112：（:=，T2，-，A）113：（j，-，-，109）114：（j，-，-，100）115：用7.5.1节的办法，把下面的语句翻译成四元式序列：whileA<CandB<DdoifA=1thenC:=C+1elsewhileA≤DdoA:=A+2;2023/2/5编译原理参考答案程序设计语言

Chapter8.–Chapter11.2023/2/