一、填空（10分）
1.1 编译程序的工作过程可划分为 、语法分析、 、中间代码生成、代码优化、
等阶段，类型检查工作一般在 阶段进行。 1.2 SLR(1)中L的含义是 。
1.3 常用的存储分配策略有静态存储分配和动态存储分配，其中，动态存储分配策略包括
分配和 分配。
1.4 用LR方法实现语法分析时，典型的操作有 、 、接受和报错。
1.5 已知数组M[0..5, 1..10]以行为主序存放，如果每个元素占2个存储单元，且起始地址为a，则元素M[2,3]的地址是 。
二、单选题（20分）
2.1识别上下文无关语言的自动机是 。 A. 下推自动机 B. NFA
C. DFA
D. 图灵机
2.2 给定文法A→bA|ca，为该文法句子的是 。 A. bb
B. bca
C. bcab
D. cab
2.3 一个句型中的最左 称为该句型的句柄。 A. 短语
B. 直接短语
C. 非终结符号 D. 终结符号
2.4 已知文法G[S]:S→A1 A→A1|S0|0。与G等价的正规式是 。 A. 0(0|1)*1
B. 1*|0*1
C. 0(1|10)*1
D. 1(10|01)*0
2.5从编译程序的语法分析角度看，源程序是句子的集合， 可以较好地反映句子的结构。
A. 线性表 B. 树 C. 完全图 D. 堆栈 2.6词法分析的输出由 两部分组成。 A. 字符串和正规式 C. 文法和正规式
B. 记号和自动机 D. 记号的种类和属性
2.7 一个文法产生的 的集合称为该文法产生的语 A. 句子
B. 短语 C. 非终结符 D. 终结符
2.8 程序设计语言一般可分为低级语言和高级语言，低级语言指的是与机器硬件构造密切相关的语言。用低级语言编写程序的特点是 。 A．程序的执行效率低，编写效率低，可读性强 B．程序的执行效率低，编写效率高，可读性差 C．程序的执行效率高，编写效率低，可读性强 D．程序的执行效率高，编写效率低，可读性差
2.9 表达式采用逆波兰式表示时可以不用括号，而且可以用基于 的求值过程进行计算。与逆波兰式ab+cd+*对应的中缀表达式是 。
A. 栈 B. 队列 C. 符号表 D. 散列表 A. a+b+c*d B. (a+b)* c+d C. (a+b)* (c+d) D. a+b*c+d
三、简答题（30分）
3.1 （6分）请分别写出传值调用和引用调用时，下述代码的输出结果。
program main(input,output)
procedure f(a,b)
begin
a := b - a; b := a * b + 1;
end; begin
x := 2; y := 6; f(y,x); print(x,y); end.
3.2 （8分）请简要说明进行自上而下的语法分析时，文法中为什么不能有左递归和公共左因子。
3.3 （10分）请计算下面文法G中各非终结符的FIRST和FOLLOW集合。该文法是LL(1)文法吗？为什么？ G：E→E* T | T
T→T - F | F F→(E) | id
3.4（6分）设某程序执行到某一时刻时，控制栈中的内容如下所示（其中M是主程序，P、Q、R、S均是过程）。
(a) 给出所有在生存期的活动的调用关系(提示：若A调用B，则记为A→B)； (b) 试根据访问链中的内容画出主程序和过程的嵌套关系树。
S的活动记录S的活动记录控制链Q的活动记录R的活动记录P的活动记录M的活动记录访问链四、综合题（40分）
4.1（10分）设有正规式r=1(0|1)0，试给出： （a）（4分）识别该正规集的NFA；
*
（b）（6分）识别该正规集的DFA（要有计算过程）；
4.2（20分）设有上下文无关无法G[E]及其语法制导翻译如下（注：G中终结符id仅由单
个英文字母组成，如a, b等）：
E→E*T | T T→T+F | F F→(E) | id
11
{E.place=newtemp; emit(*, E.place, T.place, E.place;} {E.place=T.place;}
{T.place=newtemp; emit(+, T.place, F.place, T.place;} {T.place=F.place;} {F.place=E.place;} {F.place=id.name;}
1
1
(a)（5分）画出句子a+(b+c)*d的分析树；
(b)（3分）写出当a=1、b=2、c=3、d=4时的计算结果；（*表示算术乘、+表示算术加） (c)（9分）将文法G简化为：E→E*T|T，T→T+F|F，F→id，给出其识别活前缀的DFA。 (d)（3分）该文法是SLR(1)文法吗？为什么？ 4.3（10分）阅读以下程序代码
if (y > 0 or x > y)
while (x > y) do x = x - y else y = 0
（a）（4分）请画出其代码结构图（程序流程图）； （b）（6分）给出其三地址码序列。
模拟试题三参考答案
一、填空（10分）
1.1 编译程序的工作过程可划分为 词法分析 、语法分析、 语义分析 、中间代码生成、
代码优化、 目标代码生成 等阶段，类型检查工作一般在 语义分析 阶段进行。 1.2 SLR(1)中L的含义是 从左至右扫描输入序列 。
1.3 常用的存储分配策略有静态存储分配和动态存储分配，其中，动态存储分配策略包括
栈式 分配和 堆式 分配。
1.4 用LR方法实现语法分析时，典型的操作有 移进 、 归约 、接受和报错。 1.5 已知数组M[0..5, 1..10]以行为主序存放，如果每个元素占2个存储单元，且起始地址为a，则元素M[2,3]的地址是 a+44 。
二、单选题（20分）
2.1识别上下文无关语言的自动机是 A 。 A. 下推自动机 B. NFA
C. DFA
D. 图灵机
2.2 给定文法A→bA|ca，为该文法句子的是 B 。 A. bb
B. bca
C. bcab
D. cab
2.3 一个句型中的最左 B 称为该句型的句柄。 A. 短语
B. 直接短语
C. 非终结符号 D. 终结符号
2.4 已知文法G[S]:S→A1 A→A1|S0|0。与G等价的正规式是 C 。 A. 0(0|1)*1
B. 1*|0*1
C. 0(1|10)*1
D. 1(10|01)*0
2.5从编译程序的语法分析角度看，源程序是句子的集合， B 可以较好地反映句子的结构。
A. 线性表 B. 树 C. 完全图 D. 堆栈 2.6词法分析的输出由 D 两部分组成。 A. 字符串和正规式 C. 文法和正规式
B. 记号和自动机 D. 记号的种类和属性
2.7 一个文法产生的 A 的集合称为该文法产生的语 A. 句子
B. 短语 C. 非终结符 D. 终结符
2.8 程序设计语言一般可分为低级语言和高级语言，低级语言指的是与机器硬件构造密切相关的语言。用低级语言编写程序的特点是 D 。 A．程序的执行效率低，编写效率低，可读性强 B．程序的执行效率低，编写效率高，可读性差 C．程序的执行效率高，编写效率低，可读性强 D．程序的执行效率高，编写效率低，可读性差
2.9 表达式采用逆波兰式表示时可以不用括号，而且可以用基于 A 的求值过程进行计算。与逆波兰式ab+cd+*对应的中缀表达式是 C 。
A. 栈 B. 队列 C. 符号表 D. 散列表 A. a+b+c*d B. (a+b)* c+d C. (a+b)* (c+d) D. a+b*c+d
三、简答题（30分）
3.1 （6分）请分别写出传值调用和引用调用时，下述代码的输出结果。
program main(input,output)
procedure f(a,b)
begin
a := b - a; b := a * b + 1;
end; begin
x := 2; y := 6; f(y,x); print(x,y);
end.
解：传值调用: 2,6 引用调用: -7,-4
3.2 （8分）请简要说明进行自上而下的语法分析时，文法中为什么不能有左递归和公共左因子。
解：若有左递归，则分析可能先入死循环。若有公共左因子，则分析过程可能需要回溯，从而降低分析效率。
3.3 （10分）请计算下面文法G中各非终结符的FIRST和FOLLOW集合。该文法是LL(1)文法吗？为什么？
G：E→E* T | T T→T - F | F F→(E) | id 解：FIRST(E) = FIRST(T) = FIRST(F) = {(, id}
FOLLOW(E) = {#,*,)} FOLLOW(T) = {#,*,),-} FOLLOW(F) = {#,*,),-}
该文法不是LL(1)文法，因为FIRST(E* T)与FIRST(T)交集不空，或文法中有左递归。 3.4（6分）设某程序执行到某一时刻时，控制栈中的内容如下所示（其中M是主程序，P、Q、R、S均是过程）。
(a) 给出所有在生存期的活动的调用关系(提示：若A调用B，则记为A→B)； (b) 试根据访问链中的内容画出主程序和过程的嵌套关系树。
S的活动记录S的活动记录控制链Q的活动记录R的活动记录P的活动记录M的活动记录访问链
解：（a）调用关系: M→P→R→Q→S→S （b）嵌套关系树:
MPRQS
四、综合题（40分）
4.1（10分）设有正规式r=1(0|1)0，试给出： （a）（4分）识别该正规集的NFA；
（b）（6分）识别该正规集的DFA（要有计算过程）； 解：（a）NFA
01*
11203（b） {1} {2} {2，3} {2，3} {2，3} 1 {2} {2} {2} 00 1112013
4.2（20分）设有上下文无关无法G[E]及其语法制导翻译如下（注：G中终结符id仅由单个英文字母组成，如a, b等）：
E→E*T {E.place=newtemp; emit(*, E.place, T.place, E.place;}
| T {E.place=T.place;} 11
T→T+F {T.place=newtemp; emit(+, T.place, F.place, T.place;} | F {T.place=F.place;} F→(E) {F.place=E.place;} | id {F.place=id.name;}
(a)（5分）画出句子a+(b+c)*d的分析树；
(b)（3分）写出当a=1、b=2、c=3、d=4时的计算结果；（*表示算术乘、+表示算术加） (c)（9分）将文法G简化为：E→E*T|T，T→T+F|F，F→id，给出其识别活前缀的DFA。 (d)（3分）该文法是SLR(1)文法吗？为什么？ 解：(a)
EETTF(aTTFb+FcE)+F*TFd11
(b) 1+(2+3)*4=1+5*4=24 (c)拓广文法，加S->E
I4I1I0S->.EE->.E*TE->.TT->.T+FT->.FF->.iS->E.E->E.*TE->E*.TT->.T+FT->.FF->.iI6E->E*T.T->T.+F*TF+T->F.iI7ETFI2E->T.T->T.+F+T->T+.FF->.iI5T->F.I3iFiF->i.T->T+F.I8I9(d) 是SLR(1)。因为冲突项为：I1，I2，I6 对于I1： * Follow(S)
对于I2： + Follow(E)={#，），i, *} 对于I6： + Follow(E)={#，），i, *}
4.3（10分）阅读以下程序代码
if (y > 0 or x > y)
while (x > y) do x = x - y else y = 0
（a）（4分）请画出其代码结构图（程序流程图）； （b）（6分）给出其三地址码序列。 解：（a）（4分）
x > 0 ?
falsex > y ?truefalsey = 0truefalsex > y ?truex = x - y（b） （5分）
101 if y > 0 goto 105 102 goto 103
103 if x > y goto 105 104 goto 110 105 if x > y goto 106 goto 111 107 t1 = x – y 108 x = t1 109 goto 105 110 y = 0 111
因篇幅问题不能全部显示，请点此查看更多更全内容