编译原理作业标准答案

第一章引言

一、解释下列各词

源语言:编写源程序的语言（基本符号，关键字），各种程序设计语言都可以作为源语言。

源程序: 用接近自然语言（数学语言）的源语言（基本符号，关键字）编写的程序，它是翻译程序处理的对象。

目标程序: 目标程序是源程序经过翻译程序加工最后得到的程序。目标程序

（结果程序）一般可由计算机直接执行。

低级语言：机器语言和汇编语言。

高级语言：是人们根据描述实际问题的需要而设计的一个记号系统。如同自然语言（接近数学语言和工程语言）一样，语言的基本单位是语句，由符号组和一组用来组织它们成为有确定意义的组合规则。

翻译程序: 能够把某一种语言程序（源语言程序）改变成另一种语言程序（目标语言程序），后者与前者在逻辑上是等价的。其中包括：编译程序，解释程序，汇编程序。

编译程序: 把输入的源程序翻译成等价的目标程序（汇编语言或机器语言），

然后再执行目标程序（先编译后执行），执行翻译工作的程序称为编译程序。

解释程序: 以该语言写的源程序作为输入，但不产生目标程序。按源程序中语句动态顺序逐句的边解释边执行的过程，完成翻译工作的程序称为解释程序。

二、什么叫“遍”？

指对源程序或源程序的中间形式（如单词，中间代码）从头到尾扫描一次，并作相应的加工处理，称为一遍。

三、简述编译程序的基本过程的任务。

编译程序的工作是指从输入源程序开始到输出目标程序为止的整个过程，整个过程可以划分5个阶段。

词法分析：输入源程序，进行词法分析，输出单词符号。

语法分析：在词法分析的基础上，根据语言的语法规则把单词符号串分解成各类语法单位，并判断输入串是否构成语法正确的“程序”。

中间代码生成：按照语义规则把语法分析器归约（或推导）出的语法单位翻译成一定形式的中间代码。

优化：对中间代码进行优化处理。

目标代码生成：把中间代码翻译成目标语言程序。

四、编译程序与解释程序的区别？

编译程序生成目标程序后，再执行目标程序；然而解释程序不生成目标程序，边解释边执行。

五、有人认为编译程序的五个组成部分缺一不可，这种看法正确吗？

编译程序的5个阶段中，词法分析，语法分析，语义分析和代码生成生成是必须完成的。而中间代码生成和代码优化并不是必不可少的。优化的目的是为了提高目标程序的质量，没有这一部分工作，仍然能够得到目标代码、

六、编译程序的分类

目前基本分为：诊断编译程序，优化编译程序，交叉编译程序，可变目标编译程序。

第二章高级语言及其语法描述

一、P36

6、令文法为

N → D∣ND

D → 0∣1∣2∣?∣9

⑴文法描述的语言L（G）是什么？

⑵给出句子34，568的最左推导和最右推导。

解：⑴

L（G）={α∣α为可带前导0的正整数}

或L（G）={（0∣1∣2∣?∣9）+ }

或 L（G）={α∣α为数字串}

⑵

最左推导：N?ND?DD?3D?34

N?ND?NDD?DDD?5DD?56D?568

最右推导：N?ND?N4?D4?34

N?ND?N8?ND8?N68?D68?568

7、写出一个文法，使其语言是奇数集，且每个奇数是不以0开头。

解：N → C∣AC∣ABC

C → 1∣3∣5∣7∣9

A → 1∣2∣?∣9

B → B`∣BB`

B` → 0∣A

8、令文法为

E → T∣E+T∣E-T

T → F∣T*F∣T/F

F →（E）∣i

⑴给出i+i*i，i*（i+i）的最左推导和最右推导。

⑵给出i+i+i，i+i*i的语法树。

解：⑴

最左推导E?E+T?T+T?F+T?i+T?i+T*F?i+F*F?i+i*F?i+i*i

E?T?T*F?F*F?i*F?i*(E)?i*(E+T)?i*(T+T)?i*(F+T)?i*(i+T)

?i*(i+F)?i*(i+i)

最右推导E?E+T?E+T*F?E+T*i?E+F*i?E+i*i?T+i*i?F+i*i?i+i*i

E?T?T*F?T*(E)?T*(E+T)?T*(E+F)?T*(E+i)?T*(T+i)?T*(F+i)

?T*(i+i)?F*(i+i)?i*(i+i)

⑵构造语法树

E 最左推导构造语法树

E + T

E + T i

T i

i

10、把下列文法改写为无二义的：

S → SS∣（S）∣（）

解：改写后的文法

S → SA∣（S）∣（）

A →（S）∣（）

第三章词法分析

一、P64

7、构造下列正规式相应的DFA M

⑴构造相应的NFA M

⑵构造转换矩阵表（用子集法）

I I0 I1 S 0 1

{X} {1,2,3} 0 1 {1,2,3} {2,3} {2,3,4} 1 2 3

{2,3} {2,3} {2,3,4} 2 2 3

2,3,4} {2,3,5} {2,3,4} 3 4 3 {2,3,5} {2,3} {2,3,4,Y} 4 2 5 {2,3,4,Y} {2,3,5} {2,3,4} 5 4 3

⑷将DFA M最小化

①将DFA M的状态划分为非终态集{0,1,2,3,4}和终态集{5}

π={0，1，2，3，4}，{5}

②对每一个子集及每一个a∈∑进行考察；

{0，1，2，3，4}1={1，3，3，3，5}?{0，1，2，3，4}

对于输入1是可区别的，将{0，1，2，3，4}分为 {0,1,2，3} 和 {4}。

πnew = {0,1,2，3}，{4}，{5}

③对πnew 进行考察；

{0，1，2，3}0={-，2，2，4}?{0，1，2，3}

由于0结点不能接受输入的数字“0”，并不属于任何状态集，所以先将{0}结点区别出来,又由于3结点输入的数字“0”到达4结点，所以将3结点也区别出来{3}。将{0，1,2，3} 分为 {0} ，{1，2}和 {3}

πnew = {0}，{1,2}，{3}，{4}，{5}

④对πnew 进行考察；

{1,2}0={2}?{1，2}，{1,2}1={3}?{3}

则{1，2}不可划分合为一个状态，最终的结果是；

πnew = {0}，{1,2}，{3}，{4}，{5}。

⑸根据最小化的结果构造矩阵表

旧名 {0} {1，2} {3} {4} {5}

新名 0 1 2 3 4

S 0 1

0 1

1 1 2

2 3 2

3 1 4

4 3 2

⑹构造最小化的DFA M

0 0

12将下图的有限自动机确定化和最小化

⑴该有限自动机输入同一字符a时到达两个不同的结点,所以是NFA。

⑵构造转换矩阵表（用子集法）

I I a I b S a b

{0} {0，1} {1} 0 1 2

{0，1} {0，1} {1} 1 1 2

{1} {0} 2 0

⑶由转换矩阵构造DFA M

⑷将DFA M 最小化

①将DFA M 的状态划分为非终态集{2}和终态集{0，1}

π={2}，{0，1}

②对每一个子集及每一个a ∈∑

进行考察；

{0，1}A ={1}

?{0，1}

{0，1}b ={2，2}?

{2} 对于输入a 和b 均是不可区别的，所以

πnew = {0,1}，{2}

⑸根据最小化的结果构造矩阵表

旧名 {0，1} {2} S a b

新名 0 1 0 0 1

1 0

⑹构造最小化的DFA M

二、14、构造一个DFA M ，它接受∑={0，1}上所有满足如下条件的字符串：每个1都有0直接跟在右边。

⑴写出正规集的正规式的表示形式

（0∣10）*

⑵构造相应的NFA M

⑶构造转换矩阵表（用子集法）

I I0 I1 S 0 1

{X，1，Y} {！，Y} {2} 0 1 2

{1，Y} {1，Y} {2} 1 1 2

{2} {1，Y} 2 1

⑷由转换矩阵构造DFA M

⑸将DFA M最小化

①将DFA M的状态划分为非终态集{2}和终态集{0，1}

π={2}，{0，1}

②对每一个子集及每一个0，1∈∑进行考察；

{0，1}0={1}?{0，1}

{0，1}1={2，2}?{2}

对于输入a和b均是不可区别的，所以

πnew = {0,1}，{2}

⑸根据最小化的结果构造矩阵表

旧名 {0，1} {2} S 0 1

新名 0 1 0 0 1

1 0

⑹构造最小化的DFA M

第四章语法分析-自上而下

一、用P76的文法写出表达式 (i+i)*i 的预测分析过程。

步骤符号栈输入串所用的产生式

0 #E （i+i）*i#

1 #E`T （i+i）*i# E→TE`

2 #E`T`F （i+i）*i# T→FT`

3 #E`T`）E（（i+i）*i# F→（E）

4 #E`T`）E i+i）*i#

5 #E`T`）E`T i+i）*i# E→TE`

6 #E`T`）E`T`F i+i）*i# T→FT`

7 #E`T`）E`T`i i+i）*i# F→i

8 #E`T`）E`T` +i）*i#

9 #E`T`）E` +i）*i# T`→ε

10 #E`T`）E`T+ +i）*i# E`→+TE`

11 #E`T`）E`T i）*i#

12 #E`T`）E`T`F i）*i# T→FT`

13 #E`T`）E`T`i i）*i# F→i

14 #E`T`）E`T` ）*i#

15 #E`T`）E` ）*i# T`→ε

16 #E`T`））*i# E`→ε

18 #E`T` *i#

19 #E`T`F* *i# T`→*FT`

20 #E`T`F i#

21 #E`T`i i# F→i

22 #E`T` #

23 #E` # T`→ε

24 # # E`→ε

二、P81

1、考虑下面文法G

S→ a∣^∣（T）

T→T，S∣S

⑴消除文法的左递归。

⑵经改写后的文法是否是LL（1）的？给出它的预测分析表。

解：

⑴经考察该文法S→ a∣^∣（T）的各侯选式的首字符都是终结符号，所以只有T→T，S∣S是直接左递归。根据改写算法，改写后的文法是：

S→ a∣^∣（T）

T→ST`

T`→，ST`∣ε

⑵证明改写后的文法是否是LL（1）的.

①证明S→ a∣^∣（T）各侯选式的FIRST是否两两相交。

FIRST（a）?FIRST（^）=φ

FIRST（a）?FIRST（（）=φ

FIRST（^）?FIRST（（）=φ

②证明T`→，ST`∣ε的FIRST（T`）和FOLLOW（T`）是否相交。

求FIRST（T`）={，，ε}

FOLLOW（T`）={ ) }

FIRST（T`）? FOLLOW（T`）={，，ε}?{ ) }=φ

该文法是LL（1）的。

⑶构造预测分析表

a ， ^ （） #

S S→ a S→^ S→（T）

T T→ST` T→ST` T→ST` T` T`→，ST` T`→ε

2、下面的文法G

E→ TE`

E`→+E∣ε

T→FT`

T`→T∣ε

F→PF`

F`→*F`∣ε

P→（E）∣^∣a∣b

⑴计算这个文法的每个非终结符的FIRST和FOLLOW。

⑵证明这个文法是LL（1）的

⑶构造它的预测分析表。

解：

⑴求非终结符的FIRST和FOLLOW。

求非终结符的FIRST：

因为E`→+E∣ε，所以FIRST（E`）={+，ε}

因为F`→*F`∣ε，所以FIRST（F`）={*，ε}

因为P→（E）∣^∣a∣b，所以FIRST（P）={（， ^， a， b }

因为F→PF`，所以FIRST（F）= FIRST（P）

因为T→FT`，所以FIRST（T）={FIRST（F）

因为E→ TE`，所以FIRST（E）= FIRST（T）

因为T`→T∣ε，所以FIRST（T`）= FIRST（T）?{ ε}

={（， ^， a， b ，ε}

求非终结符的FOLLOW：

因为E→TE`的E是文法的开始符号，FOLLOW（E）={#}，又因为P→（E），所以FOLLOW （E）={#}?FIRST（））\{ε}={#，)}

因为E→ TE`，所以FOLLOW（E`）=FOLLOW（E）

因为E→TE`，并且E`≠ε，所以FOLLOW（T）=FIRST（E`）\{ε},又因为E`→ε,所以FOLLOW （T）={+}? FOLLOW（E）={+}? {#,}}={+，#,) }.

因为T→FT`，所以FOLLOW（T`）=FOLLOW（T）={+，#,) }.

因为T→FT`，并且T`≠ε，所以FOLLOW（F）=FIRST（T`）\{ε},又因为T`→ε,所以FOLLOW （F）={（，^，a，b }? FOLLOW（T）={（，^，a，b }?{+，#,) }

={（，^，a，b ,+，#,)}

因为F→PF`，所以FOLLOW（F`）=FOLLOW（F）={（，^，a，b ,+，#,)}.

因为F→PF`，并且F`≠ε，所以FOLLOW（P）=FIRST（F`）\{ε},又因为F`→ε,所以FOLLOW （P）={*}? FOLLOW（F）={*}?{（，^，a，b,+,）,# }

={*,（，^，a，b ,+，),# }.

⑵证明这个文法是LL（1）的

①证明P→(E)∣^∣a∣b各侯选式的FIRST是否两两相交。

FIRST（(E)）?FIRST（^）=φ

FIRST（(E)）?FIRST（a）=φ

FIRST（(E)）?FIRST（b）=φ

FIRST（^）?FIRST（a）=φ

FIRST（^）?FIRST（b）=φ

FIRST（a）?FIRST（b）=φ

②证明E`→+E∣ε,T`→T∣ε,F`→*F`∣ε非终结符号的FIRST和FOLLOW是否相交。

FIRST（E`）? FOLLOW（E`）={+，ε}?{#, ) }=φ

FIRST（T`）? FOLLOW（T`）={（， ^， a， b ，ε}?{+，#,) }=φ

FIRST（F`）? FOLLOW（F`）={*，ε}?{（，^，a，b ,+，#,)}=φ

该文法是LL（1）的。

⑶构造预测分析表

+ * ( ) a b ^ #

E TE` TE` TE` TE`

E` +E` εε

T FT` FT` FT` FT`

T` ε T ε T T T ε

F PF` PF` PF` PF`

F` ε *F` εεεεεε

P (E) a b ^

第五章 语法分析-自上而下分析

二、P133

1、 令文法为

E →E+T ∣T

T →T*F ∣F

F →（E ）∣i

证明E+T*F 是它的一个句型，指出这个句型的所有短语，直接短语和句柄。

证明输入串E+T*F 是文法的一个句型，建立一个最右推导:

E ?E+T ?E+T*

F ，E+T*F 是该文法的句型。 E * =>E 且 E + =>E+T*F

所以，E+T*F 是句型E+T*F+i 对于E 的一个短语。 因为 E * =>E+T 且 T ?T*F

所以，T*F 是句型E+T*F 对于T →T*F 的一个直接短语。

句型E+T*F 的短语为E+T*F ，直接短语为T*F ，由于直接短语是唯一的，因此T*F 为句柄。

三、P134

5考虑文法

S →AS ∣b

A →SA ∣a

⑴列出这个文法的所有LR （0）项目。

⑵构造这个文法的LR （0）项目规范族及识别活前缀的DFA 。

⑶这个文法是SLR（1）的吗？若是，构造出它的SLR分析表。

解：

⑴构造拓广文法，并列出文法的所有项目

S`→S S`→·S S`→S·

S→AS S→·AS S→A·S S→AS·

S→b S→·b S→b·

A→SA A→·SA A→S·A A→SA·

A→a A→·a A→a·

⑵构造这个文法的LR（0）项目规范族及识别活前缀的DFA。

⑶证明文法是SLR（1）的吗？

为了验证这个文法是否是SLR(1)文法，必须对LR(0)项目规范族的各个项目集I，验证其是否存在“移进－归约”、“归约－归约”冲突。该项目规范族中的I1,I4,I5存在“移进－归约”，只需证明存在集合的?a,b?，FOLLOW(S`)，FOLLOW(S)，FOLLOW(A)两两不相交。对此求出FOLLOW(S`)＝?＃?，FOLLOW(S)＝?#,a,b?，FOLLOW(A)＝?a,b?。

验证如下：

对状态I1有

FOLLOW(S`)＝?＃?；A→·a；S→·b。

因此FOLLOW(S`)??a,b?＝?＃???a,b?＝φ，所以不存在“移进－归约”冲突。

对状态I4有

FOLLOW(S`)＝?a,b?；A→·a；S→·b。

因此FOLLOW(A)??a,b?=?a,b???a,b?≠φ，所以存在“移进－归约”冲突。

对状态I5也同样存在这种冲突，即FOLLOW(S)??a,b?

=?＃,a,b???a,b?≠φ，因此，该文法不是SLR(1)文法。

四、P135

7、证明下面文法是SLR（1）担不是LR（0）的

S→A

A→Ab∣bBa

B→aAc∣a∣aAb

证明：

因为项目A→Ab·和B→aAb·出现在一个项目集中，造成“归约-归”约冲突，所以不是LR（0）文法。又因为FOLLOW（A）={b，c，#}，FOLLOW（B）={a}使得FOLLOW（A）∩FOLLOW （B）=φ，构造SLR（1）分析表时不会出现冲突，所以该文法是SLR（1）的。

五、对给定文法G，构造分析表，并利用此分析表判定符号串accd是否文法的句子？

(0)S→E ⑴E →aA ⑵E →bB ⑶A →cA ⑷A→d ⑸B →cB ⑹B →d

解：该文法在P110，分析表在P109，

①构造LR（0）的项目在P105（略）。

②构造LR（0）识别活前缀的DFA在P106（略）

③构造LR（0）分析表在P109（略）。

④利用LR

第六章属性文法和语法制导翻译

思考题

P164 1

第七章语义分析和中间代码产生

一、P218

5、把下列赋值语句翻译为三地址代码序列,语义规则在P181：

A[i，j]:=B[i，j]+C[A[K，i]+D[i+j]]

解：

求A[i，j]

L→id (i)

{L.place:=id.place; L.offset:=null}

E→L

{if L.offset=null then E.place:=L.place

else begin

E.place:=newtemp;

emit(E.place := L.place[L.offset])

end}

Elist→id[E (i)

{Elist.place:=E.place; Elist.ndim:=1; Elist.array:=id.place} L→id (j)

{L.place:=id.place; L.offset:=null}

E→L

{if L.offset=null then E.place:=L.place

else begin

E.place:=newtemp;

emit(E.place:=L.place[L.offset])

end}

Elist→Elist,E (j)

{t:=newtemp; m:=Elist.ndim+1;

emit(t := Elist.place * limit(Elist1.array,m)

emit(t := t + E.place)

Elist.array:=Elist1.array; Elist.place:=t; Elist.ndim:=m;} L→Elist ]

{ L.place:=newtemp;

emit(L.place ‘:=’ Elist.arry ‘- ‘c )

L.offset:=newtemp;

emit(L.offset ‘:=’ w ‘*’Elist.place)}

求B[i,j]的处理同A[i,j](省略中间过成)

Elist→id[E (i)

{Elist.place:=E.place; Elist.ndim:=1; Elist.array:=id.place} Elist→Elist,E (j)

{t:=newtemp; m:=Elist.ndim+1;

emit(t := Elist.place * limit(Elist1.array,m)

emit(t := t + E.place)

Elist.array:=Elist1.array; Elist.place:=t; Elist.ndim:=m;} L→Elist ]

{ L.place:=newtemp;

emit(L.place ‘:=’ Elist.arry ‘- ‘c )

L.offset:=newtemp;

emit(L.offset ‘:=’ w ‘*’Elist.place)}

E→L

{if L.offset=null then E.place:=L.place

else begin

E.place:=newtemp;

emit(E.place:=L.place[L.offset])

end}

求A[K，i]

Elist→id[E (k)

{Elist.place:=E.place; Elist.ndim:=1; Elist.array:=id.place} Elist→Elist,E (i)

{t:=newtemp; m:=Elist.ndim+1;

emit(t := Elist.place * limit(Elist1.array,m)

emit(t := t + E.place)

Elist.array:=Elist1.array; Elist.place:=t; Elist.ndim:=m;} L→Elist]

{ L.place:=newtemp;

emit(L.place ‘:=’ Elist.arry ‘- ‘c )

L.offset:=newtemp;

emit(L.offset ‘:=’ w ‘*’Elist.place)}

E→L

{if L.offset=null then E.place:=L.place

else begin

E.place:=newtemp;

emit(E.place:=L.place[L.offset])

end}

求D[i+j]

E→E+E

{E.place:=newtemp;

emit(E.place := E1.place + E2.place)}

Elist→id[E (i+j)

{Elist.place:=E.place; Elist.ndim:=1; Elist.array:=id.place}

L→Elist]

{ L.place:=newtemp;

emit(L.place ‘:=’ Elist.arry ‘- ‘c )

L.offset:=newtemp;

emit(L.offset ‘:=’ w ‘*’Elist.place)}

E→L

{if L.offset=null then E.place:=L.place

else begin

E.place:=newtemp;

emit(E.place:=L.place[L.offset])

end}

求C[A[K，i]+D[i+j]]

E→E+E

{E.place:=newtemp;

emit(E.place := E1.place + E2.place)}

Elist→id[E

{Elist.place:=E.place; Elist.ndim:=1; Elist.array:=id.place}

L→Elist]

{ L.place:=newtemp;

emit(L.place ‘:=’ Elist.arry ‘- ‘c )

L.offset:=newtemp;

emit(L.offset ‘:=’ w ‘*’Elist.place)}

E→L

{if L.offset=null then E.place:=L.place

else begin

E.place:=newtemp;

emit(E.place:=L.place[L.offset])

end}

求B[i,j]+C[A[K，i]+D[i+j]]

E→E+E

{E.place:=newtemp;

emit(E.place := E1.place + E2.place)}

求A[i,j]:=B[i,j]+C[A[K，i]+D[i+j]]

S→L:=E

{if L.offset=null then emit(L.place:=E.place)

else emit(L.place[L.offset]:=E.place)}

三地址代码序列:

100 (T1:= i * n2)

101 (T1:= T1 + j)

102 (T2:= A - CA)

103 (T3:= T1 * 4)

104 (T4:= i * n2)

105 (T4:= T1 + j)

106 (T5:= B - CB)

107 (T6:= T4 * 4)

108 (T7:= T5[T6]) T7存放B[i,j]的值

109 (T8:= i * n2)

110 (T8:= T1 + j)

112 (T9:= A - CA)

113 (T10:= T8 * 4)

114 (T11:= T9[T10]) T11存放A[K,i]的值

115 (T12:= i + j)

116 (T13:= D - CD)

117 (T14:= T12 * 4)

118 (T15:= T13[T14]) T15存放D[i+j]的值

119 (T16:=T11+T15) T16存放A[k,i]+ D[i+j]的值

120 (T17:= C - CC)

121 (T18:= T16 * 4)

122 (T19:= T17[T18]) T19存放C[A[K，i]+D[i+j]]的值

123 (T20:=T7+T19) T20存放B[i,j]+C[A[K，i]+D[i+j]]的值

124 (T2[T1]:=T20)

6、写出下列布尔表达式的翻译过程(第一条四元式地址为100),语义规则在P190。

A or（

B and not（

C or D）

A or M1（

B and M2 not（

C or M3 D）

解：

E→id (A)

{E.truelist:=makelist(nextqutd)(100);

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

emit(jnz, A.piace, , 0)

emit(j, , , , 0)

M1→ε

{M1.quad:=nextquad}(102)

E→id (B)

{E.truelist:=makelist(nextqutd)(102);

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

emit(jnz, B.piace, , 0)

emit(j, , , , 0)

M2→ε

{M2.quad:=nextquad}(104)

E→id (C)

{E.truelist:=makelist(nextqutd)(104);

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

emit(jnz, B.piace, , 0)

emit(j, , , , 0)

M3→ε

{M3.quad:=nextquad}(106)

E→id (D)

{E.truelist:=makelist(nextqutd)(106);

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

emit(jnz, B.piace, , 0)

emit(j, , , , 0)

E→E1 or M3 E2

{backpatch(E1.falselist,M3.quad);

E.truelist:=merge(E1.truelist,E2.truelist);

E.falselist:=E2.falselist}

E→not E

{ E.truelist:=E1.falselist; E.falselist:=E2.truelist} E→E1 and M2 E2

{backpatch(E1.turelist,M2.quad);

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

E.truelist:=E2.truelist}

E→E1 or M1 E2

{backpatch(E1.falselist,M1.quad);

E.truelist:=merge(E1.turelist,E2.truelist);

E.falstlist:=E2.falselist}

四元式序列:

100 (jnz, A, ,0 )

101 (jmp, , ,102)

102 (jnz, B, ,104)

103 (jmp, , ,0 )

104 (jnz, C, ,103)

105 (jmp, , ,106)

106 (jnz, D, ,104)

107 (jmp, , ,100)

二、写出下列语句的翻译过程(第一条四元式地址为100), 语义规则在P196。

解:

求A

M1→ε

{M1.quad:=nextquad}100

E→E1 reLop E2 (A

{E.trulist:=makelist(nextquad);

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

emit(jrelop, id1.place, id2.place, 0)；

emit(jmp , _ , _ , 0)}

M2→ε

{M1.quad:=nextquad}102

E→E1 reLop E2 (B

{E.trulist:=makelist(nextquad);

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

emit(jrelop, id1.place, id2.place, 0)；

emit(jmp , _ , _ , 0)}

M3→ε

{M3.quad:=nextquad}104

求A=1

E→E1 reLop E2 (A=1)

{E.trulist:=makelist(nextquad);

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

emit(jrelop, id1.place, id2.place, 0)；

emit(jmp , _ , _ , 0)}

M4→ε

{M4.quad:=nextquad}106

求c:=c+1

E→E+E

{E.place:=newtemp;

emit(E.place := E1.place + E2.place)}

S→id:=E

{p:=lookup(https://www.sodocs.net/doc/e417359466.html,);if p≠null then emit(p:=E.place) else error } N→ε

{N.nextlist:=makelist(nextquad); emit(jmp, , ,0)} M5→ε

{M5.quad:=nextquad}108

求A:=A+Z

E→E+E

{E.place:=newtemp;

emit(E.place := E1.place + E2.place)}

S→id:=E

{p:=lookup(https://www.sodocs.net/doc/e417359466.html,);if p≠null then emit(p:=E.place) else error }

求if A=1 then c:=c+1 else A:=A+Z

S→if E then M1 S1 N else M2 S2

{backpatch(E.truelist,M1.quad);

backpatch(E.falselist,M2.quad);

S.nextlist:=merge(S1.nextlist,N.nextlist,S2.nextlist)} 求While A

S→While M1 E do M2 S1

{backpatch (S1.nextlist,M1 .quad);

backpatch (E.truelist,M2.quad);

S.nextlist:=E.falselist;

emit(‘j,_,_,’ M1..quad)}

L→S

{L.nextlist:= S.nextlist }

L S→S

{backpatch (L.nextlist, M.quad)

四元式序列:

100 (j<, A, C,102)

101 (jmp, , ,112)

102 (j<, B, D,104)

103 (jmp, , , 112)

104 (j=, A, 1,106)

105 (jmp, , ,109)

106 (+ , C, 1, T1)

107 (:=, T1, , C)

108 (jmp, , ,100)

109 (+ , A , Z,T2)

110 (:=, T2, , A)

111 (jmp, , ,100)

112

第十章优化

思考题

一、P306

1, 2, 3（B1）(按结点顺序写出优化后的四元式序列)

二、试画出如下中间代码序列的程序流图

a、求必经结点与必经结点集；

b、求回边；

c、由回边求循环

给定的中间代码序列为：

J := 0;

L1: I := 0;

If I<8 goto L3;

L2: A := B+C;

B :=D*C;

L3: IF B=0 goto L4;

Write B;

Goto L5;

L4: I := I+1;

IF I<8 Goto L2;

L5: J := J+1;

IF J <=3 goto L1;

HALT;

第九章运行时存储空间组织

思考题

一、何谓静态分配,对程序语言有何要求? 何谓动态分配,对程序语言有何要求?编译时如何实现动态分配?

二、P269 4.