编译原理练习题(2)

1、语法制导的翻译是基于属性文法的，属性有两类，即综合属性和继承属性。

2、在语法树中，一个结点的综合属性的值由其子结点的属性确定，而继承属性则由该结点的父结点或兄弟结点的某些属性确定。

3、语义分析阶段所生成的与源程序等价的中间表示形式可以有逆波兰表示、三元式表示和四元式表示等。

4、生成中间代码主要是为了使目标代码的优化容易实现。

简答题：

1、给出下列表达式的逆波兰式： (1)-a+b*(-c+d) (2)a+b*(c-d)/e-f 答：(1)a-bc-d+*+ (2)abcd-*e/+f-

2、给出-(a+b)*(c+d)-(a+b+c)的三元式和四元式。(其中单目运算—用@表示) 1 (+,a,b) (+,a,b,T1)

2 (@,1,_) (@,T1,_,T2) 3 (+,c,d) (+,c,d,T3) 4 (*,2,3) (*,T2,T3,T4) 5 (+,a,b) (+,a,b,T5) 6 (+,c,5) (+,T5,c,T6) 7 (-,4,6) (-,T4,T6,T7)

优化：

1、下列 优化方法不是针对循环优化进行的。

A、强度削弱 B、删除归纳变量 C、删除公共子表达式 D、代码外提 2、对于一个基本块来说，正确的说法是 。 A、只有一个入口语句和一个出口语句 B、有一个入口语句和多个出口语句 C、有多个入口语句和一个出口语句 D、只有多个入口语句和多个出口语句

判断：

数组元素的地址计算与数组的存储方式有关。 循环中的不变运算都可以提到循环外。

根据优化设计到的程序范围，优化可分为局部优化、循环优化和全局优化三个不同的级别。 局部优化是在基本块范围内进行的一种优化。

在优化中，可把循环中的不变运算提到循环外去，这种方法称为代码外提。

简答题

1、已知三地址代码序列为： (1) i:=1 (2) i:=i+1 (3) j:=1

6

(4) j:=j+1 (5) k:=i mod j

(6) if k≠0 goto (4)

(7) if i≠j goto (10) (8)write I (9)writeln

(10) if i<10000 goto(2) (11)halt

划分基本块，并画出流图

2、试把以下程序划分为基本块并作出其程序流图。 read C A:=0 B:=1

L1:A:=A+1 iF B≥C goto L2 B:=B+1 goto L1 L2:write A halt

2、 试构造以下基本块G的DAG

(1)T0：=3.14 (2)T1：=2*T0 (3)T2：=R+r (4)A：=T1*T2 (5) B：=A (6) T3：=2*T0 (7)T4：=R+r (8T5：=T3+T4 (9)T6：=R-r (10) B：=T5*T6

A,T5

N6 *

T0 N1 N2

read C A:=0 B:=1 L1:A:=A+1 iF B≥C goto L2 B:=B+1 goto L1 L2:write A halt B N8 * T2,T4 N5 + T1,T3 N3 R N4 r N7 - T6 3.14 6.28 7

已知如下翻译模式，用回填法给出a>b or c>d and e>f 的四元式序列，要求给出简单过程。 文法及其翻译模式如下：

(1)E→E1 and M E2 {backpatch(E1.truelist,M.quad);

E.truelist:= E2.truelist)

E.falselist:=merge(E1.falselist,E2.falselist )

(2) E→E1 or M E2 {backpatch(E1.falselist,M.quad);

E.truelist:=merge(E1.truelist,E2.truelist) E.falselist:=E2.falselist}

(3)E1→id1 relop id2 {E.truelist:= makelist(nextquad);

E.falselist:=makelist(nextquad+1);

Emit(‘j’relop.op ‘,’id1.place ‘,’id2.place ‘,’ ‘0’ );Emit(‘j,-,-,0’)}

(4)M→ε {M.quad:=nextquad} E.t={100,104 } E.f={103，105} E.t={100 } or M.q={102} E.t={ 104} E.f={101 } E.f={103,105} ε a > b E.t={102 } and M.q={104} E.t={ 104} E.f={103 }E.f={105} ε c > d e > f

四元式序列为： 100 （j>，a，b，0） 101 （j，--，--，102） 102 (j>，c，d，104) 103 (j，--，--，0） 104 (j>，e，f，0) 105 (j，--，--，0）

8

有文法G（S）： S→A|B A→aAb|c B→aBb |d

试构造此方法的LR（0）项目集规范族。 1)将文法G拓广为文法G’ S’->S S->A S->B A->aAb

2)列出LR（0）的所有项目：

1．S’->?S 5. A->?aAb 9. A->?c 13. B->?aBb 17.B-> ?d S->S? 6. A->a?Ab 10. A->c? 14. B->a?Bb 18 B->d? S->? A 7. A->aA?b 11. S->?B 15. B->aB?b S->A? 8.A->aAb? 12. S->B? 16 B->aBb? 3)用ε-CLOSURE办法构造文法G’的LR（0）项目集规范族： I0: S’->?S ,S->? A, A->?aAb, A->?c, S->?B, B->?aBb, B-> ?d I1: S’->S? I2: S->A? I3: S->B?

I4: A->a?Ab, A->?aAb, A->?c, B->a?Bb, B->?aBb, B-> ?d I5: A->c? I6: B->d? I7: A->aA?b I8: A->aAb? I9: B->aB?b I10: B->aBb?

9

A->c B->aBb B->d

已知现在寄存器R，其中A是活跃变量，试将以下三地址代码翻译成汇编代码的形式。

T1：=A+B T2：=T1*C A：=T2+D 目标代码序列为： LD R,A ADD R,B MUL R,C ADD R,D ST R,A

10

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库编译原理练习题(2)在线全文阅读。