编译模拟试题答案

《编译模拟试题答案》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、《编译原理》考试卷（120分钟）班级学号姓名评分一、填空（20分，每空1分）1．文法G包括四个组成部分：一组终结符号，一组非终结符号，一组产生式，以及一个开始符号。2．文法按产生式的形式分为四种类型，它们是：0型文法，又称短语文法；1型文法，又称上下文有关文法；2型文法，又称上下文无关文法；3型文法，又称正规文法。3．最右推导称为规范推导，由规范推导产生的句型称为规范句型。4．设G是一个文法，S是它的开始符号，如果S=*>α，则称α是一个句型。仅由终结符号组成的句型是一个句子。5对于一个文法G而言，如果L(G)中存在某个句子对应两棵不同的语法树，那么该文法就称为是二义

2、的。6．通常程序设计语言的单词符号分为五种：基本字、标识符、常数、算符、界限符。7．在自底向上分析法中，LR分析法把“可归约串”定义为句柄，算符优先分析法把“可归约串”定义为最左素短语。8．编译中常用的中间代码形式有逆波兰式、三元式、树代码和四元式等。9．对中间代码优化按涉及的范围分为局部优化，循环优化和全局优化。10．局部优化主要包括合并已知量、利用公共子表达式和删除无用赋值等内容。第1页二、编译过程通常分为哪几个主要阶段？每个阶段的主要功能？（15分）答：编译过程通常分为词法分析、语法分析、语义分析、中间代码生成、代码优化和目标代码生成六个主要阶段。各个阶段的主要

3、功能如下：词法分析阶段：读入源程序，对构成源程序的字符流进行扫描和分解，识别出一个个单词，并表示成计算机内部的形式（TOKEN字）。语法分析阶段：在词法分析的基础上，将单词序列分解成各类语法短语，如“表达式”、“语句”、“程序”等，确定整个输入串是否构成语法上正确的程序。语义分析阶段：审查源程序有无语义错误，为代码生成阶段收集类型信息。中间代码生成阶段：将源程序翻译成一种复杂性介于源程序与目标程序之间的内部形式（中间代码）。代码优化：对前阶段产生的中间代码进行等价变换，目的是使将来生成的目标代码更为高效。目标代码生成：把中间代码变换成特定机器上的绝对指令代码或可重定位

4、的指令代码或汇编指令代码。三、设有文法G1（10分）G1：S→SaQ∣Q1．证明句型QbRae是规范句型Q→QbR∣RR→cSd∣e证：因为句型QbRae可由文法开始符S经过规范推导产生，推导过程如下：S=R>SaQ=R>SaR=R>Sae=R>Qae=R>QbRae所以句型QbRae是规范句型。2．给出句型QbRae的短语，直接短语和句柄：短语：QbReQbRae直接短语：QbRe句柄：QbR第2页四、对于文法G2，填写各产生式的选择集合和G2的预测分析表。（15分）G2：①E→TE'SELECT(①)={(,i}②E'→+TE’SELECT(②)={+}③E'→ε

5、SELECT(③)={#,)}④T→FT'SELECT(④)={(,i}⑤T'→*FT’SELECT(⑤)={*}⑥T'→εSELECT(⑥)={+,#,)}⑦F→(E)SELECT(⑦)={(}⑧F→iSELECT(⑧)={i}+*()i#EE→TE'E→TE'E'E'→+TE’E'→εE'→εTT→FT'T→FT'T'T'→εT'→*FT’T'→εT'→εFF→(E)F→i五、对于文法G3，填写下列集合和G3的优先关系表。（15分）G3：E→E+T∣TFIRSTVT（E）={+,*,(,i}LASTVT（E）={+,*,),i}T→T*F∣FFIRSTVT（T）=

6、{*,(,i}LASTVT（T）={*,),i}F→（E）∣iFIRSTVT（F）={(,i}LASTVT（F）={),i}+*（）i#+><<><>*>><><>（<<<=<）>>>>i>>>>#<<<<=第3页六、把下面的语句翻译成四元式序列。（10分）（只给出最后结果，设nextstat当前值为100）whileA

7、,2,T2108::=,T2,-,A109:j,-,-,100110:S.CHAIN=101七、用基本块代码生成算法生成目标代码。（15分）（假定允许使用R1和R2寄存器，临时变量Ti出基本块后都不活跃）四元式选取R目标代码RVALUEAVALUET1：=A+B空闲的R1LDR1,AADDR1,BR1中含有T1T1在R1中T2：=C-T1空闲的R2LDR2,CSUBR2,R1R2中含有T2T2在R2中T3：=D*E空闲的R1LDR1,DMULR1,ER1中含有T3R2中含有T2T3在R1中T2在R2中T4：=F+G释放R2STR2,T2LDR2,FA