编译原理与技术模拟试题一

模拟试题一一、填空题（10分）1.1从程序运行的角度看，编译程序和解释程序的主要区别是： 。1.2编译程序的基本组成有：词法分析、 、 、中间代码生成、代码优化、 、 和 。1.3 正规式r和s等价说明 相同。1.4不含子串baa的所有a、b符号串的正规式是 。1.5 规范规约（最左归约）和 是互逆的两个过程。1.6在赋值语句“x = y + 2”中，常量2是右值，变量x提供 ，变量y提供右值。二、选择题（20分）2.1文法的终结符集和非终结符集的交集一定为空。词法分析器交给语法分析器的文法符号一定是 ，它只能出现在产生式的右部。A. 终结符B. 非终结符C. 产生式D. 起始符号2.2为数组声明a:array1.4, 2.3中a分配的存储空间的首地址为base_a，且每个数组元素占据一个存储单元。若以行为主存放，数组元素a3, 3在存储空间中相对base_a的偏移量是 。 A. 2B. 3 C. 5D. 62.3主流程序设计语言（如Pascal、C+等）均采用 和最近嵌套原则，为此类语言的编译器设计的符号表应该具有后进先出的性质。A. 静态作用域B. 动态作用域C. 静态绑定D. 动态绑定2.4参数传递中，值调用传递的是实参的右值（或值），引用调用传递的是实参的 。A.右值B. 左值 C. 名字D. 结果2.5 静态数据区用于存放一对一的绑定、且编译时就可确定存储空间大小的数据； 用于存放一对多的绑定且与活动同生存期的数据。A. 栈B. 堆 C. 数组D. 链表2.6 LR(1)分析法中，L的含义是 ，R的含义是最右推导的逆，1的含义是确定下一个动作向前看1个终结符。A. 最左推导B. 自左向右扫描输入C.最左归约 D. 自右向左扫描输入2.7改写文法或者规定文法符号的优先级和结合性是 的基本方法。A. 代码生成 B. 语法分析 C. 语义分析 D. 去除文法的二义性2.8 是正规式(1|3|5)(202)(c|de)表示的正规集合中的元素。 A. 135202cdeB. 1202cC. 302cde D. 52c2.9 表达式“(a+b)* (c-d)”的后缀表示为 。 A. ab+cd-*B. abcd+-*C. ab+*cd-D. abcd*+-2.10若程序P经编译并链接后可执行，则 。 A. P是正确的程序B. P中没有语法错误C. P中没有逻辑错误 D. P在运行中不会出错三、简答题（30分）3.1（6分） 有文法G：SaSbS|bSaS|和G产生的一个句子ababab。(a) 该文法是二义的吗？为什么？(b) 该文法产生的语言L(G)=？3.2（10分）有文法G：S(L)|a, LL,S|S。(a) 说明G不是LL(1)文法；(b) 将G改写为LL(1)文法。3.3（5分）简述过程的活动和活动的生存期。3.4（9分）给出语句while (ab) do if (cd) then x:= y+z的中间代码序列。四、综合题（40分）4.1（15分）有C+程序如下所示：#include int f(int n)if (n2) return n;return f(n-1)+f(n-2);void main() int a=4; coutf(a)endl;(a)（5分）画出程序运行时的活动树；(b)（3分）给出程序的运行结果；(c)（5分）若控制栈从左向右增长（最右边是栈顶），请问(main, f(4), f(1)是不是一个可能的控制栈状态？为什么？(d)（2分）为C语言设计的栈式存储分配策略中，是否需要display？为什么？4.2（10分）某表达式的语法制导翻译方案如下(运算符-,*,+的优先级依次递减)。（1） M M.stat:=nextstat; （2） E E1 + M E2 backpatch(E1.fc，M.stat)；E.tc:=merge(E1.tc,E2.tc); E.fc := E2.fc; （3） E E1 * M E2 backpatch(E1.tc, M.stat)；E.fc:=merge( E1.fc , E2.fc); E.tc:=E2.tc; （4） E - E1 E.tc:=E1.fc; E.fc:=E1.tc; （5） E (E1) E.tc:=E1.tc; E.fc:=E1.fc; （6） E id E.tc:=mkchain(nextstat); E.fc:=mkchain(nextstat+1);emit(if id.place goto _); emit(goto _); (a)（5分）给出表达式p*(-a)+b的注释分析树；(b)（5分）根据上述翻译方案，生成表达式p*(-a)+b的三地址码序列。4.3（15分）已知一个NFA如下图所示。(a) (5分)用自然语言简要叙述该自动机所识别的语言的特点，列举两个它可识别的串。(b) (2分)写出与该自动机等价的正规式r。(c)（8分）用子集法构造识别r的最小DFA。模拟试题一参考答案一、填空题（10分）1.1从程序运行的角度看，编译程序和解释程序的主要区别是： 运行目标程序时控制权在解释程序而不在目标程序，或者是否生成目标代码，或者是否与机器相关 。1.2编译程序的基本组成有：词法分析、 语法分析 、 语义分析 、中间代码生成、代码优化、 目标代码生成 、 表格管理 和 出错处理 。1.3 正规式r和s等价说明 r和s表示的正规集 相同。1.4不含子串baa的所有a、b符号串的正规式是 a*(b|ba)* 。1.5 规范规约（最左归约）和 规范推导 是互逆的两个过程。1.6在赋值语句“x = y + 2”中，常量2是右值，变量x提供 左值 ，变量y提供右值。二、选择题（20分）2.1文法的终结符集和非终结符集的交集一定为空。词法分析器交给语法分析器的文法符号一定是 A ，它只能出现在产生式的右部。A. 终结符B. 非终结符C. 产生式D. 起始符号2.2为数组声明a:array1.4, 2.3中a分配的存储空间的首地址为base_a，且每个数组元素占据一个存储单元。若以行为主存放，数组元素a3, 3在存储空间中相对base_a的偏移量是 C 。 A. 2B. 3 C. 5D. 62.3主流程序设计语言（如Pascal、C+等）均采用 A 和最近嵌套原则，为此类语言的编译器设计的符号表应该具有后进先出的性质。A. 静态作用域B. 动态作用域C. 静态绑定D. 动态绑定2.4参数传递中，值调用传递的是实参的右值（或值），引用调用传递的是实参的 B 。A. 右值B. 左值 C. 名字D. 结果2.5 静态数据区用于存放一对一的绑定、且编译时就可确定存储空间大小的数据； A 用于存放一对多的绑定且与活动同生存期的数据。A. 栈B. 堆 C. 数组D. 链表2.6 LR(1)分析法中，L的含义是 B ，R的含义是最右推导的逆，1的含义是确定下一个动作向前看1个终结符。A. 最左推导B. 自左向右扫描输入C.最左归约 D. 自右向左扫描输入2.7改写文法或者规定文法符号的优先级和结合性是 D 的基本方法。A. 代码生成 B. 语法分析 C. 语义分析 D. 去除文法的二义性2.8 B 是正规式(1|3|5)(202)(c|de)表示的正规集合中的元素。 A. 135202cdeB. 1202cC. 302cde D. 52c2.9 表达式“(a+b)* (c-d)”的后缀表示为 A 。 A. ab+cd-*B. abcd+-*C. ab+*cd-D. abcd*+-2.10若程序P经编译并链接后可执行，则 B 。 A. P是正确的程序B. P中没有语法错误C. P中没有逻辑错误 D. P在运行中不会出错三、简答题（30分）3.1（6分） 有文法G：SaSbS|bSaS|和G产生的一个句子ababab。(a)该文法是二义的吗？为什么？(b)该文法产生的语言L(G)=？解：(a) 是二义文法，对句子ababab存在两个分析树如下所示：(b) L(G)=a,b个数相等的a,b串3.2（10分）有文法G：S(L)|a, LL,S|S。(a)说明G不是LL(1)文法；(b)将G改写为LL(1)文法。解：(a) 因为FIRST(L, S)FIRST(S)=a，即非终结符L产生式的两个候选项有公共左因子，所以G不是LL(1)文法。(b) G中有左递归，消除左递归如下：1将没有直接左递归的S代入有直接左递归的L产生式，得：LL,(L)| L,a | (L)|a （或：LL,S | (L)|a）消除直接左递归，得：L (L)L|aLL,(L)L| ,aL |最后的消除左递归的文法G：G：S(L)|aL (L)L|aLL,(L)L| ,aL |（或：L,SL|）3.3（5分）简述过程的活动和活动的生存期。解：过程的一次运行称为过程的一次活动；活动的生存期是指从进入活动的第一条指令开始执行，到离开活动的最后一条指令执行完成的时间，其中包括被调用过程活动的生存期。3.4（9分）给出语句while (ab) do if (cd) then x:= y+z的中间代码序列。解：程序流图：中间代码：101 (j, a, b, 103)102 (j, -, -, 108)103 (j, c, d, 105)104 (j, -, -, 101)105 (+, y, z, t1)106 (:=, t1, -, x)107 (j, -, -, 101)108 .或：101 if ab goto 103102 goto 108103 if cd goto 105104 goto 101105 t1 := y+z106 x := t1107 goto 101108 .四、综合题（40分）4.1（15分）有C+程序如下所示：#include int f(int n)if (n2) return n;return f(n-1)+f(n-2);void main() int a=4; coutf(a)endl;(a)（5分）画出程序运行时的活动树；(b)（3分）给出程序的运行结果；(c)（5分）若控制栈从左向右增长（最右边是栈顶），请问(main, f(4), f(1)是不是一个可能的控制栈状态？为什么？(d)（2分）为C语言设计的栈式存储分配策略中，是否需要display？为什么？解：(a) 活动树如下：(b) 程序的运行结果为：3(c) 不是一个可能的控制栈状态，因为f(4)不能直接调用f(1)。从活动树也可以看出，f(4)所在的任何一条路径上，f(4)和f(1)不相邻。(d) 不需要，因为display是用于访问非本地数据的。而C程序中不允许过程的嵌套定义，故C程序中的变量或者是全程的，或者是本地的，没有所谓的非本地数据。4.2（10分）某表达式的语法制导翻译方案如下(运算符-,*,+的优先级依次递减)。（1） M M.stat:=nextstat; （2） E E1 + M E2 backpatch(E1.fc，M.stat)；E.tc:=merge(E1.tc,E2.tc); E.fc := E2.fc; （3） E E1 * M E2 backpatch(E1.tc, M.stat)；E.fc:=merge( E1.fc , E2.fc); E.tc:=E2.tc; （4） E - E1 E.tc:=E1.fc; E.fc:=E1.tc; （5） E (E1) E.tc:=E1.tc; E.fc:=E1.fc; （6） E id E.tc:=mkchain(nextstat); E.fc:=mkchain(nextstat+1);emit(if id.place goto _); emit(goto _); (a)（5分）给出表达式p*(-a)+b的注释分析树；(b)（5分）根据上述翻译方案，生成表达式p*(-a)+b的三地址码序列。解：（a）注释分析树如下：(b)三地址码序列如下：(1) if p goto 3 (2) goto 5 (3) if a goto 5 (4) goto - (5) if b goto - (6) goto -4.3（15分）已知一个NFA如下图所示。(a) (5分) 用自然语言简要叙述该自动机所识别的语言的特点，列举两个它可识别的串。(b)（2分）写出与该自动机等价的正规式r。(c)（8分）用子集法构造识别r的最小DFA。解：(a) 该自动机所识别的语言是包含子串“bb”的a、b符号串。例如，abba、abbbab。(b) r =(a|b)*bb(a|b)*(c) 1.子集法构造DFAab0 A0 A0,1 B0,1 B0 A0,1,2 C0,1,2 C0,2 D0,1,2 C0,2 D0,2 D0,1,2 C即：（其中，C和D中含NFA的终态，故C和D是DFA的终态）abAABBACCDCDDC2最小化DFA：= A,B = C,D move(A,a) = , move(B,a) = move(A,b) = , move(B,a) = 将分割成两个和。 因此，原状态集合划分成= A = C,D = B move(C,a) = , move(D,a) = move(C,b) = , move(D,b) = 状态C和D不可区分，因此可将C、D合并成一个状态。abAABBACCCC