编译模拟试题答案.doc

编译原理考试卷（120分钟）班级 学号 姓名 评分 一、 填空 （20分，每空1分） 1文法G包括四个组成部分：一组终结符号，一组非终结符号，一组产生式，以及一个开始符号。 2文法按产生式的形式分为四种类型，它们是：0型文法，又称短语文法；1型文法，又称上下文有关文法；2型文法，又称上下文无关文法；3型文法，又称正规文法。 3最右推导称为规范推导，由规范推导产生的句型称为规范句型。 4设G是一个文法，S是它的开始符号，如果 S=*，则称是一个句型。仅由终结符号组成的句型是一个句子。 5 对于一个文法G而言，如果L(G)中存在某个句子对应两棵不同的语法树，那么该文法就称为是二义的。 6通常程序设计语言的单词符号分为五种：基本字、标识符、常数、算符、界限符。 7在自底向上分析法中，LR分析法把“可归约串”定义为句柄，算符优先分析法把“可归约串”定义为最左素短语。 8编译中常用的中间代码形式有逆波兰式、三元式、树代码和四元式等。 9对中间代码优化按涉及的范围分为局部优化，循环优化和全局优化。10局部优化主要包括合并已知量、利用公共子表达式和删除无用赋值等内容。 第1页二、编译过程通常分为哪几个主要阶段？每个阶段的主要功能？（15分）答：编译过程通常分为词法分析、语法分析、语义分析、中间代码生成、代码优化和目标代码生成六个主要阶段。各个阶段的主要功能如下：词法分析阶段：读入源程序，对构成源程序的字符流进行扫描和分解，识别出一个个单词，并表示成计算机内部的形式（TOKEN字）。语法分析阶段：在词法分析的基础上，将单词序列分解成各类语法短语，如“表达式”、“语句”、“程序”等，确定整个输入串是否构成语法上正确的程序。语义分析阶段：审查源程序有无语义错误，为代码生成阶段收集类型信息。中间代码生成阶段：将源程序翻译成一种复杂性介于源程序与目标程序之间的内部形式（中间代码）。代码优化：对前阶段产生的中间代码进行等价变换，目的是使将来生成的目标代码更为高效。目标代码生成：把中间代码变换成特定机器上的绝对指令代码或可重定位的指令代码或汇编指令代码。三、设有文法G1 （10分） G1：SSaQ Q1证明句型 QbRae 是规范句型 QQbR R RcSd e证：因为句型 QbRae 可由文法开始符S经过规范推导产生，推导过程如下：S =R SaQ =R SaR =R Sae =R Qae =R QbRae所以句型 QbRae 是规范句型。 2给出句型 QbRae 的短语，直接短语和句柄：短语：QbR e QbRae直接短语：QbR e句柄：QbR 第2页四、对于文法G2，填写各产生式的选择集合和G2的预测分析表。 （15分） G2： ETE SELECT()= ( , i E+TE SELECT()= + E SELECT()= # , ) TFT SELECT()= ( , i T*FT SELECT()= * T SELECT()= + , # , ) F(E) SELECT()= ( F i SELECT()= i +*()i# EETEETEEE+TEEETTFTTFTTTT*FTTTFF(E)F i五、对于文法G3，填写下列集合和G3的优先关系表。 （15分）G3：EE+T T FIRSTVT（E）= +, *, (, i LASTVT（E）= +, *, ), i TT*F F FIRSTVT（T）= *, (, i LASTVT（T）= *, ), i F（E）i FIRSTVT（F）= (, i LASTVT（F）= ), i +*（）i#+*（=i#=第3页六、把下面的语句翻译成四元式序列。 （10分）（只给出最后结果，设nextstat当前值为100）while AC do if A0 then A:=A+1 else A:=A+2100:j ,A ,C ,102101:j ,- ,- ,0102:j ,A ,0 ,104103:j ,- ,- ,107104:+ ,A ,1 ,T1105:= ,T1 ,- ,A106:j ,- ,- ,100107:+ ,A ,2 ,T2108:= ,T2 ,- ,A109:j ,- ,- ,100110:S.CHAIN=101七、用基本块代码生成算法生成目标代码。 （15分）（假定允许使用R1和R2寄存器，临时变量Ti 出基本块后都不活跃）四元式选取R目标代码RVALUEAVALUET1：= A+B空闲的R1LD R1 , AADD R1 , BR1中含有T1T1在R1中T2：= C-T1空闲的R2LD R2 , CSUB R2 , R1R2中含有T2T2在R2中T3：= D*E空闲的R1LD R1 , DMUL R1 , ER1中含有T3R2中含有T2T3在R1中T2在R2中T4：= F+G释放R2ST R2 , T2LD R2 , FADD R2 , GR1中含有T3R2中含有T4T3在R1中T4在R2中T5:= T3-T4T3独占的R1SUB R1 , R2R1中含有T5T5在R1中W：= T2/T5空闲的R2LD R2 , T2DIV R2 , R1R2中含有WW在R2中释放R2ST R2 , W- 第4页编译原理复习题本门课程的重点是语法分析。它包含的内容广（第3章：文法；第5、6、7章：分析方法），基本概念和基本方法多。为了便于大家复习，现把这四章的内容归纳如下：一、 文法1 文法定义 G=(VN, VT, P, S)VN：一组非终结符号VT：一组终结符号P： 一组产生式S： 一个开始符号2 文法分类 按对产生式施加不同的限制把文法分成四种类型：0型：短语文法1型：上下文有关文法2型：上下文无关文法3型：正规文法（正则文法、线性文法）3 涉及的上下文无关文法：算符文法、算符优先文法、LL（1）文法、LR文法4 文法的二义性5 文法的实用限制二、 分析方法1 自顶向下分析递归下降法：分析LL（1）文法产生的句子；由一组递归过程组成。LL（1）分析法（预则分析法）：分析LL（1）文法产生的句子；由一个总控程序和一个LL（1）分析表组成。2 自底向上分析算符优先分析法：非规范归约，用“最左素短语”定义“可归约串”；分析算符优先文法产生的句子；由一个总控程序和一个算符优先分析表组成。LR分析法：规范归约，用“句柄”定义“可归约串”；分析LR文法产生的句子；由一个总控程序和一个LR分析表组成。三、 基本概念（按概念的关联性分组记忆）1 直接推出、推导、句型、句子、语言、最左推导、最右推导（规范推导）、规范句型2 直接归约、归约、短语、直接短语、最左直接短语（句柄）、素短语、最左素短语、规范归约（最左归约）四、 基本方法（要求熟练做题）1 写递归下降子程序2 构造LL(1)分析表（涉及消除左递归、提左因子、FIRST、FOLLOW、SELECT集）3 构造算符优先分析表（涉及FIRSTVT、LASTVT集）其它章节的内容比较单一，在复习的基础上重点思考下列问题：1 什么叫翻译程序？什么叫汇编程序？什么叫编译程序？2 编译过程分哪几个主要阶段？每个阶段的主要任务是什么？3 单词符号分哪几类？各举出例子。4 存储分配有哪几种？影响存储分配策略的主要因素是什么？5 通常参数传递有哪些主要方式？每种方式是如何实现的？6 中间代码通常有哪些类型？各有什么特