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

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

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

• 静态语义检查
• 类型检查
• 控制流检查
• 一致性检查
• 相关名字检查
• 名字的作用域分析语法分析器中间代码产生器静态检查器中间代码优化器

第2页：第七章语义分析和中间代码产生（续）

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

• 便于进行与机器无关的代码优化工作
• 易于移植
• 使编译程序的结构在逻辑上更为简单明确源语言程序目标语言程序中间语言程序CompilerFront EndCompilerBack End

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

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

图表示

DAG、抽象语法树

• 后缀式，逆波兰表示
• 三地址代码
• 四元式
• 间接三元式7.1中间语言

第4页：7.1.1后缀式

7.1.1后缀式

后缀式表示法

Lukasiewicz发明的一种表示表达式的方法，又称逆波兰表示法。

• 一个表达式E的后缀形式可以如下定义：1.如果E是一个变量或常量，则E的后缀式是E自身。2.如果E是E1op E2形式的表达式，其中op是任何二元操作符，则E的后缀式为E1
• E2
• op，其中E1
• 和E2
• 分别为E1和E2的后缀式。3.如果E是(E1)形式的表达式，则E1的后缀式就是E的后缀式。

第5页：后缀式的计算

后缀式的计算

一般的计算过程是

自左至右扫描后缀式，每碰到运算量就把它推进栈。每碰到k目运算符就把它作用于栈顶的k个项，并用运算结果代替这k个项。

第6页：后缀式的计算（续）

后缀式的计算（续）

• )op E(2)E→ (E(1))E→id语义动作E.code= E(1).code || E(2).code ||opE.code:= E(1).codeE.code:=id•E.code表示E后缀形式•op表示任意二元操作符•“||”表示后缀形式的连接。

第7页：后缀式的计算

后缀式的计算

例

输入串a+b+c的分析和翻译POST：12345E→E(1)op E(2)E.code:= E(1).code || E(2).code ||opE→ (E(1))E.code:= E(1).codeE→idE.code:=idab+c+…

第8页：7.1.2图表示法

7.1.2图表示法

• 图表示法
• DAG
• 抽象语法树

第9页：7.1.2图表示法（续）

7.1.2图表示法（续）

• 无循环有向图(Directed Acyclic Graph，简称DAG)
• 对表达式中的每个子表达式，DAG中都有一个结点
• 一个内部结点代表一个操作符，它的孩子代表操作数
• 在一个DAG中代表公共子表达式的结点具有多个父结点

第10页：7.1.2图表示法

7.1.2图表示法

• =b*(-c)+b*(-c)的图表示法assigna+*buminuscDAGassigna+*buminusc抽象语法树*buminusc

第11页：抽象语法树对应的代码

抽象语法树对应的代码

T1

=-cT2:=b*T1T3:=-cT4:=b*T3T5:=T2+T4a:=T5assigna+*buminusc抽象语法树*buminusc

第12页：DAG对应的代码

DAG对应的代码

T1

=-cT2:=b*T1T5:=T2+T2a:=T5assigna+*buminuscDAG抽象语法树对应的代码：T1:=-cT2:=b*T1T3:=-cT4:=b*T3T5:=T2+T4a:=T5

第13页：DAG对应的代码（续）

DAG对应的代码（续）

d=ES.nptr

=mknode(‘assign’,mkleaf(id,id.place),E.nptr)E→E1+E2E.nptr:=mknode(‘+’,E1.nptr,E2.nptr)E→E1*E2E.nptr:=mknode(‘*’,E1.nptr,E2.nptr)E→-E1E.nptr:=mknode(‘uminus’,E1.nptr)E→ (E1)E.nptr:=E1.nptrE→idE.nptr:=mkleaf(id,id.place)

第14页：7.1.3三地址代码

7.1.3三地址代码

三地址代码x

=y op z

第15页：7.1.3三地址代码（续）

7.1.3三地址代码（续）

• =b*(-c)+b*(-c)的图表示法assigna+*buminuscDAGassigna+*buminusc抽象语法树*buminusc

第16页：7.1.3三地址代码

7.1.3三地址代码

=-cT1

=-cT2:=b*T1T2:=b*T1T3:=-cT5:=T2+T2T4:=b*T3a:=T5T5:=T2+T4a:=T5对于抽象语法树的代码对于DAG的代码

第17页：三地址语句的种类

三地址语句的种类

x

=yopz

x

=opy

x

=y[i]及x[i]:=y的索引赋值

x

=&y,x:=*y和*x:=y的地址和指针赋值

• x:=y
• gotoL
• ifxrelopygotoL或ifagotoL
• paramx和callp,n，以及返回语句returny

第18页：三地址语句的种类（续）

三地址语句的种类（续）

• 对表达式E求值并置于变量T中值
• id.place:=T

第19页：三地址语句的种类

三地址语句的种类

• 非终结符号S有综合属性S.code，它代表赋值语句S的三地址代码。
• 非终结符号E有如下两个属性：
• E.place表示存放E值的名字。
• E.code表示对E求值的三地址语句序列。
• 函数newtemp的功能是，每次调用它时，将返回一个不同临时变量名字,如T1,T2,…。

第20页：三地址语句的种类（续）

三地址语句的种类（续）

规则S→id=ES.code

=E.code || gen(id.place ‘:=’ E.place)E→E1+E2E.place:=newtemp;E.code:=E1.code || E2.code ||gen(E.place ‘:=’ E1.place ‘+’ E2.place)E→E1*E2E.place:=newtemp;E.code:=E1.code || E2.code ||gen(E.place ‘:=’ E1.place ‘*’ E2.place)E→-E1E.place:=newtemp;E.code:=E1.code ||gen(E.place ‘:=’ ‘uminus’ E1.place)E→ (E1)E.place:=E1.place;E.code:=E1.codeE→idE.place:=id.place;E.code=‘ ’

第21页：三地址语句

三地址语句

• 四元式
• 一个带有四个域的记录结构，这四个域分别称为op, arg1, arg2及resultoparg1arg2result(0)uminuscT1(1)*bT1T2(2)uminuscT3(3)*bT3T4(4)+T2T4T5(5):=T5a

第22页：三地址语句（续）

三地址语句（续）

三个域

op、arg1和arg2oparg1arg2(0)uminusc(1)*b(0)(2)uminusc(3)*b(2)(4)+(1)(3)(5)assigna(4)

• 三元式
• 通过计算临时变量值的语句的位置来引用这个临时变量

第23页：三地址语句

三地址语句

x[i]

=yoparg1arg2(0)[ ] =xi(1)y

x

=y[i]oparg1arg2(0)= [ ]yi(1)assignx(0)

第24页：三地址语句（续）

三地址语句（续）

间接码表

一张指示器表，按运算的先后次序列出有关三元式在三元式表中的位置。

优点

方便优化，节省空间

• 间接三元式
• 为了便于优化，用三元式表+间接码表表示中间代码

第25页：三地址语句

三地址语句

例如，语句X:=(A+B)*C;Y:=D↑(A+B)的间接三元式表示如下表所示。

第26页：7.2说明语句

7.2说明语句

• 说明语句

第27页：7.3.1简单算术表达式及赋值语句

7.3.1简单算术表达式及赋值语句

7.3赋值语句的翻译 7.3.1简单算术表达式及赋值语句

第28页：7.3.1简单算术表达式及赋值语句（续）

7.3.1简单算术表达式及赋值语句（续）

规则S→id=ES.code

=E.code || gen(id.place ‘:=’ E.place)E→E1+E2E.place:=newtemp;E.code:=E1.code || E2.code ||gen(E.place ‘:=’ E1.place ‘+’ E2.place)E→E1*E2E.place:=newtemp;E.code:=E1.code || E2.code ||gen(E.place ‘:=’ E1.place ‘*’ E2.place)E→-E1E.place:=newtemp;E.code:=E1.code ||gen(E.place ‘:=’ ‘uminus’ E1.place)E→ (E1)E.place:=E1.place;E.code:=E1.codeE→idE.place:=id.place;E.code=‘ ’

第29页：7.3.1简单算术表达式及赋值语句

7.3.1简单算术表达式及赋值语句

=E{p

=lookup(id.name);ifp

nilthenemit(p‘

=’E.place)elseerror}E→E1+E2{E.place:=newtemp;emit(E.place‘:=’E1.place‘+’E2.place)}E→E1*E2{E.place:=newtemp;emit(E.place‘:=’E1.place‘*’E2.place)}S→id:=E S.code:=E.code || gen(id.place ‘:=’ E.place)E→E1+E2E.place:=newtemp;E.code:=E1.code || E2.code ||gen(E.place ‘:=’ E1.place ‘+’ E2.place)E→E1*E2E.place:=newtemp;E.code:=E1.code || E2.code || gen(E.place ‘:=’ E1.place ‘*’ E2.place)

第30页：产生赋值语句三地址代码

产生赋值语句三地址代码

nilthenE.place

=pelseerror}E→-E1E.place:=newtemp;E.code:=E1.code || gen(E.place ‘:=’ ‘uminus’ E1.place)E→ (E1) E.place:=E1.place;E.code:=E1.codeE→id E.place:=id.place;E.code=‘ ’

第31页：7.3.2数组元素的引用

7.3.2数组元素的引用

• 用
• 数组元素地址的计算：

第32页：7.3.2数组元素的引用（续）

7.3.2数组元素的引用（续）

• n2+i2)n3+i3)…)nk+ik)×w +base-((…((low1n2+low2)n3+low3)…)nk+lowk)×w
• C= base-((…((low1n2+low2)n3+low3)…)nk+lowk)×w

第33页：7.3.2数组元素的引用

7.3.2数组元素的引用

id出现的地方也允许下面产生式中的L出现L → id [ Elist ] | idElist→Elist,E | E为了便于处理，文法改写为L→Elist ]| idElist→Elist, E |id [ E

第34页：7.3.2数组元素的引用（续）

7.3.2数组元素的引用（续）

Elist.ndim

下标个数计数器

Elist.place

表示临时变量，用来临时存放已形成的Elist中的下标表达式计算出来的值

第35页：7.3.2数组元素的引用

7.3.2数组元素的引用

• L.place：
• 若L为下标变量，指存放CONSPART的临时变量的整数码
• L.offset：
• 若L为简单变量，null，
• 若L为下标变量，指存放VARPART的临时变量的整数码

第36页：7.3.2数组元素的引用（续）

7.3.2数组元素的引用（续）

• =E(2) E→E+E(3) E→(E)(4) E→L(5) L→Elist ](6) L→id(7) Elist→ Elist, E(8) Elist→id [ E

第37页：7.3.2数组元素的引用

7.3.2数组元素的引用

=E{ if L.offset=null then emit(L.place ‘:=’ E.place)else emit(L.place ‘ [’ L.offset ‘]’‘:=’ E.place)}(2) E→E1+E2{ E.place:=newtemp;emit(E.place ‘:=’ E1.place ‘+’ E2.place)}

第38页：7.3.2数组元素的引用（续）

7.3.2数组元素的引用（续）

=E1.place}(4) E→L{ if L.offset=null thenE.place:=L.placeelse beginE.place:=newtemp;emit(E.place ‘:=’L.place ‘[’ L.offset ‘]’)end}

第39页：7.3.2数组元素的引用

7.3.2数组元素的引用

+i3)…)nk+ik)×w +base-((…((low1n2+low2)n3+low3)…)nk+lowk)×w(8)Elist→id [ E{ Elist.place=E.place;Elist.ndim:=1;Elist.array:=id.place }

第40页：7.3.2数组元素的引用（续）

7.3.2数组元素的引用（续）

3+i3)…)nk+ik)×w +base-((…((low1n2+low2)n3+low3)…)nk+lowk)×w(7)Elist→ Elist1, E{t=newtemp;m:=Elist1.ndim+1;emit(t ‘:=’Elist1.place‘*’limit(Elist1.array,m));emit(t ‘:=’ t ‘+’E.place);Elist.array:= Elist1.array;Elist.place:=t;Elist.ndim:=m}

第41页：7.3.2数组元素的引用

7.3.2数组元素的引用

+i3)…)nk+ik)×w+base-((…((low1n2+low2)n3+low3)…)nk+lowk)×w(5)L→Elist ]{ L.place=newtemp;emit(L.place ‘:=’Elist.array‘－’C);L.offset:=newtemp;emit(L.offset ‘:=’w ‘*’Elist.place) }(6)L→id{ L.place:=id.place; L.offset:=null }

第42页：7.3.2数组元素的引用（续）

7.3.2数组元素的引用（续）

• 用E.type表示非终结符E的类型属性
• 对应产生式E
• E1op E2的语义动作中关于E.type的语义规则可定义为：{if E1.type=integer andE2.type=integerE.type:=integerelse E.type:=real }
• 算符区分为整型算符intop和实型算符realop，

第43页：7.3.2数组元素的引用

7.3.2数组元素的引用

x:=y＋i*j其中x、y为实型；i、j为整型。这个赋值句产生的三地址代码为：T1:=iint*jT3:=inttorealT1T2:=yreal+T3x:=T2

第44页：7.3.2数组元素的引用（续）

7.3.2数组元素的引用（续）

• =newtemp;if E1.type=integer and E2.type=integer thenbeginemit (E.place ‘:=’ E1.place ‘int+’ E2.place);E.type:=integerendelse if E1.type=real and E2.type=real thenbeginemit (E.place ‘:=’ E1.place ‘real+’ E2.place);E.type:=realend

第45页：7.3.2数组元素的引用

7.3.2数组元素的引用

d E2.type=real then beginu=newtemp;emit (u ‘:=’ ‘inttoreal’ E1.place);emit (E.place ‘:=’ u ‘real+’ E2.palce);E.type:=realendelse if E1.type=real and E1.type=integer then beginu:=newtemp;emit (u ‘:=’ ‘inttoreal’ E2.place);emit (E.place ‘:=’ E1.place ‘real+’ u);E.type:=realendelse E.type:=type_error}

第46页：7.3.3记录中域的引用

7.3.3记录中域的引用

• 用
• 符号表表项之中保存记录中的域的类型和相对地址信息

第47页：7.4布尔表达式的翻译

7.4布尔表达式的翻译

产生布尔表达式的文法

E→EorE | EandE |

• 布尔表达式的两个基本作用:
• 用于逻辑演算,计算逻辑值;
• 用于控制语句的条件式.
• E | (E) | i rop i | i

第48页：A解释成if A then

A解释成if A then

计算布尔表达式通常采用两种方法:1.如同计算算术表达式一样,一步步算1or(not0and0)or0=1or(1and0)or0=1or0or0=1or0=12.采用某种优化措施把AorB解释成if A then true else B把AandB解释成if A then B else false把 A解释成if A then false else true

第49页：两种不同的翻译方法

两种不同的翻译方法

第一种翻译法

AorBandC=D翻译成(1)(=,C,D,T1)(2)(and,B,T1,T2)(3)(or,A,T2,T3)

第50页：7.4.1数值表示法

7.4.1数值表示法

• a or b and not c翻译成T1:=not cT2:=b and T1T3:=aorT1
• a<b的关系表达式可等价地写成if a<b then 1 else 0，翻译成100:if a<b goto 103101:T:=0102:goto 104103:T:=1104:

第51页：7.4.1数值表示法（续）

7.4.1数值表示法（续）

• 过程emit将三地址代码送到输出文件中
• nextstat给出输出序列中下一条三地址语句的地址索引
• 每产生一条三地址语句后，过程emit便把nextstat加1

第52页：关于布尔表达式的数值表示法

关于布尔表达式的数值表示法

2{E.place=newtemp;emit(E.place ‘:=’ E1.place ‘or’ E2.place)}E→E1and E2{E.place:=newtemp;emit(E.place ‘:=’ E1.place ‘and’ E2.place)}E→not E1{E.place:=newtemp;emit(E.place ‘:=’ ‘not’ E1.place)}E→(E1){E.place:=E1.place}

第53页：关于布尔表达式的数值表示法（续）

关于布尔表达式的数值表示法（续）

id1relop id2{ E.place:=newtemp;emit(‘if’ id1.place relop. op id2. place‘goto’ nextstat+3);emit(E.place ‘:=’ ‘0’);emit(‘goto’ nextstat+2);emit(E.place‘:=’ ‘1’)}E→id{ E.place:=id.place }a<b翻译成100:if a<b goto 103101:T:=0102:goto 104103:T:=1104:

第54页：布尔表达式a<

布尔表达式a&lt

• borc<dande<f的翻译结果100:if a<b goto 103101:T1:=0102:goto 104103:T1:=1104:if c<d goto 107105:T2:=0106:goto 108107:T2:=1108: if e<f goto 111109: T3:=0110: goto 112111: T3:=1112: T4:=T2and T3113: T5:=T1or T4E
• id1relop id2{ E.place:=newtemp;emit(‘if’ id1.place relop. op id2. place‘goto’ nextstat+3);emit(E.place ‘:=’ ‘0’);emit(‘goto’ nextstat+2);emit(E.place‘:=’ ‘1’) }E→id{ E.place:=id.place }E→E1or E2{ E.place:=newtemp;emit(E.place ‘:=’ E1.place ‘or’ E2.place)}E→E1and E2{ E.place:=newtemp;emit(E.place ‘:=’ E1.place ‘and’ E2.place) }

第55页：7.4.2作为条件控制的布尔式翻译

7.4.2作为条件控制的布尔式翻译

• 为条件控制的布尔式翻译
• 条件语句ifEthenS1elseS2赋予E两种出口:一真一假E.codeS1.codeS2.codeTo E.trueTo E.falsegoto S.nextS.next……E.true:E.false:

第56页：7.4.2作为条件控制的布尔式翻译（续）

7.4.2作为条件控制的布尔式翻译（续）

例：把语句:ifa>corb<dthenS1elseS2翻译成如下的一串三地址代码if a>c goto L2 “真”出口goto L1L1:if b<d goto L2 “真”出口goto L3 “假”出口L2:(关于S1的三地址代码序列)goto LnextL3:(关于S2的三地址代码序列)Lnext:

第57页：对于一个布尔表达式E

对于一个布尔表达式E

• 引用两个标号
• E.true是E为‘真’时控制流转向的标号
• E.false是E为‘假’时控制流转向的标号

第58页：对于一个布尔表达式E（续）

对于一个布尔表达式E（续）

• E1or E2E1.true=E.true;E1.false:=newlabel;E2.true:=E.true;E2.false:=E.false;E.code:=E1.code ||gen(E1.false ‘:’) || E2.codeE1.codeTo E.trueTo E1.falseE2.codeTo E.trueTo E.false

第59页：对于一个布尔表达式E

对于一个布尔表达式E

• E1and E2E1.true=newlabel;E1.false:=E.false;E2.true:=E.true;E2.false:=E.fasle;E.code:=E1.code ||gen(E1.true ‘:’) || E2.codeE1.codeTo E.falseTo E1.trueE2.codeTo E.trueTo E.false

第60页：对于一个布尔表达式E（续）

对于一个布尔表达式E（续）

• not E1E1.true=E.false;E1.false:=E.true;E.code:=E1.codeE→ (E1)E1.true:=E.true;E1.false:=E.false;E.code:=E1.code

第61页：对于一个布尔表达式E

对于一个布尔表达式E

• id1relop id2E.code=gen(‘if ’ id1.placerelop.op id2.place ‘goto’ E.true) ||gen(‘goto’ E.false)E→trueE.code:=gen(‘goto’ E.true)E→falseE.code:=gen(‘goto’ E.false)

第62页：考虑如下表达式

考虑如下表达式

• a<b or c<d and e<f假定整个表达式的真假出口已分别置为Ltrue和Lfalse，则按定义将生成如下的代码：if a<b goto Ltruegoto L1L1:if c<d goto L2goto LfalseL2:if e<f goto Ltruegoto Lfalse

第63页：布尔表达式的翻译

布尔表达式的翻译

• 两遍扫描
• 为给定的输入串构造一棵语法树；
• 对语法树进行深度优先遍历，进行语义规则中规定的翻译。
• 一遍扫描

第64页：一遍扫描实现布尔表达式的翻译

一遍扫描实现布尔表达式的翻译

• 采用四元式形式
• 把四元式存入一个数组中，数组下标就代表四元式的标号
• 约定四元式(jnz, a,-, p)表示if a goto p四元式(jrop, x, y, p)表示if x rop y goto p四元式(j,-,-, p)表示goto p

第65页：一遍扫描实现布尔表达式的翻译（续）

一遍扫描实现布尔表达式的翻译（续）

有时,四元式转移地址无法立即知道,我们只好把这个未完成的四元式地址作为E的语义值保存,待机"回填"。

第66页：一遍扫描实现布尔表达式的翻译

一遍扫描实现布尔表达式的翻译

• 假定E的四元式中需要回填"真"出口的p，q，r三个四元式，则E.truelist为下列链:(p)(x，x，x，0)…(q)(x，x，x，p)…(r)(x，x，x，q)链尾E.truelist=r

第67页：变量nextquad

变量nextquad

• 变量nextquad，它指向下一条将要产生但尚未形成的四元式的地址(标号)。nextquad的初值为1，每当执行一次emit之后，nextquad将自动增1。
• 函数makelist(i)，它将创建一个仅含i的新链表，其中i是四元式数组的一个下标(标号)；函数返回指向这个链的指针。
• 函数merge(p1,p2)，把以p1和p2为链首的两条链合并为一，作为函数值，回送合并后的链首。
• 过程backpatch(p, t)，其功能是完成“回填”，把p所链接的每个四元式的第四区段都填为t。

第68页：变量nextquad（续）

变量nextquad（续）

• E1and M E2(3)| not E1(4)| (E1)(5)| id1relop id2(6)| id(7)M→

第69页：变量nextquad

变量nextquad

{ M.quad

=nextquad }

第70页：变量nextquad（续）

变量nextquad（续）

backpatch(E1.falselist, M.quad)E.truelist:=merge(E1.truelist, E2.truelist);E.falselist:=E2.falselist }(2) E→E1and M E2{ backpatch(E1.truelist, M.quad);E.truelist:=E2.truelist;E.falselist:=merge(E1.falselist,E2.falselist) }E1.codeTo E.trueTo E1.falseE2.codeTo E.trueTo E.falseE1.codeTo E.falseTo E1.trueE2.codeTo E.trueTo E.false

第71页：变量nextquad

变量nextquad

truelist=E1.falselist;E.falselist:=E1.truelist}(4) E→(E1){ E.truelist:=E1.truelist;E.falselist:=E1. falselist}

第72页：变量nextquad（续）

变量nextquad（续）

d2{ E.truelist=makelist(nextquad);E.falselist:=makelist(nextquad+1);emit(‘j’ relop.op ‘,’ id1.place ‘,’ id2.place‘,’‘0’);emit(‘j,－,－, 0’) }(6) E→id{ E.truelist:=makelist(nextquad);E.falselist:=makelist(nextquad+1);emit(‘jnz’ ‘,’ id.place ‘,’ ‘－’ ‘,’‘0’)；emit(‘ j,-,-, 0’) }

第73页：布尔表达式的翻译模式

布尔表达式的翻译模式

• 作为整个布尔表达式的"真""假"出口(转移目标)仍待回填.

第74页：布尔表达式的翻译模式（续）

布尔表达式的翻译模式（续）

• b or c<d and e<f100(j<, a, b, 0)101(j,-,-, 102)102(j<, c, d, 104)103(j,-,-, 0)104(j<, e, f,100)truelist105(j,-,-,103)falselist

第75页：A解释成if A then

A解释成if A then

• rue回顾布尔表达式的翻译

第76页：A解释成if A then（续）

A解释成if A then（续）

id1relop id2{ E.place:=newtemp;emit(‘if’ id1.place relop. op id2. place ‘goto’ nextstat+3);emit(E.place ‘:=’ ‘0’);emit(‘goto’ nextstat+2);emit(E.place‘:=’ ‘1’) }E→id{ E.place:=id.place }E→E1or E2{ E.place:=newtemp;emit(E.place ‘:=’ E1.place ‘or’ E2.place)}E→E1and E2{ E.place:=newtemp;emit(E.place ‘:=’ E1.place ‘and’ E2.place) }

第77页：布尔表达式的翻译

布尔表达式的翻译

• 作为条件控制的布尔式翻译
• 一遍扫描实现布尔表达式的翻译

第78页：7.4.2作为条件控制的布尔式翻译

7.4.2作为条件控制的布尔式翻译

• 为条件控制的布尔式翻译
• 条件语句ifEthenS1elseS2赋予E两种出口:一真一假E.codeS1.codeS2.codeTo E.trueTo E.falsegoto S.nextS.next……E.true:E.false:

第79页：7.4.2作为条件控制的布尔式翻译（续）

7.4.2作为条件控制的布尔式翻译（续）

• E1or E2E1.true=E.true;E1.false:=newlabel;E2.true:=E.true;E2.false:=E.false;E.code:=E1.code ||gen(E1.false ‘:’) || E2.codeE1.codeTo E.trueTo E1.falseE2.codeTo E.trueTo E.false

第80页：7.4.2作为条件控制的布尔式翻译

7.4.2作为条件控制的布尔式翻译

• E1and E2E1.true=newlabel;E1.false:=E.false;E2.true:=E.true;E2.false:=E.fasle;E.code:=E1.code ||gen(E1.true ‘:’) || E2.codeE1.codeTo E.falseTo E1.trueE2.codeTo E.trueTo E.false

第81页：7.4.2作为条件控制的布尔式翻译（续）

7.4.2作为条件控制的布尔式翻译（续）

• not E1E1.true=E.false;E1.false:=E.true;E.code:=E1.codeE→ (E1)E1.true:=E.true;E1.false:=E.false;E.code:=E1.code

第82页：7.4.2作为条件控制的布尔式翻译

7.4.2作为条件控制的布尔式翻译

• id1relop id2E.code=gen(‘if ’ id1.placerelop.op id2.place ‘goto’ E.true) ||gen(‘goto’ E.false)E→trueE.code:=gen(‘goto’ E.true)E→falseE.code:=gen(‘goto’ E.false)

第83页：布尔表达式的翻译

布尔表达式的翻译

• 作为条件控制的布尔式翻译
• 一遍扫描实现布尔表达式的翻译

第84页：布尔表达式的翻译（续）

布尔表达式的翻译（续）

• E1and M E2(3)| not E1(4)| (E1)(5)| id1relop id2(6)| id(7)M→

第85页：布尔表达式的翻译

布尔表达式的翻译

backpatch(E1.falselist, M.quad)E.truelist:=merge(E1.truelist, E2.truelist);E.falselist:=E2.falselist }(2) E→E1and M E2{ backpatch(E1.truelist, M.quad);E.truelist:=E2.truelist;E.falselist:=merge(E1.falselist,E2.falselist) }(3) E→not E1{ E.truelist:=E1.falselist;E.falselist:=E1.truelist}(4) E→(E1){ E.truelist:=E1.truelist;E.falselist:=E1. falselist}

第86页：布尔表达式的翻译（续）

布尔表达式的翻译（续）

{ M.quad

=nextquad }

第87页：布尔表达式的翻译模式

布尔表达式的翻译模式

• 作为整个布尔表达式的"真""假"出口(转移目标)仍待回填.

第88页：7.5控制语句的翻译

7.5控制语句的翻译

• 考虑下列产生式所定义的语句S → if E then S1| if E then S1else S2| while E do S1其中E为布尔表达式。

第89页：7.5控制语句的翻译（续）

7.5控制语句的翻译（续）

if-then语句S → if E then S1E.codeS1.codeTo E.trueTo E.false……E.true:E.false:

第90页：if-then语句语义规则表

if-then语句语义规则表

• E then S1E.true=newlabel;E.flase:=S.next;S1.next:=S.nextS.code:=E.code||gen(E.true ‘:’)||S1.codeE.codeS1.codeTo E.trueTo E.false……E.true:E.false:

第91页：if-then语句语义规则表（续）

if-then语句语义规则表（续）

if-then-else语句S →if E then S1else S2E.codeS1.codeS2.codeTo E.trueTo E.falsegoto S.nextS.next……E.true:E.false:

第92页：if-then语句语义规则表

if-then语句语义规则表

• S→if E then S1else S2E.true=newlabel;E.false:=newlabel;S1.next:=S.nextS2.next:=S.next;S.code:=E.code||gen(E.true ‘:’)||S1.code||gen(‘goto’ S.next) ||gen(E.false ‘:’)||S2.codeE.codeS1.codeS2.codeTo E.trueTo E.falsegoto S.nextS.next……E.true:E.false:

第93页：if-then语句语义规则表（续）

if-then语句语义规则表（续）

while-do语句S → while E do S1E.codeS1.codeTo E.trueTo E.falsegoto S.beginS.begin:……E.true:E.false:

第94页：if-then语句语义规则表

if-then语句语义规则表

• ile E do S1S.begin=newlabel;E.true:=newlabel;E.false:=S.next;S1.next:=S.begin;S.code:=gen(S.begin ‘:’) ||E.code||gen(E.true ‘:’)||S1.code||gen(‘goto’ S.begin)E.codeS1.codeTo E.trueTo E.falsegoto S.beginS.begin:……E.true:E.false:

第95页：考虑如下语句

考虑如下语句

生成下列代码

L1:ifa<bgotoL2gotoLnextL2:ifc<dgotoL3gotoL4L3:T1:=y+zx:=T1gotoL1L4:T2:=y-zx:=T2gotoL1Lnext:

第96页：一遍扫描翻译控制流语句

一遍扫描翻译控制流语句

考虑下列产生式所定义的语句

(1)S→if E then S(2)| if E then S else S(3)| while E do S(4)| begin L end(5)| A(6) L→L;S(7)| S

第97页：if语句的翻译相关产生式S

if语句的翻译相关产生式S

• N→

第98页：翻译模式

翻译模式

{M.quad

=nextquad}4.N→

{N.nextlist

=makelist(nextquad);emit(‘j,－,－,－’)}

第99页：翻译模式（续）

翻译模式（续）

• E的代码S(1)的代码“真”出口“假”出口为了便于"回填"，改写产生式为:S→while M1E do M2S1M→

第100页：翻译模式

翻译模式

{M.quad

=nextquad}

第101页：翻译模式（续）

翻译模式（续）

产生式L→L;S改写为：L→L1; M SM→

第102页：翻译模式

翻译模式

{M.quad

=nextquad}

第103页：翻译模式（续）

翻译模式（续）

其它几个语句的翻译1.S→beginLend{S.nextlist:=L.nextlist}2.S→A{S.nextlist:=makelist()}3.L→S{L.nextlist:=S.nextlist}

第104页：翻译模式

翻译模式

nilthenemit(p‘

=’E.place)elseerror}E→E1+E2{E.place:=newtemp;emit(E.place‘:=’E1.place‘+’E2.place)}P195S→ifEthenMS1{backpatch(E.truelist,M.quad);S.nextlist:=merge(E.falselist,S1.nextlist)}M→

{M.quad

=nextquad}S→A{S.nextlist:=makelist()}P195S→whileM1EdoM2S1{backpatch(S1.nextlist,M1.quad);backpatch(E.truelist,M2.quad);S.nextlist:=E.falselistemit(‘j,－,－,’M1.quad)}M→

{M.quad

=nextquad}

第105页：翻译模式（续）

翻译模式（续）

• b) doif (c<d) then x:=y+z;100(j<, a, b, 102)101(j,-,-, 107)102(j<, c, d, 104)103(j,-,-, 100)104(+, y, z, T)105(:=, T,-, x)106(j,-,-,100)107

第106页：7.5.2标号与goto语句

7.5.2标号与goto语句

向后转移

L1:…………gotoL1;

向前转移

gotoL1;……L1:……

• 标号定义形式L: S；
• 标号引用goto L；
• 示例：

第107页：7.5.2标号与goto语句（续）

7.5.2标号与goto语句（续）

• ) (j,-,-, 0)…(q) (j,-,-, p)…(r) (j,-,-, q)已未

第108页：产生式S

产生式S

→gotoL的语义动作:{查找符号表；IFL在符号表中且"定义否"栏为"已"THENGEN(J，-，-，P)ELSEIFL不在符号表中THENBEGIN把L填入表中；置"定义否"为"未"，"地址"栏为NXQ；GEN(J，-，-，0)ENDELSEBEGINQ:=L的地址栏中的编号；置地址栏编号为NXQ；GEN(J，-，-，Q)END}

第109页：产生式S（续）

产生式S（续）

对应的语义动作

1.若i所指的标识符(假定为L)不在符号表中，则把它填入，置"类型"为"标号"，定义否为"已"，"地址"为nextquad；2.若L已在符号表中但"类型"不为标号或"定义否"为"已"，则报告出错；3.若L已在符号表中，则把标号"未"改为"已"，然后，把地址栏中的链头(记为q)取出，同时把nextquad填在其中，最后，执行BACKPATCH(q，nextquad )。

第110页：7.5.3CASE语句的翻译

7.5.3CASE语句的翻译

• 语句结构case E ofC1:S1;C2:S2;…Cn-1:Sn-1;otherwise:Snend

第111页：7.5.3CASE语句的翻译（续）

7.5.3CASE语句的翻译（续）

• C1goto L2S1的代码goto nextL2:if T
• C2goto L3S2的代码goto nextL3:…Ln-1:if T
• Cn-1goto LnSn-1的代码goto nextLn:Sn的代码next:
• 改进:

第112页：7.5.3CASE语句的翻译

7.5.3CASE语句的翻译

翻译法(二):计算E并放入T中goto testL1:关于S1的中间码goto next…Ln-1:关于Sn-1的中间码goto nextLn:关于Sn的中间码goto nexttest:if T=C1goto L1if T=C2goto L2…if T=Cn-1goto Ln-1goto Lnnext:(case, C1,P1)(case, C2,P2)…(case, Cn-1, Pn-1)(case, T, Pn)(label, NEXT,-,-)Pi是Li在符号表中的位置

第113页：7.6过程调用的处理

7.6过程调用的处理

传地址

把实在参数的地址传递给相应的形式参数

• 用的处理
• 过程调用主要对应两种事:
• 传递参数
• 转子
• 调用段预先把实在参数的地址传递到被调用段可以拿到的地方；
• 程序控制转入被调用段之后，被调用段首先把实在参数的地址抄进自己相应的形式单元中；
• 过程体对形式参数的引用域赋值被处理成对形式单元的间接访问。

第114页：7.6过程调用的处理（续）

7.6过程调用的处理（续）

翻译方法：把实参的地址逐一放在转子指令的前面.例如，CALLS(A，X+Y)翻译为:计算X+Y置于T中的代码parAparTcallS

第115页：过程调用的翻译

过程调用的翻译

过程调用文法

(1)S→callid(Elist)(2)Elist→Elist,E(3)Elist→E

• 参数的地址存放在一个队列中
• 最后对队列队列中的每一项生成一条par语句

第116页：过程调用的翻译（续）

过程调用的翻译（续）

翻译模式3.Elist→E{初始化queue仅包含E.place}2.Elist→Elist,E{将E.place加入到queue的队尾}1.S→callid(Elist){for队列queue中的每一项pdoemit(‘param’p);emit(‘call’id.place)}

第117页：过程调用的翻译

过程调用的翻译

• P217-1，3，4，5，6，7，12