期末考试试卷A卷
A.指示器
B.临时变量
C.符号表
D.程序变量
2009?2010学年度第二学期 《编译原理》 期末考试试卷
课程代码： 0660116试卷编号：1-A 命题日期： 2010年 6 月 15 日
答题时限： 120 分钟 考试形式：闭卷笔试
得分统计表:
一、单项选择题（请从4个备选答案中选择最适合的一项，每小题 2分，共20 分）
注意：须将本题答案写在下面的表格中，写在其它地方无效
1.编译程序是对（ ）
A.汇编程序的翻译 C.机器语言的执行
B. 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
5.若项目集I K 含有A ?则在状态
A ?动作的一定是（ ）
A . LALR 文法
B . LR （0）文法 K 时，仅当面临输入符号a FOLLOW （A ）时，才采取
C . LR （1）文法
D . SLR （1）文法
6.四元式之间的联系是通过（
）实现的
7.文法G: S x Sx | y所识别的语言是( )
* * *
A. xyx
B. (xyx)
C. x n yx n(n》0)
D. x yx
8.有一语法制导翻译如下所示:
S b Ab{print1”
A(B{pri nt2”}
A a{pri nt3
”
B Aa){pri nt 4 ”}
若输入序列为b（（（aa）a）a）b,且采用自下而上的分析方法，则输出序列为（）
A. B. 34242421 C. D.
9. 关于必经结点的二元关系，下列叙述不正确的是（）
A .满足自反性
B .满足传递性C.满足反对称型 D .满足对称性
10. 错误的局部化是指（）。
A .把错误理解成局部的错误B.对错误在局部范围内进行纠正
C.当发现错误时，跳过错误所在的语法单位继续分析下去
D .当发现错误时立即停止编译，待用户改正错误后再继续编译
二、判断题（每小题1分，共5 分）
1. 文法G的一个句子对应于多个推导，则G是二义性的。（X ）
2. 动态的存储分配是指在运行阶段为源程序中的数据对象分配存储单元。（V ）
3. 算符优先文法采用“移进-规约”技术，其规约过程是规范的。（X ）
4. 删除归纳变量是在强度削弱以后进行。（V ）
5. 在目标代码生成阶段，符号表用于目标代码生成。（X ）
三、简答题（每小题5分，共15分）
1. 构造正规式（0 I 1） 00相应的正规式并化简。（共5分）
（1）根据正规式，画出相应的NFA M （2分）
（2）用子集法将NFA确定化（2分）
将所有子集重命名，得到转换矩阵:
S
01
01
2
132
212
332
(3)化简，并画出DFA M (1分)
划分为状态：{0,2} {1 } {3}将这三个状态命名为0, 1 , 2三个状态
S01
010
120
220
2. 设文法G[S]:（共5分）
S f S + aT | aT | +aT
T f*aT | *a
(1) 写出句型aT + a *a*a的最右推导并画出语法树(2分)
S S+ aT S+ a*aT S+a*a*a aT+a*a*a
(2)写出该句型中所有的短语、直接短语、句柄和最左素短语。(3分)
短语：aT、*a*a、*a、aT+a*a*a
直接短语：aT、*a
句柄：aT
最左素短语：aT
3?将下列语句翻译为逆波兰表示，三元式、间接三元式和四元式表示:
a = (
b + c) * e + (b + c) / f
(1)逆波兰表示(1分)
abc + e * bc + f / + =（共 5 分）
*
⑵三元式（1分）
① (+,b, c)
② (*,①,e) ③ (+,b, c) ④ (/,③,f) ⑤ （+,②,④ ⑥ (=,a,⑤:
（3）间接三元式（1分）
① (+, b, c) ② (*,①,e)
③ (/,①,f)
④ （+,②,③） ⑤ (=,a,④)
间接码表：①②①③④⑤
⑷四元式(2
分)
① (+, b, c, T1)
② (*, T1, e,T2) ③ (+, b, c, T3)
④ (/, T3, f, T4) ⑤ (+, T2, T4, T5) ⑥
(=,T5, - , a)
四、综合题（共60分）
1. 已知文法G(S):(共15分)
S * A A 0A1 |*
(1)求文法G 的各非终结符号的FIRSTVT 和LASTVT 集合。(5分) FIRSTVT(S)={ * } LASTVT(S)={ 1, *} FIRSTVT(A)={ 0, * } LASTVT(S)={ 1, *}
（2）构造文法G 的优先关系矩阵，并判断该文法是否是算符优先文法
文法G 中的任何终结符对至多只存在一种优先关系，所以文法 G 是 （3）分析句子*0*1，并写出分析过程。（5分）
(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(O)项目集规范族，并给出识别活前缀的DFA。 (7分)
(3) 构造其SLR分析表，并判断该文法是否是SLR(1)文法。(7分)
状态11移进—规约冲突，计算S的Follow集合：Follow(S) ={#},可以采用SLR冲突消解法, 得到如下SLR分析表：
该文法是SLR (1)文法。
3. 设有如下基本块：(共10分)
T1 = A + B
T2 = 5
M = T2 * 4
T3 = C - D
T4 = M + T3
L = T1 * T3
T4 = A + B
（2）假设变量L , M , N在基本块出口之后是活跃的，给出优化后的四元式序列。（5分）N = A + B
M=20
T3=C-D
L=N*T3
4. 以下程序段是最内循环（共13分）
A = 0
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，则1=100可以用C=B+100替代，相应的1=1+1可用C=C+1替代，再将新的不变运算提到循环外。
5. 有一程序如下：
program ex; a: in teger;
procedure PP(x: integer); beg in:
x:=5; x:=a+1 end;
begi n
a:=2; PP(a); write(a) end
试用图表示ex调用PP(a)前后活动记录的过程。(共7 分)
PP_TOP —
PP_SP —ex_TOP —
ex_SP —
PP的活动记录(调用PP( a)之后)
ex的活动记录(调用PP (a)之前)