编译原理教程课西安电子科大出版社第三版后习题答案——第二章

{2,3,5,7,9,10} {2,4,5,7,8,10} {2,4,5,7,8,10} {11} {6} ห้องสมุดไป่ตู้ {2,5,7,8,10} φ φ
{2,3,5,7,10} {2,3,5,7,9,10} φ φ
{11} {11} φ φ S
{6} {6} φ φ
3: 5: 6: S a b S S A a b A a A S b A
文法： (1) 最左推导: 最右推导: (2) (((a,a),^,(a)),a) (((S,a),^,(a)),a) (((T,a),^,(a)),a) (((T,S),^,(a)),a) (((T),^,(a)),a)
((S,^,(a)),a) ((T,^,(a)),a) ((T,S,(a)),a) ((T,(a)),a) ((T,(S)),a) ((T,(T)),a) ((T,S),a) ((T),a) (S,a) (T,S) (T) S “移进-归约”过程： 步骤 栈 输入串 动作 0 # (((a,a),^,(a)),a)# 预备 1 #( ((a,a),^,(a)),a)# 进 2 #(( (a,a),^,(a)),a)# 进 3 #((( a,a),^,(a)),a)# 进 4 #(((a ,a),^,(a)),a)# 进 5 #(((S ,a),^,(a)),a)# 归 6 #(((T ,a),^,(a)),a)# 归 7 #(((T, a),^,(a)),a)# 进 8 #(((T,a ),^,(a)),a)# 进 9 #(((T,S ),^,(a)),a)# 归 10 #(((T ),^,(a)),a)# 归 11 #(((T) ,^,(a)),a)# 进 12 #((S ,^,(a)),a)# 归 13 #((T ,^,(a)),a)# 归 14 #((T, ^,(a)),a)# 进 15 #((T,^ ,(a)),a)# 进 16 #((T,S ,(a)),a)# 归 17 #((T ,(a)),a)# 归 18 #((T, (a)),a)# 进 19 #((T,( a)),a)# 进 20 #((T,(a )),a)# 进 21 #((T,(S )),a)# 归 22 #((T,(T )),a)# 归

第二章 词法分析2.1 完成下列选择题： (1) 词法分析器的输出结果是 。

a. 单词的种别编码 b. 单词在符号表中的位置 c. 单词的种别编码和自身值 d. 单词自身值 (2) 正规式M1和M2等价是指 。

a. M1和M2的状态数相等 b. M1和M2的有向边条数相等 c. M1和M2所识别的语言集相等 d. M1和M2状态数和有向边条数相等 (3) DFA M(见图2-1)接受的字集为 。

a. 以0开头的二进制数组成的集合 b. 以0结尾的二进制数组成的集合 c. 含奇数个0的二进制数组成的集合 d. 含偶数个0的二进制数组成的集合 【解答】 (1) c (2) c (3) d图2-1 习题的DFA M2.2 什么是扫描器？扫描器的功能是什么？ 【解答】 扫描器就是词法分析器，它接受输入的源程序，对源程序进行词法分析并识别出一个个单词符号，其输出结果是单词符号，供语法分析器使用。

通常是把词法分析器作为一个子程序，每当词法分析器需要一个单词符号时就调用这个子程序。

每次调用时，词法分析器就从输入串中识别出一个单词符号交给语法分析器。

2.3 设M=({x,y}, {a,b}, f, x, {y})为一非确定的有限自动机，其中f 定义如下： f(x,a)={x,y} f {x,b}={y} f(y,a)=Φ f{y,b}={x,y} 试构造相应的确定有限自动机M ′。

【解答】 对照自动机的定义M=(S,Σ,f,So,Z)，由f 的定义可知f(x,a)、f(y,b)均为多值函数，因此M 是一非确定有限自动机。

先画出NFA M 相应的状态图，如图2-2所示。

图2-2 习题的NFA M用子集法构造状态转换矩阵，如表表2-1 状态转换矩阵1b将转换矩阵中的所有子集重新命名，形成表2-2所示的状态转换矩阵，即得到 M ′=({0,1,2},{a,b},f,0,{1,2})，其状态转换图如图2-3所示。

编译原理第三版课后习题答案编译原理是计算机科学中的一门重要课程，它研究的是如何将高级程序语言转换为机器语言的过程。

而《编译原理》第三版是目前被广泛采用的教材之一。

在学习过程中，课后习题是巩固知识、提高能力的重要环节。

本文将为读者提供《编译原理》第三版课后习题的答案，希望能够帮助读者更好地理解和掌握这门课程。

第一章：引论习题1.1：编译器和解释器有什么区别？答案：编译器将整个源程序转换为目标代码，然后一次性执行目标代码；而解释器则逐行解释源程序，并即时执行。

习题1.2：编译器的主要任务是什么？答案：编译器的主要任务是将高级程序语言转换为目标代码，包括词法分析、语法分析、语义分析、中间代码生成、代码优化和目标代码生成等过程。

第二章：词法分析习题2.1：什么是词法分析？答案：词法分析是将源程序中的字符序列划分为有意义的词素（token）序列的过程。

习题2.2：请给出识别下列词素的正则表达式：（1）整数：[0-9]+（2）浮点数：[0-9]+\.[0-9]+（3）标识符：[a-zA-Z_][a-zA-Z_0-9]*第三章：语法分析习题3.1：什么是语法分析？答案：语法分析是将词法分析得到的词素序列转换为语法树的过程。

习题3.2：请给出下列文法的FIRST集和FOLLOW集：S -> aAbA -> cA | ε答案：FIRST(S) = {a}FIRST(A) = {c, ε}FOLLOW(S) = {$}FOLLOW(A) = {b}第四章：语义分析习题4.1：什么是语义分析？答案：语义分析是对源程序进行静态和动态语义检查的过程。

习题4.2：请给出下列文法的语义动作：S -> if E then S1 else S2答案：1. 计算E的值2. 如果E的值为真，则执行S1；否则执行S2。

第五章：中间代码生成习题5.1：什么是中间代码？答案：中间代码是一种介于源代码和目标代码之间的表示形式，它将源代码转换为一种更容易进行优化和转换的形式。

编译原理第三版答案第一章答案1.问题：什么是编译器？答案：编译器是一种将源程序转换为目标程序的软件工具。

它负责对源代码进行词法分析、语法分析、语义分析和代码生成等一系列操作，最终生成可执行的目标程序。

2.问题：编译器的主要任务是什么？答案：编译器的主要任务是将高级语言程序转换为能被计算机硬件执行的机器码。

它包括了对源代码进行词法分析、语法分析、语义分析、中间代码生成、代码优化和目标代码生成等过程。

3.问题：编译器的工作过程是什么？答案：编译器的工作过程分为多个阶段。

首先是词法分析，将源代码拆分成一个个的词法单元。

然后是语法分析，根据语法规则构建语法树。

接着是语义分析，对语法树进行检查，确保程序的语义正确。

之后是中间代码生成和优化，将语法树转换为更加高效的中间代码。

最后是目标代码生成，将中间代码转换为特定的目标机器代码。

4.问题：编译器的优化技术有哪些？答案：编译器的优化技术包括了常量折叠、公共子表达式消除、循环优化、函数内联和代码重排等。

这些技术可以提高程序的执行效率和优化代码的空间利用率。

5.问题：编译器的应用领域有哪些？答案：编译器广泛应用于软件开发领域。

它们被用于将高级语言转换为目标机器码，用于开发操作系统、编程语言和应用软件等。

第二章答案1.问题：什么是有限自动机（DFA）？答案：有限自动机是一种表示有限状态和状态之间转换关系的模型。

它可以根据输入字符进行状态转换，最终决定是否接受某个字符串。

2.问题：有限自动机的主要组成部分是什么？答案：有限自动机主要由状态集合、输入字符集、转移函数、初始状态和接受状态集合组成。

3.问题：什么是正则表达式？答案：正则表达式是一种用于描述字符串模式的表达式。

它由普通字符和特殊字符组成，可以用于匹配符合条件的字符串。

4.问题：正则表达式的常用操作符有哪些？答案：正则表达式的常用操作符包括了字面量字符、字符类、重复操作符、选择操作符和位置操作符等。

5.问题：正则表达式如何转换为有限自动机？答案：正则表达式可以通过字面化、连接、选择和闭包等操作转换为等价的有限自动机。

第二章习题解答之五兆芳芳创作P36-6(1)()L G1是0~9组成的数字串(2)最左推导:最右推导:P36-7G(S)P36-8文法：最左推导:最右推导:语法树：/******************************** *****************/P36-9句子iiiei有两个语法树：P36-10/*****************************/P36-11/***************L1: L2: L3: L4:***************/第三章习题参考答案P64–7 (1)101101(|)*确定化：1 01 1 1 最小化：1 01 1 1 P64–8 (1) (2) (3) P64–12 (a)aa,ba 确定化：给状态编号：aaab b ba 最小化：a ab ab (b)b a b a ba a a1已经确定化了,进行最小化 最小化：a b aP64–14 (1) 01 0 (2):(|1εε0 确定化：给状态编号：YY1 1最小化：1 1第四章P81–1(1) 依照T,S的顺序消除左递归递归子程序：procedure S;beginif sym='a' or sym='^'then abvanceelse if sym='('then beginadvance;T;if sym=')' then advance;else error;endelse errorend;procedure T;beginS;'Tend;procedure 'T;beginif sym=','then beginadvance;S;'Tendend;其中:sym:是输入串指针IP所指的符号advance:是把IP调至下一个输入符号error:是出错诊察程序(2)FIRST(S)={a,^,(} FIRST(T)={a,^,(} FIRST('T)={,,ε} FOLLOW(S)={),,,#} FOLLOW(T)={)} FOLLOW('T)={)}预测阐发表是LL(1)文法P81–2文法：(1)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,^,+,),#}(2)考虑下列产生式:FIRST(+E)∩FIRST(ε)={+}∩{ε}=φFIRST(+E)∩FOLLOW(E')={+}∩{#,)}=φFIRST(T)∩FIRST(ε)={(,a,b,^}∩{ε}=φFIRST(T)∩FOLLOW(T')={(,a,b,^}∩{+,),#}=φFIRST(*F')∩FIRST(ε)={*}∩{ε}=φFIRST(*F')∩FOLLOW(F')={*}∩{(,a,b,^,+,),#}=φFIRST((E))∩FIRST(a)∩FIRST(b)∩FIRST(^)=φ所以,该文法度LL(1)文法.(3)(4)procedure E;beginif sym='(' or sym='a' or sym='b' or sym='^' then begin T; E' endelse errorendprocedure E';beginif sym='+'then begin advance; E endelse if sym<>')' and sym<>'#' then error endprocedure T;beginif sym='(' or sym='a' or sym='b' or sym='^' then begin F; T' endelse errorendprocedure T';beginif sym='(' or sym='a' or sym='b' or sym='^' then Telse if sym='*' then errorendprocedure F;beginif sym='(' or sym='a' or sym='b' or sym='^' then begin P; F' endelse errorendprocedure F';beginif sym='*'then begin advance; F' endendprocedure P;beginif sym='a' or sym='b' or sym='^'then advanceelse if sym='(' thenbeginadvance; E;if sym=')' then advanceelse errorendelse errorend;P81–3/***************(1)是，满足三个条件.(2)不是，对于A不满足条件3.(3)不是，A、B均不满足条件3.(4)是，满足三个条件.***************/第五章P133–1短语: E+T*F, T*F,直接短语: T*F句柄: T*FP133–2文法：(1)最左推导:最右推导:(2)(((a,a),^,(a)),a)(((S,a),^,(a)),a)(((T,a),^,(a)),a)(((T,S),^,(a)),a)(((T),^,(a)),a)((S,^,(a)),a)((T,^,(a)),a)((T,S,(a)),a)((T,(a)),a)((T,(S)),a)((T,(T)),a)((T,S),a)((T),a)(S,a)(T,S)(T)S“移进-归约”进程：步调栈输入串动作0 # (((a,a),^,(a)),a)# 预备1 #( ((a,a),^,(a)),a)# 进2 #(( (a,a),^,(a)),a)# 进3 #((( a,a),^,(a)),a)# 进4 #(((a ,a),^,(a)),a)# 进5 #(((S ,a),^,(a)),a)# 归6 #(((T ,a),^,(a)),a)# 归7 #(((T, a),^,(a)),a)# 进8 #(((T,a ),^,(a)),a)# 进9 #(((T,S ),^,(a)),a)# 归10 #(((T ),^,(a)),a)#归11 #(((T) ,^,(a)),a)# 进12 #((S ,^,(a)),a)# 归13 #((T ,^,(a)),a)# 归14 #((T, ^,(a)),a)# 进15 #((T,^ ,(a)),a)# 进16 #((T,S ,(a)),a)# 归17 #((T ,(a)),a)# 归18 #((T, (a)),a)# 进19 #((T,( a)),a)# 进20 #((T,(a )),a)# 进21 #((T,(S )),a)# 归22 #((T,(T )),a)# 归23 #((T,(T) ),a)# 进24 #((T,S ),a)# 归25 #((T ),a)# 归26 #((T) ,a)# 进27 #(S ,a)# 归28 #(T ,a)# 归29 #(T, a)# 进30 #(T,a )# 进31 #(T,S )# 归32 #(T )# 归33 #(T) # 进34 #S # 归P133–3(1)FIRSTVT(S)={a,^,(}FIRSTVT(T)={,,a,^,(}LASTVT(S)={a,^,)}LASTVT(T)={,,a,^,)}(2)G是算符文法，并且是算符优先文法6(3)优先函数（4）栈输入字符串动作# （a,(a,a)）# 预备#( a, (a,a))# 进#(a , (a,a))# 进#(t , (a,a))# 归#（t, (a,a)）# 进#（t,（a,a））# 进#（t,（a ,a））# 进#（t,（t ,a））# 归#（t,（t, a））# 进#（t,（t,a ））# 进#（t,（t,s ））# 归#（t,（t ））# 归#（t,（t））# 进#（t,s ）# 归#（t ）# 归#（t ）# 进# s # 归successP134–5(1)0.'→⋅S S 1.'→⋅S S 2.S AS →⋅ 3.S A S →⋅4.S AS →⋅5.S b →⋅6.S b →⋅7.A SA →⋅8.A S A →⋅ 9.A SA →⋅ 10.A a →⋅11.A a →⋅(2)Aεε εd确定化：AabS S b69S A ba Abba机关LR(0)项目集标准族也可以用GO 函数来计较得到.所得到的项目集标准族与上图中的项目集一样: 0I ={'→⋅S S ，S AS →⋅，S b →⋅，A SA →⋅，A a →⋅} GO(0I ，a)={ A a →⋅}=1I GO(0I ，b)={ S b →⋅}=2IGO(0I ，S)={ '→⋅S S ，A S A →⋅，A SA →⋅，A a →⋅，S AS →⋅，S b →⋅}=3IGO(0I ，A)={ S A S →⋅，S AS →⋅，S b →⋅，A SA →⋅，A a →⋅}=4I GO(3I ，a)={ A a →⋅}=1I GO(3I ，b)={ S b →⋅}=2IGO(3I ，S)={ A S A →⋅，S AS →⋅，S b →⋅，A SA →⋅，A a →⋅}=5I GO(3I ，A)={ A SA →⋅，S A S →⋅，S AS →⋅，S b →⋅，A SA →⋅，A a →⋅}=6IGO(4I ，a)={ A a →⋅}=1I GO(4I ，b)={ S b →⋅}=2IGO(4I ，S)={ S AS →⋅，A S A →⋅，S AS →⋅，S b →⋅，A SA →⋅，A a →⋅}=7IGO(4I ，A)={ S A S →⋅，S AS →⋅，S b →⋅，A SA →⋅，A a →⋅}=4I GO(5I ，a)={ A a →⋅}=1I GO(5I ，b)={ S b →⋅}=2IGO(5I ，S)={ A S A →⋅，S AS →⋅，S b →⋅，A SA →⋅，A a →⋅}=5I GO(5I ，A)={ A SA →⋅，S A S →⋅，S AS →⋅，S b →⋅，A SA →⋅，A a →⋅}=6IGO(6I ，a)={ A a →⋅}=1I GO(6I ，b)={ S b →⋅}=2IGO(6I ，S)={ S AS →⋅，A S A →⋅，S AS →⋅，S b →⋅，A SA →⋅，A a →⋅}=7IGO(6I ，A)={ S A S →⋅，S AS →⋅，S b →⋅，A SA →⋅，A a →⋅}=4I GO(7I ，a)={ A a →⋅}=1I GO(7I ，b)={ S b →⋅}=2IGO(7I ，S)={ A S A →⋅，S AS →⋅，S b →⋅，A SA →⋅，A a →⋅}=5I GO(7I ，A)={ A SA →⋅，S A S →⋅，S AS →⋅，S b →⋅，A SA →⋅，A a →⋅}=6I项目集标准族为C={1I ，2I ，3I ，4I ，5I ，6I ，7I } (3)不是SLR 文法状态3，6，7有移进归约冲突状态3：FOLLOW(S’)={#}不包含a,b状态6：FOLLOW(S)={#,a,b}包含a,b,；移进归约冲突无法消解状态7：FOLLOW(A)={a,b}包含a,b ；移进归约冲突消解 所以不是SLR 文法.(4)机关例如LR(1)项目集标准族 见下图：对于状态5，因为包含项目[b a AS A / ⋅→]，所以遇到搜索符号a 或b 时，应该用AS A →归约.又因为状态5包含项目[b a a A / ⋅→]，所以遇到搜索符号a 时，应该移进.因此存在“移进-归约”矛盾，所以这个文法不是LR(1)文法.b b bASa SS aSSA ba a Sb bAA/********************第六章会有点难P164–5(1)E→E1＋T {if (E1.type = int) and (T.type = int ) then E.type := intelse E.type := real}E→T {E.type := T.type}T→num.num {T.type := real}T→num {T.type := int}(2)P164–7S→L1|L2lengthL.2)}S→L {S.val:=L.val}L→L1B {L.val:=2*L1.val + B.val;L.length:=L1.length+1}L→B {L.val:=B.c;L.length :=1}B→0 {B.c:=0}B→1 {B.c:=1}***********************/第七章P217–1a*(-b+c) ab@c+*a+b*(c+d/e) abcde/+*+-a+b*(-c+d) a@bc@d+*+if (x+y)*z =0 then (a+b)↑c else a↑b↑c xy+z*0= ab+c↑abc↑↑￥或xy+z*0= P1 jez ab+c↑ P2 jump abc↑↑P1 P2P217–3-(a+b)*(c+d)-(a+b+c)的三元式序列:(1)+, a, b(2)@, (1), -(3)+, c, d(4)*, (2), (3)(5)+, a, b(6)+, (5), c(7)-, (4), (6)直接三元式序列:三元式表：(1)+, a, b(2)@, (1), -(3)+, c, d(4)*, (2), (3)(5)+, (1), c(6)-, (4), (5)直接码表：(1)(2)(3)(4)(1)(5)(6)四元式序列:(1)+, a, b, 1T(2)@, 1T, -, 2T(3)+, c, d, 3T(4)*, 2T, 3T, 4T(5)+, a, b, 5T(6)+, 5T, c, 6T(7)-, 4T, 6T, 7TP218–4自下而上阐发进程中把赋值句翻译成四元式的步调:A:=B*(-C+D)步调输入串栈PLACE 四元式(1) A:=B*(-C+D)(2) :=B*(-C+D) iA (3) B*(-C+D) i:=A- (4) *(-C+D)i:=i A-B (5) *(-C+D)i:=E A-B (6) *(-C+D)i:=E A-B (7) (-C+D)i:=E* A-B- (8) -C+D)i:=E*( A-B-- (9)C+D) i:=E*(- A-B--- (10) +D) i:=E*(-i A-B---C (11) +D) i:=E*(-E A-B---C (@,C,-, T 1) (12) +D) i:=E*(E A-B--T 1 (13) D) i:=E*(E+ A-B--T 1- (14) ) i:=E*(E+i A-B--T 1-D (15) ) i:=E*(E+E A-B--T 1-D (+,T 1,D,T 2) (16) ) i:=E(E A-B--T 2 (17) i:=E*(E) A-B--T 2- (18) i:=E+E A-B-T 2 (*,B,T 2,T 3) (19) i:=E A-T 3 (:=,T 3,-,A) (20) A产生的四元式： (@,C,-, T 1) (+,T 1,D,T 2) (*,B,T 2,T 3) (:=,T 3,-,A)P218–5/****************设A ：10*20，B 、C 、D ：20，宽度为w ＝4 则T1:= i * 20T1:=T1+jT2:=A –84T3:=4*T1Tn:=T2[T3] //这一步是多余的T4:= i + jT5:=B–4T6:=4*T4T7:=T5[T6]T8:= i * 20T8:=T8+jT9:=A–84T10:=4*T8T11:=T9[T10]T12:= i + jT13:=D–4T14:=4*T12T15:= T13[T14]T16:=T11+T15T17:=C–4T18:=4*T16T19:=T17[T18]T20:=T7+T19Tn:=T20******************/P218–6100.(jnz, A, -, 0)101.(j, -, -, 102)102.(jnz, B, -, 104)103.(j, -, -, 0)104.(jnz, C, -, 103)105.(j, -, -, 106)106.(jnz, D, -, 104) --假链链首107.(j, -, -, 100) --真链链首假链：{106,104，103}真链：{107,100}P218–7100.(j<, A, C, 102)101.(j, -, -, 0)102.(j<, B, D, 104)103.(j, -, -, 101)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)P219–12/********************(1)MAXINT – 5MAXINT – 4MAXINT – 3MAXINT – 2MAXINT – 1MAXINT(2)翻译模式办法1：for E1 := E2 to E3 do S1 do MS F S → {backpatch(S1.nextlist,nextquad);backpatch(F.truelist,M.quad);emit(F.place ‘:=’F.place ‘+’1);emit(‘j ≤,’F.place ‘,’F.end ‘,’M.quad); S.nextlist := F.falselist;}21 to :For E E I F =→{F.falselist:= makelist(nextquad); emit(‘j>,’E1.place ‘,’E2.place ‘,0’);emit(I.Place ‘:=’E1.place);F.truelist := makelist(nextquad);emit(‘j,-,-,-’);F.place := I.place;F.end := E2.place;} id I →{p:=lookup(); if p <> nil thenI.place := pelse error}ε→M {M.quad := nextquad}****************/办法2：S→ for id:=E1 to E2 do S1S→ F S1F→ for id:=E1 to E2 do21:toE E forid F =→do{INITIAL=NEWTEMP;emit(‘:=，’E1.PLACE’，-，’ INITIAL); FINAL=NEWTEMP;emit(‘:=，’E2.PLACE’，-，’ FINAL);p:= nextquad+2;emit(‘j,’ INITIAL ‘,’ FINAL ’,’ p);F.nextlist:=makelist(nextquad);emit(‘j,－,－,－’);F.place:=lookup();if F.place nil thenemit(F.place ‘:=’ INITIAL)F.quad:=nextquad;F.final:=FINAL;}{backpatch(S1.nextlist, nextquad)p:=nextquad+2;emit(‘j,’ F.place‘,’ F.final ’,’ p );S.nextlist := merge(F.nextlist, makelist(nextquad)); emit(‘j,－,－,－’);emit(‘su cc，’ F.place ’，-，’ F.place);emit(‘j,－,－,’ F.quad);}第九章P270–9(1) 传名即当进程调用时，其作用相当于把被调用段的进程体抄到调用出现处，但必须将其中出现的任一形式参数都代之以相应的实在参数.A:=2;B:=3;A:=A+1;A:=A+(A+B);print A;∴A=9(2) 传地址即当程序控制转入被调用段后，被调用段首先把实在参数抄进相应的形式参数的形式单元中，进程体对形参的任何引用或赋值都被处理成对形式单元的直接拜访.当被调用段任务完毕前往时，形式单元（都是指示器）所指的实参单元就持有所希望的值.①A:=2;B:=3;T:=A+B②把T,A,A的地址抄进已知单元J1,J2,J3③x:＝J1;y:=J2;z:=J3 //把实参地址抄进形式单元，且J2=J3④Y↑:=y↑+1Z↑:=z↑+x↑ // Y↑：对y的直接拜访Z↑：对z的直接拜访⑤print AA=8(3) 得结果每个形参均对应两个单元，第一个存放实参地址，第二个存放实参值，在进程体中对形参的任何引用或赋值都看成是对它的第二个单元的直接拜访，但在进程任务完毕前往前必须把第二个单元的内容放到第一个单元所指的那个实参单元中①A:=2;B:=3;T:=A+B②把T,A,A的地址抄进已知单元J1,J2,J3③x1:=J1;x2:=T;y1:=J2;y2:=A;z1:=J3;z2:=A; //将实参的地址和值辨别放进两个形式单元中④y2:=y2+1; z2:=z2+x2; //对形参第二个单元的直接拜访⑤x1↑：＝x2; y1↑:=y2; z1↑:=z2 //前往前把第二个单元的内容存放到第一个单元所指的实参地址中⑥print AA=7(4) 传值即被调用段开始任务时，首先把实参的值写进相应的形参单元中，然后就仿佛使用局部变量一样使用这些形式单元 A:=2;B:=3;x:=A+By:=Az:=Ay:=y+1z:=z+xprint AA=2进程调用不改动A 的值第十章P306-1P306-2read A,BF:=1C:=A*A 1BD:=B*Bif C<D goto 1L---------------------------E:=A*AF:=F+1E:=E+F2B write Ehalt---------------------------1L : E:=B*BF:=F+2E:=E+F3B write Eif E>100 goto 2L ---------------------------halt4B ---------------------------2L : F:=F-1goto 1L 5B---------------------------根本块为1B 、2B 、3B 、4B 、5B P307-4B2有回路，所以{B2}是循环，B2既是入口节点，又是出口节点（1）代码外提：不存在不变运算，故无代码外提 （2）强度削弱：A:=K*I B:=J*I *→+ （3） 删除根本归结变量：I<100 可以用A<100*K 或B<100*J代替P307-5{B2,B3}（1） （2）。

编译原理_第三版_课后答案编译原理课后题答案第二章P36-6(1)是0~9组成的数字串⑵最左推导：N= ND= NDD= NDDD = DDDD = ODDD = O1DD= 012D= 0127N= ND 二DD 二3D二34N= ND 二NDD = DDD = 5DD = 56D二568最右推导：N 二ND 二N7二ND7二N27二ND27二N127二D127二0127 N = ND = N4= D4= 34N= ND 二N8= ND8二N68二D68二568P36-7G(S)编译原理第三版课后答案O > 1|3|5|7|9N > 2|4|6|8|0D 、0|NS > 0|A0A > AD|NP36-8文法:E T T E +T|E —TT t F T* F|T/ FF > (E)|i最左推导：E = E T= T T=F T = i T = i T * F = i F * F = i i * F = i i*iE = T= T*F 二 F * F = i* F 二i *( E)二i*( E T)二i *( T T)二i *( F T) =i *( i T)二i*(i F)= i*( i i)最右推导:E= E T= E T*F= E T*i= E F*i= E i*i= T i*i= F i*i= i i*iE= T= F*T= F * F= F*( E)= F *( E T)= F *( E F)= F *( E i)=F*( T i)= F*( F i)= F*( i i)= i*(i i)/********************************P36-11*****************P36-9句子iiiei 有两个语法树:S 二 iSeS 二 iSei 二 iiSei = iiiei S= iS = iiSeS = iiSei = iiieiP36-10/**************S > TS |T T > (S)|()***************ii+i+ii-i-iii+i*i***************P36-11L1:S > ACA r aAb | abC r cC | ；L2:S > ABA》aA| ；B r bBc|bcL3:S > ABA—：aAb | ；B = aBb | ；L4:S > A| BA—；0A1| ；B-1B0| A***************/第三章习题参考答案P64 - 7(1)编译原理第三版课后答案1(01)*101(1)1101确定化:1001111最小化:{0,1,2,3,4,5},{6}{0,123,4,5}。

目录P36-6 (2)P36-7 (2)P36-8 (2)P36-9 (3)P36-10 (3)P36-11 (3)P64–7 (4)P64–8 (5)P64–12 (5)P64–14 (7)P81–1 (8)P81–2 (9)P81–3 (12)P133–1 (12)P133–2 (12)P133–3 (14)P134–5 (15)P164–5 (19)P164–7 (19)P217–1 (19)P217–3 (20)P218–4 (20)P218–5 (21)P218–6 (22)P218–7 (22)P219–12 (22)P270–9 (24)P36-6(1)L G ()1是0~9组成的数字串(2)最左推导:N ND NDD NDDD DDDD DDD DD D N ND DD D N ND NDD DDD DD D ⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒0010120127334556568最右推导:N ND N ND N ND N D N ND N D N ND N ND N D ⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒77272712712701274434886868568P36-7G(S)O N O D N S O AO A AD N→→→→→1357924680|||||||||||P36-8文法：E T E T E T TF T F T F F E i→+-→→|||*|/()| 最左推导:E E T T TF T i T i T F i F F i i F i i i E T T F F F i F i E i E T i T T i F T i i T i i F i i i ⇒+⇒+⇒+⇒+⇒+⇒+⇒+⇒+⇒⇒⇒⇒⇒⇒+⇒+⇒+⇒+⇒+⇒+********()*()*()*()*()*()*()最右推导:E E T E TF E T i E F i E i i T i i F i i i i i E T F T F F F E F E T F E F F E i F T i F F i F i i i i i ⇒+⇒+⇒+⇒+⇒+⇒+⇒+⇒+⇒⇒⇒⇒⇒+⇒+⇒+⇒+⇒+⇒+⇒+**********()*()*()*()*()*()*()*()语法树：/********************************EE FTE +T F F T +iiiEEFTE-T F F T -iiiEEFT+T F FTiii*i+i+ii-i-ii+i*i*****************/P36-9句子iiiei 有两个语法树：S iSeS iSei iiSei iiiei S iS iiSeS iiSei iiiei ⇒⇒⇒⇒⇒⇒⇒⇒P36-10/**************)(|)(|S T TTS S →→***************/P36-11/*************** L1:ε||cC C ab aAb A AC S →→→ L2:bcbBc B aA A AB S ||→→→εL3:εε||aBb B aAb A AB S →→→ L4:AB B A A B A S |01|10|→→→ε ***************/第三章习题参考答案P64–7(1)确定化：最小化：{,,,,,},{}{,,,,,}{,,}{,,,,,}{,,,}{,,,,},{},{}{,,,,}{,,}{,,,},{},{},{}{,,,}{,01234560123451350123451246012345601234135012345601231010==== 3012312401234560110112233234012345610101}{,,,}{,,}{,},{,}{},{},{}{,}{}{,}{,}{,}{}{,}{}{},{},{,},{},{},{}=====P64–8(1)01)0|1(*(2))5|0(|)5|0()9|8|7|6|5|4|3|2|1|0)(9|8|7|6|5|4|3|2|1(*(3)******)110|0(01|)110|0(10P64–12(a)确定化：给状态编号：最小化：{,},{,}{,}{}{,}{}{,}{,}{,}{}{,},{},{}012301101223032330123a ba b ====(b)已经确定化了,进行最小化最小化：{{,}, {,,,}}012345011012423451305234523452410243535353524012435011012424{,}{}{,}{,}{,,,}{,,,}{,,,}{,,,}{,}{,}{,}{,}{,}{,}{,}{,}{{,},{,},{,}}{,}{}{,}{,}{,}a b a b a b a b a b a =============={,}{,}{,}{,}{,}{,}{,}10243535353524 b a baP64–14(2):给状态编号：最小化：{,},{,}{,}{}{,}{}{,}{,}{,}{}{,},{},{}0123011012231323301230101====第四章P81–1(1) 按照T,S 的顺序消除左递归ε|,)(||^)(T S T TS T T a S S G '→''→→' 递归子程序： procedure S; beginif sym='a' or sym='^' then abvance else if sym='('then beginadvance;T;if sym=')' then advance;else error;endelse errorend;procedure T;beginS;'Tend;procedure 'T;beginif sym=','then beginadvance;S;'Tendend;其中:sym:是输入串指针IP所指的符号advance:是把IP调至下一个输入符号error:是出错诊察程序(2)FIRST(S)={a,^,(}FIRST(T)={a,^,(}FIRST('T)={,,ε}FOLLOW(S)={),,,#}FOLLOW(T)={)}FOLLOW('T)={)}预测分析表是LL(1)文法P81–2文法：|^||)(|*||b a E P F F F P F T T T F T E E E T E →'→''→→''→+→''→εεε(1)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,^,+,),#} (2)考虑下列产生式:'→+'→'→'→E E T T F F P E a b ||*|()|^||εεεFIRST(+E)∩FIRST(ε)={+}∩{ε}=φ FIRST(+E)∩FOLLOW(E')={+}∩{#,)}=φ FIRST(T)∩FIRST(ε)={(,a,b,^}∩{ε}=φ FIRST(T)∩FOLLOW(T')={(,a,b,^}∩{+,),#}=φ FIRST(*F')∩FIRST(ε)={*}∩{ε}=φFIRST(*F')∩FOLLOW(F')={*}∩{(,a,b,^,+,),#}=φ FIRST((E))∩FIRST(a) ∩FIRST(b) ∩FIRST(^)=φ 所以,该文法式LL(1)文法.(4)procedure E;beginif sym='(' or sym='a' or sym='b' or sym='^' then begin T; E' endelse errorendprocedure E';beginif sym='+'then begin advance; E endelse if sym<>')' and sym<>'#' then error endprocedure T;beginif sym='(' or sym='a' or sym='b' or sym='^' then begin F; T' endelse errorendprocedure T';beginif sym='(' or sym='a' or sym='b' or sym='^' then Telse if sym='*' then errorendprocedure F;beginif sym='(' or sym='a' or sym='b' or sym='^' then begin P; F' endelse errorendprocedure F';beginif sym='*'then begin advance; F' endendprocedure P;beginif sym='a' or sym='b' or sym='^'then advanceelse if sym='(' thenbeginadvance; E;if sym=')' then advance else error endelse errorend;P81–3/***************(1) 是，满足三个条件。

编译原理(第三版)答案《编译原理（第三版）》答案概念：1.编译器是一种程序，它把某种语言写的源程序翻译成另一种语言写的目标程序。

2.编译器的编写是一项复杂而耗时的任务，因为它必须处理语法和语义分析等复杂的编程语言概念。

3.编译器通常分为六个主要阶段：词法分析、语法分析、语义分析、中间代码生成、代码优化、代码生成。

4.词法分析是将源代码转换为令牌序列的过程，这些令牌构成了源代码的抽象语法树（AST）的节点。

5.语法分析是将令牌序列转换为抽象语法树的过程，这个抽象语法树表示了源代码的结构。

6.语义分析是检查源代码是否符合语言的规则，并收集类型信息的过程。

7.中间代码生成是将抽象语法树转换为中间代码的过程，这个中间代码可以在进行进一步优化和代码生成时更容易处理。

8.代码优化是优化中间代码以改进目标代码性能的过程。

9.代码生成是将中间代码转换为目标代码的过程。

10.编译器通常使用特定的数据结构和算法来处理编译的不同阶段，例如优先级队列用于语法分析，哈希表用于语义分析等。

习题答案：1.什么是编译器？它的主要功能是什么？编译器是一种程序，它把某种编程语言写的源程序翻译成另一种编程语言写的目标程序。

主要功能包括词法分析、语法分析、语义分析、中间代码生成、代码优化和代码生成。

2.编译器的基本组成部分是什么？编译器的基本组成部分包括词法分析器、语法分析器、语义分析器、中间代码生成器、优化器和代码生成器。

3.什么是编译器的中间表示？它有哪些形式？编译器的中间表示是编译器在源代码和目标代码之间的一个抽象级别，也被称作中间代码。

它可以是三地址码、抽象语法树或其他形式。

其中三地址码是最常见的中间表示形式之一，它是一种易于理解和处理的中间语言。

4.编译器的优化主要有哪些类型？编译器的优化主要可以分为两种类型：存储优化和执行效率优化。

存储优化主要关注如何减少目标代码的存储空间，而执行效率优化则关注如何提高目标代码的执行效率。

目录P36-6 (2)P36-7 (2)P36-8 (2)P36-9 (3)P36-10 (3)P36-11 (3)P64 ・ 7 (4)P64 -8 (5)P64 - 12 (5)P64 - 14 (7)P81-1 (8)P81-2 (9)P81-3 (12)P133 - 1 (12)P133 - 2 (12)P133 - 3 (14)P134 - 5 (15)P164 - 5 (19)P164 - 7 (19)P217 - 1 (19)P217 - 3 (20)P218 - 4 (20)P218 - 5 (21)P218 - 6 (22)P218 - 7 (22)P219 - 12 (22)P270 - 9 (24)P36-6(1)厶(G)是0~9组成的数字串(2)最左推导：NnNDn NDD => NDDD => DDDD =>0DDD n01DDn012Dn0127N a ND = DDn3Dn34N n NDn NDDn DDDd5DDd56Dn56$最右推导：N nNDnNTn ND7 => N27 => ND21 n N127 DI 27 n 0127N = NDdN4dD4 = 34N d ND a N8a ND8d N68d D68n568P36-7G(S)O T 113151719N T 214161810D T OINS T OIAOA T ADINP36-8文法：E^T\E + T\E-TT T F\T*F\T/FF^(E)\i最左推导：E + T^T + T^F + T^i + T^i + T^F^>i + F*F^i + i*F^i + i^iEn7'n7'*FnF*F=>j*Fnj*(E)=>i*(E + 7')ni*(7'+T)nj*(F + 7') => Z * (/ + T) => / * (/ + F) => / * (z + i)最右推导：E=> E + T=> E + T*F=> E + T*id E + F*i=> E + i*inT + i*in F + i*i=>i + i*iE=>T=>F*r=> F*F=> F*(£)=> F*(E + r)=>F*(E + F) =>F*(£ + /) =>F*(T+O=>F*(F+ /)=>F*(I+/)=>»*(«+/)语法树:/********************************T F i F i 1i+i+i*****************/P36-9句子iiiei 有两个语法树：S => iSeS => iSei => iiSei => iiiei SnlSn iiSeS => iiSei => iiieiP36-10/ **************S —TS\TT T (S)I()***************/P36-11/*************** LI: S I AC A -» aAb\ab C —> cC I £ L2: S^AB A T dA I £ B t bBc I be L3: S^AB A T aAb \ £ B —> aBb \ £• ・ ♦T F iF i1i+i*iL4:S T AIBA—> 0A11 88T1B0I A*** ************第三章习题参考答案P64-7(1)确定化:1 1最小化:{0,123,4,5}, {6}{0J2345}()= {1,3,5} {0J2345}] = {124,6}{0,123,4},{5},{6}{0,1,234}0 = {1,3,5}{0丄2,3},{4},{5},{6}{0丄2,3}()= {1,3} {0,123}] ={124}{0」},{2,3}{4},{5},{6}{0,1}。

第一章1．设计现代OS的主要目标是什么？答：（1）有效性（2）方便性（3）可扩充性（4）开放性2．OS的作用可表现在哪几个方面？答：（1）OS作为用户与计算机硬件系统之间的接口（2）OS作为计算机系统资源的管理者（3）OS实现了对计算机资源的抽象3．为什么说OS实现了对计算机资源的抽象？答：OS首先在裸机上覆盖一层I/O设备管理软件，实现了对计算机硬件操作的第一层次抽象；在第一层软件上再覆盖文件管理软件，实现了对硬件资源操作的第二层次抽象。

OS 通过在计算机硬件上安装多层系统软件，增强了系统功能，隐藏了对硬件操作的细节，由它们共同实现了对计算机资源的抽象。

4．试说明推劢多道批处理系统形成和収展的主要劢力是什么？答：主要动力来源于四个方面的社会需求与技术发展：（1）不断提高计算机资源的利用率；（2）方便用户；（3）器件的不断更新换代；（4）计算机体系结构的不断发展。

5．何谓脱机I/O和联机I/O？答：脱机I/O 是指事先将装有用户程序和数据的纸带或卡片装入纸带输入机或卡片机，在外围机的控制下，把纸带或卡片上的数据或程序输入到磁带上。

该方式下的输入输出由外围机控制完成，是在脱离主机的情况下进行的。

而联机I/O方式是指程序和数据的输入输出都是在主机的直接控制下进行的。

6．试说明推劢分时系统形成和収展的主要劢力是什么？答：推动分时系统形成和发展的主要动力是更好地满足用户的需要。

主要表现在：CPU 的分时使用缩短了作业的平均周转时间；人机交互能力使用户能直接控制自己的作业；主机的共享使多用户能同时使用同一台计算机，独立地处理自己的作业。

7．实现分时系统的关键问题是什么？应如何解决？答：关键问题是当用户在自己的终端上键入命令时，系统应能及时接收并及时处理该命令，在用户能接受的时延内将结果返回给用户。

解决方法：针对及时接收问题，可以在系统中设臵多路卡，使主机能同时接收用户从各个终端上输入的数据；为每个终端配臵缓冲区，暂存用户键入的命令或数据。

编译原理答案1-2《编译原理习题精选》第一章形式语言基础1．1文法与语言的形式定义1．2推导树与二义性文法1．3综合题第二章有限状态自动机和词法分析2．1有限状态自动机2．2词法分析2．3综合题第三章自顶向下句法分析3．1下推自动机与句法分析3．2LL(1)文法及其句法分析方法3．3递归子程序句法分析方法3．4综合题第四章自底向上句法分析4．1优先文法及其句法分析方法4．2LR(0)、SLR(1)文法及其句法分析方法4．3LR(1)、LALR(1)文法4．4综合题第五章句法制导翻译方法与中间代码生成5．1中间代码5．2属性文法与句法制导翻译5．3综合题第六章运行时存储和环境管理6．1存储分配6．2环境建立与管理6．3形实参数通讯6．4综合题第七章代码优化7．1基本块内代码优化7．2全局优化7．3综合题第八章综合习题精选第一章形式语言基础§1.1文法与语言的形式定义一、要点提示1．文法G是一个四元组G=（VT,VN,P,）其中：VT是非空有限的终结符集合，VN是非空有限的非终结符集合，P是非空有限产生式集合，VN是文法G的开始符号，集合P中的产生式的一般形式是（或::=），其中''是元符号，称为产生式的左部，称为产生式的右部。

Chomky根据产生式的不同形式，将文法分为四类。

分别是：0型文法（又称短语结构文法）；1型文法（又称上下文有关文法）；2型文法（又称上下文无关文法）；3型文法（又称正则文法）；编译程序所涉及的主要是2型与3型文法，分别用于句法分析与词法分析。

2型文法的一般形式为,VN,(VN∪VT)某。

3型文法的一般形式为a或a,、VN，aVT（或a，a）。

2．文法G[]中，是文法的开始符号，对某，若(VN∪VT)某，则称是G的一个句型，若VT某，则称是G的一个句子。

文法G[]的句子的全体所组成的集合称为G[]的语言，记作L(G[])={w|某w,wVT某}。

3．从实用的角度出发，在编译原理中所讨论的文法是被简化了的文法，即：a)文法中不含形如的产生式。

第二章 高级语言及其语法描述6．（1）L （G 6）={0,1,2,......,9}+（2）最左推导：N=>ND=>NDD=>NDDD=>DDDD=>0DDD=>01DD=>012D=>0127 N=>ND=>DD=>3D=>34N=>ND=>NDD=>DDD=>5DD=>56D=>568 最右推导：N=>ND =>N7=>ND7=>N27=>ND27=>N127=>D127=>0127 N=>ND=>N4=>D4=>34N=>ND=>N8=>ND8=>N68=>D68=>5687．【答案】Ｇ：S →ABC | AC | CA →1|2|3|4|5|6|7|8|9B →BB|0|1|2|3|4|5|6|7|8|9C →1|3|5|7|98．（1）最左推导：E=>E+T=>T+T=>F+T=>i+T=>i+T*F=>i+F*F=>i+i*F=>i+i*iE=>T=>T*F=>F*F=>i*F=>i*(E)=>i*(E+T)=>i*(T+T)=>i*(F+T)=>i*(i+T)=>i*(i+F)=> i*(i+i) 最右推导：E=>E+T=>E+T*F=>E+T*i=>E+F*i=>E+i*i=>T+i*i=>F+i*i=>i+i*iE=>T=>T*F=>T*(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)9．证明：该文法存在一个句子iiiei 有两棵不同语法分析树，如下所示，因此该文法是二义的。

第2章习题2-1 设有字母表A1 ={a,b,c,…,z}，A2 ={0,1,…,9}，试回答下列问题：(1) 字母表A1上长度为2的符号串有多少个？(2) 集合A1A2含有多少个元素？(3) 列出集合A1(A1∪A2)*中的全部长度不大于3的符号串。

2-2 试分别构造产生下列语言的文法：（1）{a n b n|n≥0}；（2）{a n b m c p|n,m,p≥0}；（3）{a n#b n|n≥0}∪{c n#d n|n≥0}；（4）{w#w r# | w∈{0,1}*,w r是w的逆序排列}；（5）任何不是以0打头的所有奇整数所组成的集合；（6）所有由偶数个0和偶数个1所组成的符号串的集合。

2-3 试描述由下列文法所产生的语言的特点：（1）S→10S0S→aA A→bA A→a（2）S→SS S→1A0A→1A0A→ε（3）S→1A S→B0A→1A A→CB→B0B→C C→1C0C→ε（4）S→aSS S→a2-4 试证明文法S→AB|DC A→aA|a B→bBc|bc C→cC|c D→aDb|ab为二义性文法。

2-5 对于下列的文法S→AB|c A→bA|a B→aSb|c试给出句子bbaacb的最右推导，并指出各步直接推导所得句型的句柄；指出句子的全部短语。

2-6 化简下列各个文法(1) S→aABS|bCACd A→bAB|cSA|cCC B→bAB|cSB C→cS|c(2) S→aAB|E A→dDA|e B→bE|fC→c AB|dSD|a D→eA E→fA|g(3) S→ac|bA A→c BC B→SA C→bC|d2-7 消除下列文法中的ε-产生式(1) S→aAS|b A→cS|ε(2) S→aAA A→bAc|dAe|ε2-8 消除下列文法中的无用产生式和单产生式(1) S→aB|BC A→aA|c|aDb B→DB|C C→b D→B(2) S→SA|SB|A A→B|(S)|( ) B→[S]|[ ](3) E→E+T|T T→T*F|F F→P↑F|P P→(E)|i第2章习题答案2-1 答：(1) 26*26=676(2) 26*10=260(3) {a,b,c,...,z, a0,a1,...,a9, aa,...,az,...,zz, a00,a01,...,zzz},共有26+26*36+26*36*36=34658个2-2 解：(1) 对应文法为G(S)=({S},{a,b},{ S→ε| aSb },S)(2) 对应文法为G(S)=({S,X,Y},{a,b,c},{S→aS|X,X→bX|Y,Y→cY|ε },S)(3)对应文法为G(S)=({S,X,Y},{a,b,c,d,#}, {S→X,S→Y,X→aXb|#,Y→cYd|# },S)(4) G(S)=({S,W,R},{0,1,#}, {S→W#, W→0W0|1W1|# },S)(5) G(S)=({S,A,B,I,J},{0,1,2,3,4,5,6,7,8,9},{S→J|IBJ,B→0B|IB|ε, I→J|2|4|6|8, J→1|3|5|7|9},S)(6)对应文法为S→0A|1B|ε，A→0S|1C，B→0C|1S，C→1A|0B2-3 解：(1) 本文法构成的语言集为：L(G)={(10)n ab m a0n|n,m≥0}。

最左推导:
E E T T T F T i T i T *F i F *F i i*F i i*i E T T * F F * F i * F i *(E) i *(E T) i *(T T) i *(F T) i *(i T) i *(i F) i *(i i)
C
C
D
D
E
D
E
C
F
F
E
D
(2) 1(1010*|1(010)*1)*0
I {X} {A,B,C} {y} {D,H,I,L} {E,J} {B,C} {B,C,F,G,K} {B,C,G,I,L,y} {B,C,G,J,y} {D,H,I,K,L} {E,J,y} {E,I,J,L} {J}
I0 Ф {y} Ф {E,J} Ф {y} {B,C,G,I,L,y} {B,C,G,J,y} {B,C,G, y} {E,I,J,L} Ф {J} Ф
显然不可再划分，则最简的 DFA 即为：
15 给定右线性文法 G： S→0S|1S|1A|0B A→1C|1 B→0C|0 C→0C|1C|1|0
求出一个与 G 等价的左线性文法。
解：1 由右线性文法构造 NFA：
2 从 NFA 中构造左线性文法： F→A1|B0|C0|C1 A→S1|1 B→S0|0 C→C0|C1|A1|B0
第二章 高级语言及其语法描述 4．令+、*和↑代表加，乘和乘幂，按如下的非标准优先级和结合性质的约定，计算 1+1*2↑2*1 ↑2 的值： （1） 优先顺序（从高至低）为+，*和↑，同级优先采用左结合。 （2） 优先顺序为↑，+，*，同级优先采用右结合。 解：（1）1+1*2↑2*1↑2=2*2↑1*1↑2=4↑1↑2=4↑2=16

编译原理课后答案（第三版蒋立源康慕宁编）第一章习题解答1解：源程序是指以某种程序设计语言所编写的程序。

目标程序是指编译程序（或解释程序）将源程序处理加工而得的另一种语言（目标语言）的程序。

翻译程序是将某种语言翻译成另一种语言的程序的统称。

编译程序与解释程序均为翻译程序，但二者工作方法不同。

解释程序的特点是并不先将高级语言程序全部翻译成机器代码，而是每读入一条高级语言程序语句，就用解释程序将其翻译成一段机器指令并执行之，然后再读入下一条语句继续进行解释、执行，如此反复。

即边解释边执行，翻译所得的指令序列并不保存。

编译程序的特点是先将高级语言程序翻译成机器语言程序，将其保存到指定的空间中，在用户需要时再执行之。

即先翻译、后执行。

2解：一般说来，编译程序主要由词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、代码优化程序、目标代码生成程序、信息表管理程序、错误检查处理程序组成。

3解：C语言的关键字有：auto break case char const continue default do double else enum extern float for goto if int long register return short signed sizeof static struct switch typedef union unsigned void volatile while。

上述关键字在C语言中均为保留字。

4解：C语言中括号有三种：{}，[]，（）。

其中，{}用于语句括号；[]用于数组；（）用于函数（定义与调用）及表达式运算（改变运算顺序）。

C语言中无END关键字。

逗号在C 语言中被视为分隔符和运算符，作为优先级最低的运算符，运算结果为逗号表达式最右侧子表达式的值（如：(a,b,c,d)的值为d）。

5略第二章习题解答1.（1）答：26*26=676（2）答：26*10=260（3）答：{a,b,c,...,z,a0,a1,...,a9,aa,...,az,...,zz,a00,a01,...,zzz},共26+26*36+26*36*36=34658个2.构造产生下列语言的文法（1）{anbn|n≥0}解：对应文法为G(S) = ({S},{a,b},{ S→ε| aSb },S)（2）{anbmcp|n,m,p≥0}解：对应文法为G(S) = ({S,X,Y},{a,b,c},{S→aS|X,X→bX|Y,Y→cY|ε},S)（3）{an # bn|n≥0}∪{cn # dn|n≥0}解：对应文法为G(S) = ({S,X,Y},{a,b,c,d,#}, {S→X, S→Y,X→aXb|#,Y→cYd|# },S)（4）{w#wr# | w?{0,1}*,wr是w的逆序排列}解：G(S) = ({S,W,R},{0,1,#}, {S→W#, W→0W0|1W1|# },S)（5）任何不是以0打头的所有奇整数所组成的集合解：G(S) = ({S,A,B,I,J},{-,0,1,2,3,4,5,6,7,8,9},{S→J|IBJ,B→0B|IB|e, I→J|2|4|6|8, Jà1|3|5|7|9},S)（6）所有偶数个0和偶数个1所组成的符号串集合解：对应文法为S→0A|1B|e，A→0S|1C B→0C|1S C→1A|0B3.描述语言特点（1）S→10S0S→aAA→bAA→a解：本文法构成的语言集为：L(G)={(10)nabma0n|n, m≥0}。

(3) 再考虑：仅由1组成的串，或 若干1打头的串。
最终的正规式： 1* | 1*(01|0)* = 1*(01|0)*
© 西安电子科技大学 · 软件学院
5
1. 根据模式写出正规式
习题2.4 (2) 所有不含有子串 011 的01串 思路2：考虑包含 011 的串，然后构造没有011的串 ① 含有 子串 011 的最简单的串：
© 西安电子科技大学 · 软件学院
？
| (01|10) (00|11)* (01|10) )*
4
1. 根据模式写出正规式
习题2.4 (2) 所有不含有子串 011 的01串 思路1：简单例子，观察规律 (1) 最简单的串： 0 , 1, 11, 00, 10, 01, 010, …
(2) 上述各串重复： (0 | 00 | 01 | 010 )* = (01 | 0)*
© 西安电子科技大学 · 软件学院
7
2.依据NFA/DFA，给出正规式
思路1： 回顾“正规式 与 FA的关系”
正规集 描述 正规式 识别 有限自动机
正规式、FA是从两个不同的侧面表示一个集合(即正 规集)。所以，根本的方法是以正规集为桥梁， - 先分析清楚 FA 识别的集合之结构特征， - 然后再设计此集合的正规式。
© 西安电子科技大学 · 软件学院
2
1. 根据模式写出正规式
一般思路：（1）分析题意 （2）列举一些最简单的例子 （3）寻找统一规律*,考虑所有可能情况**
习题2.4 (1) 由偶数个0和奇数个1构成的01串
解：① 最简单的串有 0个0和1个1组成的串： 1 2个0和1个1组成的串：010 ，001，100 ② 在上述串的中间、两头添加偶数个0和/或偶数个1，即可 得到满足题意的其他串。 设偶数个0/偶数个1组成的串，可用正规式 A 表示，则最 终正规式： A1A | A0A1A0A

2.1 写出下列文法所确定的语言：①、文法G = （{D}，{0,1,2,3,4,5,6,7,8,9}，P，D）其中，P={D→0|1|2|3|4|5|6|7|8|9}；该文法定义的是0到9这10个数字{0,1,2,3,4,5,6,7,8,9}；②、文法G = （{B，L，D}，{0,1,2,3,4,5,6,7,8，9}，P，B）；其中，P = {B→D|L，L→1|2|3|4|5|6|7|89，D→0|L}；该文法定义的是0到9这10个数字{0,1,2,3,4,5,6,7,8,9}；③、文法G=（{S，A}，{a，b}，P，S）其中，P={S→Aa，A→bA|a}。

该文件定义的是{b a a2|n≥0}；2.2①因为语言的句子要求由3的整数倍的a组成，所以在构造产生式时，要保证每次产生的a 的个数是3，得到文法G[s]:s→aaa|Saaa②因为符号串中a、b的个数没有直接关系，所以，将句子分成两部分：aaa和b2m-1，分别进行构造，然后再合并，可由产生式A→a|aA得到aa,而由产生式B→b|bbB得到b2m-1,由于n≥1，m≥1，所以得到文法G【s】：S→ABA →a|aAB→b|bbB③因为句子中a和B的个数一样多，且a全部在句子的前半部分，b全部在句子的后半部分，所以在构造产生式时，可让a和b对称出现，得文法G【s】：s→aSb|ab④因为句子中a、b、c的个数没有直接关系，所以分别构造生成an。

Bmck的产生式，然后再合成，可由产生式a→aA|。

得到bm，再有产生式c→cc|、得到ck，⑤文法为GS：S→（+|-）（ABC|2|4|6|8）|0C→02468B→BAB0A→123456789⑥能被5整除的整数的末尾数必定是0或5，所以只要保证生成的整数末位数字是0或5即可，据此，构造描述能被5整除集合的文法如下：GS：S→（+|-）A（0|5）A→0123456789如果还要求整数除0外，均不以0开头，则文法为GS：S→（+|-）A（0|5）（0|5）⑦由于文法的句子a∈{a，b}，因此文法的句子可分解为两种情形；以a打头的符号串以b打头的符号串于是只要在构造产生式时保证每次产生相同个数的a和b即可，可以构造文法如下LGS：S →aSbbSaabSbaSSba2.40型文法2.5P={S→aD|eE，D→bf，F→dB，A→bc，B→d}2.6、①3274的最左推导为：N→ND→NDD→NDDD→DDDD→3DDD→32DD→327D→3274①3274的最右推导为：N→ND→N4→ND4→N74→ND74→N274→D274→3274②65173的最左推导为：N→ND→NDD→NDDD→DDDDD→6DDDD→65DDD→651DD→6517365173的最右推导为：N→ND→N3→ND3→ND73→ND73→ND73→ND173→651732.7、要判断文法是否具有二义性，只要判断文法是否定义有这样的句子，该句子对应着两颗以上的语法树，或者说有两个以上不同的最右推导，或者说在对该句子进行规范规约的过程中，其规范句型的句柄不唯一。