1、 得分 一 填空题 （ 每空 2 分，共 20 分 ） 1. 不同的编译程序关于数据空间的存储分配策略可能不同，但大部分编译中采用的方案有两 种：静态存储分配方案和动态存储分配方案，而后者又分为 （ 1） 和 （ 2） 。 2. 规范规约是最 （ 3） 规约。 3. 编译程序的工作过程一般划分为 5 个阶段：词法分析、 （ 4） 、语义分析与中间代码生成，代码优化及 （ 5） 。另外还有 （ 6） 和出错处理。 4表达式 x+y*z/(a+b)的后缀式为 （ 7） 。 5文法符号的属性有综合属性和 （ 8） 。 6假设二位数组按行 存放，而且每个元素占用一个存储单元，则数组 a1.15,1.2
2、0某个元素 ai， j的地址计算公式为 （ 9）。 7局部优化是局限于一个 （ 10） 范围内的一种优化。 得分 二 选择题 （ 1-6 为单选题， 7-8 为多选题，每问 2 分，共 20 分 ） 1. 一个上下文无关文法 G 包括四个组成部分：一组终结符，一组非终结符，一个（ ），以 及一组（ ）。 A 字符串 B 产生式 C 开始符号 D 文法 2.程序的基本块是指（ ）。 A 一个子程序 B 一个仅有一个入口和一个出口的语句 C 一个没有嵌套的程序段 D 一组顺序执行的程序段，仅有一个入口和一个出口 3. 高级语言编译程序常用的语法分析方法中，递归下降分析法属于（ ）分析方法。 A 自
3、左向右 B 自顶向下 C 自底向上 D 自右向左 4在通常的语法分析方法中，（ ）特别适用于表达式的分析。 A 算符优先分析法 B LR 分析法 C 递归下降分析法 D LL（ 1）分析法 5经过编译所得到的目标程序是（ ）。 A 四元式序列 B 间接三元式序列 C 二元式序列 D 机器语言程序或汇编语言程序 6 一个文法所描述的语言是（ ）；描述一个语言的文法是（ ）。 A 唯一的 B 不唯一的 C 可能唯一，也可能不唯一 7 如果在文法 G 中存在一个句子，当其满足下列条件（ ）之一时，则称该文法是二义文法。 A 其最左推导和最右推导相同 B 该句子有两个不同的最左推导 C 该句子有两个不
4、同的最右推导 D 该句子有两棵不同的语法树 E 该句子对应的语法树唯一8 下面（ ）语法制导翻译中，采用拉链 回填技术。 A. 赋值语句 B. 布尔表达式的计算 C. 条件语句 D. 循环语句 三 解答题 （ 共 60 分 ） 得分 1 （共 15 分）已知文法 GE: EETE| （ E） |i T*|+ （ 1） 将文法 G 改造成 LL（ 1）文法；（ 5 分） （ 2） 构造文法 G 中每个非终结符的 FIRST 集合及 FOLLOW 集合；（ 5 分） （ 3） 构造 LL（ 1）分析表。 （ 5 分） 2 （共 12 分）给定文法 GS： SS(S)| （ 1） 给出句子 ()()
5、()()的规范推导过程；（ 4 分） （ 2） 指出每步推导所得句型的句柄；（ 4 分） （ 3） 画出该句子的语法推导树。（ 4 分） 3 （共 8 分）在一个移入 -规约分析过程中采用以下的语法制导翻译模式，在按一个产生式规约时，立即执行括号中的动作。 AaB print “0” ； Ac print “1” ； BAb print “2” ； （ 1） 当分析器的输入 为 aacbb 时，打印的字符串是什么？（ 3 分）（ 2） 写出分析过程。（ 5 分） 4 （ 10 分）翻译循环语句 while (ad) then x:=y+z 。要求：给出加注释的分析树及四元式序列。 参考以下部分
6、翻译模式： (1) Sif E then M S 1 backpatch(E.truelist,M.quad); S.nextlist:=merge(E.falselist,S1 .nextlist) (2) Swhile M 1 E do M2 S1 backpatch(S1.nextlist,M1,.quad); backpatch(E.truelist,M2,.quad); S.nextlist:=E.falselist emit (j, -,-,M 1 .quad) (3) SA S.nextlist:=makelist() (4) LS L.nextlist:=S.nextlist
7、(5) M M.quad:=nextquad (6) Eid 1 relop id2 E.truelist:=makelist(nextquad); e.falselist:=makelist(nextquad+1); emit(jrelop.op,id 1.place ,id 2.place,0); emit(j, -,-,0) (7) SL:=E emit(:=,E.place,-,L.place) (8) EE 1+E2E.place:=newtemp; emit(+,E1.place,E2.place,E.place,) 5 （共 15 分）设有表格构造文法 GS： Sa| (T) T
8、T,S|S (1) 计算文法 GS的 FIRSTVT 集和 LASTVT 集。（ 5 分） (2) 构造 GS的优先关系表，并判断 GS是否为算符优先文法。（ 5 分） (3) 计算 GS的优先函数。（ 5 分） 得分 二 单项选择题 （ 每题 2 分，共 10 分 ） 1. 设有文法 GI： II1|I0|Ia|Ic|a|b|c 下列符号串中是该文法句子的有（ ）。 ab0 a0c01 aaa bc10 可选项有： A B C D 2.程序的基本块是指（ ）。 A 一个子程序 B 一个仅有一个入口和一个出口的语句 C 一个没有嵌套的程序段 D 一组顺序执行的程序段，仅有一个入口和一个出口 3
9、. 高级语言编译程序常用的语法分析方法中，递归下降分析法属于（ ）分析方法。 A 自左向右 B 自顶向下 C 自底向上 D 自右向左 4经过编译所得到的目标程序是（ ）。 A 四元式序列 B 间接三元式序列 C 二元式序列 D 机器语言程序或汇编语言程序 5 运行阶段的存储组织与管理的目的是（ ）。 提高编译程序的运行速度 节省编译程序的存储空间 提高目标程序的运行速度 为运行阶段的存储分配做准备 可选项有： A. B. C. D. 2. （ 10 分） 已知文法 GS: 得分 SaBc|bAB AaAb|b Bb| （ 4） 构造其 LL（ 1）分析表； （ 5） 判断符号串 baabbb
10、是否为该文法的句子（写出含有符号栈、输入串和规则的分析过程）。 3. (10 分 ) 已知文法 G 为： EE+T|T TT*P|P Pi （ 1） 构造该文法的优先关系表（不考虑语句括号 #），并指出此文法是否为算符优先文法。（ 2） 构造文法 G 的优先函数表。 4 （ 8 分）在一个移入 -规约分析过程中采用以下的语法制导翻译模式，在按一个产生式规约时，立即执行括号中的动作。 SbAb print “1” A(B print “2” Aa print “3” BAa) print “4” （ 3） 当输入序列为 b(aa)a)a)b 时，打印的字符串是什么？（ 4） 写出移入 -规约分析
11、过程。 5 （ 12 分）翻译循环语句 while (xy) do if (a=b) then x:=2*y+a 。要求：给出加注释的分析树、三地址码序列及相应的四元式序列。 参考以下部分翻译模式： (1) Sif E then M S 1 backpatch(E.truelist,M.quad); S.nextlist:=merge(E.falselist,S1 .nextlist) (2) Swhile M 1 E do M2 S1 backpatch(S1.nextlist,M1,.quad); backpatch(E.truelist,M2,.quad); S.nextlist:=E.
12、falselist emit (j, -,-,M 1 .quad) (3) SA S.nextlist:=makelist() (4) LS L.nextlist:=S.nextlist (5) M M.quad:=nextquad (6) Eid 1 relop id2 E.truelist:=makelist(nextquad); e.falselist:=makelist(nextquad+1); emit(jrelop.op,id 1.place ,id 2.place,0); emit(j, -,-,0) (7) SL:=E emit(:=,E.place,-,L.place) (8
13、) EE 1+E2E.place:=newtemp; emit(+,E1.place,E2.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 xy goto L2 Z=s+ai I=i+1 Goto L1 L2: 7 (6 分 ) Give out the all basic blocks
14、of the following program fragment and construct the relevant flow graph(DAG). read C A=0 B=1 L4: A=A+B if BC goto L2 B=B+1 goto L4 L2: write A 8. (8 分 )Translate the assignment statement bi=b*c-b*d into (1) A syntax tree. (2) Three address instructions. 答案： (1) 栈式动态存储分配 (2) 堆式动态存储分配 (3) 左 (4) 语法分析 (
15、5) 目标代码生成 (6) 表格管理 (7) xyz*ab+/+ (8) 继承属性 (9) a+(i-1)*20+j-1 (10) 基本块 一、 选择题（每问 2 分，共 20 分） 1.C B 2.D 3.B 4.A 5.D 6.A,C 7.BCD,选对一个得 1 分且不超过满分，选错一个扣一分，扣完为止 。 8.BCD， 选对一个得 1 分且不超过满分，选错一个扣一分，扣完为止 。 二、 解答题 1 （ 1） 文法存在左递归，消除左递归后的文法为： E(E)E|i E （ 2 分） ETEE| （ 2 分） T*|+ （ 1 分） （ 2） (5 分 )没考虑 #扣 0.5 分，其它错或少
16、写一个扣 0.5 分 FIRST(E)=(,i FIRST(E)=*,+, FIRST(T)=*,+ FOLLOW(E)=),*,+,# FOWLLOW(E)= ),*,+,# FOLLOW(T)=(,i （ 3） 每错一个扣 0.5 分，全错或不写不得 分，扣完为止，共 5 分 ( ) i * + # E E(E)E EiE E E ETEE ETEE E E E T T* T+ 2（ 1） 规范推导过程如下。写错推导符号扣 0.5 分 ,错写或少写一步推导扣 0.5 分，扣完为止，最左推导 扣 2 分，共 4 分。 S S(S) S( ) S(S)() S( )() S(S)()() S(
17、S(S)()() S(S( )()() S(S(S)()()() S(S( )()()() S( )()()() ()()()() （ 2） （ 1）中加下划线的部分是句柄，标识如（ 1）。每少写一个句柄扣 0.5 分，扣完为止，共 4 分。 （ 3） 每少写步扣 0.5 分，扣完为止，共 4 分。 S S ( S ) S ( S ) S ( S ) S ( S ) S ( S ) 3（ 1） 打印的字符串是： 12020（错一个扣 0.5 分， 共 3 分 ） （ 2） 归约过程中错一步扣 0.5 分，扣完为止。 （共 5 分） 4（ 1） 每少写一步扣 0.5 分，扣完为止，共 5 分。
18、S while M1.q=100 E1.t=102 do M2.q=102 S1 E1.f=107 ad x E5.p=y + E6.p=z （ 2） 少写一个四元式扣 0.5 分，全错或不写不 y z 四元式序列为： 100( j , a, b,102) 101( j, _, _,107) 102( j , c, d ,104) 103( j, _, _,106) 104(, y, z,T1) 105(:,T1, _, x) 106( j, _, _,100) 5（ 1） 少写一个扣 1 分，全错或不写不得分，共 5 分。 FIRSTVT(S)=a,( FIRSTVT(T)=, a,( LASTVT(S)= a,) LASTVT(T)= a,), , (2)优先表如下。每错一个扣 0.5 分，全错或不写不得分，扣完为止，共 3 分
