第1 章1、编译过程包括哪几个主要阶段及每个阶段的功能。

答案：编译过程包括词法分析、语法分析、语义分析和中间代码生成、优化、目标代码生成5 个阶段。

词法分析的功能是对输入的高级语言源程序进行词法分析，识别其中的单词符号，确定它们的种类，交给语法分析器，即把字符串形式的源程序分解为单词符号串形式。

语法分析的功能是在词法分析结果的基础上，运用语言的语法规则，对程序进行语法分析，识别构成程序的各类语法范畴及它们之间的层次关系，并把这种层次关系表达成语法树的形式。

词义分析和中间代码生成的功能是在语法分析的基础上，对程序进行语义分析，“理解”其含义，产生出表达程序语义的内部表达形式（中间代码）。

优化的功能是按照等价变换的原则，对语义分析器产生的中间代码序列进行等价变换，删除其中多余的操作，对耗时耗空间的代码进行优化，以期最后得到高效的可执行代码。

目标代码生成的功能是把优化后的中间代码变换成机器指令代码，得到可在目标机器上执行的机器语言程序。

第2 章1、写一上下文无关文法G，它能产生配对的圆括号串（如：(),(()),()(())等，甚至包括0 对括号）文法为：S→(L)|LS|L L→S| ε2 、已知文法G ：E→E+T|E-T|TT→T*F|T/F|F F→(E) |i（1）给出i+i*i,i*(i-i)的最左推导，最右推导以及语法树。

（2）i-i+i 哪个算符优先。

【解答】（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)i+i*i 以及i*(i-i)的语法树如下所示：（2）i-i+i 的语法树如下图所示。

从上图的语法树可知：“-”的位置位于“+”的下层，也就是前面两个i 先进行“-”运算，再与后面的i 进行“+”运算，所以“-”的优先级高于“+”的优先级。

3 、文法G: E→ET+|T T→TF*|FF→FP↑|P P→E|i（1）试证明符号串TET+*i↑是G 的一个句型(要求画出语法树).（2）写出该句型的所有短语,直接短语和句柄.【解答】（1）采用最右推导：E⇒T⇒F⇒ FP↑⇒ Fi↑⇒ Pi↑⇒ Ei↑⇒ Ti↑⇒ TF*i↑⇒ TP*i↑⇒ TE*i↑⇒ TET+*i↑语法树如下图所示。

从文法G 的起始符号出发，能够推导出符号串TET+*i↑，所以给定符号串是文法G的句型。

(2) 该句型的短语有：ET+,TET+*,i ,TET+*i↑直接短语有：ET+, i句柄是：ET+4、已知文法G：S→iSeS|iS|i ，该文法是二义文法吗？为什么？【解答】该文法是二义文法。

因为对于句子iiiei 存在两种不同的最左推导：第 1 种推导：S⇒ iSeS⇒ iiSeS⇒ iiieS⇒ iiiei第2种推导：S⇒iS⇒iiSeS⇒iiieS⇒iiiei第3 章1、用正规式描述下列正规集：（1）C 语言的十六进制整数；（2）以ex 开始或以ex 结束的所有小写字母构成的符号串；（3）十进制的偶数。

【解答】（1）C 语言十六进制整数以0x 或者0X 开头，所以一般形式应该为（+|-|ε）(0x|0X)AA*，其中前面括号表示符号，可以有正号、负号，也可以省略（用ε表示）默认是正数，A 表示有资格出现在十六进制整数数位上的数字，AA*表示一位或者多位（一个或者多个数字的串）。

下面进一步确定A的取值，A应该为（0|1|2|3|4|5|6|7|8|9|a|b|c|d|e|f|A|B|C|D|E|F ），所以整个正规式应该为：(+|-|ε)(0x|0X)(0|1|2|3|4|5|6|7|8|9|a|b|c|d|e|f|A|B|C|D|E|F)(0|1|2|3|4|5|6|7|8|9|a|b|c|d|e|f|A |B|C|D|E|F)*也可以写成：A：0|1|2|3|4|5|6|7|8|9|a|b|c|d|e|f|A|B|C|D|E|F （+|-|ε）(0x|0X)AA*从上面看出，在用正规式描述正规集时，如本例题所示，采用自顶向下，逐步求精的方法，先描述正规集的一般规律，再对细节进行描述。

（2）以ex 开始的小写字母符号串应该为ex（小写字母）*，以ex 结尾的小写字母符号串应该为（小写字母）*ex，所以整个正规集描述为：ex（小写字母）*|（小写字母）*ex。

（3）十进制偶数个位为0、2、4、6、8，前面其他数位为0、1、2、3、4、5、6、7、8、9，因此整个正规集表示为（+|-|ε）A*B，其中A表示（0|1|2|3|4|5|6|7|8|9），B表示（0|2|4|6|8），所以表示整个正规集的正规式为：(+|-|ε)(0|1|2|3|4|5|6|7|8|9)*(0|2|4|6|8)2、构造下列正规式所对应的确定有限自动机（需要化简）：（1）(aa|b)*(a|bb)*（2）ab*c*d（3）((a|b)*| bb)*【解答】（1）首先从该正规式出发，构造等价的非确定有限自动机，如图所示。

构造(aa|b)*(a|bb)*等价非确定有限自动机得到了非确定有限自动机后，下面用子集法进行确定化，如下表所示。

状态子集 a B{X, 1, 0, 2,Y} {3, 2, Y} {1, 4, 0,2,Y}{3, 2, Y} {1, 2, 0, Y} {4}{1, 4, 0,2,Y} {3, 2, Y} {1, 2, 4, 0,Y}{1, 2, 0, Y} {3, 2, Y} {1, 4, 0, 2,Y}{4} - {2, Y}{2, Y} {2, Y} {4}将状态子集重新命名，得到如下表所示的状态转换矩阵：状态 a b0 初态，终态 1 21 终态 3 42 终态 1 23 终态 1 24 - 55 终态 5 4左上角{X}的ε闭包所对应的状态是确定有限自动机的初始状态，含有原非确定有限自动机终止状态Y 的状态子集所对应的状态是确定有限自动机的终止状态。

这样，就得到如下图所示的确定有限自动机。

首先，状态集划分为终态集{0, 1, 2, 3, 5}和非终态集{4}。

其中第二个集合已经无法进一步划分。

下面考察第一个集合，看是否需要划分为不同的集合。

我们看到，在该集合中，状态1 和5 在输入b的情况下，后继状态为4，而0，2，3在相同输入的情况下，后继状态都为2，这两组状态在相同输入的情况下，后继状态分别属于当前划分的不同子集，说明它们是可以区分的，应该将{0, 1, 2, 3, 5, 6}划分为两个子集：{0, 2, 3}和{1, 5}，这样，得到状态集合的新划分：{4}, {0, 2, 3}, {1, 5}下面考察，{0, 2, 3}和{1, 5}是否可以进一步划分。

考察{0, 2, 3}：在输入b 的情况下，它们的后继状态都是2 号状态，无法确定它们是可区分的；在输入a 的情况下，0 的后继状态是1，2 和3 的后继状态是1，说明1 与2 和3 是等价的，因此删除2 个状态。

同样考察{1,5}：在输入b 的情况下，它们的后继状态是4号状态，无法确定它们是可区分的；在输入a 的情况下，1 的后继状态是3，5 的后继状态是5，而状态3 同状态5 不属于同一个集合，因此1 与5 是可区分的，将1 和5 分开，于是得到下面的划分：{4}, {0 , 2, 3}, {1}, {5}。

经过考察，发现其中的每个状态子集都不可能进一步划分了，这样就得到了最后的划分。

对每个状态子集，选一个状态作为代表，删除其余状态，把导向被删除状态的边改成导向所选择的代表状态，就得到如下图所示的化简的确定有限自动机。

（2）首先从该正规式出发，构造等价的非确定有限自动机，如下图所示。

得到了非确定有限自动机后，下面用子集法进行确定化，如下表所示。

状态子集 a b c D {X } {1,4,2,5,3} Φ Φ Φ{1,4,2,5,3} Φ {4,2,5,3} {5,3} {Y} {4,2,5,3} Φ {4,2,5,3} {5,3} {Y} {5,3} Φ Φ {5,3} {Y} { Y} Φ Φ Φ Φ将状态子集重新命名，得到下面的状态转换矩阵如下表所示。

状态 A b c d0 初态 1 - - -1 -23 42 - 23 43 - - 3 44 终态- - - -左上角{X}的ε 闭包所对应的状态是确定有限自动机的初始状态，含有原非确定有限自动机终止状态Y 的状态子集所对应的状态是确定有限自动机的终止状态。

这样，就得到如下图所示的正规式ab*c*d 的未化简的确定有限自动机。

下面对确定有限自动机进行最小化：首先，状态集划分为非终态集{0, 1, 2,3}和终态集{4}。

其中第2 个集合无法进一步划分。

下面考察第1 个集合{0, 1, 2, 3}，看是否需要划分为不同的集合。

在该集合中，状态0 只能接受a，应该将{0, 1, 2, 3}划分为两个子集：{0}和{1,2, 3}，得到状态集合的新划分：{4}, {0}, {1, 2, 3}下面考察{1, 2, 3}是否可以进一步划分。

状态1,2 可以接受字符b,c,d，状态3 能接受c,d，所以应该将{1, 2, 3}分解为{1, 2}和{3}。

于是得到新的划分：{0},{1,2}, {3},{4}经过考察，发现其中的每个状态子集都不可能进一步划分了，得到了最后的划分。

对每个状态子集，选一个状态作为代表，删除其余状态，把导入被删除状态的边改成导向所选择的代表状态，得到如下图所示的正规式ab*c*d的的化简后的确定有限自动机。

（3）首先从该正规式出发，构造等价的非确定有限自动机，如下图所示。

得到了非确定有限自动机后，下面用子集法进行确定化，如下表所示。

状态子集 a b{X,1,3,Y } {3,1,Y} {2,3,1,Y} {3,1,Y} {3,1,Y} {2,3,1,Y} {2,3,1,Y} {3,1,Y} {2,3,1,Y} 将状态子集重新命名，得到下面的状态转换矩阵，如下表所示。

状态 a b0 初态终态 1 21 终态 1 22 终态 1 2左上角{X}的ε 闭包所对应的状态是确定有限自动机的初始状态，含有原非确定有限自动机终止状态Y 的状态子集所对应的状态是确定有限自动机的终止状态。