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

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

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

3、=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,Ha)”，“D,Ha”，“D,H”，“a”素短语：“D,H”，“a ”三、 计算题1 ( 每题13分，共1题，共13分 )7. 已知正规式(a)b*)*1、求等价的NFA；2、将NFA确定化3、若所求DFA可最小化，则求其最小化DFA；若无，说明原因。1、NFA M2、确定化：abI000,1,2 /I10,1

4、,20,1,20,1,2NFA M：3、最小化：ab01/111原图已最小化四、 计算题2 ( 每题17分，共1题，共17分 )8. 已知文法G（D）为： Dint L| real LLL,id | id1、提公因子和消除左递归；2、计算每个非终结符的FIRST和FOLLOW；3、证明该文法是否为LL（1）文法？1提公因子和消除左递归:DTLTint | realLid LL,id L|2构造First和Follow集合First(D)=int，real Follow(D)=#First(T)=int，real Follow(T)=idFirst(L)=id Follow(L)=#First(

5、L)=，, Follow(L)=#3S Tint S Treal =；S L,id L S T=；该文法是LL(1)文法五、 计算题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

6、. 已知文法G（E）：1. E E+T2. E T 3. T T*F 4. T F5. F (E)6. F i 的LR分析表为：Acction Goto Si +*（ ） $ETF0S5S41231S6Acc2r2s7r2r23r4r4r4r44S5S48235r6r6r6r66S5S4937S5S4108S5S119r1S7r1r110r3r3r3r311r5r5r5r5请按以下格式给出“i+i*i$”的LR分析过程。步骤栈输入动作说明步骤栈输入动作说明10i+i*i$ s5移入i 20i5 +i*i$ r6归约i 30F3 +i*i$ r4 归约F40T2 +i*i$ r2 归约T50E1q +i*i$ s6 移入+60E1+6 i*i$ s5移入i 70E1+6i5 *i$ r6归约i 80E1+6F3 *i$ r4 归约F90E1+6T9 *i$ s7 移入*100E1+6T9*7 i$ s5移入i 11 0E1+6T9*7i5 $ r6归约i 12 0E1+6T9*7F10 $ r3归约T*F130E1+6T9 $ r1归约E+T14 0E1 $ acc接受七、 计算题5 ( 每题12分，共1题，共1