编译原理作业参考答案

精品资料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|9c+|-|或：（未考虑正负号）sb | abb1 | 3 | 5 | 7 | 9aad | nn2 | 4 | 6 | 8 | bd0 | n或：（未考虑正负号）sc | abcc1 | 3 | 5 | 7 | 9a1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 bba | b0 |2. （ p36, 8 ）令文法为ete+te-ttft*ft/ff（ e）i（ 1 ）给出该文法的v n、v t 和 s 。（ 2 ）给出 i+i*i ， i* （i+i ）的最左推导和最右推导。（ 3 ）给出 i+i+i ， i+i*i 的语法树。答：（1 ）v n = e, t, f v t = +, -, *, /, (, ), 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+te+titii3. （p36, 9 ） 证明下面的文法是二义的：sises | isi答：对于句子iiiei 有两棵不同的语法树。因此该文法是二义的。sisesiisesiiiesiiiei sisiisesiiiesiiiei第 3 章 词法分析1. 设 m= （x，y，a，b ， ， x，y）为一个非确定有限自动机nfa m ，其中 定义如下：（x，a）=x，y（x，b）=y（y，a）=（y，b）=x，y试构造其相应的最小化的确定有限自动机dfa m 。答： 由 定义可知（x，a）， （ y， b）均为多值函数，所以是一个非确定有限自动机。（1） 根据 函数值，先构造nfa m（2） 确定化： 构造 dfa m 的转换矩阵 :ixiax，yibyx，yyx，yx，yx，y 确定 dfa m 的初始状态和终态：（a） 转换矩阵中 i 列的第一个状态为dfa m 的初始状态结点。（b） 含有 y 状态的子集均为dfa m 的终态结点 (、为终态结点 )。 根据 dfa m 的转换矩阵画出对应的状态转换图：（3） 最小化： 首先将其划分成终态集 2， 3和非终态集 1 2，3a= 22 ，3，2，3b= 22 ，3因此2，3已是不可再区分的 ,所以该 dfa m 已是最小化的。2.（p64 ，7(1) ）构造正规式 1(01)*101 相应的 dfa m 。答：（1 ）构造 nfa m 。x1（01）*101yy1（01）*101x1345x112314051y010x12345y11011（2） 构造转换矩阵ii0i1x1, 2, 31, 2, 32, 32, 3, 42, 32, 32, 3, 42, 3, 42, 3, 52, 3, 42, 3, 52, 32, 3, 4, y2, 3, 4, y 2, 3, 52, 3, 4（3） 由转换矩阵构造dfa m00306112110114513（p64 ，12(a) ）将下图所示的 nfa m 转换为等价的 dfa m ，并将该 dfa 最小化。答：该有限自动机状态0 输入同一字符a 时到达两个不同的结点 ,所以是 nfa 。（1）构造转换矩阵iiaib00，110， 110，101（ 2）由转换矩阵构造dfa m2a1a3bab（ 3）将 dfa m最小化 将 dfa m 的状态划分为非终态集 3和终态集 1，2 对每一个子集及每一个a进行考察；1 ，2a = 21 ，21 ，2b = 33因此1 ，2是不可区分的，所以最终状态为：1 ，2，3构造最小化的 dfa m ：a12，3ba4.（p64 ，12（ b）将下图所示的nfa m 转换为等价的 dfa m ，并进行最小化。bb023aabaab1b45a ab答：从图上可知该图已经是dfa m ，先只需将其最小化。首先划分为两个集合： 0,1 和2,3,4,52,3,4,5a = 1,3,0,5，划分为： 2,4 和 3,5 2,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 ，化简后的结果：b0,1aaab2,43,5ab5（p65 ， 14）构造一个dfam，它接受=0，1上所有满足如下条件的字符串：每个 1 都有 0 直接跟在右边。答：（1） ）根据题意，得到正规式：(0|10)*（2） ）构造对应的 nfa m ：0x1y102（ 3）将 nfa mi确定化为 dfa m 。相应的i0dfa mi1的状态转换矩阵如下：x, 1,y1; y21, y 21; y 1; y231101020dfa m转换图：（ 4）将 dfa m最小化： 将 dfa m 的状态划分为非终态集 3 和终态集 1, 2 对每一个子集进行考察；1, 2 0 = 21, 21, 2 1 = 3 ，33因此0, 1 是不可划分的。因此最终划分结果为：1, 2 和3最小化后的 dfa m ：01,2130第 4 章 语法分析 -自上而下1. （ p81 ， 1）考虑下面文法g sa(t)tt,ss（ 1 ）消除文法的左递归。（ 2 ）经改写后的文法是否是ll(1) 的？给出它的预测分析表。答：（ 1 ） 消除左递归：s a(t)t st t,st |（ 2 ） 证明改写后的文法是否是ll(1) 的。first(s) = a, , ( follow(s) = ， , ), # first(t) = a, , ( follow(t) = ) first(t ) = ， ,follow(t ) = ) 证 明 sa（ t）各侯选式的first 是否两两相交。first （ a）first （ ） = first （ a）first （） = first （ ）first （） = 证 明 t， st 的 first （ t）和 follow （ t）是否相交。first （ t ）follow （ t） =，=该文法是 ll （ 1）的。所以，改造后的文法是ll(1) 文法 预测分析表：a()，#ssass(t)tttsttsttsttt,st2.利用p76 表步骤4.1 的 ll(1) 分析表写出表达式符号栈输入串(i+i)*i的预测分析过程。所用的产生式0#e（i+i）*i#1#et（i+i） *i#ete2#etf（i+i）*i#tft3#et）e（ i+i）*i#f（e）4#et）ei+i ）*i#5#et）eti+i ）*i#ete6#et）etfi+i） *i#tft7#et）etii+i）*i#fi8#et）et+i）*i#9#et）e+i） *i#t10#et）et+i）*i#e +te 11#et）eti） *i#12#et）etfi）*i#tft13#et）etii）*i#fi14#et）et）*i#15#et）e）*i#t16#et） *i#e18#et*i#19#etf*i#t *ft 20#etfi#21#etii#fi22#et#23#e#t24#e3.（ p81 ， 2）对下面的文法getee +etft ttfpf 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因为 f pf ，所以 first （ f）= first （ p ） 因为 t ft ，所以 first （ t）=first （ f） 因为 e te ，所以 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+ettf*f p(e)ab由于：e+e： first(e )=+, follow(e)=#, = tt： first(t )=(, a, b, , follow(t)=+, ),# = f* f ： first(f )=*, follow(f )=+,(, a, b,),# =p(e)ab：候选式终结符首字符集两两不相交所以该文法为ll(1) 文法。（ 3 ）ll(1) 分析表*()ab#eeee+etetetete e e +eee tttttftftftft ttt ttttt ttttfffffpfpfpfpf fff *f ffffffpp(e)papbp第 5 章 语法分析 -自上而下分析1 （ p133 ， 1 ）令文法g1 为: ee+t|ttt*f|f f(e)|i证明 e+t*f是它的一个句型，指出这个句型的所有短语，直接短语和句柄。答：因为有： ee+te+t*f ， 所 以 e+t*f是文法的一个句型。短语： e+t*f, t*f直接短语： t*f句柄： t*f2.（ p133 ，3）考虑文法g2 s a | (t)t t； ss（ 1 ）计算文法g2 每个非终结符的firstvt和 lastvt 。（ 2 ）构造文法g2 的优先关系表，该文法是算符优先文法吗？（ 3 ）给出输入串 (a ； (a； a) 的算符优先分析过程。解：（ 1 ）firstvt和 lastvt firstvt(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)#; .)用 tt;s 归约14#(t)#()进栈15#(t)#) . #用 s(t) 归约16#s#结束3.（ p134 ，5）考虑文法s asb a 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 。i 4i 0i 3sss s as sbasaas as sbi 2i 5i 1sssa ss asaas aasbbasaa saaaaaasasi 6aas a asai 7sai 2bi 3ai 4ai 4aasas s asaab s asi 3bai 3i 4s baasbasa aaasbssi 7ssasi 5baas aai 3i 4asa aa s as sbai 4bi 3（ 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 ； sb。因此 follow(a)a,b=a,ba,b，所以存在“移进归约”冲突。对状态 i7 也同样存在这种冲突，即:follow(s)a,b= ,a,ba,b因此，该文法不是slr(1) 文法。4 （ p135 7 ）证明下面文法是slr(1) 文法，但不是lr(0) 文法 .s aa ab|bbab aac|a|aab证明：该文法的项目集规范族有：i0 = s ?a， a?ab ， a?bba i1 = go(i0,a) = sa ?， a a?b i2 = go(i0,b) = ab?ba ， b?aac ，b ?a ，b ?aab i3 = go(i1,b) = aab ? i4 = go(i2,b) = abb ?a i5 = go(i2,a) = ba?ac ， ba ?， b a ?ab ，a ?ab ， a?bba i6 = go(i4,a) = abba ? i7 = go(i5,a) = baa ?c， baa ?b， a a?b 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. 有文法：0. s e1 e aa2 e bb3 a ca4 a d5 b cb6 b d根据下列给出的该文法的lr(0) 分析表，写出分析符号串“ accd ”的分析过程。actiongoto状态abcd#eab0s2s311acc2s6s543s8s974r1r1r1r1r15r4r4r4r4r46s6s5107r2r2r2r2r28s8s9119r6r6r6r6r610r3r3r3r3r311r5r5r5r5r5答：步骤状态栈符号栈输入串动作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)及最终产生的四元式序列：se1orm1e2a10(e3)e4andm2e5bnote6(e7)e8orm3e9cda10 or （b and not （c or d ） 解： 语法树：翻译过程：（ 1 ）e1 id1 relop id 2（ 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) 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)=105 104(jnz, c ,_, 0)105(j, _, _, 0)(j, _, _, 106)步骤 8 回填结果(6) m3 : m3.quad:=106(7) e9 id(d) e9.truelist:=makelist(nextquad)=106 e9.falselist:=makelist(nextquad+1)=107106(jnz, d ,_, 0)(jnz,d , _,104)步骤 8 的拉链(jnz,d , _,103)步骤 11 的拉链107(j, _, _, 0)(j, _, _,100 )步骤 13 的拉链(8) e7 e8 or m3 e9backpatch (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=106 e6.falselist := e7.falselist = 107(10) e5 not e6e5.truelist := e6.falselist = 107 e5.falselist := e6.truelist = 106(11) e3 e4 and m2 e5backpatch(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 e1 or m1 e2backpatch (e1.falselist, m1.quad )=(101,102) e.truelist := merge(e1.truelist, e2.truelist)= merge(100,107) = 107e.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 thenc:=c*2 elsea:=a+x；swhilem1edom2s1（ 1） m1 解: 语法树：ae1andcm3be2difae3=then1m4s2a1n1elsem5s3a2c:=ce4*2a:=ae5+xm1.quad:=nextquad=100（ 2） e1 e1 relop e 2(ac) 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 e1 relop e 2(bd)e2.trulist:=makelist(nextquad)=102 e2.falelist:=makelist(nextquad+1)=103102(j, b, d, 0)(j, b, d, 104)，步骤 18 回填103(j , _, _ , 0)( j , _, _ , 101) ，步骤（ 5 ）拉链（ 5） eand m3backpatch (truelist,m3.quad)=backpatch(100, 102)，用 102 回填 100 e.truelist := e2.truelist=102e.falselist :=merge( e1.falselist, e2.falselist )=merge(101, 103)=103，103 指向 101（ 6） m2 m2.quad:=nextquad=104（ 7） e3 e1 relop e2(a=1) e3.trulist:=makelist(nextquad)=104 e3.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 * e 2(c*2) e4.place:=newtemp=t1106(* ， c， 2， t1)（ 10 ） a1 id:=e(c=c*2) 107(:=, t1, _, c)（ 11 ） s2 a1s2.nextlist :=makelist( )=null（ 12 ） n1 n1.nextlist:=makelist(nextquad)=108108(j,_ , _,0)(j,_ , _,100) ，步骤 18 回填（ 13 ） m5 m5.quad:=nextquad=109（ 14 ） e5 e 1 + e 2(a+x)