黄冈师范学院
2012—2013学年度第一学期期末试卷参考答案
考试课程：编译原理考核类型：考试A卷
考试形式：闭卷出卷教师：牛冀平
考试专业：计算机科学与技术，软件工程
考试班级：计科201001班，软件201001班
一、填空（每空0.5分，共 10分）
1、编译程序的功能是是对(高级语言)进行翻译，使之生成目标代码。
2、编译程序的工作过程一般划分为5个阶段：（词法分析）、语法分析、语义分析与中间代码生成，（代码优化）及目标代码生成。
另外还有表格管理和（出错处理）。
3、一个上下文无关文法所含四个组成部分是一组终结符号、一组（非终结符号）、一个开始符号、（一组产生式）。
4、设G是一个给定的文法，S是文法的开始符号，如果S=> x（其中x∈V*），则称x 是文法的一个（句型）。
5、规范归约中的可归约串是指句柄，算符优先分析中的可归约串是指（最左素短语）。
6、在编译过程中,可采用的中间代码形式有（）、（）、（）等。
（三元式、间接三元式、四元式、逆波兰式、抽象语法树）（任选三个即可）
7、语法分析最常用的两类方法是（自上而下）和（自下而上）分析法。
8、表达式（a+b)*c的后缀表达式为（ab+c*）。
9、符号表的结构一般有（线性表）、（有序表）、（散列表或哈希表）等。
分别使用的查找方法有（顺序查找）、（折半查找）和（哈希法查找）
10、代码优化的目的是（减少代码的时空开销）。
11、寄存器是CPU内部的（存储单元），其访问时间小于CPU对内存的访问时间。
12、如果一个句子存在两棵不同的语法树就说明该句子是（二义性）的。
二、选择题（每题1分，共10分）
1、文法的开始符号经多步推导产生的文法符号序列(仅包含终结符)是文法的（D ）。
A.短语
B.句柄
C.句型
D.句子
2、构造编译程序应掌握（D）。
A.源程序
B.目标语言
C.编译方法
D.以上三项都是
3、不属于循环优化的主要方法的是（B）。
A.强度削弱
B.删除无用赋值
C.删除归纳变量
D.代码外提
4、使用（A）可以定义一个程序的含义。
A.语义规则
B.词法规则
C.产生规则
D.左结合规则
5、优化可生成（D）的目标代码。
A．运行时间较短 B．占用存储空间较小
C．运行时间短但占用内存空间大 D．运行时间短且占用存储空间小
6、有文法G：E→E*T|T， T→T+i|i ,则输入串1+2*8+6按该文法G归约,其值为（B）。
A.23
B.42
C.30
D.17
7、编译技术中描述单词符号的形成规则的常用工具有（D）。
A．正规文法 B．正规式 C．有穷自动机 D．以上都是
8、编译技术中常用（ B ）描述程序语言的语法。
A．正规文法 B．上下文无法文法 C．属性文法 D．上下文有关文法
9、词法分析器的输出结果是( C )。
A．单词的种别编码 B．单词在符号表中的位置
C．单词的种别编码和自身值 D．单词自身值
10、以下( B )不是DFA的组成部分。
A．有穷字母表 B．初始状态集合 C．终止状态集合D．有限状态集合
三、简答题（每题10分，共50分）
1、有文法G[S]：S→SA|A A→a|b 写出句子aba的最左推导和最右推导。
解：句子aba的最左推导为：S=>SA=>SAA=>AAA=>aAA=>abA=>aba （5分）句子aba的最右推导为：S=>SA=>Sa=>SAa=>Sba=>Aba=>aba （5分）
2、一正规表达式为：b（b|a）| a（b|a（b|a）），写出上述正规式对应的DFA和状态装换矩阵。
解答：正规式对应的DFA为：（5分）
状态矩阵为： （5分）
状态\字符
a b X 1 3 1 2 Y 2 Y Y 3 Y Y Y
-
-
3、设G[E]: E->T|E+T|E-T, T->F|T*F|T/F , F->(E)|i 证明E+T*i*i+i 是该文法的句型
解答：
E => E+T => E+T+T => E+T*F+T => E+T*F*F+T => E+T*i*F+T => E+T*i*i+T => E+T*i*i+
F => E+T*F*i+i （5分） 或E => E+T => E+F => E+i =>E+T+i=> E+T*F+i => E+T*i+i => E+T*F*i+i => E+T*i*i+i （5分） 即，E=>* E+T*i*i+i ，所以是该文法的句型。
4、下面的文法是否是左递归的？如果是，该如何消除？ E →E+T|T T →T*F|F F →(E)|id
解答：E T 存在左递归， 可以用以下等价文法消除左递归
E →TE ’ （2分）
Y
X 1
2
3 a a
a b
b b b
a
DFA
E’→+TE’|ε（2分）
T→FT’（2分）
T’→*FT’|ε（2分）
F→(E)|id （2分）
5、设有文法G[S]：S→S/S|S-S|(S)|a，该文法是否有二义性？为什么？
解答：有.
该文法存在句子: a/a-a。
（5分）
该句子存在两颗不同的语法树，如图：（5分）
四、解答题（共30分）
1、对于下面的程序：
Program main
procedure p(x,y,z)
begin
y:=y+1;
z:=z+x;
end;
begin
a:=2; b:=3;
p(a+b,a,a);
write(a);
end.
请分别按照（1）传值(call by value)（2）传地址(call by reference) （3）传名（call by
name）(4)传结果(call by result)的参数传递方式给出程序执行时的输出结果。
解：（1）传名（call by name）输出结果为：2 （5分）（2）传地址(call by reference) 输出结果为：8 （5分）
（3）传值(call by value) 输出结果为：9 （5分）
(4) 传结果(call by result) 输出结果为：7 （5分）
2、对于文法G(S):
S-->bMb
M-->（L|a
L-->Ma)
1. 写出句型b(Ma)b的最右推导并画出语法树。
2. 写出上述句型的短语，直接短语和句柄。
答：
1. (5分)
b
Ma
b
Lb
b
bMb
S)
(
(⇒
⇒
⇒
2. (5分)
短语: Ma)，(Ma)，b(Ma)b
直接短语: Ma)
句柄: Ma)
S
b M
( T
M a
b
L
)。