语义分析和中间代码产生.ppt

第七章 语义分析和中间代码产生,内容,中间语言 说明语句 赋值语句的翻译 布尔表达式的翻译 控制语句的翻译 过程调用的处理 类型检查,语义分析与中间代码产生,词法分析和语法分析之后，编译程序的工作是进行静态语义检查和翻译 静态语义检查包括 类型检查 控制流检查 一致性检查 相关名字检查 名字的作用域分析,语法分 析器,中间代码 产生器,静态检 查器,,中间代码,优化器,,,语义分析与中间代码产生,翻译为中间语言(复杂性界于源语言和目标语言之间)的好处： 便于进行与机器无关的代码优化工作 易于移植 使编译程序的结构在逻辑上更为简单明确,源语言 程序,目标语 言程序,中间语 言程序,7.1 中间语言,常用的中间语言： 后缀式（逆波兰表示） 三地址代码 三元式 四元式 间接三元式 DAG图表示,7.1.1 后缀式,后缀式表示法：Lukasiewicz发明的一种表示表达式的方法，又称逆波兰表示法 后缀式表示法把运算量（操作数）写在前面，把算符写在后面（后缀）如a+b写成ab+ 一个表达式E的后缀形式可以如下定义： 1. 如果E是一个变量或常量，则E的后缀式是E自身 2. 如果E是E1 op E2形式的表达式，其中op是任何二元操作符，则E的后缀式为E1 E2 op，其中E1 和E2 分别为E1 和E2的后缀式。

3. 如果E是(E1)形式的表达式，则E1 的后缀式就是E的后缀式7.1.1 后缀式,abc+*等价a*(b+C) 逆波兰表示法不用括号只要知道每个算符的目数，对于后缀式，不论从哪一端进行扫描，都能对它进行唯一分解 后缀式的计算 用一个栈实现 一般的计算过程是：自左至右扫描后缀式，每碰到运算量就把它推进栈每碰到k目运算符就把它作用于栈顶的k个项，并用运算结果代替这k个项把表达式翻译成后缀式的语义规则描述,产生式 EE1op E2 E (E1) Eid,语义规则 E.code:= E1.code || E2.code ||op E.code:= E1.code E.code:=id,E.code表示E后缀形式 op表示任意二元操作符 “||”表示后缀形式的连接7.1.1 后缀式,数组POST存放后缀式：k为下标，初值为1 上述语义动作可实现为： 产生式程序段 EE1op E2POSTk:=op;k:=k+1 E (E1) EiPOSTk:=i;k:=k+1 例：输入串a+b+c的分析和翻译 POST： 1 2 3 4 5,7.1.1 后缀式,后缀式的推广： 对于条件算术表达式 if e then X else Y 可表示为eXY￥，其中￥表示三目运算if-then-else,7.1.2 图表示法,图表示法 DAG 抽象语法树 无循环有向图(Directed Acyclic Graph，简称DAG) 对表达式中的每个子表达式，DAG中都有一个结点 一个内部结点代表一个操作符，它的孩子代表操作数 在一个DAG中代表公共子表达式的结点具有多个父结点,a:=b*(-c)+b*(-c)的图表示法,7.1.2 图表示法,产生赋值语句抽象语法树的属性文法,7.1.3 三地址代码,三地址代码： 一般形式：x := y op z 三地址代码包含三个地址，两个用来表示操作数，一个用来存放结果。

表达式x + y z翻译成的三地址语句序列是 t1 := y z t2 := x + t1,7.1.3 三地址代码,三地址代码是语法树或DAG的一种线性表示 a := (b + cd ) + cd 语法树的代码DAG的代码 t1 := bt1 := b t2 := c dt2 := c d t3 := t1 + t2t3 := t1 + t2 t4 := c dt4 := t3 + t2 t5 := t3 + t4 a := t4 a := t5,7.1.3 三地址代码,三地址语句的种类 赋值语句x := y op z，x := op y，x := y 无条件转移goto L 条件转移if x relop y goto L 过程调用param x 和call p , n 过程返回return y 索引赋值x := yi和 xi := y 地址和指针赋值x := E.code:=E1.code || E2.code || gen(E.place := E1.place + E2.place) EE1*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.code Eid E.place:=id.place; E.code= ,三地址语句,四元式 一个带有四个域的记录结构，这四个域分别称为op, arg1, arg2及result。

如： a:=b*-c+b*-c 的四元式： oparg1arg2result (0)uminuscT1 (1)*bT1T2 (2)uminuscT3 (3)*bT3T4 (4)+T2T4T5 (5):=T5a,三地址语句,三元式 通过计算临时变量值的语句的位置来引用这个临时变量如： a:=b*-c+b*-c 的三元式： 三个域：op、arg1和arg2 oparg1arg2 (0)uminusc (1)*b(0) (2)uminusc (3)*b(2) (4)+(1)(3) (5)assigna(4),三地址语句,三元式 三元式中的多目运算符： xi:=y op arg1 arg2 (0) = x i (1) assign (0) y x:=yi op arg1 arg2 (0) = y i (1) assign x (0),三地址语句,间接三元式 为了便于优化，用 三元式表+间接码表 表示中间代码 间接码表:一张指示器表，按运算的先后次序列出有关三元式在三元式表中的位置 优点: 方便优化，节省空间,例如，语句 X:=(A+B)*C; Y:=D(A+B) 的间接三元式表示如下表所示。

7.2 说明语句,为局部名字建立符号表条目 为它分配存储单元 符号表中包含名字的类型和分配给它的存储单元的相对地址等信息,7.2.1 过程中的声明,计算被说明名字的类型和相对地址 P D offset := 0 D D ; D D id : T enter ( id.name, T.type, offset); offset := offset + T.width T integer T.type := integer; T.width := 4 T real T.type := real; T.width := 8 T array num of T1 T.type := array (num.val, T1.type); T.width := num.val T1.width T T1 T.type := pointer (T1.type); T.width := 4,7.2.2 保留作用域信息,所讨论语言的文法（允许嵌套过程） P D D D ; D | id : T | proc id ; D ; S 语义动作用到的函数 mktable(previous) enter(table, name, type, offset) addwidth(table, width) enterproc(table, name, newtable),P M D addwidth (top (tblptr), top (offset) ); pop(tblptr); pop (offset) M t := mktable (nil); push(t, tblprt); 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) ,7.2.2 保留作用域信息,7.2.3 记录的域名,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) ,7.3 赋值语句的翻译,注意：E.place表示存放E值的名字 newtemp：每次调用时，返回一个不同临时变量 emit 生成三地址语句并发送到输出文件中,7.3.1 简单算术表达式及赋值语句,产生赋值语句三地址代码的翻译模式 Sid:=E p:=lookup(id.name); if pnil then emit(p := E.place) else error EE1+E2 E.place:=newtemp; emit(E.place := E1.place + E2.place) EE1*E2 E.place:=newtemp; emit(E.place := E 1.place * E 2.place),7.3.1 简单算术表达式及赋值语句,产生赋值语句三地址代码的翻译模式 E-E1 E.place:=newtemp; emit(E.place:= uminusE 1.place) E(E1) E.place:=E1.place Eid p:=lookup(id.name); if pnil then E.place:=p else error ,7.3.2 数组元素的引用,数组元素地址的计算： 一维数组A的第i个元素的地址计算 base + ( i low ) w 重写成 i w + (base low w) 减少了运行时的计算,7.3.2 数组元素的引用,数组元素地址的计算： 设A为n维数组，每个元素宽度为w， lowi 为第i维 的下界，ni 是为第i维 可取值的个数, base为A的第一个元素相对地址 元素Ai1,i2,,ik相对地址公式 ((i1 n2+i2)n3+i3))nk+ik)w + base-((((low1 n2+low2)n3+low3))nk+lowk)w C= base-((((low1 n2+low2)n3+low3))nk+lowk)w,7.3.2 数组元素的引用,数组元素地址计算的翻译方案 下标变量访问的产生式 L id Elist | id Elist Elist, E | E 为了便于语义处理，改成 L Elist | id Elist Elist, E | id E,7.3.2 数组元素的引用,所有产生式： S L := E E E + E E (E ) E L L Elist L id Elist Elist, E Elist id E,7.3.2 数组元素的引用,L id L.place := id.place; L.offset := null Elist id E Elist.place := E.place; Elist.ndim := 1; Elist.array := id.place 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 L Elist L.place := newtemp; emit (L.place, :=, base(Elist.array), , invariant (Elist.array) ); L.offset := newtemp; emit (L.offset, :=, Elist.place, , w) ,7.3.2 数组元素的引用,E L if L.offset = null then / L是简单变量 / E.place := L.place else begin E.place := newtemp; emit (E.place, :=, L.place, , L.offset, ) end E E1 + E2 E.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) ,7.3.2 数组元素的引用,t1 := y 20 t1 := t1 + z,t2 :=A 84 t3 := 4 t1,t4 := t2 t3 ,x := t4,T1：y*20 T1：T1+z T2：A-84 T3：4 * T1 T4：T2T3 X：T4,7.3.2 数组元素的引用,类型转换 x := y + i j （x和y的类型是real，i和j的类型是integer） 中间代码 t1 := i int j t2 := inttoreal t1 t3 := y real+ t2 x := t3,7.3.2 数组元素的引用,关于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 . . .,7.3.3 记录中域的引用,符号表表项之中保存记录中的域的类型和相对地址信息,7.4 布尔表达式的翻译,布尔表达式有两个基本目的 计算逻辑值 在控制流语句中用作条件表达式 产生布尔表达式的文法: EE or E | E and E | not E | (E) | id relop id | id,7.4 布尔表达式的翻译,计算布尔表达式通常采用两种方法: 1. 如同计算算术表达式一样,一步步算 1 or (not 0 and 0) or 0 =1 or (1 and 0) or 0 =1 or 0 or 0 =1 or 0 =1 2. 采用某种优化措施 把A or B解释成 if A then true else B 把A and B解释成 if A then B else false 把not A解释成 if A then false else true,7.4 布尔表达式的翻译,两种不同的翻译方法: 第一种翻译法： A or B and C=D翻译成 (1) (=, C, D, T1) (2) (and, B, T1, T2) (3) (or, A, T2, T3) 第二种翻译法适合于作为条件表达式的布尔表达式使用.,7.4.1 数值表示法,a or b and not c 翻译成 T1:=not c T2:=b and T1 T3:=a or T1 a

一遍扫描,一遍扫描实现布尔表达式的翻译,采用四元式形式 把四元式存入一个数组中，数组下标就代表四元式的标号 约定: 四元式(jnz, a, -, p) 表示 if a goto p 四元式(jrop, x, y, p) 表示 if x rop y goto p 四元式(j, -, -, p) 表示 goto p,有时,四元式转移地址无法立即知道,我们只好把这个未完成的四元式地址作为E的语义值保存,待机回填 为非终结符E赋予两个综合属性E.truelist和E.falselist它们分别记录布尔表达式E所应的四元式中需回填“真”、“假”出口的四元式的标号所构成的链表,一遍扫描实现布尔表达式的翻译,例如:假定E的四元式中需要回填真出口的p，q，r三个四元式，则E.truelist为下列链: (p) (x， x，x，0) (q) (x，x，x，p) (r) (x，x，x，q),,,链尾,E. truelist =r,为了处理E.truelist和E.falselist ，引入下列语义变量和过程: 变量nextquad，它指向下一条将要产生但尚未形成的四元式的地址(标号)nextquad的初值为1，每当执行一次emit之后，nextquad将自动增1。

函数makelist(i)，它将创建一个仅含i的新链表，其中i是四元式数组的一个下标(标号)；函数返回指向这个链的指针 函数merge(p1,p2)，把以p1和p2为链首的两条链合并为一，作为函数值，回送合并后的链首 过程backpatch(p, t)，其功能是完成“回填”，把p所链接的每个四元式的第四区段都填为t布尔表达式的文法,(1) EE1 or M E2 (2) | E1 and M E2 (3)| not E1 (4)| (E1) (5)| id1 relop id2 (6)| id (7)M,布尔表达式的翻译模式,(1) EE1 or M E2 backpatch(E1.falselist, M.quad); E.truelist:=merge(E1.truelist, E2.truelist); E.falselist:=E2.falselist (2) EE1 and M E2 backpatch(E1.truelist, M.quad); E.truelist:=E2.truelist; E.falselist:=merge(E1.falselist,E2.falselist) ,布尔表达式的翻译模式,(3) Enot E1 E.truelist:=E1.falselist; E.falselist:=E1.truelist (4) E(E1) E.truelist:=E1.truelist; E.falselist:=E1. falselist,布尔表达式的翻译模式,(5) Eid1 relop id2 E.truelist:=makelist(nextquad); E.falselist:=makelist(nextquad+1); emit(j relop.op , id 1.place , id 2.place,0); emit(j, , , 0) (6) Eid E.truelist:=makelist(nextquad); E.falselist:=makelist(nextquad+1); emit(jnz , id .place , ,0)； emit( j, -, -, 0) ,布尔表达式的翻译模式,(7) M M.quad:=nextquad 作为整个布尔表达式的真假出口(转移目标)仍待回填.,a

if-then语句的属性文法 产生式语义规则 Sif E then S1 E.true:=newlabel; E.flase:=S.next; S1.next:=S.next S.code:=E.code || gen(E.true :) || S1.code,7.5.1 控制流语句,7.5.1 控制流语句,if-then-else语句的属性文法 产生式 语义规则 Sif 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,7.5.1 控制流语句,while-do语句的属性文法 产生式语义规则 Swhile 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),考虑如下语句 :while a

if 语句的翻译,相关产生式 S if E then S1 | if E then S1 else S2 改写后产生式 S if E then M S1 S if E then M1 S1 N else M2 S2 M N,if 语句的翻译,翻译模式: 1. Sif E then M S1 backpatch(E.truelist, M.quad); S.nextlist:=merge(E.falselist, S1.nextlist) 2. Sif 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) 3. M M.quad:=nextquad 4. N N.nextlist:=makelist(nextquad); emit(j,,,) ,while 语句的翻译,相关产生式 S while E do S1 改写后产生式 Swhile M1 E do M2 S1 M,while 语句的翻译,翻译模式: 1. Swhile M1 E do M2 S1 backpatch(S1.nextlist, M1.quad); backpatch(E.truelist, M2.quad); S.nextlist:=E.falselist emit(j,,, M1.quad) 2. M M.quad:=nextquad ,其它语句的翻译,产生式 LL1;S 改写为： LL1; M S M 翻译模式: 1. LL1; M S backpatch(L1.nextlist, M.quad); L.nextlist:=S.nextlist 2. M M.quad:=nextquad ,其它语句的翻译,1. Sbegin L end S.nextlist:=L.nextlist 2. SA S.nextlist:=makelist( ) 3. LS L.nextlist:=S.nextlist ,例:按照上述的语义动作，及关于赋值句和布尔表达式的翻译法，语句 while(ab) do if (cd) then x:=yz；将被翻译成如下的一串四元式：,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,7.5.2 标号与goto语句,产生式Sgoto L的语义动作: 查找符号表； IF L在符号表中且定义否栏为已 THEN GEN(J，-，-，P) ELSE IF L不在符号表中 THEN BEGIN 把L填入表中； 置定义否为未，地址栏为NXQ； GEN(J，-，-，0) END ELSE BEGIN Q:=L的地址栏中的编号； 置地址栏编号为NXQ； GEN(J，-，-，Q) END ,7.5.3 CASE语句的翻译,语句结构 case E of C1:S1; C2:S2; Cn-1:Sn-1; otherwise:Sn end,翻译法(一): T:=E L1:if TC1 goto L2 S1的代码 goto next L2:if TC2 goto L3 S2的代码 goto next L3: Ln-1:if TCn-1 goto Ln Sn-1的代码 goto next Ln:Sn的代码 next:,改进:,翻译法(二): 计算E并放入T中 goto test L1:关于S1的中间码 goto next Ln-1:关于Sn-1的中间码 goto next Ln:关于Sn的中间码 goto next test:if T=C1 goto L1 if T=C2 goto L2 if T=Cn-1 goto Ln-1 goto Ln next:,(case, C1, P1) (case, C2, P2) (case, Cn-1, Pn-1) (case, T, Pn) (label, NEXT, -, -),Pi是LI在 符号表中 的位置,7.6 过程调用的处理,过程调用主要对应两件事: 传递参数 转移到子程序 传地址:把实在参数的地址传递给相应的形式参数 调用段预先把实在参数的地址传递到被调用段可以拿到的地方； 程序控制转入被调用段之后，被调用段首先把实在参数的地址抄进自己相应的形式单元中； 过程体对形式参数的引用或赋值被处理成对形式单元的间接访问。