《中间代码生成》PPT课件

中间代码生成,第八章 中间代码生成,中间代码 说明语句的翻译 赋值语句的翻译 控制语句的翻译（if、循环） 属性文法的实现 过程调用的翻译,8.1 中间代码,作用 过渡：经过语义分析被译成中间代码序列 形式 中间语言的语句 优点 便于编译系统的实现、移植、代码优化,常用的中间代码(语言),三地址代码（四元式） 语法(结构)树（三元式）（5.2节） 后缀式逆波兰表示（2.3节） 特点 形式简单、语义明确、便于翻译 独立于目标语言,例 8-1 表达式 (A - 12) * B + 6 的中间代码,+,*,6,-,A,12,B,三地址码 T1=A-12 T2=T1*B T3=T2+6,四元组 (-, A, 12, T1) (* , T1, B, T2) (+, T2, 6, T3),三元组 (-, A, 12) (*, , B) (+, , 6),波兰表示 +*-A12B6 逆波兰表示 A12-B*6+,如何生成语言结构的三地址码,类似于 构建语法树 生成后缀表示,以S:=(A-12)*B+6为例将赋值语句变换为语法结构树,属性设置 E.p 是语法结构树指针 id.entry 是名字的符号表入口 num.val 是数值 基本函数结点构造 mknode 建中间结点 mkleaf 建叶结点,6,A,12,-,+,B,*,S,:=,生成赋值语句语法树的语法制导定义,例 8-2：a:=b*(-c)+b*(-34)的语法结构树直观描述,:=,*,-,0,+,*,-,0,id,b,num,34,id,b,id,c,id,a,root,语法结构树数组存储形式,地址 算符 操作数 操作数 0 1 2 3 4 5 6 7 8 9 10,a:=b*(-c)+b*(-34),以语法分析为中心,后缀式（逆波兰表示）,操作数 1，操作数 2，运算符 操作数，运算符 例 8-7： a := b *（- c）+ b *（- 34）的后缀式 a b c - * b 34 - * + :=,生成后缀式的属性文法,三地址代码,一般形式 x := y op z 其中 x, y, z 为变量名、常数或编译产生的临时变量 四元式（op, y, z, x）,种类：x := y op z 双目运算 x := op y 单目运算 x := y 赋值语句 if x relop y goto l 条件转移语句 (relop,x,y,l),其它语句的三地址代码,goto l 无条件转移 param x 实在参数 call p, n 过程调用 return x 过程返回 x := yi数组运算 xi := y x := integer i, j; end,文法描述,P D D D ; D D id : T T integer T real T arraynum of T1 T T1,例如： a:integer; b:real;c:array10of real,属性、过程、与全局量,文法变量T（类型）的属性 type 类型 width 占用的字节数 基本子程序 enter：设置变量的类型和地址 array：数组类型处理 全局量 offset：已分配空间字节数,说明语句的翻译模式,P offset := 0 D DD ; D Did : T enter( id.name, T.type, offset ); offset := offset + T.width Tinteger T.type := integer; T.width := 4 Treal T.type := real; T.width := 8 Tarray num of T1 T.type := array( num.val, T1.type); T.width := num.val * T1.width TT1 T.type := pointer( T1.type); T.width := 4,PMD M offset := 0 ,例 8-4 x:real; i:integer 的翻译,enter(x,real,0),offset=0,offset=8,T.type=real T.width=8,offset=12,T.type=integer T.width=4,enter(i,integer,8),Did : T enter( id.name, T.type, offset ); offset := offset + T.width,例 8-4 x:real; i:integer 的翻译,Poffset:=0D offset:=0D;D offset:=0 x:Tenter(x,T.type,offset);offset:=offset+T.width;D offset:=0 x:realT.type:=real;T.width:=8 enter(x,T.type,offset);offset:=offset+T.width;D x:real(x,real,0);offset:=8;D x:real(x,real,0);offset:=8;i:Tenter(id.name,T.type,offset); offset:=offset+T.width x:real(x,real,0);offset:=8;i:integerT.type:=integer;T.width:=4enter(i,T.type,offset);offset:=offset+T.width x:real(x,real,0);i:integer(i,integer,8);offset:=12,作用域信息的保存,所讨论语言的文法 P D S D D ; D | id : T | proc id ; D ; S 语义动作用到的函数 mktable(previous)：创建一个新的符号表； enter(table, name, type, offset) addwidth(table, width)：符号表的大小； enterproc(table, name, newtable) 在table指向的符号表中为name建立一个新表项；,P M D S addwidth (top(tblptr), top(offset); pop(tblptr); pop(offset) M t := mktable(nil); push(t,tblptr); push(0,offset) D D1 ; D2 D proc id ;N D1; S t := top(tblptr); addwidth(t,top(offset);pop(tblptr);pop(offset); enterproc(top(tblptr),id.name,t) Did:T enter(top(tblptr),id.name,T.type,top(offset); top(offset)：=top（offset）+ T.width N t := mktable(top(tblptr) ); push(t,tblptr); push(0,offset) ,处理嵌套过程中的说明语句,program sort(input,output); var a:array0.10 of integer; x:integer; procedure readarray; var i:integer; begin aend； procedure exchange(i,j:integer); begin x:=ai;ai:=aj;aj:=x;end； procedure quicksort(m,n:integer); var k,v:integer; function partition(y,z:integer):integer; var i,j:integer; begin a v exchange(i,j)end; begin end； begin end；,例：一个带有嵌套的pascal程序(图7-22),表 头,空,sort,offset,tblptr,top,top,0,表 头,空,sort,offset,tblptr,top,top,40,a array 0,x integer 40,a array 0,表 头,空,sort,offset,tblptr,top,top,44,表 头,空,sort,readarrary,表 头,offset,tblptr,top,top,44,0,a array 0,x integer 40,表 头,空,sort,readarrary,表 头,offset,tblptr,top,top,44,4,a array 0,x integer 40,i integer 0,表 头,空,sort,readarrary,表 头 4,offset,tblptr,top,top,44,a array 0,x integer 40,i integer 0,readarray,指向readarray,表 头,空,sort,readarrary,表 头 4,offset,tblptr,44,a array 0,x integer 40,i integer 0,readarray,指向readarray,exchange,表 头,top,top,0,表 头,空,sort,readarrary,表 头 4,offset,tblptr,44,a array 0,x integer 40,i integer 0,readarray,指向readarray,exchange,表 头 0,top,top,exchange,指向exchange,表 头,空,sort,readarrary,表 头 4,offset,tblptr,44,a array 0,x integer 40,i integer 0,readarray,指向readarray,exchange,表 头 0,top,top,exchange,指向exchange,表 头,quicksort,0,表 头,空,sort,readarrary,表 头 4,offset,tblptr,44,a array 0,x integer 40,i integer 0,readarray,指向readarray,exchange,表 头 0,top,top,exchange,指向exchange,表 头,quicksort,4,k integer 0,表 头,空,sort,readarrary,表 头 4,offset,tblptr,44,a array 0,x integer 40,i integer 0,readarray,指向readarray,exchange,表 头 0,top,top,exchange,指向exchange,表 头,quicksort,8,k integer 0,v integer 4,表 头,空,sort,readarrary,表 头 4,offset,tblptr,44,a array 0,x integer 40,i integer 0,readarray,指向readarray,exchange,表 头 0,top,top,exchange,指向exchange,表 头,quicksort,8,k integer 0,v integer 4,表 头,partition,0,表 头,空,sort,readarrary,表 头 4,offset,tblptr,44,a array 0,x integer 40,i integer 0,readarray,指向readarray,exchange,表 头 0,top,top,exchange,指向exchange,表 头,quicksort,8,k integer 0,v integer 4,表 头,partition,4,i integer 0,表 头,空,sort,readarrary,表 头 4,offset,tblptr,44,a array 0,x integer 40,i integer 0,readarray,指向readarray,exchange,表 头 0,top,top,exchange,指向exchange,表 头,quicksort,8,k integer 0,v integer 4,表 头,partition,8,i integer 0,j integer 4,表 头,空,sort,readarrary,表 头 4,offset,tblptr,44,a array 0,x integer 40,i integer 0,readarray,指向readarray,exchange,表 头 0,top,top,exchange,指向exchange,表 头,quicksort,8,k integer 0,v integer 4,表 头 8,partition,i integer 0,j integer 4,partition,表 头,空,sort,readarrary,表 头 4,offset,tblptr,44,a array 0,x integer 40,i integer 0,readarray,指向readarray,exchange,表 头 0,top,top,exchange,指向exchange,表 头 8,quicksort,k integer 0,v integer 4,表 头 8,partition,i integer 0,j integer 4,partition,quicksort,表 头 44,空,sort,readarrary,表 头 4,offset,tblptr,a array 0,x integer 40,i integer 0,readarray,指向readarray,exchange,表 头 0,top,top,exchange,指向exchange,表 头 8,quicksort,k integer 0,v integer 4,表 头 8,partition,i integer 0,j integer 4,partition,quicksort,记录说明的翻译,空间分配 设置首地址和各元素的相对地址 大于所需的空间 （对齐） 例： struct Node float x, y; struct node *next; node;,0,4,8,记录说明的翻译,符号表及有关表格处理 为每个记录类型单独构造一张符号表 将域名id的信息（名字、类型、字节数）填入到该记录的符号表中 所有域都处理完后，offset将保存记录中所有数据对象的宽度 T.type通过将类型构造器record应用于指向该记录符号表的指针获得,记录的域名,T record D end T record L D end T.type := record(top(tblptr); T.width := top(offset); pop(tblptr); pop(offset) L t := mktable(nil); push(t,tblprt);push(0,offset),数组说明的翻译,符号表及有关表格(内情向量)处理 维数、下标上界、下标下界、类型等 空间分配 首地址、需用空间计算 存放方式 按行存放、按列存放影响具体元素地址的计算,数组的引用与分配策略,操作 元素的引用、修改: 数组：Ai,j,k 记录、结构、联合：B.h.j 结构的引用、修改:A,B，A.c 分配策略 静态：直接完成相应的分配工作 动态：构造代码，以在运行时调用分配过程,静态数组分配要完成的工作,数组存放在一个连续的存储区中 知道起始地址 要计算该数组的大小 按照与简单变量类似的方式进行分配,？哪些要处理的问题 准备 上下界的计算 体积的计算 动态分配子程序 将计算的结果告诉动态分配子程序 进行分配,动态数组分配要完成的工作,动态分配方案下数组说明的代码结构,D id:array low1:up1 , , lown:upn of T,low1.code 送工作单元W1 up1.code 送工作单元W2 lown.code 送工作单元W2n-1 upn.code 送工作单元W2n,动态分配子程序其它参数(n,type) 转动态分配子程序入口,? D id:array num of T,8.4 赋值语句的翻译,翻译的需求 充分了解各种语言现象的语义 包括：控制结构、数据结构、单词 充分了解它们的实现方法 目标语言的语义 了解中间代码的语义 了解运行环境,实现赋值语句的翻译,基本子程序 gen(code)，emit(code)：产生一条中间代码 newtemp：产生新的临时变量 lookup：检查符号表中是否出现某名字 属性设置 中间代码序列 code 存储位置 place,为赋值语句产生三地址码的翻译模式,S id := E p := lookup(id.name); if p nil then emit( p, :=, E.place) else error E E1 + E2E.place := newtemp; emit(E.place,:=,E1.place,+,E2.place) E E1 E.place := newtemp; emit(E.place,:=,uminus,E1.place) E (E1) E.place := E1.place E id p := lookup(id.name); if p nil then E.place := p else error ,临时名字的重用,大量临时变量的使用对优化有利 大量临时变量会增加符号表管理的负担 也会增加运行时临时数据占的空间 E E1 + E2的动作产生的代码的一般形式为 计算E1到t1 计算E2到t2 t3 := t1 + t2( )( )( )( ) 临时变量的生存期像配对括号那样嵌套或并列,基于临时变量生存期特征的三地址代码,x := a b + c d e f,引入一个计数器c，它的初值为0。每当临时变量作为运算对象使用时，c减去1；每当要求产生新的临时名字时，使用$c并把c增加1。,数组元素的引用,数组元素的翻译 完成上下界检查 生成完成相对地址的计算代码 目标 x := yi 和 yi := x y为数组地址的固定部分相当于第1个元素的地址，i是相对地址，不是数组下标,数组元素地址计算-行优先,一维数组Alow1:up1 (nk=upk-lowk+1) Addr(Ai)=base+(i-low1)*w =(base-low1*w)+i*w=c+i*w 二维数组Alow1:up1 ,low2:up2；Ai1,i2 Addr(Ai1,i2)=base+(i1- low1)*n2+(i2-low2)*w = base+(i1- low1)*n2*w+(i2-low2)*w = base- low1* n2*w-low2*w +i1 * n1*w+ i2*w = base-(low1* n2 -low2)*w +(i1 * n1 + i2)*w =c+(i1*n2+ i2)*w,A1, 1, A1, 2, A1, 3 A2, 1, A2, 2, A2, 3,数组元素地址计算的翻译方案,下标变量访问的产生式 L idElist | id Elist Elist,E | E 为了使数组各维的长度n在我们将下标表达式合并到Elist时是可用的，需将产生式改写为： L Elist | id Elist Elist,E | idE,数组元素地址计算的翻译方案,L Elist | id Elist Elist,E | idE 目的 使我们在整个下标表达式列表Elist的翻译过程中随时都能知道符号表中相应于数组名id的表项，从而能够了解登记在符号表中的有关数组id的全部信息。 于是我们就可以为非终结符Elist引进一个综合属性array，用来记录指向符号表中相应数组名字表项的指针。,数组元素地址计算的翻译方案,属性 Elist.array，用来记录指向符号表中相应数组名字表项的指针。 Elist.ndim，用来记录Elist中下标表达式的个数，即数组的维数。 Elist.place，用来临时存放Elist的下标表达式计算出来的值。 函数 limit（array，j），返回nj,赋值语句完整的产生式,S L := E E E + E E (E) E L L Elist L id Elist Elist,E Elist idE,赋值语句的翻译模式,Lid L.place :=id.place;L.offset:=null ElistidE Elist.place:=E.place; Elist.ndim := 1; Elist.array := id.place ElistElist1,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 L Elist L.place := newtemp; emit(L.place,:=,base(Elist.array), invariant(Elist.array); L.offset := newtemp; emit(L.offset,:=,Elist.place,w),赋值语句的翻译模式,E Lif L.offset = null then / L是简单变量 / E.place := L.place else begin E.place := newtemp; emit(E.place,:=,L.place,L.offset,)end E E1 + E2E.place := newtemp; emit(E.place,:=,E1.place,+,E2.place) E (E1)E.place := E1.place S L := Eif L.offset=null then/L是简单变量/ emit (L.place, := , E.place) else emit(L.place,L.offset,:=,E.place),例：设A是一个1020的整型数组，w=4,例,t1 := y 20 t1 := t1 + z,例,t1 := y 20 t1 := t1 + z,t2 :=A 84 t3 := 4 t1,例,t1 := y 20 t1 := t1 + z,t2 :=A 84 t3 := 4 t1,t4 := t2 t3 ,例,t1 := y 20 t1 := t1 + z,t2 :=A 84 t3 := 4 t1,t4 := t2 t3 ,x := t4,表达式翻译中的其它问题,临时变量空间的统计 了解需求、及时释放 运算合法性检查 利用符号表保存的名字类型 类型自动转换 填加专用指令,类型转换,x := y + i j （x和y的类型是real，i和j的类型是integer） 中间代码 t1 := i int j t2 := inttoreal t1 t3 := y real+ t2 x := t3,类型转换,E E1 + E2的语义子程序 E.place := newtemp if E1.type = integer and E2.type = integer then begin emit(E.place,:=,E1.place,int+,E2.place); E.type = integer end else if E1.type = integer and E2.type = real then begin u := newtemp; emit(u,:=,inttoreal,E1.place); emit(E.place,:=,u,real+,E2.place); E.type := real end . . .,8.5 控制语句的翻译,高级语言的控制结构 顺序 begin 语句; ；语句end 条件 if_then_else、if_then switch、case 循环 while_do、do_while for、repeat_until 三地址码 goto n (j,_,_,n) if x relop y goto n(jrelop,x,y,n),布尔表达式的翻译,基本文法 EE1 or E2|E1 and E2|not E1|(E1)|id1 relop id2|id 处理方式 数值表示法（与算术表达式的处理类似） 真：E.place=1 假：E.place=0 真假出口表示法（作为条件控制） 真出口：E.true 假出口：E.false,数值表示法,a or b and not c t1:=not c t2:=b and t1 t3:=a or t2 ab 100: if ab goto 103 101: t:=0 102: goto 104 103: t:=1 104,数值表示法,E E1 or E2 E.place := newtemp; gen(E.place:=E1.placeorE2.place) E E1 and E2 E.place := newtemp; gen(E.place:=E1.placeandE2.place) E not E1 E.place := newtemp; gen(E.place:= notE1.place),数值表示法,E ( E1 ) E.place:= E1.place E id1 relop id2 E.place := newtemp; gen(ifid1.place relop.op id2.placegotonextstat+3); gen(E.place := 0) ; gen(gotonextstat+2); gen(E.place := 1) E id E.place:= id.place;,真假出口表示法,属性 E.true，E为真时控制到达的位置； E.false，E为假时控制到达的位置。 ab if ab goto E.true goto E.false EE1 or E2 如果E1为真，则立即可知E为真，即E1.true与E.true相同； 如果E1为假，则必须计算E2的值，令E1.false为E2的开始 E2的真假出口分别与E的真假出口相同,简单布尔表达式的翻译示例 例如：ab or cd and ef,if ab goto Ltrue goto L1 L1:if cd goto L2 goto Lfalse L2:if ef goto Ltrue goto Lfalse,真假出口表示法,E E1 or E2 E1.true:=E.true;E1.false:=newlab; E2.true=E.true; E2.false:=E.false; E.code := E1.code；gen(E1.false:)；E2.code E E1 and E2 E1.true:= newlab;E1.false:= E.false; E2.true=E.true; E2.false:=E.false; E.code := E1.code；gen(E1.true:) ；E2.code E not E1 E1.true:=E.false; E1.false:=E.true； E.code :=E1.code,真假出口表示法,E ( E1 ) E1.true:=E. true; E1.false:=E.false； E.code :=E1.code E id1 relop id2 E.code:=gen(ifid1.place relop id2.placegotoE.true)； gen(goto E.false) E id E.code:=gen( if id1.place goto E.true)； gen( goto E.false),混合模式布尔表达式的翻译,E E1 relop E2 E1 + E2 E.code := E1.code；E2.code； gen( ifE1.place relop E2.place gotoE.true)； gen(gotoE.false),混合模式布尔表达式的翻译示例 例如：4+ab-c and d,t1=4+a t2=b-c if t1t2 goto L1 goto Lfalse L1: if d goto Ltrue goto Lfalse,回填,两遍扫描： 从给定的输入构造出一棵语法树； 对语法树按深度优先遍历，来进行定义中给出的翻译。 一遍扫描： 先产生暂时没有填写目标标号的转移指令。 对于每一条这样的指令作适当的记录， 一旦目标标号被确定下来，再将它“回填”到相应的指令中。 E.truelist E.falselist,回填,翻译模式用到如下三个函数： 1makelist(i)：创建一个仅包含i的新表，i 是四元式数组的一个索引（下标），或说 i是四元式代码序列的一个标号。 2merge(p1，p2)：连接由指针p1和p2指向 的两个表并且返回一个指向连接后的表的 指针。 3backpatch（p，i）：把i作为目标标号回 填到p所指向的表中的每一个转移指令中 去。 此处的“表”都是为“回填”所拉的链,布尔表达式的自底向上语法制导翻译模式,E E1 or M E2 backpatch(E1.falselist,M.quad); E.truelist:=merge(E1.truelist,E2.truelist); E.falselist := E2.falselist M M.quad:=nextquad,布尔表达式的自底向上语法制导翻译模式,E E1 and M E2 backpatch(E1.truelist,M.quad); E.truelist := E2.truelist E.falselist:=merge(E1.falselist,E2.falselist); ,布尔表达式的自底向上语法制导翻译模式,E not E1 E.truelist := E1.falselist; E.falselist := E1.truelist; ,布尔表达式的自底向上语法制导翻译模式,E (E1 ) E.truelist := E1.truelist; E.falselist := E1.falselist;,布尔表达式的自底向上语法制导翻译模式,E id1 relop id2 E.truelist:=makelist(nextquad); E.falselist:=makelist(nextquad+1); emit(ifid1.place relop id2.place goto-) Emit(goto-) ,布尔表达式的自底向上语法制导翻译模式,E true E.truelist := makelist(nextquad) emit(goto-) E false E.falselist := makelist(nextquad) emit(goto-),例,E.t = 100, 104 E.f = 103,105,M.q:=102,E.t := 100 E.f := 101,E.t = 104 E.f = 103,105,E.t = 102 E.f = 103,E.t = 104 E.f = 105,图 8-29 ab or cd and ef的注释分析树,a,b,or,M.q:=104,and,c,d,e,f,100: if ab goto 101: goto - 102: if cd goto 104 103: goto 104: if ef goto 105: goto -,100: if ab goto 101: goto -,102: if cd goto 103: goto -,104: if ef goto 105: goto -,100: if ab goto 101: goto 102 102: if cd goto 104 103: goto 104: if ef goto 105: goto -,控制流语句的翻译,S if E then S1 | if E then S1 else S2 | while E do S1 | S1;S2 | A /*赋值语句*/ S.nextlist:=nil,控制流语句的翻译,控制流语句的翻译,S if E then S1 E.true := newlabel; E.false := S.next; S1.next := S.next; S.code:=E.code|gen(E.true,:)|S1.code ,控制流语句的翻译,S if E then S1 else S2 E.true := newlabel; E.false := newlabel; S1.next := S.next; S2.next := S.next; S.code :=E.code|gen(E.true,:)|S1.code | gen(goto,S.next)|gen(E.false,:)|S2.code,控制流语句的翻译,S while E do S1 S.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),控制流语句的翻译,S S1; S2 S1.next:=newlabel;S2.next:=S.next; S.code:=S1.code|gen(S1.next,:)|S2.code,例 8-4：翻译下列语句,while a y do z := x + 1; else S2 x := y,S3,生成的三地址代码序列,L1: if a y goto L5 goto L1 L5: t1:= x + 1 z := t1 goto L3 L4: x := y goto L1 Lnext:,E1.code,E2.code,S1.code,S2.code,S3.code,while ay do z:=x+1 else x:=y,控制流语句的自底向上翻译_利用回填技术,S if E then M S1 | if E then M1 S1 N else M2 S2 | while M1 E do M2 S1 | S1;M S2 M M.quad := nextquad N N.nextlist:=makelist(nextquad); emit(goto -),if-then语句的自底向上翻译,S if E then M S1 backpatch(E.truelist, M.quad) S.nextlist:=merge(E.falselist, S1.nextlist),if-then-else语句的自底向上翻译,S if E then M1 S1 N else M2 S2 backpatch(E.truelist, M1.quad); backpatch(E.falselist, M2.quad); S.nextlist:= merge(S2.nextlist,merge(N.nextlist,S1.nextlist),while语句的自底向上翻译,S while M1 E do M2 S1 backpatch(S1.nextlist,M1.quad); backpatch(E.truelist,M2.quad); S.nextlist:=E.falselist; emit(gotoM1.quad),语句列表的翻译,S S1;M S2 backpatch(S1.nextlist, M.quad); S.nextlist:=S2.nextlist,例 8-4：翻译下列语句,while a y do z := x + 1; else S2 x := y,S3,例,while ay do z:=x+1 else x:=y的注释分析树,S.n:=101,while,M1.q:=100,E.t := 100 E.f := 101,a,b,do,M2.q:=102,S1.n:=105,109,if,E.t := 102 E.f := 103,c,5,then,M1.q:=104,S1.n:=105,N.n:=109,else,M2.q:=110,S2.n:=nil,:=,x,y,while,M1.q:=104,E.t := 104 E.f := 105,x,y,do,M2.q:=106,:=,z,E.place=t1,M1.q:=100,E.t := 100 E.f := 101,M2.q:=102,E.t := 102 E.f := 103,M1.q:=104,M1.q:=104,E.t := 104 E.f := 105,M2.q:=106,+,x,1,E.place=t1,S1.n:=105,S,S.n:=nil,N.n:=109,M2.q:=110,S2.n:=nil,S1.n:=105,109,S.n:=101,生成的四元式序列,100: （j,x,y,106） 105： （j,-,-,100） 106： （+,x,1,t1） 107： （:=, t1,-,z） 108： （j,-,-,104） 109： （j,-,-,100） 110： （:=,y,-,x） 111： （j,-,-,100） 112:,while ay do z:=x+1 else x:=y,开关语句的翻译,switch E begin case V1: S1 case V2: S2 . . . case Vn - 1: Sn 1 default: Sn end,分支数较少时 t := E的代码 if t V1 goto L1 S1的代码 goto next L1: if t V2 goto L2 S2的代码 goto next L2: . . . . . . Ln-2: ift Vn-1 goto Ln-1 Sn -1的代码 goto next Ln-1: Sn的代码 next:,分支较多时，将分支测试的代码集中在一起， 便于生成较好的分支测试代码。 t := E的代码| Ln:Sn的代码 goto test | goto next L1:S1的代码 |test: if t = V1 goto L1 goto next| if t = V2 goto L2 L2:S2的代码 |. . . goto next|if t = Vn-1 goto Ln-1 . . . |goto Ln Ln-1:Sn -1的代码| next: goto next,中间代码增加一种case语句，便于代码生成器 对它进行特别处理 test: case V1 L1 case V2 L2 . . . case Vn-1 Ln-1 case t Ln next:,过程调用的翻译,S call id (Elist) Elist Elist, E Elist E,过程调用id(E1, E2, , En)的中间代码结构,E1.place := E1的代码 E2.place := E2的代码 . . . En.place := En的代码 param E1.place param E2.place . . . param En.place call id.place, n,S call id (Elist) 为长度为n的队列中的每个E.place， emit(param, E.place); emit(call, id.plase, n) Elist Elist, E 把E.place放入队列末尾 Elist E 将队列初始化，并让它仅含E.place,自顶向下的语法制导翻译,递归下降法 在递归子程序的适当位置加进语义动作 每个非终结符对应一个子程序 例：赋值语句和repeat语句的翻译,文法,S i:=A i S repeat S until E repeat E T(or E|) not,(,i T F(and T|) not,(,i F not F not F (E) ( F i(rop i|) i,首终结符集,repeat语句的目标结构,S repeat M1 S1 until M2 E backpatch(S1.nextlist, M2.quad); backpatch(E.falselist, M1.quad); S.nextlist:=E.truelist,递归下降翻译程序,function S(token):pointer; begin case token of i:begin /*处理赋值语句*/ getnext(token); if token “:=“ then error; getnext(token); E.place := A(token); gencode(:=,E.place, - , entry(i); S.chain:=0; return(S.chain) end;,递归下降翻译程序,repeat:begin /*处理repeat语句*/ R.head:=NXQ; getnext(token); S.chain:=S(token); getnext(token); if token “until“ then error; backpatch(S.chain,NXQ); getnext(token); (E.TC,E.FC):=E(token); backpatch(E.FC,R.head); S.chain:=E.TC; return(S.chain) end; end case end.,递归下降翻译程序,function E(token):pointer; begin /*翻译E T(or E|)*/ if token in not,(,i then begin (T.TC,T.FC):=T(token); getnext(token); if token “or“ then return(T.TC,T.FC); else begin backpatch(T.FC,NXQ); getnext(token); (E.TC,E.FC) := E(token); E.TC:=merge(E.TC,T.TC) end return(E.TC,E.FC) end end.,递归下降翻译程序,function T(token):pointer; begin /*翻译T F(and T|)*/ if token in not,(,i then begin (F.TC,F.FC):=F(token); getnext(token); if token “and“ then return(F.TC,F.FC); else begin backpatch(F.TC,NXQ); getnext(token); (T.TC,T.FC) := T(token); E.FC:=merge(T.FC,F.FC) end return(T.TC,T.FC) end end.,递归下降翻译程序,function F(token):pointer; begin /*F not F|(E)|i(rop i|)*/ case token of not:begin getnext(token); (F.TC,F.FC):=F(token); F.TC:=F.FC; F.FC:=F.TC end; (:begin getnext(token); (F.TC,F.FC) := E(token); getnext(token); if token “)“ then error; end,递归下降翻译程序,i:begin I1:=entry(token); if token in ,=,then begin /*处理i rop i关系式*/ getnext(token); if token i then error; I2:=entry(token); F.TC:=NXQ; gencode(jrop,I1,I2,0); F.FC:=NXQ; gencode(j,-,-,0) end else begin /*处理单个布尔变量*/ F.TC:=NXQ; gencode(jnz,I1,-,0); F.FC := NXQ; gencode(j,-,-,0); end end end case return(F.TC,F.FC) end,1.利用子程序中的局部变量实现语义分析 2.利用系统堆栈在过程间传递语义信息,LL(1)语法制导翻译,预先在源文法中的相应位置上嵌入语义动作符号（每个对应一个语义子程序），用于提示语法分析程序，当分析到达这些位置时应调