《编译原理习题大全》由会员分享，可在线阅读，更多相关《编译原理习题大全（57页珍藏版）》请在金锄头文库上搜索。
1、第1章1、编译过程包括哪几个主要阶段及每个阶段的功能。答案：编译过程包括词法分析、语法分析、语义分析和中间代码生成、优化、目标代码生成5个阶段。词法分析的功能是对输入的高级语言源程序进行词法分析，识别其中的单词符号，确定它们的种类，交给语法分析器，即把字符串形式的源程序分解为单词符号串形式。语法分析的功能是在词法分析结果的基础上，运用语言的语法规则，对程序进行语法分析，识别构成程序的各类语法范畴及它们之间的层次关系，并把这种层次关系表达成语法树的形式。词义分析和中间代码生成的功能是在语法分析的基础上，对程序进行语义分析，“理解”其含义，产生出表达程序语义的内部表达形式（中间代码）。优化的功能是
2、按照等价变换的原则，对语义分析器产生的中间代码序列进行等价变换，删除其中多余的操作，对耗时耗空间的代码进行优化，以期最后得到高效的可执行代码。目标代码生成的功能是把优化后的中间代码变换成机器指令代码，得到可在目标机器上执行的机器语言程序。第2章1、写一上下文无关文法G，它能产生配对的圆括号串（如：(),(),()()等，甚至包括0对括号）文法为：S(L)|LS|L LS| e2、已知文法G：EE+T|E-T|T TT*F|T/F|F F (E) |i（1）给出i+i*i,i*(i-i)的最左推导，最右推导以及语法树。（2）i-i+i 哪个算符优先。【解答】（1）最左推导：EE+TT+T F+T
3、 i+T i+T*F i+F*F i+i*F i+i*iETT*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)最右推导：EE+TE+T*F E+T*i E+F*i E+i*i T+i*i F+i*i i+i*iETT*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先进行“-”
4、运算，再与后面的i进行“+”运算，所以“-”的优先级高于“+”的优先级。3、文法G: EET+|T TTF*|F FFP|P PE|i（1）试证明符号串TET+*i是G的一个句型(要求画出语法树).（2）写出该句型的所有短语,直接短语和句柄.【解答】（1）采用最右推导：ETF 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：SiSeS|iS|i ，该文法是二
5、义文法吗？为什么？【解答】该文法是二义文法。因为对于句子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开头，所以一般形式应该为（+|-|e）(0x|0X)AA*，其中前面括号表示符号，可以有正号、负号，也可以省略（用e表示）默认是正数，A表示有资格出现在十六进制整数数位上的数字，AA*表示一位或者多位（一个或
6、者多个数字的串）。下面进一步确定A的取值，A应该为（0|1|2|3|4|5|6|7|8|9|a|b|c|d|e|f|A|B|C|D|E|F），所以整个正规式应该为：(+|-|e)(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（+|-|e）(0x|0X)AA*从上面看出，在用正规式描述正规集时，如本例题所示，采用自顶向下，逐步求精的方法，先描述正规
7、集的一般规律，再对细节进行描述。（2）以ex开始的小写字母符号串应该为ex（小写字母）*，以ex结尾的小写字母符号串应该为（小写字母）*ex，所以整个正规集描述为：ex（小写字母）*|（小写字母）*ex。（3）十进制偶数个位为0、2、4、6、8，前面其他数位为0、1、2、3、4、5、6、7、8、9，因此整个正规集表示为（+|-|e）A*B，其中A表示（0|1|2|3|4|5|6|7|8|9），B表示（0|2|4|6|8），所以表示整个正规集的正规式为：(+|-|e)(0|1|2|3|4|5|6|7|8|9)*(0|2|4|6|8)2、构造下列正规式所对应的确定有限自动机（需要化简）：（1）(a
8、a|b)*(a|bb)*（2）ab*c*d（3）(a|b)*| bb)*【解答】（1）首先从该正规式出发，构造等价的非确定有限自动机，如图所示。构造(aa|b)*(a|bb)*等价非确定有限自动机得到了非确定有限自动机后，下面用子集法进行确定化，如下表所示。状态子集aBX, 1, 0, 2, Y3, 2, Y1, 4, 0,2, Y3, 2, Y1, 2, 0, Y41, 4, 0,2, Y3, 2, Y1, 2, 4, 0, Y1, 2, 0, Y3, 2, Y1, 4, 0, 2, Y4-2, Y2, Y2, Y4将状态子集重新命名，得到如下表所示的状态转换矩阵：状态ab0 初态，终态12
9、1 终态342终态123终态124-55 终态54左上角X的e闭包所对应的状态是确定有限自动机的初始状态，含有原非确定有限自动机终止状态Y的状态子集所对应的状态是确定有限自动机的终止状态。这样，就得到如下图所示的确定有限自动机。首先，状态集划分为终态集0, 1, 2, 3, 5和非终态集4。其中第二个集合已经无法进一步划分。下面考察第一个集合，看是否需要划分为不同的集合。我们看到，在该集合中，状态1和5在输入b的情况下，后继状态为4，而0，2，3在相同输入的情况下，后继状态都为2，这两组状态在相同输入的情况下，后继状态分别属于当前划分的不同子集，说明它们是可以区分的，应该将0, 1, 2, 3
10、, 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 ,
11、2, 3, 1, 5。经过考察，发现其中的每个状态子集都不可能进一步划分了，这样就得到了最后的划分。对每个状态子集，选一个状态作为代表，删除其余状态，把导向被删除状态的边改成导向所选择的代表状态，就得到如下图所示的化简的确定有限自动机。（2）首先从该正规式出发，构造等价的非确定有限自动机，如下图所示。得到了非确定有限自动机后，下面用子集法进行确定化，如下表所示。状态子集a b cDX 1,4,2,5,3FFF1,4,2,5,3F4,2,5,35,3Y4,2,5,3F4,2,5,35,3Y5,3FF5,3Y YFFFF将状态子集重新命名，得到下面的状态转换矩阵如下表所示。状态Abcd0 初态1-
12、1 -2342-2343-344 终态-左上角X的e 闭包所对应的状态是确定有限自动机的初始状态，含有原非确定有限自动机终止状态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是否
13、可以进一步划分。状态1,2可以接受字符b,c,d，状态3能接受c,d，所以应该将1, 2, 3分解为1, 2和3。于是得到新的划分：0,1, 2, 3,4经过考察，发现其中的每个状态子集都不可能进一步划分了，得到了最后的划分。对每个状态子集，选一个状态作为代表，删除其余状态，把导入被删除状态的边改成导向所选择的代表状态，得到如下图所示的正规式ab*c*d的的化简后的确定有限自动机。（3）首先从该正规式出发，构造等价的非确定有限自动机，如下图所示。得到了非确定有限自动机后，下面用子集法进行确定化，如下表所示。状态子集a bX,1,3,Y 3,1,Y2,3,1,Y3,1,Y3,1,Y2,3,1,Y
14、2,3,1,Y3,1,Y2,3,1,Y将状态子集重新命名，得到下面的状态转换矩阵，如下表所示。状态ab0 初态 终态121终态122终态12左上角X的e 闭包所对应的状态是确定有限自动机的初始状态，含有原非确定有限自动机终止状态Y的状态子集所对应的状态是确定有限自动机的终止状态。得到如下图所示的正规式(a|b)*| bb)*的未化简的确定有限自动机。下面对确定有限自动机进行最小化：首先，状态集划分为非终态集F和终态集0,1,2。考察集合0,1, 2，发现其中的每个状态子集都不可能进一步划分，得到最后的划分：0,1,2。对该状态子集，选一个状态作为代表，删除其余状态，把导入被删除状态的边改成导向所
