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

《编译原理与技术模拟试题一》由会员分享，可在线阅读，更多相关《编译原理与技术模拟试题一（8页珍藏版）》请在装配图网上搜索。

1、模拟试题一 一、填空题（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.

2、1文法的终结符集和非终结符集的交集一定为空。词法分析器交给语法分析器的文法符号一定是 ，它只能出现在产生式的右部。 A. 终结符 B. 非终结符 C. 产生式 D. 起始符号 2.2为数组声明a:array[1..4, 2..3]中a分配的存储空间的首地址为base_a，且每个数组元素占据一个存储单元。若以行为主存放，数组元素a[3, 3]在存储空间中相对base_a的偏移量是 。 A. 2 B. 3 C. 5 D. 6 2.3主流程序设计语言（如Pascal、C++等）均采用 和最近嵌套原则，为此类语言的编译器设计的符号表应该

3、具有后进先出的性质。 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.

4、 自左向右扫描输入 C. 最左归约 D. 自右向左扫描输入 2.7改写文法或者规定文法符号的优先级和结合性是 的基本方法。 A. 代码生成 B. 语法分析 C. 语义分析 D. 去除文法的二义性 2.8 是正规式(1|3|5)(202)(c|de)表示的正规集合中的元素。 A. 135202cde B. 1202c C. 302cde D. 52c 2.9 表达式“(a+b)* (c-d)”的后缀表示为 。 A. ab+cd-* B. abcd+-* C. ab+*cd- D. abcd*+- 2

5、.10若程序P经编译并链接后可执行，则 。 A. P是正确的程序 B. P中没有语法错误 C. P中没有逻辑错误 D. P在运行中不会出错 三、简答题（30分） 3.1（6分） 有文法G：S→aSbS|bSaS|ε和G产生的一个句子ababab。 (a) 该文法是二义的吗？为什么？　 (b) 该文法产生的语言L(G)=？ 3.2（10分）有文法G：S→(L)|a, L→L,S|S。 (a) 说明G不是LL(1)文法； (b) 将G改写为LL(1)文法。 3.3（5分）简述过程的活动和活动的生存期。 3.4（9分）给出语句while

6、 (a int f(int n) { if (n<2) return n; return f(n-1)+f(n-2); } void main(){ int a=4; cout<

7、态？为什么？ (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 ,

8、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的三地

9、址码序列。 4.3（15分）已知一个NFA如下图所示。 (a) (5分)用自然语言简要叙述该自动机所识别的语言的特点，列举两个它可识别的串。 (b) (2分)写出与该自动机等价的正规式r。 (c)（8分）用子集法构造识别r的最小DFA。 模拟试题一参考答案 一、填空题（10分） 1.1从程序运行的角度看，编译程序和解释程序的主要区别是： 运行目标程序时控制权在解释程序而不在目标程序，或者是否生成目标代码，或者是否与机器相关 。 1.2编译程序的基本组成有：词法分析、 语法分析 、 语义分析 、中间代码生成、代码优化、 目标代码生成 、 表格管理 和

10、 出错处理 。 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:array[1..4, 2..

11、3]中a分配的存储空间的首地址为base_a，且每个数组元素占据一个存储单元。若以行为主存放，数组元素a[3, 3]在存储空间中相对base_a的偏移量是 C 。 A. 2 B. 3 C. 5 D. 6 2.3主流程序设计语言（如Pascal、C++等）均采用 A 和最近嵌套原则，为此类语言的编译器设计的符号表应该具有后进先出的性质。 A. 静态作用域 B. 动态作用域 C. 静态绑定 D. 动态绑定 2.4参数传递中，值调用传递的是实参的右值（或值），引用调用传递的是实参的 B 。 A. 右值 B. 左值 C. 名字 D.

12、 结果 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

13、B 是正规式(1|3|5)(202)(c|de)表示的正规集合中的元素。 A. 135202cde B. 1202c C. 302cde D. 52c 2.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：S

14、→aSbS|bSaS|ε和G产生的一个句子ababab。 (a)该文法是二义的吗？为什么？　 (b)该文法产生的语言L(G)=？ 解： (a) 是二义文法，对句子ababab存在两个分析树如下所示： (b) L(G)={a,b个数相等的a,b串} 3.2（10分）有文法G：S→(L)|a, L→L,S|S。 (a)说明G不是LL(1)文法； (b)将G改写为LL(1)文法。 解： (a) 因为FIRST(L, S)∩FIRST(S)={a}，即非终结符L产生式的两个候选项有公共左因子，所以G不是LL(1)文法。 (b) G中有左递归，消除左递归如下： 1．将没有直

15、接左递归的S代入有直接左递归的L产生式，得： L→L,(L)| L,a | (L)|a （或：L→L,S | (L)|a） 消除直接左递归，得：L→ (L)L|aL L→,(L)L| ,aL |ε 最后的消除左递归的文法G： G： S→(L)|a L→ (L)L|aL L→,(L)L| ,aL |ε （或：L→,SL|ε） 3.3（5分）简述过程的活动和活动的生存期。 解：过程的一次运行称为过程的一次活动；活动的生存期是指从进入活动的第一条指令开始执行，到离开活动的最后一条指令执行完成的时间，其中包括被调用过程活动的生存期。 3.4（9分）给出语句while (a

16、

17、104 goto 101 105 t1 := y+z 106 x := t1 107 goto 101 108 ... 四、综合题（40分） 4.1（15分）有C++程序如下所示： #include int f(int n) { if (n<2) return n; return f(n-1)+f(n-2); } void main(){ int a=4; cout<

18、），请问(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分）某表达式的语法制导翻译方案如下(运算

19、符-,*,+的优先级依次递减)。 （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

20、） 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 (

21、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.子集法构造DFA a b {0} A {0

22、} A {0,1} B {0,1} B {0} A {0,1,2} C {0,1,2} C {0,2} D {0,1,2} C {0,2} D {0,2} D {0,1,2} C 即：（其中，C和D中含NFA的终态，故C和D是DFA的终态） a b A A B B A C C D C D D C 2．最小化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合并成一个状态。 a b A A B B A C C C C