《编译原理教学-华南理工》2010编译模拟试题答案.docVIP

《编译原理》模拟试题 班级 学号 姓名 评分 填空 1．文法G包括四个组成部分：一组终结符号，一组非终结符号，一组产生式，以及一个开始符号。 2．文法按产生式的形式分为四种类型，它们是：0型文法，又称短语文法；1型文法，又称上下文有关文法；2型文法，又称上下文无关文法；3型文法，又称正规文法。 3．最右推导称为规范推导，由规范推导产生的句型称为规范句型。 4．设G是一个文法，S是它的开始符号，如果 S=*α，则称α是一个句型。仅由终结符号组成的句型是一个句子。 5 对于一个文法G而言，如果L(G)中存在某个句子对应两棵不同的语法树，那么该文法就称为是二义的。 6．通常程序设计语言的单词符号分为五种：基本字、标识符、常数、算符、界限符。 7．在自底向上分析法中，LR分析法把“可归约串”定义为 句柄 。 8．编译中常用的中间代码形式有逆波兰式、三元式、树代码和四元式等。 9．对中间代码优化按涉及的范围分为局部优化，循环优化和全局优化。 10．局部优化主要包括合并已知量、利用公共子表达式和删除无用赋值等内容。 11．为了构造不带回溯的递归下降分析程序，我们通常要消除 左递归 和提取 左公共因子 二、编译过程通常分为哪几个主要阶段？每个阶段的主要功能？（15分） 答：编译过程通常分为词法分析、语法分析、语义分析、中间代码生成、代码优化和目标代码生成六个主要阶段。各个阶段的主要功能如下： 词法分析阶段：读入源程序，对构成源程序的字符流进行扫描和分解，识别出一个个单词，并表示成计算机内部的形式（TOKEN字）。 语法分析阶段：在词法分析的基础上，将单词序列分解成各类语法短语，如“表达式”、“语句”、“程序”等，确定整个输入串是否构成语法上正确的程序。 语义分析阶段：审查源程序有无语义错误，为代码生成阶段收集类型信息。 中间代码生成阶段：将源程序翻译成一种复杂性介于源程序与目标程序之间的内部形式（中间代码）。 代码优化：对前阶段产生的中间代码进行等价变换，目的是使将来生成的目标代码更为高效。 目标代码生成：把中间代码变换成特定机器上的绝对指令代码或可重定位的指令代码或汇编指令代码。 三、设有文法G1 G1：S→SaQ ∣ Q 1．证明句型 QbRae 是规范句型 Q→QbR ∣ R R→cSd ∣ e 证：因为句型 QbRae 可由文法开始符S经过规范推导产生，推导过程如下： S =R SaQ =R SaR =R Sae =R Qae =R QbRae 所以句型 QbRae 是规范句型。 2．给出句型 QbRae 的语法树和句柄： 　　语法树： 句柄：QbR 四、考虑以下文法: D →　T V T →　int | float V → id ,V | id 在该文法中提取左公因子。 为所得的文法的非终结符构造First集合和Follow集合。 说明所得的文法是LL(1)文法。 为所得的文法构造LL(1)分析表 假设有输入串 int x,y,z 写出相应的LL(1)分析程序的动作。 答： a. 文法存在左公因子，提取左公因子后的文法为： 　　D →　T V T →　int | float V → id V V→ ,V |ε b. 非终结符 First集合 Follow集合 D { int , float } { $ } T { int , float } { id } V { id } { $ } V { , , ε } { $ } c. (1) First ( TV ) = { int , float } First(int) ∩ First(float)={int}∩{float}=φ; First(id V)={id}； First(,V) ∩First(ε)={,} ∩{ ε}}=φ; (2) V=ε, First(V)∩Follow(V)= { , , ε }∩{ $ }=φ 根据LL(1)文法的定义判断，此文法是LL(1)文法； d. L