编译原理期末试题(8套含答案+大题集)

a S S→ A A→ B B→ b S→ A→ B→ c S→ A→ B→c d A→d # 给出句子 的分析过程。

8. 写一个文法G, 使其语言为 L(G)={ l>=0, m>=1, n>=2} 9. 已知文法G(S): S→ (T) T→

的优先关系表如下: 关系 a ( ) , a - - .> .> ( <. <. =. <. ) - - .> .> , <. <. .> .> 请计算出该优先关系表所对应的优先函数表。 10. 何谓优化?按所涉及的程序范围可分为哪几级优化?

11. 目标代码有哪几种形式?生成目标代码时通常应考虑哪几个问题? 12. 一字母表Σ={a, b},试写出Σ上所有以a为首的字组成的正规集相

对应的正规式。

13. 基本的优化方法有哪几种?

14. 写一个文法G, 使其语言为 L(G)={ n≥0} 15. 考虑下面的程序:

p(x, y, z); ; * ; 2; 3;

p(, b, a); a .

试问,若参数传递的方式分别采用传地址和传值时,程序执行后输出 a的值是什么?

16.写出表达式a+b*()的逆波兰式和三元序列。 17.证明文法G(A) A→ | (A)| ε 是二义性的。 **

18.令Σ={},则正规式aa表示的正规集是什么? 19.何谓表?其作用是什么?

20.考虑下面的程序: …

p(x, y, z);

13 / 81

2; ; 5; 2;

p(, , a); a .

试问,若参数传递的方式分别采用传地址和传值时,程序执行后输出 a的值是什么?

21.写一个文法G, 使其语言为 L(G)={ n>0为奇数, m>0为偶数} 22.写出表达式()*()的逆波兰式和三元序列。 23.一个文法G别是(1)文法的充要条件是什么? 24.已知文法G[S]

S→S* | | * F→ |

消除文法左递归和提公共左因子。

25.符号表的作用是什么?符号表查找和整理技术有哪几种? 答案:1.所求文法是G[S]:

S→ A0 A→

B→2 |4 |6 |8

C→1 |3 |5 |7 |9 D→0 2.输出是4231

3.句子b()b的规范归约过程: 步骤 符号栈 输入串 动作 0 # b预备 () 1 (移进 ) 2 ( ) 移进 3 (a a移进 ) 4 (A a归约 ) 5 ( 移进) 6 () 移进 7 (B 归约 8 归约 9 移进 10 接受 4.传地址 6, 16 传值 2, 4 5(G)={ >0, m≥0} 6.证明:

14 / 81

因为文法G[S]存在句子有两个不同的最左推导,所以文法G[S]是是二义性的。

>>>>>

>>>>>

7.句子 的分析过程: 步骤 符号栈 输入串 产生式 0 1 S→ 2 B→ 3 4 A→d 5 6 A→ 7 B→c 8 9 B→c 10 11 12 A→d 13 # # 8.所求文法是G[S]: S→ A→ | D D→ | b

B→ | 9.

函数 f g a ( ) , 4 2 4 4 5 5 2 3 10.优化:对程序进行各种等价变换,使得从变换后的程序出发,能产生更有效的目标代码。

三种级别:局部优化、循环优化、全局优化

11.目标代码通常采用三种形式:机器语言,汇编语言,待装配机器语言模块。

应着重考虑的问题:

(1)如何使生成的目标代码较短;

(2)如何充分利用寄存器,以减少访问内存次数; (3)如何充分利用指令系统的特点。 12.正规式 a ( a | b )*。 13.删除多余运算,代码外提,强度削弱,变换循环控制条件,合并已知量,

15 / 81

复写传播和删除无用赋值。 14.文法G[S]:

S→ | a B→ 15.传值 2 传地址 15 16.逆波兰式: *

三元序列: 1 2

(1) - c d (2) * b (1) (3) / (2) e (4) + a (3) 17.证明:

因为文法G[S]存在句子 () 有两个不同的最左推导,所以文法G[S]是是二义性的。

>>(A)>()>()

>>>(A)=>() **

18.(aa)={……}

19表: 嵌套层次显示表

由于过程嵌套允许内层过程引用外层过程定义的数据,因此,当一个过程运行时必须跟踪它的所有外层过程的最新活动记录起始地址, 表就是用于登记每个外层过程的最新活动记录起始地址。 20.传地址 12

传值 5

21.所求文法是G[S]: S→ A→ | C→ |

22.逆波兰式 *

三元序列 1 2

(1) + b c (2) * (1) e (3) + b c (4) / (3) f (5) + (2) (4) (6) a (5) 23.一个文法G别是(1)文法的充要条件是: (1) (α) ∩(β)=Ф *

(2) 如果 β=>ε, (α) ∩(A)= Ф 24.消除左递归

S→’ | *’ S’→*’ | ε F→ |

提公共左因子,文法 G’(S) S→’ | *’ S’→*’ | ε F→’

F’→F |ε

25.作用:登记源程序中出现的各种名字及其信息,以及了解各阶段的进展

16 / 81

联系客服:779662525#qq.com(#替换为@) 苏ICP备20003344号-4