编译原理作业参考答案.doc_第1页
编译原理作业参考答案.doc_第2页
编译原理作业参考答案.doc_第3页
编译原理作业参考答案.doc_第4页
编译原理作业参考答案.doc_第5页
已阅读5页,还剩14页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

编译原理 作业参考答案第1章 引 言1、解释下列各词源语言:编写源程序的语言(基本符号,关键字),各种程序设计语言都可以作为源语言。源程序: 用接近自然语言(数学语言)的源语言(基本符号,关键字)编写的程序,它是翻译程序处理的对象。目标程序: 目标程序是源程序经过翻译程序加工最后得到的程序。目标程序(结果程序)一般可由计算机直接执行。低级语言:机器语言和汇编语言。高级语言:是人们根据描述实际问题的需要而设计的一个记号系统。如同自然语言(接近数学语言和工程语言)一样,语言的基本单位是语句,由符号组和一组用来组织它们成为有确定意义的组合规则。翻译程序: 能够把某一种语言程序(源语言程序)改变成另一种语言程序(目标语言程序),后者与前者在逻辑上是等价的。其中包括:编译程序,解释程序,汇编程序。编译程序: 把输入的源程序翻译成等价的目标程序(汇编语言或机器语言),然后再执行目标程序(先编译后执行),执行翻译工作的程序称为编译程序。解释程序: 以该语言写的源程序作为输入,但不产生目标程序。按源程序中语句动态顺序逐句的边解释边执行的过程,完成翻译工作的程序称为解释程序。2、什么叫“遍”?指对源程序或源程序的中间形式(如单词,中间代码)从头到尾扫描一次,并作相应的加工处理,称为一遍。3、简述编译程序的基本过程的任务。编译程序的工作是指从输入源程序开始到输出目标程序为止的整个过程,整个过程可以划分5个阶段。词法分析:输入源程序,进行词法分析,输出单词符号。语法分析:在词法分析的基础上,根据语言的语法规则把单词符号串分解成各类语法单位,并判断输入串是否构成语法正确的“程序”。中间代码生成:按照语义规则把语法分析器归约(或推导)出的语法单位翻译成一定形式的中间代码。优化:对中间代码进行优化处理。目标代码生成:把中间代码翻译成目标语言程序。4、编译程序与解释程序的区别?编译程序生成目标程序后,再执行目标程序;然而解释程序不生成目标程序,边解释边执行。5、有人认为编译程序的五个组成部分缺一不可,这种看法正确吗?编译程序的5个阶段中,词法分析,语法分析,语义分析和代码生成生成是必须完成的。而中间代码生成和代码优化并不是必不可少的。优化的目的是为了提高目标程序的质量,没有这一部分工作,仍然能够得到目标代码。6、编译程序的分类 目前基本分为:诊断编译程序,优化编译程序,交叉编译程序,可变目标编译程序。 第2章 高级语言及其语法描述1(P36)令文法为N DNDD 0129 (1)文法描述的语言L(G)是什么?(2)给出句子34,568的最左推导和最右推导。答:(1) L(G)=aa为可带前导0的正整数或L(G)=(0129)+ 或 L(G)=aa为数字串(2)最左推导:NNDDD3D34NNDNDDDDD5DD56D568最右推导:NNDN4D434NNDN8ND8N68D685682*写出一个文法,使其语言是奇数集,且每个奇数是不以0开头。答:S CAB|B (考虑了正负号)A 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | AA | A0 | eB 1|3|5|7|9C +|-|e或:(未考虑正负号)S B | ABB 1 | 3 | 5 | 7 | 9A AD | NN 2 | 4 | 6 | 8 | BD 0 | N或:(未考虑正负号)S C | ABCC 1 | 3 | 5 | 7 | 9A 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9B BA | B0 |e2.(P36, 8)令文法为 E TE+TE-TT FT*FT/FF (E)i(1)给出该文法的VN、VT和S。 (2)给出i+i*i,i*(i+i)的最左推导和最右推导。(3)给出i+i+i,i+i*i的语法树。答:(1)VN = E, T, F VT = +, -, *, /, (, ), i S = E(2)最左推导EE+TT+TF+Ti+Ti+T*Fi+F*Fi+i*Fi+i*iETT*FF*Fi*Fi*(E)i*(E+T)i*(T+T)i*(F+T)i*(i+T)i*(i+F)i*(i+i)最右推导EE+TE+T*FE+T*iE+F*iE+i*iT+i*iF+i*ii+i*iETT*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) 构造语法树 E 最左推导构造语法树 E + T E + T i T i i3.(P36, 9)证明下面的文法是二义的:S iSeS | iS i答:对于句子iiiei有两棵不同的语法树。因此该文法是二义的。 S iSeS iiSeS iiieS iiiei S iS iiSeS iiieS iiiei第3章 词法分析1设M=(x,y,a,b,d,x,y)为一个非确定有限自动机NFA M,其中d定义如下:d(x,a)=x,y d(x,b)=yd(y,a)=f d(y,b)=x,y试构造其相应的最小化的确定有限自动机DFA M。答:由d定义可知d(x,a),d(y,b)均为多值函数,所以是一个非确定有限自动机。(1)根据d函数值,先构造NFA M(2)确定化: 构造DFA M的转换矩阵:IIaIbx x,y y x,y x,y x,y y x,y 确定DFA M的初始状态和终态:(a)转换矩阵中I列的第一个状态为DFA M的初始状态结点。(b)含有y状态的子集均为DFA M的终态结点(、为终态结点)。 根据DFA M的转换矩阵画出对应的状态转换图:(3)最小化: 首先将其划分成终态集2,3和非终态集1 2,3a=2 2,3, 2,3b=2 2,3因此2,3已是不可再区分的,所以该DFA M已是最小化的。2. (P64,7(1))构造正规式1(01)*101相应的DFA M。答:(1)构造NFA M。XY 1(01)*101 X3514Y 1 (01)* 1 0 1 X321542Y 1 e e 1 0 1 01 X12345Y 0 1 e e 1 0 1 1 (2)构造转换矩阵II0I1X 1, 2, 3 1, 2, 3 2, 3 2, 3, 4 2, 3 2, 3 2, 3, 4 2, 3, 4 2, 3, 5 2, 3, 4 2, 3, 5 2, 3 2, 3, 4, Y 2, 3, 4, Y 2, 3, 5 2, 3, 4 (3)由转换矩阵构造DFA M3(P64,12(a))将下图所示的NFA M转换为等价的DFA M,并将该DFA最小化。答:该有限自动机状态0输入同一字符a时到达两个不同的结点,所以是NFA。(1)构造转换矩阵IIaIb0 0,1 1 0,1 0,1 1 1 0 (2)由转换矩阵构造DFA M123 a a b a b(3)将DFA M最小化 将DFA M的状态划分为非终态集3和终态集1,2 对每一个子集及每一个aS进行考察;1,2a = 2 1,21,2b = 3 3因此1,2是不可区分的,所以最终状态为: 1,2,3构造最小化的DFA M:12,3 a b a 4. (P64,12(b)将下图所示的NFA M转换为等价的DFA M,并进行最小化。答:从图上可知该图已经是DFA M,先只需将其最小化。首先划分为两个集合:0,1和2,3,4,52,3,4,5a = 1,3,0,5,划分为:2,4和3,52,4a = 1,0,2,4b = 3,5,无需划分3,5a = 3,5,3,5b = 2,4,无需划分0,1a = 1,0,1b = 2,4,无需划分 因此,最终的划分为:0,1、2,4和3,5,化简后的结果:5(P65,14)构造一个DFA M,它接受=0,1上所有满足如下条件的字符串:每个1都有0直接跟在右边。答:(1)根据题意,得到正规式:(0|10)*(2)构造对应的NFA M:(3)将NFA M确定化为DFA M。相应的DFA M的状态转换矩阵如下:II0I1X, 1,Y 1; Y 2 1, Y 1; Y 2 2 1; Y DFA M 转换图:(4)将DFA M最小化: 将DFA M的状态划分为非终态集3和终态集1, 2 对每一个子集进行考察;1, 20 = 2 1, 21, 21 = 3,3 3因此0, 1是不可划分的。因此最终划分结果为:1, 2和3最小化后的DFA M:第4章 语法分析-自上而下1.(P81,1)考虑下面文法GS a(T) TT,SS(1)消除文法的左递归。(2)经改写后的文法是否是LL(1)的?给出它的预测分析表。答:(1) 消除左递归:S a(T)T STT ,ST| e(2) 证明改写后的文法是否是LL(1)的。FIRST(S) = a, , ( FOLLOW(S) = ,, ), # FIRST(T) = a, , ( FOLLOW(T) = ) FIRST(T) = , , e FOLLOW(T) = ) 证明S a(T)各侯选式的FIRST是否两两相交。 FIRST(a) FIRST()= fFIRST(a) FIRST()= fFIRST() FIRST()= f 证明T,STe的FIRST(T)和FOLLOW(T)是否相交。FIRST(T) FOLLOW(T)=,e ) = f该文法是LL(1)的。所以,改造后的文法是LL(1)文法 预测分析表:a(),#S Sa S S(T) T TST TSTTST T TeT,ST 2.利用P76表4.1的LL(1)分析表写出表达式 (i+i)*i 的预测分析过程。 步骤 符号栈 输入串 所用的产生式 0 #E (i+i)*i# 1 #ET (i+i)*i# ETE 2 #ETF (i+i)*i# TFT 3 #ET)E( (i+i)*i# F(E) 4 #ET)E i+i)*i# 5 #ET)ET i+i)*i# ETE 6 #ET)ETF i+i)*i# TFT 7 #ET)ETi i+i)*i# Fi 8 #ET)ET +i)*i# 9 #ET)E +i)*i# Te 10 #ET)ET+ +i)*i# E+TE 11 #ET)ET i)*i# 12 #ET)ETF i)*i# TFT 13 #ET)ETi i)*i# Fi 14 #ET)ET )*i# 15 #ET)E )*i# Te 16 #ET) )*i# Ee 18 #ET *i# 19 #ETF* *i# T*FT 20 #ETF i# 21 #ETi i# Fi 22 #ET # 23 #E # Te 24 # # Ee3. (P81,2)对下面的文法GE TE E +Ee T FTT TeF PF F *FeP (E)ab(1)计算这个文法的每个非终结符的FIRST和FOLLOW。(2)证明这个文法是LL(1)的。(3)构造它的预测分析表。答:(1)计算每个非终结符的FIRST和FOLLOW。FIRST(E)=(, a, b, FIRST(E)= +, e FIRST(T)=(, a, b, FIRST(T)=(, a, b, , e FIRST(F)=(, a, b, FIRST(F)= * , e FIRST(P)=(, a, b, FOLLOW(E)= ) ,# FOLLOW(E)= ), # FOLLOW(T)= +, ), # FOLLOW(T)= +, ), # FOLLOW(F)= +,(, a, b, , ), # FOLLOW(F)= +,(, a, b, , ), # FOLLOW(P)= *,+,(, a, b, , ), # (求解过程:因为E+Ee,所以FIRST(E)=+, e因为F*Fe,所以FIRST(F)=*, e因为P(E)ab,所以FIRST(P)=(, , a, b 因为FPF,所以FIRST(F)= FIRST(P)因为TFT,所以FIRST(T)=FIRST(F)因为E TE,所以FIRST(E)= FIRST(T)因为TTe,所以FIRST(T)= FIRST(T) e =(, , a, b ,e求非终结符的FOLLOW:因为E TE的E是文法的开始符号,FOLLOW(E)=#,又因为P(E),所以FOLLOW(E)=#FIRST()e=#,)因为E TE,所以FOLLOW(E)=FOLLOW(E)因为E TE,并且Ee,所以FOLLOW(T)=FIRST(E)e,又因为Ee,所以FOLLOW(T)=+ FOLLOW(E)=+ #,=+,#,) .因为TFT,所以FOLLOW(T)=FOLLOW(T)=+,#,) .因为T FT,并且Te,所以FOLLOW(F)=FIRST(T)e,又因为Te,所以FOLLOW(F)=(,a,b FOLLOW(T)=(,a,b +,#,) =(,a,b ,+,#,) 因为FPF,所以FOLLOW(F)=FOLLOW(F)=(,a,b ,+,#,) .因为FPF,并且Fe,所以FOLLOW(P)=FIRST(F)e,又因为Fe,所以FOLLOW(P)=* FOLLOW(F)=*(,a,b,+,),# =*,(,a,b ,+,),# )(2)证明这个文法是LL(1)的该文法没有左递归,只需考察:E +EeT TeF *Fe P (E)ab由于:E +Ee:FIRST(E)=+, e FOLLOW(E)=#, =T Te: FIRST(T)=(, a, b, ,e FOLLOW(T)=+, ),# =F * Fe:FIRST(F)=*, e FOLLOW(F)=+,(, a, b,),# =P (E)ab:候选式终结符首字符集两两不相交所以该文法为LL(1)文法。(3)LL(1)分析表+*()ab#E E TEE TEE TEE TEE E+E EeEeTT FTT FTT FTT FTT Te TTTeTTTTTTTeFF PFF PFF PFF PFFFeF*FFeFeFeFeFeFePP(E)PaPbP第5章 语法分析-自上而下分析1(P133,1)令文法G1为:EE+T|T TT*F|F F(E)|i证明E+T*F是它的一个句型,指出这个句型的所有短语,直接短语和句柄。答:因为有:E E+T E+T*F, 所以E+T*F是文法的一个句型。短语:E+T*F, T*F直接短语:T*F句柄:T*F2. (P133,3)考虑文法G2S a | (T)T T;S S(1) 计算文法G2每个非终结符的FIRSTVT和LASTVT。(2) 构造文法G2的优先关系表,该文法是算符优先文法吗?(3) 给出输入串(a;(a;a)的算符优先分析过程。解:(1) FIRSTVT和LASTVTFIRSTVT(S) = a, , ( FIRSTVT(T) = ;,a, ,( LASTVT(S) = a, , ) LASTVG(T) = ;,a, , ) (2) 优先关系表a();#a();#是算符优先分析文法,因为优先关系表中没有冲突的关系。(3)(a,(a,a)的分析过程步骤栈余留符号串栈顶关系下一步动作0#(a;(a;a)#.(进栈1#(A;(a;a) #(;用S a归约3#(S;(a;a) #(.;;进栈4#(S;(a;a) #;.(进栈5#(S;(a;a) #(;用S a归约7#(S;(S;a) #(.;;进栈8#(S;(S;a) #;)用S a归约10#(S;(S;S) #; .)用T T;S归约11#(S;(T) #( )进栈12#(S;(T)#) .)用S (T)归约13#(S;S)#; .)用T T;S归约14#(T)#( )进栈15#(T)#) . #用S (T)归约16#S# #结束3. (P134,5)考虑文法SASb ASAa (1)构造这个文法的LR(0)项目规范族及识别活前缀的DFA。(2)这个文法是SLR(1)的吗?若是,构造出它的SLR分析表。 解:构造拓广文法: (0) SS(1) SAS(2) Sb(3) ASA(4) Aa(1)构造这个文法的LR(0)项目规范族及识别活前缀的DFA。(2)证明文法是否是SLR(1)文法?为了验证这个文法是否是SLR(1)文法,必须对LR(0)项目集规范族的各个项目集I,验证其是否存在“移进归约”、“归约归约”冲突。该项目规范族中的I1,I5,I7存在“移进归约”,只需证明存在集合的a,b,FOLLOW(S),FOLLOW(S),FOLLOW(A)两两不相交。对此求出FOLLOW(S),FOLLOW(S)#,a,b,FOLLOW(A)a,b。验证如下:对状态I1有FOLLOW(S) = ;Aa;Sb。因此FOLLOW(S) a,b = a,b = f,所以不存在“移进归约”冲突。对状态I5有FOLLOW(A) = a,b;Aa;Sb。 因此FOLLOW(A) a,b = a,b a,b f,所以存在“移进归约”冲突。对状态I7也同样存在这种冲突,即:FOLLOW(S) a,b = ,a,b a,b f因此,该文法不是SLR(1)文法。4(P135 7)证明下面文法是SLR(1)文法,但不是LR(0)文法.SA AAb|bBa BaAc|a|aAb证明:该文法的项目集规范族有:I0 = SA,AAb,AbBa I1 = GO(I0,A) = SA,AAb I2 = GO(I0,b) = AbBa,BaAc,Ba,BaAb I3 = GO(I1,b) = AAb I4 = GO(I2,B) = AbBa I5 = GO(I2,a) = BaAc,Ba,BaAb,AAb,AbBa I6 = GO(I4,a) = AbBa I7 = GO(I5,A) = BaAc,BaAb,AAb I8 = GO(I5,b) = I2I9 = GO(I7,b) = BaAb,AAb 因为项目集I9中有AAb和BaAb ,存在“归约-归约”冲突,所以不是LR(0)文法。又因为FOLLOW(A) = b,c,# ,FOLLOW(B) = a 使得FOLLOW(A) FOLLOW(B) =,因此构造SLR(1)分析表时不会出现冲突,所以该文法是SLR(1)的。5有文法:0S E1E aA 2E bB 3A cA 4A d5B cB 6B d根据下列给出的该文法的LR(0)分析表,写出分析符号串“accd”的分析过程。状态 ACTIONGOTOa b c d # E A B 0 S2 S3 1 1 acc 2 S6 S5 4 3 S8 S9 7 4 r1 r1 r1 r1 r1 5 r4 r4 r4 r4 r4 6 S6 S5 10 7 r2 r2 r2 r2 r2 8 S8 S9 11 9 r6 r6 r6 r6 r6 10 r3 r3 r3 r3 r3 11 r5 r5 r5 r5 r5 答:步骤状态栈符号栈输入串动作00#accd#S2,移进102#accd#S6,移进2026#accd#S6,移进30266#accd#S5,移进402665#accd#用r4(Ad)归约5026610#accA#用r3(AcA)归约602610#acA#用r3(AcA)归约7024#aA#用r1(EaA)归约801#E#acc第6章 语义分析和中间代码生成1根据给出的语义规则,写出下列布尔表达式的翻译过程(假设第1条四元式地址为100)及最终产生的四元式序列:A10 or(B and not(C or D)解: 语法树:翻译过程:(1)E1id1 relop id2 (A10)E1.truelist:=makelist(nextquad)=100 E1.falselist:=makelist(nextquad+1)=101 100(j, A, 10, 0 ) 101(j, _, _, 0)(j, _, _,102) 步骤13回填结果(2) M1 : M1.quad:=102(3) E4id (B) E4.truelist:=makelist(nextquad)=102 E4.falselist:=makelist(nextquad+1)=103 102(jnz, B , _, 0) (jnz, B , _,104) 步骤11回填结果 103(j, _, _, 0) (4) M2 : M2.quad:=104(5) E8id (C) E8.truelist:=makelist(nextquad)=104 E8.falselist:=makelist(nextquad+1)=105 104(jnz, C , _, 0) 105(j, _, _, 0) (j, _, _, 106) 步骤8回填结果(6) M3 : M3.quad:=106(7) E9id (D) E9.truelist:=makelist(nextquad)=106 E9.falselist:=makelist(nextquad+1)=107 106(jnz, D , _, 0) (jnz,D , _,104)步骤8的拉链 (jnz,D , _,103)步骤11的拉链 107(j, _, _, 0) (j, _, _,100 ) 步骤13的拉链(8) E7E8 or M3 E9 backpatch (E8.falselist, M3.quad )=(105,106) E7.truelist := merge(E8.truelist, E9.truelist) =merge(104,106)=106 E7.falselist := E9.falselist= 107(9) E6(E7) E6.truelist := E7.truelist=106 E6.falselist := E7.falselist = 107(10) E5not E6E5.truelist := E6.falselist = 107E5.falselist := E6.truelist = 106(11) E3E4 and M2 E5backpatch(E4.truelist, M2.quad )=(102, 104) E3.falselist:= merge(E4.falselist, E5.falselist) = merge(103,106)=106 E3.truelist := E5.truelist = 107(12) E2(E3)E2.truelist := E3.truelist=107 E2.falselist := E3.falselist=106(13)E E1 or M1 E2backpatch (E1.falselist, M1.quad )=(101,102) E.truelist := merge(E1.truelist, E2.truelist) = merge(100,107) = 107 E.falselist := E2.falselist=106最终结果:A10 or(B and not(C or D)100(j, A, 10, 0 )101(j, _, _,102) 无条件转102(jnz, B , _,104) 条件转103(j, _, _, 0)104(jnz, C , _, 0)105(j, _, _, 106) 无条件转106(jnz,D , _,103)106和103是一条链107(j, _, _,100) 107和100是一条链2. 根据给出的语义规则,把下面的语句翻译成四元式序列(设第1条四元式地址为100):While ac and bd do if a=1 then c:=c*2 else a:=a+x ; 解: 语法树:(1)M1e M1.quad:=nextquad=100(2)E1E1 reLop E2 (ac) E1.trulist:=makelist(nextquad)=100 E1.falelist:=makelist(nextquad+1)=101 100(j, a, c, 0) (j, a, c, 102),步骤(5)回填 101(j , _ , _ , 0)(3)M3e M2.quad:=nextquad=102(4)E2E1 reLop E2 (bd) E2.trulist:=makelist(nextquad)=102 E2.falelist:=makelist(nextquad+1)=103 102(j, b, d, 0) (j, b, d, 104),步骤18回填 103(j , _ , _ , 0) ( j , _ , _ , 101),步骤(5)拉链(5)E E1 and M3 E2backpatch ( E1. truelist, M3.quad)=backpatch(100, 102) ,用102回填100 E.truelist := E2.truelist=102 E.falselist :=merge( E1.falselist, E2.falselist )=merge(101, 103)=103,103指向101(6)M2e M2.quad:=nextquad=104(7)E3E1 reLop E2 (a=1) E3.trulist:=makelist(nextquad)=104 E3.falelist:=makelist(nextquad+1)=105 104(j=, a, 1, 0) (j=, a, 1,106),步骤17回填 105(j , _ , _ , 0) (j , _ , _ ,109) ,步骤17回填(8)M4e M4.quad:=nextquad=106(9)E4E1 * E2 (c*2) E4.place:=newtemp=T1 106(*,c, 2, T1)(10)A1id:=E (c=c*2) 107(:=, T1, _, c)(11)S2A1 S2.nextlist :=makelist( )=NULL(12)N1e N1.nextlist:=makelist(nextquad)=108108(j,_ , _,0) (j,_ , _,100),步骤18回填(13)M5e M5.quad:=nextquad=109(14)E5E1 + E2(a+x) E5.place:=new

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论