编译原理习题大全.docVIP

第1章 1、编译过程包括哪几个主要阶段及每个阶段的功能。 答案：编译过程包括词法分析、语法分析、语义分析和中间代码生成、优化、目标代码生成5个阶段。 词法分析的功能是对输入的高级语言源程序进行词法分析，识别其中的单词符号，确定它们的种类，交给语法分析器，即把字符串形式的源程序分解为单词符号串形式。 语法分析的功能是在词法分析结果的基础上，运用语言的语法规则，对程序进行语法分析，识别构成程序的各类语法范畴及它们之间的层次关系，并把这种层次关系表达成语法树的形式。 词义分析和中间代码生成的功能是在语法分析的基础上，对程序进行语义分析，“理解”其含义，产生出表达程序语义的内部表达形式（中间代码）。 优化的功能是按照等价变换的原则，对语义分析器产生的中间代码序列进行等价变换，删除其中多余的操作，对耗时耗空间的代码进行优化，以期最后得到高效的可执行代码。 目标代码生成的功能是把优化后的中间代码变换成机器指令代码，得到可在目标机器上执行的机器语言程序。 第2章 1、写一上下文无关文法G，它能产生配对的圆括号串（如：(),(()),()(())等，甚至包括0对括号） 文法为：S((L)|LS|L L(S| ( 2、已知文法G：E(E+T|E-T|T T(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*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+T*F( E+T*i ( E+F*i ( E+i*i ( T+i*i ( F+i*i ( i+i*i E(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*|F F(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开始的小