编译原理模拟试题的答案.doc

编译原理模拟试题班级 学号 姓名 评分 一、 填空 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：SSaQ Q1证明句型 QbRae 是规范句型 QQbR R RcSd 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 | ida. 在该文法中提取左公因子。b. 为所得的文法的非终结符构造First集合和Follow集合。c. 说明所得的文法是LL(1)文法。d. 为所得的文法构造LL(1)分析表e. 假设有输入串int x,y,z写出相应的LL(1)分析程序的动作。答：a. 文法存在左公因子，提取左公因子后的文法为：D T VT int | floatV id VV ,V |b. 非终结符First集合Follow集合D int , float $ T int , float id V id $ V , , $ c. (1) First ( TV ) = int , float First(int) First(float)=intfloat=; First(id V)=id； First(,V) First()=, =; (2) V=, First(V)Follow(V)= , , $ = 根据LL(1)文法的定义判断，此文法是LL(1)文法；d. LL(1)分析表为：intfloatid,$DD TVD TVTT intT floatVVidVVV ,VVe. 输入串int x,y,z的LL(1)分析：步骤分析栈输入串分析程序的动作1$Dint x,y,z$D TV2$VTint x,y,z$T int3$V intint x,y,z$int匹配4$Vx,y,z$VidV5$ Vxx,y,z$x匹配6$ V,y,z$V ,V7$ V,y,z$, 匹配8$ Vy,z$VidV9$ Vyy,z$y匹配10$ V,z$V ,V11$ V,z$, 匹配12$ Vz$VidV13$ Vzz$z匹配14$接受五、考虑以下的文法：E ( L ) | aL L , E | Ea. 为这个文法构造LR(0)项目的DFA。b. 判断这个文法是否是LR(0)文法？若不是，请描述出LR(0)冲突，如果是，则构造LR(0)分析表。c. 判断这个文法是否为SLR(1)文法？若是，构造SLR(1)分析表。d. 显示分析栈和输入串(a),a,(a,a)的SLR(1)分析程序的工作。答：拓广文法：(0) E E(1) E ( L ) (2) E a(3) L L , E (4) L Ea( I0：EE E(L) EaI2：E(L) LL,ELEE(L)Ea Ad I3：EaI1：E EI4：E(L)LL,E I5：L EE(aEL I6：E(L), I7：LL,EE(L)Ea(a I8：LL,EE是LR(0)文法, LR(0)分析表为:ACTIONGOTOa(),$EL0S3S211acc2S3S2s4543r2r2r2r2r24S6S75r4r4r4r4r46r1r1r1r1r17S3S288r3r3r3r3r3非终结符Follow集合E $ E), , ,$L), , 是SLR(1)文法,SLR(1)分析表为:ACTIONGOTOa(),$EL0S3S211acc2S3S2s4543r2r2r24S6S75r4r46r1r1r17S3S288r3r3步骤分析栈输入ACTIONGOTO1$0(a),a,(a,a)$S22$0(2(a),a,(a,a)$S23$0(2(2a),a,(a,a)$S34$0(2(2a3),a,(a,a)$r255$0(2(2E5),a,(a,a)$r446$0(2(2L4),a,(a,a)$S67$0(2(2L4)6,a,(a,a)$r158$0(2E5,a,(a,a)$r449$0(2L4,a,(a,a)$S710$0(2L4,7a,(a,a)$S311$0(2L4,7a3,(a,a)$r2812$0(2L4,7E8,(a,a)$r3413$0(2L4,(a,a)$S714$0(2L4,7(a,a)$S215$0(2L4,7(2a,a)$S316$0(2L4,7(2a3,a)$r2517$0(2L4,7(2E5,a)$r4418$0(2L4,7(2L4,a)$S719$0(2L4,7(2L4,7a)$S320$0(2L4,7(2L4,7a3)$r2821$0(2L4,7(2L4,7E8)$r3422$0(2L4,7(2L4)$S623$0(2L4,7(2L4)6)$r1824$0(2L4,7E8)$r3425$0(2L4)$S626$0(2L4)6$r1127$0E1$acc六、把下面的语句翻译成四元式序列。 （只给出最后结果，设LABEL当前值为100）while AC do if A0 then A:=A+1 else A:=A+2100:j ,A ,C ,102101:j ,- ,- ,110102:j ,A ,0 ,104103:j ,- ,- ,107104:+ ,A ,1 ,T1105:= ,T1 ,- ,A106:j ,- ,- ,100107:+ ,A ,2 ,T2108:= ,T2 ,- ,A109:j ,- ,- ,100110:S.NEXT=101七、设有基本块 T1：2 T2：10/T1 T3：SR T4：SR A：T2 * T4 B：A T5：SR T6：T3 * T5 B：T6 (1) 画出DAG图； (2) 假设基本块出口时只有A，B还被引用，请写出优化后的四元序列。T3T6T1 T45SR2B10T2T4AB+-*T5T3:=S-RT4:=S+