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

《[编译原理与技术]考试卷.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、西南科技大学网络教育学院（2015）/（2016）学年第2学期试题单〈A卷〉课程名称：编译原理与技术专业班级：命题教师：周宏毅学生姓名：学号：成绩：考试时间：月日一、简答题(每题4分，共5题，共20分)1.什么是编译程序？编译程序也叫编译系统，是把用高级语言编写的面向过程的源程序翻译成目标程序的语言处理程序。主要是进行词法分析和语法分析，又称为源程序分析，分析过程中发现有语法错误，给出提示信息。2.按编译方式在计算机上执行用高级语言编写的程序，一般需经过那两个阶段，各自的任务是什么？编译阶段:词法分析,语法分析,

2、语义分析运行阶段:中间代码生成,中间代码优化，目标代码生成3.编译程序的组织形式，按逻辑可分为那几个阶段？词法分析器、语法分析器、语义分析器、中间代码生成器、独立于机器的代码优化器、代码生成器、依赖于机器的代码优化器4.写出“abc”的前缀、后缀及子串？前缀:a,ab后缀:c,bc字串:abc2.数据空间的存储分配策略有哪些？首次拟合法最佳拟合法最差拟合法二、问答与作图题(每题12分，共1题，共12分)6.已知文法G(S)为:SàS+D︱D*S︱DDàD，H︱HHàa︱(S)1、给出句型“(D，H＋a)”最左推导

3、和最右推导；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分)*DSD+SDSD+SD*SDS语法树：短语：“(D,H＋a)”，“D,H＋a”，“D,H”，“a”　　素短语：“D,H”，“a”　　　　　　　　三

4、、计算题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∴原图已最小化四、计算题2(每题17分，共1题，共17分)8.已知文法G（D）为：D→intL

5、realLL→L,id

6、id1、提公因子和消除左递归；2、计算每个非终结符的FIRST和FOLLOW；3、

7、证明该文法是否为LL（1）文法？1提公因子和消除左递归:D→TLT→int

8、realL→idL’L’→,idL’

9、ε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)文法五、计算题3

10、(每题13分，共1题，共13分)9.对文法G(S)：S→a

11、b

12、(T)T→T，S

13、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(),＃a>>>b>>>(<<<=<)>>>,<<<>>>＃<<<=六、计算题4(每题13分，共1题，共13分)10.已知文

14、法G（E）：1.E→E+T2.E→T3.T→T*F4.T→F5.F→(E)1.F→i的LR分析表为：AcctionGotoSi+*（）$ETF0S5　　S4　　1231　S6　　　Acc　　　2　r2s7　r2r2　　　3　r4r4　r4r4　　　4S5　　S4　　8235　r6r6　r6r6　　　6S5　　S4　　　937S5　　S4　　　　108　S5　　S11　　　　9　r1S7　r1r1　　　10　r3r3　r3r3　　　11　r5r5　r5r5　　　请按以下格式给出“i+i*i$”的LR分析过程。步骤栈

15、输入动作说明步骤栈输入动作说明10i+i*i$····s5移入i20i5+i*i$····r6归约i30F3+i*i$····r4归约F40T2+i*i$····r2归约T50E1q+i*i$····s6移入+60E1+6i*i$····s5移入i70E1+6i5*i$····r6归约i80E1+6F3*i$····r4归约F90E1+6T9*i$····s7移入*100