期末考试试卷A卷文稿归稿存档编号:[KKUY-KKIO69-OTM243-OLUI129-G00I-FDQS58-
2009~2010学年度第二学期
《编译原理》期末考试试卷
课程代码: 0660116 试卷编号: 1-A 命题日期: 2010 年 6 月 15 日
答题时限: 120 分钟考试形式:闭卷笔试
20
注意:须将本题答案写在下面的表格中,写在其它地方无效
A. 汇编程序的翻译
B. 高级语言程序的解释执行
C. 机器语言的执行
D. 高级语言的翻译
2. 词法分析器的输出结果是()
A.单词的种别编码B.单词在符号表中的位置
C.单词的种别编码和自身值D.单词自身值
3. 在规范规约中,用()来刻画可规约串。
A.直接短语 B.句柄 C.最左素短语 D.素短语
4. 与正规式(a* | b) * (c | d)等价的正规式是()
A.a* (c | d) | b(c | d) B.a* (c | d) * | b(c | d) *
C.a* (c | d)| b* (c | d) D.(a | b) * c| (a | b) * d
含有Aα·,则在状态K时,仅当面临输入符号a∈FOLLOW(A) 5. 若项目集I
K
时,才采取Aα·动作的一定是()
A.LALR文法 B.LR(0) 文法C.LR(1)文法 D.SLR(1)文法
6. 四元式之间的联系是通过()实现的。
A. 指示器
B. 临时变量
C. 符号表
D. 程序变量
7.文法G:S x Sx | y所识别的语言是()
A.xyx B.(xyx) * C.x n yx n(n≥0) D.x*yx*
8. 有一语法制导翻译如下所示:
S b Ab {print “1”}
A(B {print “2”}
Aa {print “3”}
BAa) {print “4”}
若输入序列为b(((aa)a)a)b,且采用自下而上的分析方法,则输出序列为()
A. B. C. D.
9.关于必经结点的二元关系,下列叙述不正确的是()
A.满足自反性 B.满足传递性 C.满足反对称型D.满足对称性10.错误的局部化是指()。
A.把错误理解成局部的错误B.对错误在局部范围内进行纠正C.当发现错误时,跳过错误所在的语法单位继续分析下去
D.当发现错误时立即停止编译,待用户改正错误后再继续编译
1分,共5分)
G是二义性的。(×)
2. 动态的存储分配是指在运行阶段为源程序中的数据对象分配存储单元。(√)
3. 算符优先文法采用“移进-规约”技术,其规约过程是规范的。(×)
4. 删除归纳变量是在强度削弱以后进行。(√)
5. 在目标代码生成阶段,符号表用于目标代码生成。(×)
5分,共15分)
1. 构造正规式(0∣1)*00相应的正规式并化简。(共5分)
(1)根据正规式,画出相应的NFA M(2分)
(
(3)化简,并画出DFA M (1分)
0,1,2三个状态
2.
S →S + aT | aT | +aT T →*aT | *a
(1)写出句型 aT + a *a *a 的最右推导并画出语法树(2分) SS +aTS +a*aTS+a*a*aaT+a*a*a
(2)写出该句型中所有的短语、直接短语、句柄和最左素短语。(3分) 短语:aT 、*a 、aT+a*a*a
直接短语: 句柄:aT 最左素短语:aT
3. 将下列语句翻译为逆波兰表示,三元式、间接三元式和四元式表示:(共5分) a = (b + c) * e + (b + c) / f (1) 逆波兰表示(1分) abc + e * bc + f / + = (2) 三元式(1分) ① (+,b, c) ② (*,①,e) ③ (+,b, c) ④ (/,③,f)
S
S + a * a * a
a T
T
⑤ (+,②, ④)
⑥ (=,a, ⑤)
(3) 间接三元式(1分)
① (+, b, c)
② (*,①, e)
③ (/,①,f)
④ (+, ②,③)
⑤ (=, a, ④)
间接码表:①②①③④⑤
(4) 四元式(2分)
① (+, b, c, T1)
② (*, T1, e,T2)
③ (+, b, c, T3)
④ (/, T3, f, T4)
⑤ (+, T2, T4, T5)
⑥ (=, T5,-, a)
60分)
:(共15分)
S * A
A 0A1 | *
(1)求文法G的各非终结符号的FIRSTVT和LASTVT集合。(5分)FIRSTVT(S)={ * } LASTVT(S)={ 1, *}
FIRSTVT(A)={ 0, * } LASTVT(S)={ 1, *}
(2)
5分)
文法G G是一个算符优先文法。
(3)分析句子*0*1,并写出分析过程。(5分)
2.已知文法G(S):(共15分)
S aS | bS | a
(1)构造该文法的拓广文法。(1分)
(0)S’→S
(1) S→aS
(2)A→bS
(3)A→a
(2) 构造其LR(0)项目集规范族,并给出识别活前缀的DFA。(7分)
(3)构造其SLR分析表,并判断该文法是否是SLR(1)文法。(7分)
移进-规约冲突,计算S的Follow集合:Follow(S)={#},可以采用状态I
1
SLR
3.设有如下基本块:(共10分)
T1 = A + B
T2 = 5
M = T2 * 4
T3 = C - D
T4 = M + T3
L = T1 * T3
T4 = A + B
N
4.
A B5C
I = 1
L1: B = J + 1
C = B + I
A = C + A
if I = 100 GOTO L2
I = I + 1
GOTO L1
L2:
(1)画出程序流图,并找出回边与循环。(3分)
流图中有一条回边
B3 B2,且B2DOMB3,所以,有一个循环{B2, B3},B2是循环入口结点,也是出口结点。 (2)对循环优化(8分)
1. 代码外提:对于B2中的赋值四元式B=J+1,由于循环中没有对J 的定值操作,所有对J 的定值都在循环外,所以,它是循环中的不变运算,可以进行代码外提。
2. 删除归纳变量:循环中I 是基本归纳变量,C 是与I 同族的归纳变量,两者有如下线性关系:C=B+I ,则I=100可以用C=B+100替代,相应的I=I+1可用C=C+1替代,再将新的不变运算提到循环外。 (3)画出优化后的程序流图(2分)
5. 有一程序如下: program ex; a: integer; procedure PP(x: integer);
begin:
x:=5; x:=a+1
end;
begin
a:=2;
PP(a);
write(a)
end
试用图表示ex调用
PP_TOP →
PP_SP → ex_TOP →
ex_SP →PP的活动记
录
ex的活动记录(调用PP