山东理工 编译原理 期末试题

山东理工大学编译原理 2010-2011第一学期期末试题

一．（15）

1.乔姆斯基把文法分成____种类型，在编译原理中用来描述程序设计语言词法结构的是______文法，用来描述程序设计语言语法结构的是______文法。

2.一个上下文无关文法 G 包括四个组成部分：一组终结符号，一组______，一个开始符号以及一组______。

3.自上而下语法分析法会遇到的主要问题有______和______。

4.最右推导也称______，最右推导的逆过程称为最左归约，也称为______。

5.一个文法符号的______属性是通过语法树中它的文结点和/或兄结点的相应文法符号和属性来计算的，而______属性是通过语法树中它的子结点的属性之值来计算的。 6.常用的两种动态存贮分配方法是______动态分配和______动态分配。

7.在 PASCAL 语言中，为了在过程的嵌套调用过程中实现对非局部名字的访问，可以采用______和活动记录，或______和活动记录的方式。

二．（15）

1. 请画出编译程序的总框图。

2. 请给出表达式(a+b)*c+c/d 的后缀式，并将其表示成三元式、四元式和间接三元式。

3.设文法 G(s):S→(A)|a A→A+s|s ，请构造各非终结符的 FIRSTVT 集合和 LASTVT 集合。

三．（10）将下列语句翻译成四元式序列（假定地址从 100 开始） While( a>b and a

If a>0 then b:= b+1 Else d:= d-1

四．（15）构造一个 DFA，它接收∑={a,b}上所有满足如下条件的字符串：每个 a 都有 b 直接跟在右边。

五．（10）有文法 G[S]:S→BA.A→BS|d.B→aA|bS|C

(1)

证明文法 G 是 LL(1)文法 (2)构造 LL(1)分析表。

六．（10）设有基本块.B:= 3 G:= B*F K:= B*5

D:= A+C H:= A+C L:= K+J E:= A*C I:= A*C M:= L F:= D+E J:= H+I

(1) 画出 DAG 图 (2)假设基本块出口时只有 L 被引用，请写出优化后的四元序

八．（10）

现有如下基本块的三地址代码序列.

T1:= A+B T2:= T1-C T3:= D=T2 T4:= D+E W:= T3*T4.

假定只有两个寄存器 R0 和 R1 可用，变量 W 在基本块出口的活跃变量，试利用基本块的代码生成算法，生成其汇编语言的目标代码，并给出其寄存器描述和地址描述。

九．（15）某语言的拓广文法 G’为：(0)S'→S (1)S→AB (2)A→aBa| (3)B→bab| (1)请构造该文法的 LR(0)项目集规范族；

(2)该文法是 SLR(1)文法吗？若是构造相应分析表； (3)给出输入串 baab#分析过程

本文来源：https://www.bwwdw.com/article/1mut.html