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