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

《编译原理》期末试题（三）

1、 从优化的范围的角度，优化可以分哪两类？对循环的优化可以有哪三种？ 答：从优化的范围的角度，优化可以分为局部优化和全局优化两类； 对循环的优化有三种：循环不变表达式外提、归纳变量删除与计算强度削减。 2、写出表达式a=b*c+b*d对应的逆波兰式、四元式序列和三元式序列。 答：逆波兰式： abc*bd*+:= 四元式序列：

三元式序列: OP ARG1 ARG2

(1) (* b， c ) (2) (* b， d ) (3) (+ (1)， (2)) (4) (:= (3)， a)

(1) (*， b， c， t1) (2) (*， b， d， t2) (3) (+， t1， t2，t3) (4) (:=， t3， /， a)

3、对于文法G(S):

S ?bMbM ?(L|aL ?Ma）

答：1） S?bMb?b(Lb?b(Ma)b 2） 短语: Ma)， (Ma)， b(Ma)b 直接短语: Ma) 句柄: Ma)

b ( S M b T L M a ) 三、 设有字母表{a，b}上的正规式R=(ab|a)*。

解：（1）

2 - 0 ε a 1 a b ε + 3

（2）将（1）所得的非确定有限自动机确定化

ε a b -0 1 1 3 12 2 1 +3 第21页共6页

2 +

-+ a 0 b a 1 + a

（3）对（2）得到的DFA化简，合并状态0和2 为状态2：

2 -+ b a 1 +

（4）令状态1和2分别对应非终结符B和A

G: A→aB|a|ε； B→aB|bA|a|b|ε；可化简为：G: A→aB|ε；B→aB|bA|ε

a 四、 设将文法G改写成等价的LL(1)文法，并构造预测分析表。

G：S→S*aT|aT|*aT； T→+aT|+a

解：消除左递归后的文法G’: S→aTS’|*aTS’

S’→*aTS’|ε

T→+aT|+a

提取左公因子得文法G’’: S→aTS’|*aTS’

S’→*aTS’|ε T→+aT’

T’→T|ε Select(S→aTS’)={a} Select(S→*aTS’)={*}

Select(S→aTS’)∩Select(S→*aTS’)=Ф Select(S’→*aTS’)={*}

Select(S’→ε)=Follow(s’)={#}

Select(S’→*aTS’)∩Select(S’→ε)= Ф Select(T→+aT’)={+}

Select(T’→T)=First(T) ={+}

Select(T’→ ε)=Follow(T’)={*,#}

Select(T’→T)∩Select(T’→ε)= Ф 所以该文法是LL(1)文法。 预测分析表： * + a # S →*aTS’ →aTS’ 第22页共6页

S’ →*aTS’ T T’ → ε →ε → ε →+aT’ →T 6设文法G 为： S→A；A→BA|ε；B→aB|b

解：（1）拓广文法G’：(0) S’→S (1) S→A (2) A→BA(3) A→ε(4)

B→aB (5) B→b ； FIRST(A) = {ε, a, b}；FIRST(B) = {a, b}

构造的DFA 如下:

项目集规范族看出，不存在冲突动作。∴该文法是LR(1)文法。

（2） LR(1)分析表如下：

(3)输入串abab 的分析过程为：

第23页共6页

简答题 3、设有文法G[S]: S→S(S)S|ε，该文法是否为二义文法？说明理由。 答：是二义的，因为对于（）（）可以构造两棵不同的语法树。 S S

S ( S ) S S ( S ) S

ε ε S ( S ) S S ( S ) S ε ε

ε ε ε ε ε ε

五、 给定文法G[S]：

S→aA|bQ； A→aA|bB|b；B→bD|aQ ；Q→aQ|bD|b；D→bB|aA ；E→aB|bF

F→bD|aE|b

构造相应的最小的DFA 。

解：先构造其NFA： 用子集法将NFA确定化：

S A Q BZ DZ D B a A A Q Q A A Q b Q BZ DZ D B B D

第24页共6页