模拟试题二
一、填空题（10分）
1.1 正规式0(101)0所表示的语言是含有 。
1.2 最右推导(或规范推导) 是与规范归约（最左归约）互逆的一个过程，规范归约每次归约的符号串称为 。
1.3 3型文法是正规文法，对应的分析器是 自动机；2型文法是 ，对应的分析器是 自动机。
1.4文法G产生的 的全体是该文法描述的语言，记为L(G)。文法G1和G2等价当且仅当 。
1.5编译器分析源程序时遇到的错误可分为两类。表达式中括号不匹配是 错误， 运算对象与运算符号不匹配是 错误。
1.6 表达式(a+b*c)/(a+b)-d的后缀式为 。
*
*
**
二、选择题（20分）
2.1 不属于程序语言翻译软件。 A. 编译程序
B. 解释程序
C. 汇编程序
D. 编辑程序
2.2 表达式中的类型检查在 时进行。 A. 词法分析
B. 语法分析
C. 语义分析
D. 优化
2.3中间代码的主要形式有后缀式 、 和树（或图） 。 A. 三地址码
B. 正规式
C. 产生式
D. 符号表
2.4数组元素的地址计算公式由不变部分和可变部分这两部分组成， 。 A. 可变部分在编译时确定，不变部分在运行时确定 B. 不变部分在编译时确定，可变部分在运行时确定 C. 不变部分和可变部分均在编译时确定 D. 不变部分和可变部分均在运行时确定
2.5 常用的存储分配策略有 分配、栈分配和堆分配。 A. 数组
B. 链表
C. 静态
D. 动态
2.6 显示表(Display)用来记录各嵌套层次活动记录的sp，它的内容在 时确定。 A. 编译
B. 运行
C. 优化
D. 代码生成
2.7过程的嵌套层次树反映了过程之间的嵌套关系；活动的活动树反映了顺序执行程序的活动的 。
A. 运行时间长短 B. 大小
C. 状态
D. 调用关系
2.8编译器和解释器是两种高级语言处理程序，与编译器相比， 。 A. 解释器不参与运行控制，程序执行的速度慢
B. 解释器参与运行控制，程序执行的速度慢 C. 解释器参与运行控制，程序执行的速度快 D. 解释器不参与运行控制，程序执行的速度快
2.9 语法分析中的预测分析法是 的一种语法分析方法。 A. 自左至右
B. 自上而下
C. 自下而上
D. 自右至左
2.10 当程序运行陷于死循环时，说明程序中存在 。 A. 语法错误 B. 静态的语义错误 C. 词法错误
D. 动态的语义错误
三、简答题（20分）
3.1（5分）指出NFA与DFA的主要区别。
3.2（5分）举例说明下述文法G是二义的。有哪些方法可以消除文法的二义性。 G：S→0A|B1
A→1A|ε
B→0
3.3（10分）对下述C++程序，
(a) 指出p1和p2分别采用什么样的参数传递方式； (b)给出程序的执行结果。
void p1(int a, int b, int c) {c=c+10; b=a*b+c;} void p2(int &a, int &b, int &c){c=c+10; b=a*b+c;} void main()
{ int x=80, y=20, z=0, t=0; z=x+y*90;
p1(x+y,x,z); cout << \结果=\ t=x+y;
p2(t,x,z); cout << \结果=\}
3.4（5分）简述活动记录和访问链的主要作用，以及访问链的指向。 3.5（5分）为什么可以给变量赋值而不可以给常量赋值？
四、综合题（40分）
4.1（10分）有NFA N如右图: (a) 求出N的最小DFA D； (b) 给出N所识别语言的正规式r。
1aba2aa43
4.2（10分）下图所示的分析树用到了某个上下文无关文法的所有产生式。 (a) （2分）给出该文法的所有非终结符号集合N和终结符号集合T。
(b) （3分）给出该文法的产生式集合。
(c) （3分）写出句型aAaBcbdcc的直接短语和句柄。
Sa A c BA a B b S c Ac b B d cε
4.3（20分）有上下文无关无法G1和语法制导翻译如下：
(1) V → id
{var_no:=var_no+1;} {arr_no:=arr_no+1;} {exp_no:=exp_no+1;} {exp_no:=exp_no+1;}
(2) | id(E) (3) E → E + V (4) | V
(a) （6分）给出G1的识别活前缀的DFA；
(b) （4分） G1是LR(0)的吗？为什么？是SLR(1)的吗？为什么？ (c) （3分）给出句型id(id(id)+id)的分析树；
(d) （2分）若语义变量var_no、arr_no和exp_no的初值均为0，请给出分析句子id(id(id)+id)之后它们各自的值；
(e) （5分）说明G1不是LL(1)文法的理由并将G1改写为LL(1)文法G1'。
模拟试题二参考答案
一、填空题（10分）
1.1 正规式0(101)0所表示的语言是含有 偶数个1的串 。
1.2 最右推导(或规范推导) 是与规范归约（最左归约）互逆的一个过程，规范归约每次归约的符号串称为 句柄 。
1.3 3型文法是正规文法，对应的分析器是 有限 自动机；2型文法是 上下文无关文法 ，对应的分析器是 下推 自动机。
1.4文法G产生的 句子 的全体是该文法描述的语言，记为L(G)。文法G1和G2等价当且仅当 L(G1)=L(G2) （或两者描述的语言相同）。
1.5编译器分析源程序时遇到的错误可分为两类。表达式中括号不匹配是 语法 错误， 运算对象与运算符号不匹配是 语义 错误。
1.6 表达式(a+b*c)/(a+b)-d的后缀式为 abc*+ab+/d- 。
*
*
**
二、选择题（20分）
2.1 D 不属于程序语言翻译软件。 A. 编译程序
B. 解释程序
C. 汇编程序
D. 编辑程序
2.2 表达式中的类型检查在 C 时进行。 A. 词法分析
B. 语法分析
C. 语义分析
D. 优化
2.3中间代码的主要形式有后缀式 、 A 和树（或图） 。 A. 三地址码
B. 正规式
C. 产生式
D. 符号表
2.4数组元素的地址计算公式由不变部分和可变部分这两部分组成， B 。 A. 可变部分在编译时确定，不变部分在运行时确定 B. 不变部分在编译时确定，可变部分在运行时确定 C. 不变部分和可变部分均在编译时确定 D. 不变部分和可变部分均在运行时确定
2.5 常用的存储分配策略有 C 分配、栈分配和堆分配。 A. 数组
B. 链表
C. 静态
D. 动态
2.6 显示表(Display)用来记录各嵌套层次活动记录的sp，它的内容在 B 时确定。 A. 编译
B. 运行
C. 优化
D. 代码生成
2.7过程的嵌套层次树反映了过程之间的嵌套关系；活动的活动树反映了顺序执行程序的活动的 D 。
A. 运行时间长短 B. 大小
C. 状态
D. 调用关系
2.8编译器和解释器是两种高级语言处理程序，与编译器相比， B 。 A. 解释器不参与运行控制，程序执行的速度慢
B. 解释器参与运行控制，程序执行的速度慢 C. 解释器参与运行控制，程序执行的速度快 D. 解释器不参与运行控制，程序执行的速度快
2.9 语法分析中的预测分析法是 B 的一种语法分析方法。 A. 自左至右
B. 自上而下
C. 自下而上
D. 自右至左
2.10 当程序运行陷于死循环时，说明程序中存在 D 。 A. 语法错误 B. 静态的语义错误 C. 词法错误
D. 动态的语义错误
三、简答题（20分）
3.1（5分）指出NFA与DFA的主要区别。
解：主要区别在于在当前状态下遇到下一个符号的状态转移是否确定，NFA不确定，DFA确定。
3.2（5分）举例说明下述文法G是二义的。有哪些方法可以消除文法的二义性。 G：S→0A|B1
SB0101SAAε A→1A|ε B→0
解： G的一个句子“01”可以有如下的两棵分析树：
可以改写文法为非二义的，也可以规定文法符号的优先级和结合性，限制分析的每一步仅有唯一选择。
3.3（10分）对下述C++程序，
(a) 指出p1和p2分别采用什么样的参数传递方式； (b)给出程序的执行结果。
void p1(int a, int b, int c) {c=c+10; b=a*b+c;} void p2(int &a, int &b, int &c){c=c+10; b=a*b+c;} void main()
{ int x=80, y=20, z=0, t=0; z=x+y*90;
p1(x+y,x,z); cout << \结果=\ t=x+y;
p2(t,x,z); cout << \结果=\}
解： p1采用值调用，p2采用引用调用。
程序执行结果为： p1 结果=80 p2 结果=9890
3.4（5分）简述活动记录和访问链的主要作用，以及访问链的指向。
解：活动记录用于提供活动所需的环境，访问链用于访问非本地数据。访问链的指向有两种：
编译原理与技术模拟试题二
