上海大学编译原理试卷2013-2014春(附答案).doc

试卷序号： 第 1 页 ( 共 8 页 )

上海大学 2013～ 2014 学年春 季学期试卷A
课程名： 编译原理 课程号： 08305013 学分： 5
参考答案

题号
一（10）
二(10)
三(10)
四(15)
五(12)
六(15)
七(12)
八(16)
得分

一、判断题（本大题共10 小题，每小题1 分，共10 分）
判断下列各题正误，正确者在括号内打“√”，错误者在括号内打“×”。
1. 对中间代码的优化不依赖于具体的计算机。 （ √ ）
2. 程序流图中的每条回边对应于一个循环。 （√ ）
3. 自底向上语法分析时必须先消除文法中的左公共因子。 （ × ）
4. 使用逆波兰式描述表达式时无须使用括号。 （ √ ）
5. 编译程序是对高级语言程序的解释执行。 （ × ）
6. 符号表内容的一个重要作用是作为上下文语义合法性检查的依据。 （ √ ）
7. 状态中含有冲突的文法有可能是一个SLR(1)文法。 （ √ ）
8. 语义处理中“拉链”的作用是使“回填”更为有效。 （ √ ）
9. 算符优先分析法是一种自下而上的语法分析方法。 （ √ ）
10. 编译程序能找出源程序中所有错误。 （ × ）

成
绩

得分

阅卷人

二、选择题（本大题共10 小题，每小题1 分，共10 分）
在每小题列出的备选项中只有一个是符合题目要求的，请将其代码填写在题中的空格内。错选、多选或未选均无分。
1． 以下优化技术除 b 外，都是针对循环优化进行的。
a) 强度削弱 b) 删除多余运算 c) 变换控制条件 d) 代码外提
2．下列 d 工作不属于编译阶段的前端。
a) 语法分析 b) 词法分析 c) 中间代码生成 d) 目标代码生成
3 表达式 (a + b)*c / d对应的逆波兰式是 a 。
a) ab+c*d/ b) abc+/*d c) ab*c+/d d) abc*/d+
4．一个句型中称为句柄的是该句型中最左的 d 。
a) 非终结符 b) 句子 c) 短语 d)直接短语
5．以下 c 函数是PL/0编译程序中的词法分析器。
a) term b) expression c) getsym d) factor
6．PL/0编译程序的语法分析采用的是 b 。
a) LR分析法 b) 递归子程序法 c) 算符优先分析法 d) 预测分析法
7．程序所需的数据空间在程序运行前就可确定，称为 d 方法。
a) 动态分配 b) 堆式分配 c)栈式分配 d)静态分配
8．下列语句中， c 语句不是基本块的入口语句。
a) 程序的首条 b) 被转向的目标 c) 停止 d) 条件转移的下一条
9．给定文法A→bAa | a | b，下列符号串中语法正确的是 a 。
a) bbaaa b) babba c) abaab d) aabab
10． c 和代码优化部分不是每个编译程序都必需的。
a) 目标代码生成 b) 词法分析 c) 中间代码生成 d) 语法分析

第 2 页( 共 8 页 )

第 3 页( 共 8 页 )
三、设计题（本大题共2小题，每小题5分，共10分）
1．定义一个上下文无关文法G[S]，生成下述语言L：
L= { an dm bn | n,m≥1 }
答G[A]：A→aAb | aBb
B→dB | d
2．证明下列文法G[A]是一个二义文法：
A→B+B | B
B→B*B | A | a
答：∵ 对于句子a+a*a 存在两个不同的最左推导：
1: A=>B+B=>a+B=>a+B*B=>aa*B=>a+a*a
2: A=>B=>B*B=>A*B=>B+B*B=>a+B*B=>a+a*B=>a+a*a
∴ G[A]是一个二义文法

四、设计题（本大题共3小题，每小题5分，共15分）
设有正规式 r = (a |ab) (a|b)* b
1． 构造一个NFA M，接受L(r)。

2. 把上述NFA M转化为等价的DFA M。

3．给出DFA M所对应的正规文法。
G[S]：S→aA A→aB | bC
B→aB | bC C→aB | bC | ε

五、设计题（本大题共2小题，第1题7分，第2题5分，共12分）
对下列基本块B应用DAG进行优化，设只有S、W在基本块后面还要继续引用。
B: T1 := a+b
T2 := 3.14
S := T1*T2
T3 := a+b
T4 := 2.56
T5 T2+T4
W := T5*T1
S := T5*T3
1．基本块B的DAG
答：
2．优化后的基本块B’
答： T1:=a+b
T5:=5.70
W:=T5*T1
S:=W

第 4 页( 共 8 页 )
第 5 页( 共 8 页 )
六、分析题（本大题共2小题，第1题5分，第2题10分，共15分）
1．对下列属性文法中的语义处理功能作简略说明：
E→id1 rop id2 { E.true:=nextstat;
E.false:=nextstat+1;
E.Codebegin:=nextstat;
emit(‘if’ id1.place ‘rop’ id2.place ‘goto’–);
emit(‘goto’-) }
答：E.true：E的真出口链
E. false：E的假出口链
E.Codebegin: E的代码开始地址
Nextstat：下一条代码地址
emit： 生成一条四元式
2． 在下划线处填写正确内容，完成下列源语句通过语法制导翻译后生成的四元式序列。
源语句： while (s<100) and((a< b) or (a=b)) do
begin
a:=a+1;
if (a then s:= s+a;
end;
四元式序列：
1) if s<100 goto(3)
2) goto (14)
3) if a s:=t2
13 ) goto (1)
14)

七、 证明题（本大题共3小题，每题4分，共12分）
设有文法G[S]： S→B A
A→AB | Aa | a
B→ba | bB

1) 证明G[S]是一个非LL(1)文法。
答：
∵ A含左递归（以及A、B含公共左因子）∴ G[S]非LL(1)文法。

2) 把 G[S]等价改写为LL(1)文法G1[S]。
答：
G1[S]:
S→B A
A→aA’
A’→BA’| a A’ | ε
B→bB’
B’→a | B

3) 证明G1[S]为LL(1)文法。
答：
对于S,A,B:仅有一个候选，选择唯一；
对于A’：
Select(A’→BA’) = {b}
Select(A’→aA’’) = {a}
Select(A’→ ε) = {#}
{a}∩{ b} = Æ 且 {a}∩{ #} = Æ 且 {b}∩{ #} = Æ
选择唯一

对于B’：
Select (B’→a) = {a}
Select (B’→B) = { b}
{a}∩{b} = Æ
选择唯一
∴ G1[S]为LL(1)文法。

第 6 页( 共 8 页 )八、综合题（本大题共3小题，第1题6分，第2，3题各5分共16分）
设有文法G[S’]: (0) S’→E
(1) E→E+T
(2) E→T
(3) T→n
4) T→r

1. 证明G[S]是SLR(1)文法,构造G[S]的SLR(1)分析表。
答：LR(0)项目集规范族：

∵ 状态I1含有移进-归约冲突∴ G[S]是非LR(0)文法
∵ follow(S’)={#} ∩ {+}= Æ∴ G[S]是SLR(1)文法

SLR(1)分析表：

状态
ACTION
GOTO
+ n r #
E T
0
1
2
3
4
5
6
s3 s4
s5 acc
r2 r2
r3 r3
r4 r4
s3 s4
r1 r1
1 2

6

第 7 页( 共 8页 )

第 8页( 共 8页 )
2. 对输入串 n+r+n# 给出分析过程：

步骤
状态 符号
输入串
动作
1．
2.
3.
4.
5
6.
7.
8.
9.
10.
11.
12.
0 #
03 #n
02 #T
01 #E
015 #E+
0154 #E+r
0156 #E+T
01 #E
015 #E+
0153 #E+n
0156 #E+T
01 #E
n+r+n#
+r+n#
+r+n#
+r+n#
r+n#
+n#
+n#
+n#
n#
#
#
#
s3
r3
r2
s5
s4
r4
r1
s5
s3
r3
r1
acc

3．将文法G[S’]扩充为属性文法:
(0) S’→E { }
(1) E→E+T { print(“+”) }
(2) E→T { }
(3) T→n { print(“n”) }
(4) T→r { print(“r”) }

写出对输入串 n+r+n# 进行语法制导翻译分析后，输出的符号串。
答：输出的符号串: nr+n+