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

11. 目标代码有哪几种形式？生成目标代码时通常应考虑哪几个问题？

12. 一字母表Σ={a, b}，试写出Σ上所有以a为首的字组成的正规集相对应的正规式。 13. 基本的优化方法有哪几种？

nn

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

?

procedure p(x, y, z); begin y:=y+z; z:=y*z+x end; begin

第7页共6页

a:=2; b:=3;

p(a+b, b, a); print a end.

试问，若参数传递的方式分别采用传地址和传值时，程序执行后输出 a的值是什么? 16.写出表达式a＋b*(c-d)/e的逆波兰式和三元序列。 17.证明文法G(A) A→AA | (A)| ε 是二义性的。

**

18.令Σ={a,b}，则正规式ab|ba表示的正规集是什么？ 19.何谓DISPLAY表？其作用是什么？ 20.考虑下面的程序：

?

procedure p(x, y, z)； begin y:=y+2; z:=z+x; end begin

a:=5; b:=2;

p(a+b, a-b, a); print a end.

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

nnm

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

S→S*aF | aF | *aF F→+aF | +a

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

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

S→AB |B A0 A→AD |C

B→2 |4 |6 |8

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

3.句子b(aa)b的规范归约过程： 步骤 符号栈 输入串 动作 0 1 2 3 4 # #b #b( #b(a #b(A 第8页共6页

b(aa)b# (aa)b# aa)b# a)b# a)b# 预备 移进 移进 移进 归约 5 6 7 8 9 10 #b(Ma #b(Ma) #b(B #bA #bAb #S )b# b# b# b# # # 移进 移进 归约 归约 移进 接受 4.传地址 A=6, B=16 传值 A=2, B=4

nm

5.L(G)={dab |n>0, m≥0} 6.证明：

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

S=>SaS=>SaSaS=>aSaS=>aaS=>aa S=>SaS=>aS=>aSaS=>aaS=>aa 7.句子 adccd 的分析过程： 步骤 符号栈 输入串 产生式 0 1 2 3 4 5 6 7 8 9 10 11 12 13 8.所求文法是G[S]: S→AB

A→aAc | D D→bD | b B→aBb | aabb 9.

函数 f g a 4 5 ( 2 5 ) 4 2 , 4 3 #S #AB #AAa #AA #Ad #A #SB #Sc #S #AB #Ac #A #d # adccd# adccd# adccd# dccd# dccd# ccd# ccd# ccd# cd# cd# d# d# d# # A→BS B→c B→c A→d A→d S→BA B→aA

10.优化：对程序进行各种等价变换，使得从变换后的程序出发，能产生更有效的目标代码。 三种级别：局部优化、循环优化、全局优化

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

第9页共6页

应着重考虑的问题：

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

(2)如何充分利用寄存器，以减少访问内存次数； (3)如何充分利用指令系统的特点。 12.正规式 a ( a | b )*。

13.删除多余运算，代码外提，强度削弱，变换循环控制条件，合并已知量，复写传播和删除无用赋值。 14.文法G[S]:

S→aB | a B→bc |bBc 15.传值 a=2 传地址 a=15

16.逆波兰式: abcd-*e/+

三元序列: op arg1 arg2 (1) - c d (2) * b (1) (3) / (2) e (4) + a (3) 17.证明：

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

A=>AA=>(A)A=>()A=>()

A=>AA=>A=>(A)=>()

**

18.(ab|ba)={a,b,ab,ba,aab,bba??} 19.Display表: 嵌套层次显示表

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

21.所求文法是G[S]: S→AC

A→aaAbb | ab C→ccC | cc

22.逆波兰式 abc+e*bc+f/+:=

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

*

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

S→aFS’ | *aFS’ S’→*aFS’ | ε F→+aF | +a

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

第10页共6页