[编译原理与技术]考试卷

第1页共7页西南科技大学网络教育学院（2015）/（2016）学年第2学期试题单〈A卷〉课程名称：编译原理与技术专业班级：命题教师：周宏毅学生姓名：学号：成绩：考试时间：月日一、简答题(每题4分，共5题，共20分)1.什么是编译程序？编译程序也叫编译系统，是把用高级语言编写的面向过程的源程序翻译成目标程序的语言处理程序。主要是进行词法分析和语法分析，又称为源程序分析，分析过程中发现有语法错误，给出提示信息。2.按编译方式在计算机上执行用高级语言编写的程序，一般需经过那两个阶段，各自的任务是什么？编译阶段:词法分析,语法分析,语义分析运行阶段:中间代码生成,中间代码优化，目标代码生成3.编译程序的组织形式，按逻辑可分为那几个阶段？词法分析器、语法分析器、语义分析器、中间代码生成器、独立于机器的代码优化器、代码生成器、依赖于机器的代码优化器4.写出“abc”的前缀、后缀及子串？前缀:a,ab后缀:c,bc字串:abc第2页共7页5.数据空间的存储分配策略有哪些？首次拟合法最佳拟合法最差拟合法二、问答与作图题(每题12分，共1题，共12分)6.已知文法G(S)为:SS+D︱D*S︱DDD，H︱HHa︱(S)1、给出句型“(D，H＋a)”最左推导和最右推导；2、给出句型“D*D+D”的语法树；3、给出句型“(D，H＋a)”的短语和素短语；最左推导：S=D=H=(S)=(S+D)=(D+D)=(D,H+D)=(D,H+H)=(D,H+a)(一步0.25分,共2分)最右推导：S=D=H=(S)=(S+D)=(S+H)=(S+a)=(D+a)=(D,H+a)(一步0.25分,共2分)语法树：短语：“(D,H＋a)”，“D,H＋a”，“D,H”，“a”D+SD*SDS*DSD+SDS第3页共7页素短语：“D,H”，“a”三、计算题1(每题13分，共1题，共13分)7.已知正规式((ε｜a)b*)*1、求等价的NFA；2、将NFA确定化3、若所求DFA可最小化，则求其最小化DFA；若无，说明原因。1、NFAM2、确定化：abI0{0}{0,1,2}/I1{0,1,2}{0,1,2}{0,1,2}NFAM：3、最小化：∵ab01/111∴原图已最小化第4页共7页四、计算题2(每题17分，共1题，共17分)8.已知文法G（D）为：D→intL|realLL→L,id|id1、提公因子和消除左递归；2、计算每个非终结符的FIRST和FOLLOW；3、证明该文法是否为LL（1）文法？1提公因子和消除左递归:D→TLT→int|realL→idL’L’→,idL’|ε2构造First和Follow集合First(D)={int，real}Follow(D)={#}First(T)={int，real}Follow(T)={id}First(L)={id}Follow(L)={#}First(L’)={‘，’,ε}Follow(L’)={#}3∵S{T→int}∪S{T→real}=Φ；S{L’→,idL’}∪S{T→ε}=Φ；∴该文法是LL(1)文法第5页共7页五、计算题3(每题13分，共1题，共13分)9.对文法G(S)：S→a|b|(T)T→T，S|S1、构造各非终结符的FIRSTVT和LASTVT集合；2、构造算符优先表。1求FIRSTVT和LASTVT:FIRSTVT（Ｓ）={a，b，(}LASTVT(Ｓ)={‘,’，a，b，）}FIRSTVT（T）={a，b，（}LASTVT(T)={‘,’，a，b，）}（一条1.5分,共6分）2关系表ab(),＃ab(=),＃=六、计算题4(每题13分，共1题，共13分)10.已知文法G（E）：1.E→E+T2.E→T3.T→T*F4.T→F5.F→(E)第6页共7页6.F→i的LR分析表为：AcctionGotoSi+*（）$ETF0S5S41231S6Acc2r2s7r2r23r4r4r4r44S5S48235r6r6r6r66S5S4937S5S4108S5S119r1S7r1r110r3r3r3r311r5r5r5r5请按以下格式给出“i+i*i$”的LR分析过程。步骤栈输入动作说明步骤栈输入动作说明10i+i*i$····s5移入i20i5+i*i$····r6归约i30F3+i*i$····r4归约F40T2+i*i$····r2归约T50E1q+i*i$····s6移入+60E1+6i*i$····s5移入i第7页共7页70E1+6i5*i$····r6归约i80E1+6F3*i$····r4归约F90E1+6T9*i$····s7移入*100E1+6T9*7i$····s5移入i110E1+6T9*7i5$····r6归约i120E1+6T9*7F10$····r3归约T*F130E1+6T9$····r1归约E+T140E1$····acc接受七、计算题5(每题12分，共1题，共12分)11.翻译下列语句为逆波兰式。ifXYX=X+1;elseC=C+X;逆波兰式：XY【p1】JPTXX1+=【p2】JPF[p1]CCX+=[p2]