河南科技大学期末考试编译原理试卷及答案
(5) 的地址
4. 在通常的语法分析方法中，（）
A.算符优先分析法B
C.递归下降分析法D
5 .经过编译所得到的目标程序是（
A.四元式序列B 特别适用于表达式的分析。
.LR分析法
.LL （1）分析法
）。
.间接三元式序列
.机器语言程序或汇编语言程序
河南科技大学电信科卷A
填空题（每空2分，共20分）
1. 不同的编译程序关于数据空间的存储分配策略可
能不同，但大部分编译中采用的方案有两种：静态存储分配方案和动态存储分配方案，而后者又分为（1）和（2）。
2. 规范规约是最（3）规约。
3. 编译程序的工作过程一般划分为5个阶段：词法分析、（4）、语义分析与中间代码生成，代码优化及
另外还有（6）和出错处理。
4 .表达式x+y*z/（a+b）的后缀式为（7）。
5 ?文法符号的属性有综合属性和（8）。
6 .假设二位数组按行存放，而且每个元素占用一个存储单元，则数组a[1..15,1..2O] 某个元素a[i , j] 计算公式为（9）。
7 .局部优化是局限于一个（10）范围内的一种优化。
选择题（1-6为单选题，7-8为多选题，每问2分，共20分）
1. 一个上下文无关文法 G包括四个组成部分：一组终结符，一组非终结符，一个（）,以及一组（
A.字符串 B .产生式 C .开始符号 D . 文法
2. 程序的基本块是指（）。
A. 一个子程序 B . 一个仅有一个入口和一个出口的语句
C. 一个没有嵌套的程序段 D . 一组顺序执行的程序段，仅有一个入口和一个出口
3. 高级语言编译程序常用的语法分析方法中，递归下降分析法属于（）分析方法。
A.自左向右 B .自顶向下 C .自底向上 D .自右向左
6. 一个文法所描述的语言是（）;描述一个语言的文法是（）。
A .
如果在文法G 中存在一个句子，当其满足下列条件( )之一时，则称该文法是二义文法。
其最左推导和最右推导相同 B .该句子有两个不同的最左推导 C. E .
该句子对应的语法树唯一 卜面() 语法制导翻译中，采用拉链一回填技术。
B.
布尔表达式的计算
C.
条件语句
D.
循环语句
解答题(共60分)
1.(共15分)已知文法
G[E]:
(1)
将文法G 改造成LL (1)文法; (5分)
构造文法G 中每个非终结符的
FIRST 集合及 FOLLOW!合；(5 分)
(3)
构造LL ( 1)分析表。(5分)
(1)当分析器的输入为
aacbb 时，打印的字符串是什么?
3分)
该句子有两个不同的最右推导
D .该句子有两棵不同的语法树
i ETE| (E) |i
—*|+
2. (共 12 分)给定文法 G[S] : S T S(S)| &
(1) 给出句子(()())()() 的规范推导过程；(4分)
(2) 指出每步推导所得句型的句柄； (4分) (3)
画出该句子的语法推导树。 (4分)
3. (共8分)在一个移入-规约分析过程中采用以下的语法制导翻译模式，在按一个产生式规约时，立即执行 括号中的动作。
A T a
B {print “ 0”； } A T c {print “ 1”； } B T Ab {print “ 2”； }
(2) 写出分析过程。(5分)
4. (10分)翻译循环语句 while (a
。要求：给出加注释的分析树及四元式序
列。
参考以下部分翻译模式:
(1) S T if E then M S 1 {backpatch(E.truelist,M.quad);
S. nextlist:=merge(E.falselist,S
1
. nextlist)}
(2) S T while M 1 E do M 2 S 1 {backpatch(S
1
.nextlist,M 1,.quad);
8.
backpatch(E.truelist,M
2, .quad);
单项选择题（每题2分，共10分）
S T a| A |（T ）
T T T,S|S
（1） 计算文法 G[S]的FIRSTVT 集和LASTVT 集。（5分）
⑵构造G[S]的优先关系表，并判断
G[S]是否为算符优先文法。（5 分）
⑶计算G[S]的优先函数。（5分）
1.设有文法 G[I] : I T I1|l0|la|lc|a|b|c
S.
nextlist:=E.falsel
ist
emit (
'M .quad)} 5.
⑶ S T A
⑷
L T S
M
T ￡
⑹ E T id
relop id 1 emit
(
emit (
{S.
nextlist:=makelist()} {L.n extlist:=S. nextlist}
{M.quad:=n extquad}
{E.truelist:=makelist( nextq
uad);
e.falselist:=makelist (n extquad+1);
'j 'relop.op, ‘, 'id 1.place ‘, 'id 2.place ‘, ''O'); j ,-,-,0 ')}
(8)
T L:=E
{emit(:=,E.place,-, L.place)}
{E.place:=newtemp;
emit(+,E
1
.place,E
2.place,E.place,)}
（共15分）设有表格构造文法 G[S]:
①ab0 ② a0c01
③aaa
可选项有：
A.①
B .②③④
C
. ③④
2.程序的基本块是指（ 、 ）。
F 列符号串中是该文法句子的有（
）。
A. 一个子程序 B ④ bc10
D .①②③④
一个仅有一个入口和一个出口的语句
)分析方法。 。要求：给出加注释的分析树、三地址
3.高级语言编译程序常用的语法分析方法中，递归下降分析法属于(
4 .经过编译所得到的目标程序是( A.四元式序列 B C. 二元式序列 D
)。
.间接三元式序列
.机器语言程序或汇编语言程序
b| &
(4) 构造其LL (1)分析表；
(5)
判断符号串
baabbb 是否为该文法的句子(写出含有符号栈、输入串和规则的分析过程)
。
3. (10 分)已知文法 G 为：
i E+T|T
T*P|P
P T i
(1) 构造该文法的优先关系表(不考虑语句括号 #),并指出此文法是否为算符优先文法。
(2)
构造文法G 的优先函数表。
4.
(8分)在一个移入-规约分析过程中采用以下的语法制导翻译模式，在按一个产生式规约时，立即执行括 号中的动作。 S T bAb {print “ 1 ”} A T (B {print “ 2”} A
T a {print
“ 3”} B T Aa) {print
“ 4” }
(3) 当输入序列为b(((aa)a)a)b 时，打印的字符串是什么？
(4)
写出移入-规约分析过程。
5.
(12 分)翻译循环语句 while (x>y) do if (a=b) then x:=2*y+a
A.自左向右 B .自顶向下 C
自底向上 D
自右向左
①提高编译程序的运行速度 ② ③ 提高目标程序的运行速度
④ 可选项有 :
A.①②
B. ②③
C.
得分
2.
(10分)已知文法
S T aBc|bAB
5. 运行阶段的存储组织与管理的目的是(
)。
节省编译程序的存储空间 为运行阶段的存储分配做准备
③④ D. ④②
G[S]:
A^ aAb|b
码序列及相应的四元式序列。