《编译原理与技术模拟试题二》由会员分享，可在线阅读，更多相关《编译原理与技术模拟试题二（7页珍藏版）》请在金锄头文库上搜索。
1、模拟试题二一、填空题（10 分）1.1 正规式 0*(10*1)*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 不
2、属于程序语言翻译软件。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. 静态
3、 D. 动态2.6 显示表(Display)用来记录各嵌套层次活动记录的 sp，它的内容在 时确定。A. 编译 B. 运行 C. 优化 D. 代码生成2.7 过程的嵌套层次树反映了过程之间的嵌套关系；活动的活动树反映了顺序执行程序的活动的 。A. 运行时间长短 B. 大小 C. 状态 D. 调用关系2.8 编译器和解释器是两种高级语言处理程序，与编译器相比， 。A. 解释器不参与运行控制，程序执行的速度慢 B. 解释器参与运行控制，程序执行的速度慢C. 解释器参与运行控制，程序执行的速度快D. 解释器不参与运行控制，程序执行的速度快2.9 语法分析中的预测分析法是 的一种语法分析方法。A. 自
4、左至右 B. 自上而下C. 自下而上D. 自右至左 2.10 当程序运行陷于死循环时，说明程序中存在 。A. 语法错误 B. 静态的语义错误 C. 词法错误 D. 动态的语义错误 三、简答题（20 分）3.1（5 分）指出 NFA 与 DFA 的主要区别。3.2（5 分）举例说明下述文法 G 是二义的。有哪些方法可以消除文法的二义性。G：S0A|B1A1A|B03.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
5、 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 “p1 结果=“ x;t=x+y;p2(t,x,z); cout “ p2 结果=“ x endl;3.4（5 分）简述活动记录和访问链的主要作用，以及访问链的指向。3.5（5 分）为什么可以给变量赋值而不可以给常量赋值？四、综合题（40 分）4.1（10 分）有 NFA N 如右图:(a) 求出 N 的最小 DFA D； (b) 给出 N 所识别语言的正规式 r。4.2（10 分）下图所示的分析树用到了某个上下文无关文法的所有产生式。(a) （
6、2 分）给出该文法的所有非终结符号集合 N 和终结符号集合 T。1234aa aab(b) （3 分）给出该文法的产生式集合。(c) （3 分）写出句型 aAaBcbdcc 的直接短语和句柄。Sa A c BA a B b S c Ac b B d c4.3（20 分）有上下文无关无法 G1 和语法制导翻译如下：(1) V id var_no:=var_no+1;(2) | id(E)arr_no:=arr_no+1;(3) E E + Vexp_no:=exp_no+1;(4) | Vexp_no:=exp_no+1;(a) （6 分）给出 G1 的识别活前缀的 DFA；(b) （4 分）
7、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*(10*1)*0*所表示的语言是含有 偶数个 1 的串 。1.2 最右推导(或规范推导) 是与规范归约（最左归约）互逆的一个过程，规范归约每次归约的符号串称为 句柄
8、 。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.
9、 编辑程序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)用来记录
10、各嵌套层次活动记录的 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. 自下而上
11、D. 自右至左 2.10 当程序运行陷于死循环时，说明程序中存在 D 。A. 语法错误 B. 静态的语义错误 C. 词法错误 D. 动态的语义错误 三、简答题（20 分）3.1（5 分）指出 NFA 与 DFA 的主要区别。解：主要区别在于在当前状态下遇到下一个符号的状态转移是否确定，NFA 不确定，DFA 确定。3.2（5 分）举例说明下述文法 G 是二义的。有哪些方法可以消除文法的二义性。G：S0A|B1A1A|B0解： G 的一个句子“01”可以有如下的两棵分析树：可以改写文法为非二义的，也可以规定文法符号的优先级和结合性，限制分析的每一步仅有唯一选择。3.3（10 分）对下述 C+程序
12、，(a) 指出 p1 和 p2 分别采用什么样的参数传递方式； (b)给出程序的执行结果。void p1(int a, int b, int c) c=c+10; b=a*b+c;void p2(int 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 “p1 结果=“ x;t=x+y;p2(t,x,z); cout “ p2 结果=“ x endl;解： p1 采用值调用，p2 采用引用调用。程序执行结果为： p1 结果=80 p2 结果=98903.4（5 分）简述活动记录和访问链的主要作用，
13、以及访问链的指向。解：活动记录用于提供活动所需的环境，访问链用于访问非本地数据。访问链的指向有两SB10 0S0A1A种：非显示表指向直接外层的最新活动记录，显示表指向同层次新活动记录。3.5（5 分）为什么可以给变量赋值而不可以给常量赋值？解：因为变量有存储空间(左值)，常量仅是值(右值)。四、综合题（40 分）4.1（10 分）有 NFA N 如右图:(a) 求出 N 的最小 DFA D； (b) 给出 N 所识别语言的正规式 r。解：(a)确定化：m(1, a)=2 1=A(初态)m(2, a)=3,4m(2, b)=22=B, m(3 4, a)=2 3,4=C(终态)即：m(A, a
14、)=Bm(B, a)=C(终态)m(B, b)=Bm(C, a)=B它已经是最小 DFA。(b) r=a(b|aa)*a，它所描述的语言是由 a 开始和结尾的、偶数个 a 组成的 a、b 串。4.2（10 分）下图所示的分析树用到了某个上下文无关文法的所有产生式。(a) （2 分）给出该文法的所有非终结符号集合 N 和终结符号集合 T。(b) （3 分）给出该文法的产生式集合。(c) （3 分）写出句型 aAaBcbdcc 的直接短语和句柄。解：(a) 非终结符集合 N=S, A, B 终结符集合 T=a, b, c, d(b) 产生式集合： S aAcB | Bd A AaB | c B B
15、ScA | b |(c) 句型 aAaBcbdcc 的直接短语是 AaB(AAaB)、(B)、c(Ac)，其中 AaB 是句柄。4.3（20 分）有上下文无关无法 G1 和语法制导翻译如下：(1) V id var_no:=var_no+1;(2) | id(E)arr_no:=arr_no+1;(3) E E + Vexp_no:=exp_no+1;(4) | Vexp_no:=exp_no+1;(a) （6 分）给出 G1 的识别活前缀的 DFA；1234aa aabABCaa abSa A c BA a B b S c Ac b B d c(b) （4 分） G1 是 LR(0)的吗？为什么？是 SLR(1)的吗？为什么？(c) （3 分
