编译原理作业参考答案

第1章引言1、解释下列各词源语言:编写源程序的语言（基本符号，关键字），各种程序设计语言都可以作为源语言。源程序:用接近自然语言（数学语言）的源语言（基本符号，关键字）编写的程序，它是翻译程序处理的对象。目标程序:目标程序是源程序经过翻译程序加工最后得到的程序。目标程序（结果程序）一般可由计算机直接执行。低级语言：机器语言和汇编语言。高级语言：是人们根据描述实际问题的需要而设计的一个记号系统。如同自然语言（接近数学语言和工程语言）一样，语言的基本单位是语句，由符号组和一组用来组织它们成为有确定意义的组合规则。翻译程序:能够把某一种语言程序（源语言程序）改变成另一种语言程序（目标语言程序），后者与前者在逻辑上是等价的。其中包括：编译程序，解释程序，汇编程序。编译程序:把输入的源程序翻译成等价的目标程序（汇编语言或机器语言），然后再执行目标程序（先编译后执行），执行翻译工作的程序称为编译程序。解释程序:以该语言写的源程序作为输入，但不产生目标程序。按源程序中语句动态顺序逐句的边解释边执行的过程，完成翻译工作的程序称为解释程序。2、什么叫“遍”？指对源程序或源程序的中间形式（如单词，中间代码）从头到尾扫描一次，并作相应的加工处理，称为一遍。3、简述编译程序的基本过程的任务。编译程序的工作是指从输入源程序开始到输出目标程序为止的整个过程，整个过程可以划分5个阶段。词法分析：输入源程序，进行词法分析，输出单词符号。语法分析：在词法分析的基础上，根据语言的语法规则把单词符号串分解成各类语法单位，并判断输入串是否构成语法正确的“程序”。中间代码生成：按照语义规则把语法分析器归约（或推导）出的语法单位翻译成一定形式的中间代码。优化：对中间代码进行优化处理。目标代码生成：把中间代码翻译成目标语言程序。4、编译程序与解释程序的区别？编译程序生成目标程序后，再执行目标程序；然而解释程序不生成目标程序，边解释边执行。5、有人认为编译程序的五个组成部分缺一不可，这种看法正确吗？编译程序的5个阶段中，词法分析，语法分析，语义分析和代码生成生成是必须完成的。而中间代码生成和代码优化并不是必不可少的。优化的目的是为了提高目标程序的质量，没有这一部分工作，仍然能够得到目标代码。6、编译程序的分类目前基本分为：诊断编译程序，优化编译程序，交叉编译程序，可变目标编译程序。第2章高级语言及其语法描述1（P36）令文法为NDNDD0129（1）文法描述的语言L（G）是什么？（2）给出句子34，568的最左推导和最右推导。答：（1）L（G）={为可带前导0的正整数}或L（G）={（0129）+}或L（G）={为数字串}（2）最左推导：NNDDD3D34NNDNDDDDD5DD56D568最右推导：NNDN4D434NNDN8ND8N68D685682*．写出一个文法，使其语言是奇数集，且每个奇数是不以0开头。答： SCAB|B（考虑了正负号） A1|2|3|4|5|6|7|8|9|AA|A0| B1|3|5|7|9 C+|-|或：（未考虑正负号） SB|AB B1|3|5|7|9 AAD|N N2|4|6|8|B D0|N或：（未考虑正负号）SC|ABC C1|3|5|7|9 A1|2|3|4|5|6|7|8|9 BBA|B0|2.（P36,8）令文法为ETE+TE-TTFT*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)=2\*GB2⑵构造语法树E最左推导构造语法树E+TE+TiTii3.（P36,9）证明下面的文法是二义的： SiSeS|iSi答：对于句子iiiei有两棵不同的语法树。因此该文法是二义的。SiSeSiiSeSiiieSiiieiSiSiiSeSiiieSiiiei第3章词法分析1．设M=（{x，y}，{a，b}，，x，{y}）为一个非确定有限自动机NFAM，其中定义如下：（x，a）={x，y}（x，b）={y}（y，a）=（y，b）={x，y}试构造其相应的最小化的确定有限自动机DFAM’。答：由定义可知（x，a），（y，b）均为多值函数，所以是一个非确定有限自动机。（1）根据函数值，先构造NFAM（2）确定化：①构造DFAM’的转换矩阵:IIaIb{x}①{x，y}②{y}③{x，y}②{x，y}②{x，y}②{y}③{x，y}②②确定DFAM’的初始状态和终态：（a）转换矩阵中I列的第一个状态①为DFAM’的初始状态结点。（b）含有y状态的子集均为DFAM’的终态结点(②、③为终态结点)。③根据DFAM’的转换矩阵画出对应的状态转换图：（3）最小化：①首先将其划分成终态集{2，3}和非终态集{1}②{2，3}a=｛2｝{2，3}，{2，3}b=｛2｝{2，3}因此{2，3}已是不可再区分的,所以该DFAM’已是最小化的。2.（P64，7(1)）构造正规式1(01)*101相应的DFAM。答：（1）构造NFAM。XY1（01）*XYX3514Y1X3514YX32X321542Y01X1X12345Y11011（2）构造转换矩阵II0I1{X}①{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）由转换矩阵构造DFAM3．（P64，12(a)）将下图所示的NFAM转换为等价的DFAM’，并将该DFA’最小化。答：该有限自动机状态0输入同一字符a时到达两个不同的结点,所以是NFA。（1）构造转换矩阵IIaIb{0}①{0，1}②{1}③{0，1}②{0，1}②{1}③{1}③{0}①（2）由转换矩阵构造DFAM12123abab（3）将DFAM最小化=1\*GB3①将DFAM的状态划分为非终态集{3}和终态集{1，2}=2\*GB3②对每一个子集及每一个a进行考察；{1，2}a={2}{1，2}{1，2}b={3}{3}因此{1，2}是不可区分的，所以最终状态为：{1，2}，{3}构造最小化的DFAM：12，312，3ba4.（P64，12（b））将下图所示的NFAM转换为等价的DFAM’，并进行最小化。答：从图上可知该图已经是DFAM，先只需将其最小化。首先划分为两个集合：{0,1}和{2,3,4,5}{2,3,4,5}a={1,3,0,5}，划分为：{2,4}和｛3,5｝{2,4}a={1,0}，{2,4}b={3,5}，无需划分{3,5}a={3,5}，{3,5}b={2,4}，无需划分{0,1}a={1}，{0,1}b={2,4}，无需划分因此，最终的划分为：{0,1}、{2,4}和｛3,5｝，化简后的结果：5．（P65，14）构造一个DFAM，它接受={0，1}上所有满足如下条件的字符串：每个1都有0直接跟在右边。答：（1）根据题意，得到正规式：(0|10)*（2）构造对应的NFAM：（3）将NFAM确定化为DFAM。相应的DFAM的状态转换矩阵如下：II0I1{X,1,Y}①{1;Y}②{2}③{1,Y}②{1;Y}②{2}③{2}③{1;Y}②DFAM转换图：（4）将DFAM最小化：①将DFAM的状态划分为非终态集{3}和终态集{1,2}②对每一个子集进行考察；{1,2}0={2}{1,2}{1,2}1={3，3}{3}因此{0,1}是不可划分的。因此最终划分结果为：{1,2}和{3}最小化后的DFAM：第4章语法分析-自上而下1.（P81，1）考虑下面文法GSa^(T)TT,SS（1）消除文法的左递归。（2）经改写后的文法是否是LL(1)的？给出它的预测分析表。答：消除左递归：Sa^(T)TST’T’,ST’|证明改写后的文法是否是LL(1)的。FIRST(S)={a,^,(} FOLLOW(S)={，,),#}FIRST(T)={a,^,(} FOLLOW(T)={)}FIRST(T’)={，,} FOLLOW(T’)={)}=1\*GB3①证明Sa^（T）各侯选式的FIRST是否两两相交。FIRST（a）FIRST（^）=FIRST（a）FIRST（（）=FIRST（^）FIRST（（）==2\*GB3②证明T’，ST’的FIRST（T’）和FOLLOW（T’）是否相交。FIRST（T’）FOLLOW（T’）={，，}{}=∴该文法是LL（1）的。所以，改造后的文法是LL(1)文法③预测分析表：a^()，#SSaS^S(T)TTSTTT’ST’ST’T’T’T’,ST’2.利用P76表4.1的LL(1)分析表写出表达式(i+i)*i的预测分析过程。步骤符号栈输入串所用的产生式0#E（i+i）*i#1#E’T（i+i）*i#ETE’2#E’T’F（i+i）*i#TFT’3#E’T’）E（（i+i）*i#F（E）4#E’T’）Ei+i）*i#5#E’T’）E`Ti+i）*i#ETE’6#E’T’）E’T’Fi+i）*i#TFT’7#E’T’）E’T’ii+i）*i#Fi8#E’T’）E’T’+i）*i#9#E’T’）E’+i）*i#T’10#E’T’）E’T++i）*i#E’+TE’11#E’T’）E’Ti）*i#12#E’T’）E’T’Fi）*i#TFT’13#E’T’）E’T’ii）*i#Fi14#E’T’）E’T’）*i#15#E’T’）E’）*i#T’16#E’T’））*i#E’18#E’T’*i#19#E’T’F**i#T’*FT’20#E’T’Fi#21#E’T’ii#Fi22#E’T’#23#E’#T’24##E’3.（P81，2）对下面的文法GETE’E’+ETFT’T’TFPF’F’*F’P(E)^ab（1）计算这个文法的每个非终结符的FIRST和FOLLOW。（2）证明这个文法是LL(1)的。（3）构造它的预测分析表。答：（1）计算每个非终结符的FIRST和FOLLOW。 FIRST(E)={(,a,b,^} FIRST(E’)={+,} FIRST(T)={(,a,b,^} FIRST(T’)={(,a,b,^,} FIRST(F)={(,a,b,^} FIRST(F’)={*,} 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`+E，所以FIRST（E`）={+，}因为F`*F`，所以FIRST（F`）={*，}因为P（E）^ab，所以FIRST（P）={（，^，a，b因为FPF`，所以FIRST（F）=FIRST（P）因为TFT`，所以FIRST（T）={FIRST（F）因为ETE`，所以FIRST（E）=FIRST（T）因为T`T，所以FIRST（T`）=FIRST（T）{}={（，^，a，b，求非终结符的FOLLOW：因为ETE`的E是文法的开始符号，FOLLOW（E）={#}，又因为P（E），所以FOLLOW（E）={#}FIRST（））\{}={#，)}因为ETE`，所以FOLLOW（E`）=FOLLOW（E）因为ETE`，并且E`≠，所以FOLLOW（T）=FIRST（E`）\{},又因为E`,所以FOLLOW（T）={+}FOLLOW（E）={+}{#,}}={+，#,}.因为TFT`，所以FOLLOW（T`）=FOLLOW（T）={+，#,}.因为TFT`，并且T`≠，所以FOLLOW（F）=FIRST（T`）\{},又因为T`,所以FOLLOW（F）={（，^，a，bFOLLOW（T）={（，^，a，b{+，#,}={（，^，a，b,+，#,因为FPF`，所以FOLLOW（F`）=FOLLOW（F）={（，^，a，b,+，#,.因为FPF`，并且F`≠，所以FOLLOW（P）=FIRST（F`）\{},又因为F`,所以FOLLOW（P）={*FOLLOW（F）={*}{（，^，a，b,+,）,#={*,（，^，a，b,+，,#）（2）证明这个文法是LL(1)的该文法没有左递归，只需考察：E’+ET’TF’*F’P(E)^ab由于：E’+E：FIRST(E’)={+,}∩FOLLOW(E’)={#,}}=ФT’T：FIRST(T’)={(,a,b,^,}∩FOLLOW(T’)={+,),#}=ФF’*F’：FIRST(F’)={*,}∩FOLLOW(F’)={+,(,a,b,^,),#}=ФP(E)^ab：候选式终结符首字符集两两不相交所以该文法为LL(1)文法。（3）LL(1)分析表+*()ab^#EETETETETE’E’E’E’E’E’+EE’E’TTFT’TFT’TFT’TFT’T’T’T’TT’T’TT’TT’TT’FFPFFPFFPFFPF’’’’F’F’F’*F’F’F’F’F’F’F’PP(E)PaPbP^第5章语法分析-自上而下分析1．（P133，1）令文法G1为:E→E+T|TT→T*F|FF→(E)|i证明E+T*F是它的一个句型，指出这个句型的所有短语，直接短语和句柄。答：因为有：EE+TE+T*F，所以E+T*F是文法的一个句型。短语：E+T*F,T*F直接短语：T*F句柄：T*F2.（P133，3）考虑文法G2S→a∧|(T)T→T；SS计算文法G2每个非终结符的FIRSTVT和LASTVT。构造文法G2的优先关系表，该文法是算符优先文法吗？给出输入串(a；(a；a))的算符优先分析过程。解：FIRSTVT和LASTVTFIRSTVT(S)={a,∧,(}FIRSTVT(T)={；，a,∧,(}LASTVT(S)={a,∧,)}LASTVG(T)={；，a,∧,)}优先关系表a∧()；#a∧()；#是算符优先分析文法，因为优先关系表中没有冲突的关系。（3）(a,(a,a))的分析过程步骤栈余留符号串栈顶关系下一步动作0#(a；(a；a))##<.((进栈1#(A；(a；a))#(<.aa进栈2#(a；(a；a))#a.>；用S→a归约3#(S；(a；a))#(<.；;进栈4#(S;(a；a))#;<.((进栈5#(S;(a；a))#(<.aa进栈6#(S;(a；a))#a.>；用S→a归约7#(S;(S；a))#(<.；;进栈8#(S;(S;a))#;<.aa进栈9#(S;(S;a))#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）考虑文法S→ASbA→SAa（1）构造这个文法的LR(0)项目规范族及识别活前缀的DFA。（2）这个文法是SLR（1）的吗？若是，构造出它的SLR分析表。解：构造拓广文法：(0)S’→S (1)S→AS (2)S→b (3)A→SA (4)A→a（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’)=＃；A→·a；S→·b。因此FOLLOW(S’)a,b=＃a,b=，所以不存在“移进－归约”冲突。对状态I5有FOLLOW(A)=a,b；A→·a；S→·b。因此FOLLOW(A)a,b=a,ba,b，所以存在“移进－归约”冲突。对状态I7也同样存在这种冲突，即:FOLLOW(S)a,b=＃,a,ba,b因此，该文法不是SLR(1)文法。4．（P1357）证明下面文法是SLR(1)文法，但不是LR(0)文法.S→AA→Ab|bBaB→aAc|a|aAb证明：该文法的项目集规范族有： I0={S→•A，A→•Ab，A→•bBa} I1=GO(I0,A)={S→A•，A→A•b} I2=GO(I0,b)={A→b•Ba，B→•aAc，B→•a，B→•aAb} I3=GO(I1,b)={A→Ab•} I4=GO(I2,B)={A→bB•a} I5=GO(I2,a)={B→a•Ac，B→a•，B→a•Ab，A→•Ab，A→•bBa} I6=GO(I4,a)={A→bBa•} I7=GO(I5,A)={B→aA•c，B→aA•b，A→A•b} I8=GO(I5,b)=I2 I9=GO(I7,b)={B→aAb•，A→Ab•}因为项目集I9中有A→Ab•和B→aAb•，存在“归约-归约”冲突，所以不是LR（0）文法。又因为FOLLOW(A)={b，c，#}，FOLLOW(B)={a}使得FOLLOW(A)∩FOLLOW(B)=φ，因此构造SLR(1)分析表时不会出现冲突，所以该文法是SLR(1)的。5．有文法：0．S’→E1．E→aA2．E→bB3．A→cA4．A→d5．B→cB6．B→d根据下列给出的该文法的LR(0)分析表，写出分析符号串“accd”的分析过程。状态ACTIONGOTOabcd#EAB0S2S311acc2S6S543S8S974r1r1r1r1r15r4r4r4r4r46S6S5107r2r2r2r2r28S8S9119r6r6r6r6r610r3r3r3r3r311r5r5r5r5r5答：步骤状态栈符号栈输入串动作00#accd#S2，移进102#accd#S6，移进2026#accd#S6，移进30266#accd#S5，移进402665#accd#用r4（A→d）归约5026610#accA#用r3（A→cA）归约602610#acA#用r3（A→cA）归约7024#aA#用r1（E→aA）归约801#E#acc第6章语义分析和中间代码生成1．根据给出的语义规则，写出下列布尔表达式的翻译过程(假设第1条四元式地址为100)及最终产生的四元式序列：A<10or（Bandnot（CorD））解：语法树：翻译过程：（1）E1→id1relopid2 （A<10）E1.truelist:=makelist(nextquad)=100E1.falselist:=makelist(nextquad+1)=101100(j<,A,10,0)101(j,_,_,0)(j,_,_,102)步骤13回填结果(2)M1→ε:M1.quad:=102(3)E4→id(B)E4.truelist:=makelist(nextquad)=102E4.falselist:=makelist(nextquad+1)=103102(jnz,B,_,0)(jnz,B,_,104)步骤11回填结果103(j,_,_,0)(4)M2→ε:M2.quad:=104(5)E8→id(C)E8.truelist:=makelist(nextquad)=104E8.falselist:=makelist(nextquad+1)=105104(jnz,C,_,0)105(j,_,_,0)(j,_,_,106)步骤8回填结果(6)M3→ε:M3.quad:=106(7)E9→id(D)E9.truelist:=makelist(nextquad)=106E9.falselist:=makelist(nextquad+1)=107106(jnz,D,_,0)(jnz,D,_,104)步骤8的拉链(jnz,D,_,103)步骤11的拉链107(j,_,_,0)(j,_,_,100)步骤13的拉链(8)E7→E8orM3E9backpatch(E8.falselist,M3.quad)=(105,106)E7.truelist:=merge(E8.truelist,E9.truelist)=merge(104,106)=106E7.falselist:=E9.falselist=107(9)E6→(E7)E6.truelist:=E7.truelist=106E6.falselist:=E7.falselist=107(10)E5→notE6E5.truelist:=E6.falselist=107E5.falselist:=E6.truelist=106(11)E3→E4andM2E5backpatch(E4.truelist,M2.quad)=(102,104)E3.falselist:=merge(E4.falselist,E5.falselist)=merge(103,106)=106E3.truelist:=E5.truelist=107(12)E2→(E3)E2.truelist:=E3.truelist=107E2.falselist:=E3.falselist=106（13）E→E1orM1E2backpatch(E1.falselist,M1.quad)=(101,102)E.truelist:=merge(E1.truelist,E2.truelist)=merge(100,107)=107E.falselist:=E2.falselist=106最终结果：A<10or（Bandnot（CorD））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)：Whilea<candb<ddoifa=1thenc:=c*2elsea:=a+x；解:语法树：（1）M1→M1.quad:=nextquad=100（2）E1→E1reLopE2(a<c)E1.trulist:=makelist(nextquad)=100E1.falelist:=makelist(nextquad+1)=101100(j<,a,c,0)(j<,a,c,102)，步骤（5）回填101(j,_,_,0)（3）M3→M2.quad:=nextquad=102（4）E2→E1reLopE2(b<d){E2.trulist:=makelist(nextquad)=102E2.falelist:=makelist(nextquad+1)=103102(j<,b,d,0)(j<,b,d,104)，步骤18回填103(j,_,_,0)(j,_,_,101)，步骤（5）拉链（5）EandM3backpatch(truelist,M3.quad)=backpatch(100,102)，用102回填100E.truelist:=E2.truelist=102E.falselist:=merge(E1.falselist,E2.falselist)=merge(101,103)=103，103指向101（6）M2→M2.quad:=nextquad=104（7）E3→E1reLopE2(a=1)E3.trulist:=makelist(nextquad)=104E3.falelist:=makelist(nextquad+1)=105104(j=,a,1,0)(j=,a,1,106)，步骤17回填105(j,_,_,0)(j,_,_,109)，步骤17回填（8）M4→M4.quad:=nextquad=106（9）E4→E1*E2(c*2)E4.place:=newtemp=T1106(*，c，2，T1)（10）A1→id:=E(c=c*2)107(:=,T1,_,c)（11）S2→A1S2.nex