《编译原理》课程试卷A及答案

1、10/10编译原理 课程试卷A专业： 考试日期： 时间： 总分：100分 闭卷一大题：简答题(每小题6分，共30分)1.什么是文法，按Chomsky文法分类方法，把文法分成了哪几类？2.编译程序可以分为哪几个阶段，每个阶段的任务是什么？3. 在编译程序中，符号表的功能是什么？4. 什么是代码优化？代码优化的主要技术有哪些？5. 自底向上语法分析方法的基本思想是什么？二大题：若表达式文法GE为：E E+T|E-T |TT T*F | T/F | FF (E)|i1. 请构造句型E+T*F 对应的语法树。(4分)2. 请写出该句型的所有的短语、直接短语、句柄和素短语。(6分)三大题：已知如图1所示

2、NFA M，请将M转换成与其等价的DFA。(10分)图1四大题：已知文法GS：S a | b | (T) T STT ，ST| 1. 计算该文法的FIRST、FOLLOW、SELECT集合。(10分)2. 上述文法是LL(1)文法吗?若是，则构造LL(1)分析表。(10分)五大题：已知文法GS：A aAb | aAd | 1. 构造该文法的识别LR(0)活前缀的DFA。(10分)2. 说明该文法不是LR(0)文法，是SLR(1)文法，并构造SLR(1)分析表。(10分)六大题：根据以下的基本块：B:=3D:=A+CE:=A*CF:=D+EG:=B*FH:=A+CI:=A*CJ:=H+IK:=B

3、*5L:=K+JM:=L1构造基本块对应的DAG图。(5分)2若G，M，L在基本块后要引用，写出优化后的代码(5分)。编译原理试卷A答案一大题：1.答：词法分析阶段：读源程序，对字符流进行扫描和分解，识别出一个个单词。语法分析阶段：将单词分解成各类语法短语。语义分析阶段：审查源程序有无语义错误，为代码生成阶段收集类型信息。中间代码生成阶段：半源程序变成一种内部表示形式。代码优化阶段：对中间代码进行变换或改造，使生成的目标代码更为高效。目标代码生成阶段：把中间代码变换成特定机器上的绝对指令代码或可重定位的指令代码或汇编指令代码。2.答：文法是一个四元组（VN,VT,P,S），其中VN为非终结符号

4、集，VT为终结符号集，P为产生式集，S为开始符号。按乔姆斯基分类，把文法分成四种类型：0型（短语文法）、型（上下文有关文法）、型（上下文无关文法）、型（正规文法）。3.答：对输入符号串自左向右进行扫描，并将输入符逐个移入一个后进先出栈中，边移入边分析，一旦栈顶符号串形成某个句型的句柄时，就用该产生式的左部非终结符代替相应右部的文法符号串，重复这一过程直到归约到栈中只剩文法的开始符号时则为分析成功，也就确认输入串是文法的句子。4.答：符号表的功能：收集符号属性；上下文语义的合法性检查的依据；作为目标代码生成阶段地址分配的依据。5.答：优化就是对代码进行等价变换，使得变换后的代码运行把那间与变换前

5、代码运行结果相同，而运行速度加大或占用存储空间少，或两者都有。优化技术有：删除多余运算、代码外提、强度削弱、变换循环控制条件、合并已知量与复写传播、删除无用赋值。二大题： 解： E E + TT * F短语：T*F,E+T*F 直接短语：T*F句柄：T*F 素短语：T*F三大题：解：abA00,11B0,10,11C10a得DFA为： 四大题：解：是否=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)=）改写后文法中，相同左部非终结符对应的两条不同产生式的select集交集均为空改写后文法是LL（1）文法（2）LL（1）分析表为：ab（），#Sab(T)T，STTSTSTST五大题：解：（1）拓广文法为:(1)AA (1)AaAb (2)AaAd (3)A 构造LR(0)识别活前缀的DFA：=在I0、I2项目集中，存在移进归约冲突，故不是LR（0）文法。又afollow(A)=ab,d,#=移归冲突可以用SLR（）的简单的向右查看一个符号的方法解决该文法是SLR（1）文法(2)改进的SLR(1)分析表为：状态ACTIONGOTOabd#A0S2r3r3r31