编译原理习题大全.doc

第1章1、编译过程包括哪几个主要阶段及每个阶段的功能。答案：编译过程包括词法分析、语法分析、语义分析和中间代码生成、优化、目标代码生成5个阶段。词法分析的功能是对输入的高级语言源程序进行词法分析，识别其中的单词符号，确定它们的种类，交给语法分析器，即把字符串形式的源程序分解为单词符号串形式。语法分析的功能是在词法分析结果的基础上，运用语言的语法规则，对程序进行语法分析，识别构成程序的各类语法范畴及它们之间的层次关系，并把这种层次关系表达成语法树的形式。词义分析和中间代码生成的功能是在语法分析的基础上，对程序进行语义分析，“理解”其含义，产生出表达程序语义的内部表达形式（中间代码）。优化的功能是按照等价变换的原则，对语义分析器产生的中间代码序列进行等价变换，删除其中多余的操作，对耗时耗空间的代码进行优化，以期最后得到高效的可执行代码。目标代码生成的功能是把优化后的中间代码变换成机器指令代码，得到可在目标机器上执行的机器语言程序。第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 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先进行“-”运算，再与后面的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 ，该文法是二义文法吗？为什么？【解答】该文法是二义文法。因为对于句子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*表示一位或者多位（一个或者多个数字的串）。下面进一步确定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*从上面看出，在用正规式描述正规集时，如本例题所示，采用自顶向下，逐步求精的方法，先描述正规集的一般规律，再对细节进行描述。（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）(aa|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 初态，终态121 终态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, 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 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-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是否可以进一步划分。状态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,Y2,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。对该状态子集，选一个状态作为代表，删除其余状态，把导入被删除状态的边改成导向所选择的代表状态，得到如下图所示的正规式(a|b)*| bb)*的化简后的确定有限自动机。 第4章1、自上而下与自下而上的语法分析策略有什么区别？【解答】自上而下语法分析是从文法开始符号出发，不断使用文法的产生式进行推导，分析成功的标志是推导出待分析的终结符号串。而自下而上语法分析是从待分析的终结符号串出发，使用产生式规则，对当前的符号串（开始时是待分析的终结符号串），寻找其中的子串b，利用规则Ab，将b替换成A，得到新的符号串。分析过程的主要操作是归约。分析成功的标志是从给定的终结符号串出发，经过不断归约，得到文法起始符号。2、对下列文法，构造预测分析表（如果含有左递归，则消除左递归；如果存在公共左因子，则提取公共左因子），如果是LL(1)文法，则举例说明预测分析程序对句子进行语法分析的过程：（1）SAS | bASA | a（2）SAAAb | bBaBaAc | a | aAb（3）SAaAb | BbBaAeBe解答：（1）该文法中含有左递归，消除后得到如下的文法：SAS | bAbAB | aBBSAB | e该文法中没有公共左因子。预测分析表为如下表所示。SAS | b,ASA | a的预测分析表aB#SSASSASS bAA aBAbABBBSABB eBSABB e由于预测分析表中含有多重入口，因此给定文法不是LL(1)文法。（2）该文法存在左递归，消除后文法变成：SAAbBaCCbC | eBaAc | a | aAb关于B的规则中，不同候选之间存在公共左因子，提取后得到：SAAbBaCCbC | eBaDDAE | eEc | b构造出的预测分析表如下表所示。SA,AAb | bBa,BaAc | a | aAb的预测分析表aBC#SSAAA bBaCCCbCC eC eC eBBaDDD eDAEEE bEc预测分析表中含有多重入口，因此，给定文法不是LL(1)文法。（3）该文法不含左递归，也无需提取公共左因子（没有公共左因子）。下面计算FIRST集合和FOLLOW集合：对于SAaAb | BbBa，每个候选的FIRST集合分别为FIRST(AaAb) = a，FIRST(BbBa) = b。对于Ae，其惟一候选的FIRST集合为FIRST(e) = e。对于Be，其惟一候选的FIRST集合为FIRST(e) = e。每个非终结符的FOLLOW集合分别为FOLLOW(S) = #，FOLLOW(A) = a, b，FOLLOW(B) = a, b。因此，构造出如下表所示的预测分析表：SAaAb|BbBa,Ae,Be的预测分析表aB#SSAaAbS BbBaAAeAeBBeBe预测分析表中不含多重入口，因此，给定文法为LL(1)文法。第5章1、给定算符文法：Sa | | (T)TT,S | S（1）构造算符优先关系表；（2）该文法是否为算符优先文法？为什么？如果是算符优先文法，请给出句子(a, (a, a)的算符优先分析过程（指出堆栈和缓冲区的变化）。【解答】（1）首先计算每个非终结符的FIRSTVT和LASTVT集合。FIRSTVT(S) = a, , ( FIRSTVT(T) = ，, a, , (LASTVT(S) = a, , )LASTVT(T) = ，, a, , )下面考察每个产生式的右部，寻找两个终结符相邻或者两个终结符中间夹一个非终结符，终结符后跟非终结符，以及非终结符后跟终结符的情况。针对该文法，得到：l (T)，两个终结符中间夹一个非终结符，据此得到 ( = )。l ( T，终结符后跟非终结符，据此得到(FIRSTVT(T)中的每个元素，即( ，, ( a, ( , ( )，即， ), a ), ), ) )。l T, ，非终结符后跟终结符，据此得到LASTVT(T)中的每个元素 ,，即，, a ，, ，,) ，。l ,S ，终结符后跟非终结符，据此得到,FIRSTVT(S),即,a，, ，,(,)# b， a = b， a b即优先关系表中不存在多重入口。下面使用得到的优先关系表，利用算符优先分析算法，对句子(a, (a, a)进行语法分析。经过初始化，堆栈栈顶只有#，缓冲区指针指向句子第一个终结符，并且在句子末尾附加了#作为句子结束标志。堆栈和缓冲区具有如下的形式：（1）由于#( ，所以应该移进，得到如下的情形：（2）此时，栈顶第一个终结符为（，当前输入符号为a，由于(, ，所以应该在栈顶寻找最左素短语，对其进行归约。由于此时堆栈中(a ，所以最左素短语就是a本身，将其归约为非终结符，用N表示，得到：（4）此时栈顶第一个终结符为(，当前输入符号仍然为, ，由于(, ，所以应该移进，堆栈和缓冲区变成如下的情形：（5）此时栈顶第一个终结符为, ，当前输入符号为 (，由于, ( ，所以还是采取移进动作，得到： （6）此时栈顶第一个终结符为(，当前输入符号为a，由于( , ，所以应该在栈顶找最左素短语，对其进行归约。由于此时堆栈中(a ，所以a本身是最左素短语，对其进行归约，得到：（8）此时栈顶第一个终结符为(，当前输入符号为, ，由于(, ，所以应该移进：（9）此时缓冲区第一个终结符为,，输入符号为a，由于,)，所以应该归约。由于,)，所以应该进行归约。由于堆栈中()，所以应该进行归约。由于此时堆栈中( = ) ，而,)，所以应该进行归约。由于此时堆栈中(#，所以应该进行归约。由于此时堆栈中( = )，#(，所以当前的最左素短语为(N)，对其进行归约，得到：此时栈顶的第一个终结符为#，当前的输入符号也为#，标志分析成功。2、课件第5章中练习题。第6章1、给定文法：E (L) | aL L,E | E（1）构造识别活前缀的确定有限自动机（LR(0)项目集规范族）；（2）构造LR(0)分析表；（3）构造SLR(1)分析表；（4）该文法是否为LR(0)文法？为什么？（5）该文法是否为SLR(1)文法？为什么？（6）用SLR(1)分析表对(a), a)进行LR语法分析，给出分析程序的每一步动作及缓冲区和堆栈的变化情况。【解答】（1）首先对文法进行拓广，得到如下的拓广文法：S EE (L)E aL L,EL E构造识别活前缀的确定有限自动机（LR(0)项目集规范族）如下图所示：（2）LR(0)项目集规范族中有9个项目集（确定有限自动机的状态），所以LR(0)分析表应该有9行，每行对应一个状态。假设用数字08分别对应I0I8。对于0号状态这一行，考察项目集I0，其中含3个项目，分别为待约项目S E，移进项目E (L)和E a。对于S E，由于GO(I0, E) = I1，所以在这一行E列（GOTO子表）中放置状态1；对于E (L)，应该在(列放置移进动作,由于GO (I0, () = I2，所以应该设置s2；对于E a，应该在a列放置移进动作，由于GO(I0, a) = I3，所以应该放置s3。对于1号状态这一行，由于I1中只有接受项目，所以在这一行#列应该设置接受动作（acc）。对于2号状态这一行，含有3个待约项目E (L)，L L,E和L E，因此，根据它们填充GOTO子表，具体地，根据待约项目E (L)及GO(I2, L) = I4,在这一行L列放置状态号4，根据待约项目L L,E及GO(I2, L)也是在这一行L列放置状态号4，根据待约项目L E及GO(I2, E) = I8，在这一行E列放置状态号8。此外，在这个项目集中还有两个移进项目E (L)和E a，根据E (L)及GO(I2, () = I2，应该在这一行(列放置s2，根据E a及GO(I2, a) = I3，应该在这一行a列放置s3。对于3号状态，由于其中只含一个归约项目E a，据此需要在这一行每个终结符对应的列上（动作子表的）放置用Ea进行归约的动作，即r3。按照同样的方式考察其他状态，得到：4号状态行 )列（动作子表）放置状态号s5，,列（动作子表）放置s6；5号状态行动作子表每一列放置用E (L)进行归约的动作，即r2；6号状态行a列放置s3，(列放置s2，E列放置状态7；7号状态行动作子表每一列放置用L L,E进行归约的动作，即r4；8号状态行动作子表每一列放置用L E进行归约的动作，即r5。根据前面的分析，可以得到如下表所示的LR(0)分析表：状态ACTION（动作）GOTO（转移）a(),#EL0s3s211acc2s3s2843r3r3r3r3r34s5s65r2r2r2r2r26s3s277r4r4r4r4r48r5r5r5r5r5（3）SLR(1)分析表的构造与LR(0)只是在归约项目上有所不同。在识别活前缀的确定有限自动机中，包含归约项目的状态（项目集）有4个，分别为I3、I5、I7和I8。现在我们考察这些项目集。对于I3，其中只包含了归约项目E a，在构造LR(0)分析表时，根据该归约项目在3号状态行每个终结符列上都放上了用E a进行归约的动作，即r3，而SLR(1)分析法针对这样的归约项目，要计算规则左部非终结符的FOLLOW集，对于该项目即是计算FOLLOW(E)，由于FOLLOW(E) = #，,，所以在#，)和,列上放置归约动作r3；对于I5，其中只包含归约项目E (L)，由于FOLLOW(E) = #，,，所以在5号状态行#，)和,列上放置用E (L)进行归约的动作，即r2；同样，对于I7中的归约项目L L,E，要计算FOLLOW(L)，它为,，所以在7号状态行,和)列上放置用L L,E进行归约的动作，即r4；对于I8中的归约项目L E，要计算FOLLOW(L),它为,，所以在8号状态行,和)列放置用L E进行归约的动作，即r5。就得到如表5-7所示的SLR(1)分析表：状态ACTION（动作）GOTO（转移）a(),#EL0s3s211acc2s3s2843r3r3r34 s5s65r2r2r26s3s277r4r48r5r5（4）该文法是LR(0)文法，因为构造出的LR(0)分析表不含多重入口。（5）该文法是SLR(1)文法，因为构造出的SLR(1)分析表不含多重入口。（6）下面给出LR分析算法利用SLR(1)分析表对句子(a), a)进行语法分析的过程。分析开始时，首先将压入堆栈（状态0为识别活前缀的确定有限自动机的初始状态），同时在句子末尾添加#作为结束标志，缓冲区指针指向句子的第一个终结符，此时堆栈和缓冲区如下所示：（1）此时栈顶的状态为0，当前输入符号为（，查找分析表0行(列，得到s2，即移进并转入2号状态，此时应该将压栈，同时缓冲区指针后移，得到如下的情形：（2）此时栈顶的状态为2，输入符号为(，查找符号表，得到s2，执行移进动作，得到下图：（3）此时栈顶状态为2，当前输入符号为a，查找符号表，得到s3，移进且转移到3号状态，得到如下情形：（4）在当前情况下，栈顶状态为3，输入符号为)，查找符号表，得到r3，即用Ea进行归约。此时，首先将栈顶的弹出，得到：（5）由于归约出的文法符号为E，而此时栈顶状态为2，所以查找2号状态行E列，得到状态号8，将压栈，得到如下的情形：（6）此时栈顶的状态为8，输入符号为)，查找符号表，得到r5，即用L E进行归约。执行完此归约后，堆栈和缓冲区变成如下的情形：（7）此时栈顶状态为4，输入符号为)，查找符号表得到s5，移进，得到：（8）此时栈顶状态为5，输入符号为,，查找符号表，得到r2，即用E (L)进行归约。为此，先弹出栈顶(L)，得到：（9）查找符号表2行E列得到状态8，于是将压栈，得到如下的情形：（10）此时栈顶的状态为8，当前输入符号为,，查找符号表，得到r5，用L E进行归约。归约后，得到如下的情形：（11）查找符号表4行,列，得到s6，即移进，转移到6号状态，得到：（12）此时当前状态为6，输入符号为a，从符号表查到s3，移进，得到：（13）此时当前状态为3，输入符号为) ，得到r3，要用E a进行归约。归约后得到：（14）此时当前状态为7，输入符号为) ，得到r4，即用L L,E进行归约。归约后得到：（15）此时当前状态为4，输入符号为) ，得到s5，移进转移到5号状态，得到：（16）此时查找5行#列，得到r2，即用E (L)进行归约。归约后得到： 此时，当前状态为1,输入符号为#，查找符号表，得到acc，即接受，说明分析成功，证明输入串(a), a)是给定文法的句子。2、给定文法：A A (A) | e（1）构造LR(0)分析表，说明该文法是否为LR(0)文法。如果不是指出分析表中存在的动作冲突；（2）构造SLR(1)分析表，说明该文法是否为SLR(1)文法，为什么？（3）构造LR(1)分析表，说明该文法是否为LR(1)文法，为什么？【解答】（1）首先对文法进行拓广，得到如下的拓广文法： S A A A (A) A e对该拓广文法构造识别活前缀的确定有限自动机（LR(0)项目集规范族）如下图所示。据此，设计的LR(0)分析表如下表所