发布时间 : 星期五 文章编译原理试卷答案练习题 - 图文更新完毕开始阅读
10-03.仅考虑一个基本块,不能确定一个赋值是否真是无用的。 ( ) 10-04.削减运算强度破坏了临时变量在一基本块内仅被定义一次的特性。 ( ) 10-05.在中间代码优化中循环上的优化主要有不变表达式外提和削减运算强度。 ( ) 10-06.在中间代码优化中循环上的优化主要有不变表达式外提和削减运算强度。 ( ) 四、名词解释: 2-16.短语 2-17.简单短语
2-18.句柄 2-19.规范推导 2-21.语言 4-11.语法分析
4-12.选择符集合SELECT 5-14.活前缀 5-15.可归前缀 5-16.LR(0)项目 5-17.算符优先文法 6-01.语义规则 6-03.后缀式
6-04.四元式
6-05.语法制导翻译 6-06.翻译方案 9-08.活动
9-09.活动记录
9-10.活动的生存期 10-02.基本块
10-07.无环路有向图(DAG)
五、简答题:
2-19什么是句子? 什么是语言? 2-20.已知文法G[E]为:
E→T|E+T|E-T T→F|T*F|T/F F→(E)|i
① 该文法的开始符号(识别符号)是什么?
②请给出该文法的终结符号集合VT和非终结符号集合VN。 ③ 找出句型T+T*F+i的所有短语、简单短语和句柄。 2-21.已知文法G[S]为:
S→dAB A→aA|a B→Bb|ε
① 试向G[S]是否为正规文法,为什么? ② G[S]新产生的语言是什么? ③ G[S]能否改写为等价的正规文法?
2-22.设有语言L(G)={ada| a∈(a,b), a为a之逆},试构造产生此语言的上下文无关文法G。 2-23.证明下面文法G[N]是二义性文法。 G[N]: N →SE∣E S →SD∣D
R
*
R
E →0∣2∣10
D →0∣1∣2
3-03.简述DFA与NFA有何区别 ? 3-04.试给出非确定自动机的定义。
3-05. 为正规式(a|b)a(a|b) 构造一个等价的确定的有限自动机。
3-07. 给定下列自动机: b 1 a a 其中:开始状态:0 终止状态:2 a ? 0 2 b
b (1)把此自动机转换为确定自动机DFA。
(2)给出此DFA的正则表达式。 4-13.消除下列文法G[E]的左递归。
E→E-T∣T T→T/F∣F F→( E )∣i
4-14.在LL(1)分析法中,LL分别代表什么含义? 4-15.自顶向下分析思想是什么? 4-16.自顶向下的缺点是什么? 4-17.LL(1)文法的定义是什么? 4-18.什么是文法的左递归?
4-19.递归下降法的主要思想是什么? 5-19.自底向上分析法的原理是什么? 5-20.简单优先方法基本思想是什么? 5-21.三种优先关系的定义是什么? 5-22.如何确定简单优先文法的句柄?
5-23. 给定文法G[Z]: 1. Z→C S 2. C→if E then
其中:Z、C、S、A、E∈VN ; 3. S→A=E
if、then、=、∨、i∈VT 4. E→E∨A
5. E→A
6. A→i
a) 构造此文法的LR(0)项目集规范族,并给出识别活前缀的DFA。 b) 构造其SLR(1)分析表。 5-24. 设有文法G[S]:
S→aA A→Ab A→b
*
求识别该文法所有活前缀的DFA。
6-07.语法制导翻译方法的基本思想是什么?
6-09.在一个属性文法中,对应于每个产生式A→a都有一套与之相关联的语义规则,每条规则的形式为
b:=f(c1,c2?,ck),其中对于b的要求是什么?
6-10.给定文法及相应的翻译方案:
S→bTc {print(“0”)} S→a {print(“1”)} T→R {print(“2”)} R→R/S {print(“3”)} R→S {print(“4”)}
为该文法设计翻译方案,使句型bR/bTc/bSc/ac经该翻译方案翻译后,输出串:
0342031320
6-10.给定文法及相应的翻译方案:)
E→E+T {print(“5”)} E→T {print(“4”)} T→T*F {print(“3”)} T→F {print(“2”)} F→( E ) {print(“1”)} F→i {print(“0”)}
对于句型T+(T*(F+T)*i),处理完该句型后输出是什么? 7-05.常用的中间语言种类有哪几种?
7-06.给定下列中缀式,分别写出等价的逆波兰表示和抽象语法树(运算符优先级按常规理解)。 (1)―a≤b∧a>0∨b<0 (2)a―(a*b―d)*(a―b*d)/d (3)―a+b≤0∨a<0∧(a―b)>2 (4)a*(b*c―a)≤b+c∧d
7-07给定下列中缀式,分别写出等价的后缀式和四元式(运算符优先级按常规理解)。 (1)(a+b*c)/(a+b)-d (2)x+y≤z∨a>0 (3)x+y≤0∨ (x―y)>2 (4)a:= (b*c―a) * a
8-04.符号表的组织方式有哪几种?
8-05. 在整个编译期间,对于符号表的操作有哪些?
8-06.符号表的作用有哪些?
9-11.解释抽象地址的结构和出现的原因。
9-12.描述活动记录的具体结构及display表的作用。 9-13.参数传递有换名(call by name)、传值(call by value)、传地址(call by reference)和传结果(call by result)等方式,试叙编译程序处理“传值”和“传地址”方式时的要点,并指明处理“换名”与“传地址”,以及“传值”与“传结果”方式之间的主要差别。 9-14.运行时存储器的划分是怎样的?
10-08.简述“循环中数组元素地址计算的优化”的主要思想,并举例说明。 10-09. 简述优化的原则是什么? 10-10.简述常用的优化技术有哪些? 10-11. 设有基本块: (1) a:=b-c (2) d:=a+4
(3) e:=a-b (4) f:=a+4 (5) b:=b+c (6) c:=b-f (7) b:=b-c (8) f:=b+f (9) a:=a-f (1) 画出DAG图;
(2) 假设基本块出口时只有a,b还被引用,请写出优化后的三地址代码序列。
10-12.设有基本块 T1:=2 T2:=10/T1 T3:=S-R T4:=S+R A:=T2 * T4 B:=A T5:=S+R T6:=T3 * T5 B:=T6
(1) 画出DAG图;
(2) 假设基本块出口时只有A,B还被引用,请写出优化后的三地址代码序列。 11-01.目标代码有哪几种形式?生成目标代码时通常应考虑哪几个问题? 11-02.什么是非活跃变量?什么是活跃变量?
综合题:
给定文法G[S]及相应翻译方案为:
1.S?bRc {print:”1”}
2.S?a {print:”2”}
3.R?R/S {print:”3”}
4.R?S {print:”4”}
40. 按chomsky分类法,文法G属于哪一型文法?
41. 符号串bR/bRc/ac是不是该文法的一个句型,请证实。 42. 若是句型,写出该句型的所有短语、简单短语,以及句柄。 43. 构造识别该文法的活前缀的DFA。 44. 判断该文法是LR(0)还是SLR(1),并构造其相应的语法分析表。 45. 对于bR/bRc/ac这个输入符号串,该翻译方案的输出是什么?