1、装 订 线院系： 专业班级： 姓名： 学号： 编译原理考试卷A答案一大题：1. 答：词法分析阶段：读源程序，对字符流进行扫描和分解，识别出一个个单词。语法分析阶段：将单词分解成各类语法短语。语义分析阶段：审查源程序有无语义错误，为代码生成阶段收集类型信息。中间代码生成阶段：半源程序变成一种内部表示形式。代码优化阶段：对中间代码进行变换或改造，使生成的目标代码更为高效。目标代码生成阶段：把中间代码变换成特定机器上的绝对指令代码或可重定位的指令代码或汇编指令代码。2. 答：文法是一个四元组（VN,VT,P,S），其中VN为非终结符号集，VT为终结符号集，P为产生式集，S为开始符号。按乔姆斯基分类，
2、把文法分成四种类型：0型（短语文法）、型（上下文有关文法）、型（上下文无关文法）、型（正规文法）。3. 答：对输入符号串自左向右进行扫描，并将输入符逐个移入一个后进先出栈中，边移入边分析，一旦栈顶符号串形成某个句型的句柄时，就用该产生式的左部非终结符代替相应右部的文法符号串，重复这一过程直到归约到栈中只剩文法的开始符号时则为分析成功，也就确认输入串是文法的句子。4. 答：符号表的功能：收集符号属性；上下文语义的合法性检查的依据；作为目标代码生成阶段地址分配的依据。5. 答：优化就是对代码进行等价变换，使得变换后的代码运行把那间与变换前代码运行结果相同，而运行速度加大或占用存储空间少，或两者都有
3、。优化技术有：删除多余运算、代码外提、强度削弱、变换循环控制条件、合并已知量与复写传播、删除无用赋值。二大题： 解： E E + T T * F短语：T*F,E+T*F直接短语：T*F句柄：T*F 素短语：T*F三大题：解：abA00,11B0,10,11C10aC得DFA为：BaabAb四大题：解：是否=First集Follow集S否a,b,（，,）,#T否a,b,（）T是，,）Select(Sa)=a select(Sb)=b select(S(T)=（Select(TST)=a,b,（ select(T，ST )=， select(T)=）改写后文法中，相同左部非终结符对应的两条不同产生
4、式的select集交集均为空改写后文法是LL（1）文法（2） LL（1）分析表为：ab（），#Sab(T)T，STTSTSTST五大题：解：（1）拓广文法为:(0) AA (1)AaAb (2)AaAd (3)A A构造LR(0)识别活前缀的DFA：I1:AAbI4:AaAbI0:AA AaAb AaAd AAI2:AaAb AaAd AaAb AaAd AaI3:AaAbAaAd=I5:AaAdd在I0、I2项目集中，存在移进归约冲突，故不是LR（0）文法。又afollow(A)=ab,d,#=移归冲突可以用SLR（）的简单的向右查看一个符号的方法解决该文法是SLR（1）文法(2)改进的SLR(1)分析表为：状态ACTIONGOTOabd#A0S2r3r3r311acc2r3r3r333S4S54r1r1r15r2r2r2L,Mn9六大题：解：（1）DAG图为：Gn7+*F,Jn6+D,HE,In5n4*+K15n8n3n2n1BCA3（2） 优化后的代码为：S1=A+CS2=A*CS3=S1+S2G=3*S3L=15+S3M=L
