1、编译原理 作业参考答案1第 1 章 引 言1、解释下列各词源语言:编写源程序的语言（基本符号，关键字） ，各种程序设计语言都可以作为源语言。源程序: 用接近自然语言（数学语言）的源语言（基本符号，关键字）编写的程序，它是翻译程序处理的对象。目标程序: 目标程序是源程序经过翻译程序加工最后得到的程序。目标程序（结果程序）一般可由计算机直接执行。低级语言：机器语言和汇编语言。高级语言：是人们根据描述实际问题的需要而设计的一个记号系统。如同自然语言（接近数学语言和工程语言）一样，语言的基本单位是语句，由符号组和一组用来组织它们成为有确定意义的组合规则。翻译程序: 能够把某一种语言程序（源语言程序）改
2、变成另一种语言程序（目标语言程序） ，后者与前者在逻辑上是等价的。其中包括：编译程序，解释程序，汇编程序。编译程序: 把输入的源程序翻译成等价的目标程序（汇编语言或机器语言） ，然后再执行目标程序（先编译后执行） ，执行翻译工作的程序称为编译程序。解释程序: 以该语言写的源程序作为输入，但不产生目标程序。按源程序中语句动态顺序逐句的边解释边执行的过程，完成翻译工作的程序称为解释程序。2、什么叫“遍”？指对源程序或源程序的中间形式（如单词，中间代码）从头到尾扫描一次，并作相应的加工处理，称为一遍。3、简述编译程序的基本过程的任务。编译程序的工作是指从输入源程序开始到输出目标程序为止的整个过程，整
3、个过程可以划分5 个阶段。词法分析：输入源程序，进行词法分析，输出单词符号。语法分析：在词法分析的基础上，根据语言的语法规则把单词符号串分解成各类语法单位，并判断输入串是否构成语法正确的“程序” 。中间代码生成：按照语义规则把语法分析器归约（或推导）出的语法单位翻译成一定形式的中间代码。优化：对中间代码进行优化处理。目标代码生成：把中间代码翻译成目标语言程序。4、编译程序与解释程序的区别？编译程序生成目标程序后，再执行目标程序；然而解释程序不生成目标程序，边解释边执行。5、有人认为编译程序的五个组成部分缺一不可，这种看法正确吗？编译程序的 5 个阶段中，词法分析，语法分析，语义分析和代码生成生
4、成是必须完成的。而中间代码生成和代码优化并不是必不可少的。优化的目的是为了提高目标程序的质量，没有这一部分工作，仍然能够得到目标代码。6、编译程序的分类目前基本分为：诊断编译程序，优化编译程序，交叉编译程序，可变目标编译程序。 编译原理 作业参考答案2第 2 章 高级语言及其语法描述1（P36）令文法为N DNDD 0129（1）文法描述的语言 L（G）是什么？（2）给出句子 34，568 的最左推导和最右推导。答：（1）L（G）=为可带前导 0 的正整数或 L（G）=（0129） + 或 L（G）=为数字串（2）最左推导：NNDDD3D34NNDNDDDDD5DD56D568最右推导：NND
5、N4D434NNDN8ND8N68D685682*写出一个文法，使其语言是奇数集，且每个奇数是不以 0 开头。答：S CAB|B （考虑了正负号）A 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | AA | A0 | B 1|3|5|7|9C +|-|或：（未考虑正负号）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 |2.（P36,
6、 8）令文法为E TE+TE-TT FT*FT/FF （E）i（1）给出该文法的 VN、V T和 S。（2）给出 i+i*i，i*（i+i）的最左推导和最右推导。（3）给出 i+i+i，i+i*i 的语法树。答：（1）VN = E, T, F VT = +, -, *, /, (, ), i 编译原理 作业参考答案3S = 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
7、*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 iT ii3.（P36, 9）证明下面的文法是二义的：S iSeS | iS i答：对于句子 iiiei 有两棵不同的语法树。因此该文法是二义的。S iSeS iiSeS iiieS iiieiS iS iiSeS iiieS iiiei编译原理 作业参考答案4第 3 章 词法分析1设 M=（x，y，a，b，x，y）为一个非确定有限自动机 NFA M，其中定义如下：（x，a）=x，y （x，b
8、）=y（y，a）= （y，b）=x，y试构造其相应的最小化的确定有限自动机 DFA M。答：由定义可知（x，a） ，（y，b）均为多值函数，所以是一个非确定有限自动机。（1）根据函数值，先构造 NFA M（2）确定化： 构造 DFA M的转换矩阵 :I Ia Ibx 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
9、= 2 2，3， 2，3b=2 2，3因此2，3已是不可再区分的,所以该 DFA M已是最小化的。2. （P64，7(1)）构造正规式 1(01)*101 相应的 DFA M。答：（1）构造 NFA M。1（01）*101 1 （01）* 1 0 1 X YX 3 51 4 Y编译原理 作业参考答案51 1 0 1 01 0 1 1 0 1 1 （2）构造转换矩阵I I0 I1X 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,
10、 3, 5 2, 3, 4 （3）由转换矩阵构造 DFA M1001111101 234 5603 （P64，12(a)）将下图所示的 NFA M 转换为等价的 DFA M，并将该 DFA最小化。答：该有限自动机状态 0 输入同一字符 a 时到达两个不同的结点,所以是 NFA。（1）构造转换矩阵I Ia Ib0 0，1 1 0，1 0，1 1 1 0 （2）由转换矩阵构造 DFA Ma123X 321 542 YX 1 2 3 4 5 Y编译原理 作业参考答案6abab（3）将 DFA M 最小化 将 DFA M 的状态划分为非终态集3和终态集1，2 对每一个子集及每一个 a进行考察；1，2a
11、 = 2 1，21，2b = 3 3因此1，2是不可区分的，所以最终状态为： 1，2，3构造最小化的 DFA M：a b a 4. （P64，12 （b） ）将下图所示的 NFA M 转换为等价的 DFA M，并进行最小化。aaabaa012 34 5bbbbba答：从图上可知该图已经是 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
12、、2,4和3,5 ，化简后的结果：abbaaa0 , 1b2 , 4 3 , 55 （P65，14 ）构造一个 DFA M，它接受=0，1上所有满足如下条件的字符串：每个1 都有 0 直接跟在右边。答：（1）根据题意，得到正规式：(0|10)*（2）构造对应的 NFA M：1 2，3编译原理 作业参考答案701x 12Y0（3）将 NFA M 确定化为 DFA M。相应的 DFA M 的状态转换矩阵如下：I I0 I1X, 1,Y 1; Y 2 1, Y 1; Y 2 2 1; Y DFA M 转换图：01131200（4）将 DFA M 最小化： 将 DFA M 的状态划分为非终态集3和终态
13、集 1, 2 对每一个子集进行考察；1, 20 = 2 1, 21, 21 = 3， 3 3因此0, 1是不可划分的。因此最终划分结果为：1, 2 和3最小化后的 DFA M：1031 , 20编译原理 作业参考答案8第 4 章 语法分析-自上而下1.（P81，1）考虑下面文法 GS a(T)TT,SS（1）消除文法的左递归。（2）经改写后的文法是否是 LL(1)的？给出它的预测分析表。答：（1） 消除左递归：S a(T)T STT ,ST| （2） 证明改写后的文法是否是 LL(1)的。FIRST(S) = a, , ( FOLLOW(S) = ，, ), # FIRST(T) = a, ,
14、 ( FOLLOW(T) = ) FIRST(T) = ， , FOLLOW(T) = ) 证明 S a（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 ( ) ， #S Sa S S(T) T TST TST TST T T T,ST 2.利用 P76 表 4.1 的 LL(1)分析表写出表
15、达式 (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）E i+i）*i#5 #ET）ET i+i）*i# ETE6 #ET）ETF i+i）*i# TFT7 #ET）ETi i+i）*i# Fi8 #ET）ET +i）*i# 9 #ET）E +i）*i# T编译原理 作业参考答案910 #ET）ET+ +i）*i# E+TE11 #ET）ET i）*i#12 #ET）ETF i）*i# TFT13 #ET）ETi i）*
16、i# Fi14 #ET）ET ）*i# 15 #ET）E ）*i# T16 #ET） ）*i# E18 #ET *i# 19 #ETF* *i# T*FT20 #ETF i# 21 #ETi i# Fi22 #ET # 23 #E # T24 # # E3. （P81，2）对下面的文法 GE TEE +ET FTT TF PFF *FP (E)ab（1）计算这个文法的每个非终结符的 FIRST 和 FOLLOW。（2）证明这个文法是 LL(1)的。（3）构造它的预测分析表。答：（1）计算每个非终结符的 FIRST 和 FOLLOW。FIRST(E)=(, a, b, FIRST(E)= +,
17、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）=*， 因为
18、 P（E）ab，所以 FIRST（P）=（， ， a， b 因为 FPF，所以 FIRST（F）= FIRST（P）因为 TFT，所以 FIRST（T）=FIRST（F）因为 E TE，所以 FIRST（E）= FIRST（T）因为 TT，所以 FIRST（ T）= FIRST（T） =（， ， a， b ，编译原理 作业参考答案10求非终结符的 FOLLOW：因为 E TE的 E 是文法的开始符号，FOLLOW（E）=#，又因为 P（E） ，所以 FOLLOW（E）=#FIRST（） ）=#， )因为 E TE，所以 FOLLOW（E）=FOLLOW（E）因为 E TE，并且 E，所以 FO
19、LLOW（T）=FIRST （E） ,又因为 E,所以FOLLOW（T）=+ FOLLOW（E）=+ #,=+，#, .因为 TFT，所以 FOLLOW（T）=FOLLOW（T）=+，#, .因为 T FT，并且 T，所以 FOLLOW（F）=FIRST （T） ,又因为 T,所以FOLLOW（F）=（，a，b FOLLOW（T）=（，a，b +，#, =（，a，b ,+，#, 因为 FPF，所以 FOLLOW（F）=FOLLOW（F）=（，a，b ,+，#, .因为 FPF，并且 F，所以 FOLLOW（P）=FIRST（F） ,又因为 F,所以FOLLOW（P）=* FOLLOW（ F）=
20、*（，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)分析表+ * ( ) a b #E E TE E TE E TE E TEE E+E E ET T FT T FT T FT T FTT T TT T TT TT TT TF F PF F PF F PF F PFF F F*F F F F F F FP P(E) Pa Pb P
