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

编译原理课程试卷A专业：考试日期： 时间： 总分：100分闭卷一大题：简答题（每小题6分，共30分）:号学什么是文法，按Chomsky文法分类方法，把文法分成了哪几类？:号学编译程序可以分为哪几个阶段，每个阶段的任务是什么？在编译程序中，符号表的功能是什么？什么是代码优化？代码优化的主要技术有哪些？..名姓自底向上语法分析方法的基本思想是什么？..名姓二大题：若表达式文法G[E]为：E—E+TIE-TITT—T*FIT/FIFF—（E）li请构造句型E+T*F对应的语法树。（4分）•级班业专请写出该句型的所有的短语、直接短语、句柄和素短语。（6分）•级班业专三大题：已知如图1所示NFAM,请将M转换成与其等价的DFAo（10分）•.系院•.系院四大题：已知文法G[S]：S—a丨b丨（T）T—ST'tj,stq£计算该文法的FIRST、FOLLOW、SELECT集合。（10分）上述文法是LL（1）文法吗?若是，则构造LL（1）分析表。（10分）五大题：已知文法G[S]：A—aAb|aAd|£构造该文法的识别LR（0）活前缀的DFAo（10分）说明该文法不是LR（0）文法，是SLR⑴文法，并构造SLR⑴分析表。（10分）六大题：根据以下的基本块：B:=3D:二A+CE:二A*CF:二D+EG:二E*FH:二A+CI:=A*CJ:二H+IK:=B*5L:二K+JM:=L构造基本块对应的DAG图。（5分）若G,M,L在基本块后要引用，写出优化后的代码（5分）。..号学..名姓•级班业专代码或汇编指令代码。阶段地址分配的依据。..号学..名姓•级班业专代码或汇编指令代码。阶段地址分配的依据。编译原理试卷A答案一大题：或1.答：词法分析阶段：读源程序，对字符流进行扫描和分解，识别出一个个单词。I 语法分析阶段：将单词分解成各类语法短语。I 语义分析阶段：审查源程序有无语义错误，为代码生成阶段收集类型信息。i 中间代码生成阶段：半源程序变成一种内部表示形式。j 代码优化阶段：对中间代码进行变换或改造，使生成的目标代码更为高效。目标代码生成阶段：把中间代码变换成特定机器上的绝对指令代码或可重定位的指令答：文法是一个四元组（VN,VT,P,S）,其中Vn为非终结符号集，V］为终结符号集，P为产生式集，s为开始符号。按乔姆斯基分类，把文法分成四种类型：0型（短语文法）、1型订 （上下文有关文法）、2型（上下文无关文法）、3型（正规文法）。答：对输入符号串自左向右进行扫描，并将输入符逐个移入一个后进先出栈中，边移入边分析，一旦栈顶符号串形成某个句型的句柄时，就用该产生式的左部非终结符代替相应右部的文法符号串，重复这一过程直到归约到栈中只剩文法的开始符号时则为分析成功，也就确认输入串是文法的句子。答：符号表的功能：收集符号属性；上下文语义的合法性检查的依据；作为目标代码生成答：优化就是对代码进行等价变换，使得变换后的代码运行把那间与变换前代码运行结果相同，而运行速度加大或占用存储空间少，或两者都有。优化技术有：删除多余运算、代装码外提、强度削弱、变换循环控制条件、合并已知量与复写传播、删除无用赋值。二大题：E+T•.系院解： EE+T•.系院直接短语：T*F素短语：T*F短语：直接短语：T*F素短语：T*F句柄：T*F三大题：解:abA{0}{0,1}{1}B{0,1}{0,1}{1}C{1}{0}①解:是否=>£First集Follow集s否{a,b,(}{，,),#}T否{a,b,(}{)}V是{{)}Select(S—a)={a}select(Sfb)={b}select(Sf(T))={(}Select(TfST')={a,b,(}select(T'f,ST')={,} select(T'f£)={)}•・•改写后文法中，相同左部非终结符对应的两条不同产生式的select集交集均为空・•・改写后文法是LL(1)文法(2)LL(1)分析表为：ab()#S—a—b-(T)TfST'T，—ST，—ST，fST，f£五大题：解：(1)拓广文法为:(0)A'^A (l)A-aAb(2)A—aAd(3)A—£构造LR(0)识别活唇的DFA：•・•在I。丄项目集中，存在移进归约冲突，故不是LR(0)文法。又{a}Plfollow(A)二{a}Pl{b,d,#}二①移归冲突可以用SLR(1)的简单的向右查看一个符号的方法解决・••该文法是SLR(1)文法(2)改进的SLR⑴分析表为：状态A