编译原理与技术模拟试题三.doc

模拟试题三一、填空（10分）1.1 编译程序的工作过程可划分为 、语法分析、 、中间代码生成、代码优化、 等阶段，类型检查工作一般在 阶段进行。1.2 SLR(1)中L的含义是 。1.3 常用的存储分配策略有静态存储分配和动态存储分配，其中，动态存储分配策略包括 分配和 分配。1.4 用LR方法实现语法分析时，典型的操作有 、 、接受和报错。1.5 已知数组M0.5, 1.10以行为主序存放，如果每个元素占2个存储单元，且起始地址为a，则元素M2,3的地址是 。二、单选题（20分）2.1识别上下文无关语言的自动机是 。 A. 下推自动机B. NFA C. DFA D. 图灵机2.2 给定文法AbA|ca，为该文法句子的是 。 A. bb B. bcaC. bcab D. cab2.3 一个句型中的最左 称为该句型的句柄。 A. 短语 B. 直接短语C. 非终结符号 D. 终结符号2.4 已知文法GS:SA1AA1|S0|0。与G等价的正规式是 。 A. 0(0|1)*1 B. 1*|0*1C. 0(1|10)*1D. 1(10|01)*0 2.5从编译程序的语法分析角度看，源程序是句子的集合， 可以较好地反映句子的结构。 A. 线性表 B. 树 C. 完全图 D. 堆栈2.6词法分析的输出由 两部分组成。 A. 字符串和正规式 B. 记号和自动机 C. 文法和正规式 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;beginx := 2; y := 6; f(y,x); print(x,y);end.3.2 （8分）请简要说明进行自上而下的语法分析时，文法中为什么不能有左递归和公共左因子。3.3 （10分）请计算下面文法G中各非终结符的FIRST和FOLLOW集合。该文法是LL(1)文法吗？为什么？G：EE * T | TTT - F | FF(E) | id3.4（6分）设某程序执行到某一时刻时，控制栈中的内容如下所示（其中M是主程序，P、Q、R、S均是过程）。(a) 给出所有在生存期的活动的调用关系(提示：若A调用B，则记为AB)；(b) 试根据访问链中的内容画出主程序和过程的嵌套关系树。四、综合题（40分）4.1（10分）设有正规式r=1(0|1)*0，试给出： （a）（4分）识别该正规集的NFA；（b）（6分）识别该正规集的DFA（要有计算过程）；4.2（20分）设有上下文无关无法GE及其语法制导翻译如下（注：G中终结符id仅由单个英文字母组成，如a, b等）：EE1*TE.place=newtemp; emit(*, E1.place, T.place, E.place;| TE.place=T.place;TT1+FT.place=newtemp; emit(+, T1.place, F.place, T.place;| FT.place=F.place;F(E)F.place=E.place;| idF.place=;(a)（5分）画出句子a+(b+c)*d的分析树；(b)（3分）写出当a=1、b=2、c=3、d=4时的计算结果；（*表示算术乘、+表示算术加）(c)（9分）将文法G简化为：EE*T|T，TT+F|F，Fid，给出其识别活前缀的DFA。(d)（3分）该文法是SLR(1)文法吗？为什么？4.3（10分）阅读以下程序代码if (y 0 or x y) while (x y) do x = x - yelse y = 0 （a）（4分）请画出其代码结构图（程序流程图）；（b）（6分）给出其三地址码序列。模拟试题三参考答案一、填空（10分）1.1 编译程序的工作过程可划分为 词法分析 、语法分析、 语义分析 、中间代码生成、代码优化、 目标代码生成 等阶段，类型检查工作一般在 语义分析 阶段进行。1.2 SLR(1)中L的含义是 从左至右扫描输入序列 。1.3 常用的存储分配策略有静态存储分配和动态存储分配，其中，动态存储分配策略包括 栈式 分配和 堆式 分配。1.4 用LR方法实现语法分析时，典型的操作有 移进 、 归约 、接受和报错。1.5 已知数组M0.5, 1.10以行为主序存放，如果每个元素占2个存储单元，且起始地址为a，则元素M2,3的地址是 a+44 。二、单选题（20分）2.1识别上下文无关语言的自动机是 A 。 A. 下推自动机B. NFA C. DFA D. 图灵机2.2 给定文法AbA|ca，为该文法句子的是 B 。 A. bb B. bcaC. bcab D. cab2.3 一个句型中的最左 B 称为该句型的句柄。 A. 短语 B. 直接短语C. 非终结符号 D. 终结符号2.4 已知文法GS:SA1AA1|S0|0。与G等价的正规式是 C 。 A. 0(0|1)*1 B. 1*|0*1C. 0(1|10)*1D. 1(10|01)*0 2.5从编译程序的语法分析角度看，源程序是句子的集合， B 可以较好地反映句子的结构。 A. 线性表 B. 树 C. 完全图 D. 堆栈2.6词法分析的输出由 D 两部分组成。 A. 字符串和正规式 B. 记号和自动机 C. 文法和正规式 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;beginx := 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：EE * T | TTT - F | FF(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，则记为AB)；(b) 试根据访问链中的内容画出主程序和过程的嵌套关系树。解：（a）调用关系: MPRQSS（b）嵌套关系树:四、综合题（40分）4.1（10分）设有正规式r=1(0|1)*0，试给出： （a）（4分）识别该正规集的NFA；（b）（6分）识别该正规集的DFA（要有计算过程）；解：（a）NFA（b）011222，322，32，324.2（20分）设有上下文无关无法GE及其语法制导翻译如下（注：G中终结符id仅由单个英文字母组成，如a, b等）：EE1*TE.place=newtemp; emit(*, E1.place, T.place, E.place;| TE.place=T.place;TT1+FT.place=newtemp; emit(+, T1.place, F.place, T.place;| FT.place=F.place;F(E)F.place=E.place;| idF.place=;(a)（5分）画出句子a+(b+c)*d的分析树；(b)（3分）写出当a=1、b=2、c=3、d=4时的计算结果；（*表示算术乘、+表示算术加）(c)（9分）将文法G简化为：EE*T|T，TT+F|F，Fid，给出其识别活前缀的DFA。(d)（3分）该文法是SLR(1)文法吗？为什么？解：(a) (b) 1+(2+3)*4=1+5*4=24 (c)拓广文法，加S-E (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