还剩3页未读,继续阅读
文本内容:
编译原理复习
一、选择
1、构造编译程序应掌握A.源程序B.目标文件C.编译方法D.以上三项
2、编译程序绝大多数时间花在上A.出错处理B.词法分析C.目标代码生成D.表格管理
3、编译程序是对A.汇编程序的翻译B.高级语言程序的解释执行C.机器语言的执行D.高级语言的翻译
4、词法分析器的输出结果是A.单词的种别编码B.单词在符号表中的位置C.单词的种别编码和自身值D.单词自身值
5、正规式Ml和M2等价是指A.M1和M2的状态数相等B.Ml和M22的有向变条数相等C.Ml和M2所识别的语言集相等D.M1和M2状态数和有向边条数
6、DFAM接受的字集为A.以0开头的二进制数组成的集合B.以0结尾的二进制数组成的集合C.含奇数个0的二进制数组成的集合D.含偶数个0的二进制数组成的集合
7、文法G[S]:S-某S某|y所识别的语言是A.某y某B.某y某某C.某ny某n n20D.某ny某n
8、如果文法G[S]是无二义的,则它的任何句子ciA.最左推导和最右推导对应的语法树必定相同B.最左推导和最右推导对应的语法树可能不同C.最左推导和最右推导必定相同D.可能存在两个不同的最左推导,但它们对应的语法树相同
9、采用自顶向下分析,必须A.消除左递归B.消除右递归C,消除回溯D.提取公共左因子
10、设a、b、c是文法的终结符,且满足有限关系@=13和6=的则A.必有a=cB.必有=葭.必有b=aD.a~c都不一定成立
11、在规范规约中,用开刻画可归约串A.直接短语B.句柄C.最左素短语D.素短语
12、若a为终结符,则Af a•a B为项目A.规约B.移近C.接受D.待约
13、若项目集合Ik含有Af a,则在状态k时,仅当面临的输入符号a£FOLLOW・A时,才采取“A-a•”动作的一定是A.LALR文法B.LRO文法C.LR1文法D.SLRl文法
14、同心集合并有可能产生新的冲突A.指示器B.临时变量C.符号表D.程序变量
16、间接三元式表示法的优点为A.采用间接码表,便于优化处理B.节省存储空间,不便于表的修改C.便于优化处理,节省存储空间D.节省存储空间,不便于优化处理
17、表达式n AVBA CVD的逆波兰表示为A.ABVACDVB.A BVCD VAC.ABVq CDVAD.A BVACDV18过程的DISPLAY表中n nn记录了A.过程的连接数据B.过程的嵌套层次C.过程的返回地址D.过程的入口地址
19、过程P1调用P2是,连接数据不包含A.嵌套层次显示表B.老SP值C.返回地址D.全局DISPLAY表地址
20、堆式动态分配申请和释放存储空间遵守原则A.先请先放B.先请后放C.后请先放D.任意
21、.栈式动态分配与管理在过程返回时应做的工作有A.保护SPB,恢复SPC,保护T0PD.恢复T0P
22.如果活动记录中没有DISPLAY表,则说明A.程序中不允许有递归定义的过程B.程序中不允许有嵌套定义的过程C.程序中不允许有嵌套定义的过程,也不允许有递归定义的过程D.程序中允许有递归定义的过程,也允许有嵌套定义的过程
23、优化可生成的目标代码A.运行时间较短B.占用存储空间较小C.运行时间短但占用内存空间大D.运行时间短且占用存储空间小
24、下列优化方法不是针对循环优化进行的A.强度削弱B.删除归纳变量C,删除多余运算D.代码外提
25、基本块内的优化为A.代码外提,删除归纳变量B.删除多余运算,删除无用赋值C.强度削弱,代码外提D.循环展开,循环合并
26、在程序流图中,我们称具有下述性质的节点序列为一个循环A.它们是非连通的且只有一个入口结点B.它们是强连通的但有多个入口结点C.它们是非连通的但有多个入口结点D.它们是强联通的且只有一个入口结点
27、关于必经结点的二元关系,下列叙述中不正确的是A.满足自反性B.满足传递性C.满足反对称性D.满足对称性
28、有一语法制导翻译如下S-bAb{print1”}A-B{print2”}Af a{print3”}Bf Aa{print“4”}若输入序列为b aa aab,且采用自底向上的分析方法,则输出序列为A.32224441B.34242421C.12424243D.
3444221229、错误的局部化是A.把错误理解成局部的错误B.对错误在局部范围内进行纠结C.当发现错误时,跳过错误所在的语法单位继续分析下去D.当发现错误时立即停止编译,待用户改正错误后再继续编译
二、填空
1、编译程序划分的类型
2、编译程序是对—高级语言的翻译.
3、若文法是无二义的,则规范推导与规范归纳的关系
4、词法分析程序输出的单词符号通常表示成二元式的形式
5、语言的目标是,是一个特殊的非终结符
6、描述语言L={ab|nNm21}的文法为
7、程序语言的生成系统是,而识别系统则是
8、语法分析器的功能是输入输出
9、两个自动机等价是指DFA和NFA
10、文法四元组G[S]二{VTVTSP
11、词法分析器的输出结果是
12、语法分析的方法种类
13、文法符号的属性种类
14、文法G所描述的语言是的集合
15、为使编译程序能正确翻译,对程序设计语言必须使用的定义方法
16、LR语法分析法是指扫描输入串和进行规范归纳
17、首节点是指从它开始到控制流程图中任何一个结点都有一条通路的结点
18、生成中间代码时所依据的是
19、划分基本块的关键问题是准确定义入口和出口语句
20、错误的局部化是指当发现错误时,跳过错误所在的语法单位继续分析下去
21、基本块是指
22、基本块的优化方法,循环优化的方法
23、优化可生成的目标代码
24、优化对象所涉及的范围,优化的分类
25、一个好的编译程序应具有较强的或能力
26、代码优化所遵循的原则是程序的等价变换原则
27、动态语义检查需要生成相应的目标代码,它是在运行时进行的
28、编译生成的目标代码不可能是
29、语法制导翻译
30、编译程序是将源程序成目标程序后再执行
31、中间代码
32、编译模型的最后一个阶段是代码生成
33、在编译程序的全过程中,都需对进行频繁地访问,耗费的时间占很大比例
三、简答1,四类文法的关系与区别答由四类文法的定义可知,从0型文法到3型文法逐渐增加限制厂3型文法都属于0型文法,
2、3型文法不一定属于1型文法(如果存在形如A-§的产生式,则不属于1型文法),3型文法属于2型文法四类文法的区别如下
(1)1型文法中不允许有形如“A-§”的产生式存在,而
2、3型文法则允许形如§”的产生式存在
(2)
0、1型文法的产生式左部存在含有终结符号的符号串或两个以上的非终结符,而2型和3型文法的产生式左部只允许是单个的非终结符号
2.中间代码的优化原则答等价原则有效原则合算原则源程序表格管理目标程序语义分析与中间代码生成器出词法分析器语法分析器错处优化目标代码生成器理
3.编译程序的结构(图)
4.解释程序与编译程序的区别答编译程序是将源程序翻译成目标程序后再执行该目标程序;而解释程序则逐条读出源程序中的语句并解释执行,即在解释程序的执行过程中并不产生目标程序典型的解释型高级语言是BASIC语言
5.构造编译程序应掌握的内容答构造一个编译程序必须掌握下述三方面的内容⑴对被编译的源语言(如c、PASCAL等),要深刻理解其结构(语法)和含义⑵必须对目标机器的硬件和指令系统有深刻的了解⑶必须熟练掌握编译方法,编译方法掌握的如何将直接影响到编译程序的成败,一个好的编译方法可能得到事半功倍的效果
6.编译程序的工作过程答编译程序的工作过程是指从输入源程序开始到输出目标程序为止的整个过程此过程是非常复杂的一般来说,整个编译过程可以划分成五个阶段词法分析阶段、语法分析阶段、语义分析和中间代码生成阶段、优化阶段和目标代码生成阶段
7.堆式存储分配中需解决的问题答对于堆式存储分配来说,需要解决两个问题一是堆空间的分配,即当运行程序需要一块空间时应分配哪一块给它;另一个问题是分配空间的回收,由于返回堆的不同空间是按任意次序进行的,所以需要研究专门的回收分配策略
8.NFA和DFA的区别答NFA和DFA的区别主要有两点其一是NFA可以有若干个初始状态,而DFA仅有一个初始状态;其二是NFA的状态转换函数f不是单值函数,而是一个多值函数,即fi,a={某些状态的集合}ieS,它表示不能由当前状态和当前输入字符唯一地确定下一个要转换的状态,也即允许同一个状态对同一个输入字符可以有不同的输出边
四、计算
1.文件G[S]S-aS|bS|a构造LR0项目集规范族;给出识别活前缀的DFA;构造SLR1分析表,判断是否为SLRl文法
2.表达式A+B某C-D+EC-D飞翻译成逆波兰式、四元式、三元式、间接三元式
3.程序I=400J=200LlJ=J+lreadIifI5000gotoL2writeJhaltL2:1=1某1gotoLl画控制流程图求各个结点的必经结点集;求回边求循环
4.文件G[S]S-L|aS|aLf L,S|S1S,a最右推导,画语法树2该句型中所有的短语,直接短语、句柄和最左素短语
5.文件G[S]S^S+aT|aT|+aTT一某aT|某alaT+a某a某a最右推导,画语法树;⑵该句型中所有的短语、直接短语、句柄和最左素短语陶阴二;正规表达式某Galbb ab某,a|b某aa,求出等价的简化Ur AM.HK夕『二昼乎个号:E产DAG进行优化,画出DAG图;假定变量L,M,N在出口之后7E活跃的,与出优化后的四兀式序列。