6 下标变量的中间代码生成 下标:数组；变量： 下标变量：即数组分量： 简单变量：id，其地址可查到；

Presentation on theme: "6 下标变量的中间代码生成 下标:数组；变量： 下标变量：即数组分量： 简单变量：id，其地址可查到；"— Presentation transcript:

1 6 下标变量的中间代码生成 下标:数组；变量： 下标变量：即数组分量： 简单变量：id，其地址可查到；
数组分量还有结构体成员其地址不可查，如何访问？ 下标变量的中间代码就是计算其地址。

2 例：C语言的数组 int A[5][6]; Off Level dir TypePtr A ElemType Size Kind
VarKind A ElemType Size Kind 5*6*size(int) ArrayTy Low Up 4 ElemType IntPtr Size 6*size(int) Kind ArrayTy Low Up 5 A[0][0] A[0][1] A[0][2] A[0][3] A[0][4] A[0][5] A[1][0] A[1][1] A[1][2] A[1][3] A[1][4] A[1][5] A[2][0] A[2][1] A[2][2] A[2][3] A[2][4] A[2][5] A[3][0] A[3][1] A[3][2] A[3][3] A[3][4] A[3][5] A[4][0] A[4][1] A[4][2] A[4][3] A[4][4] A[4][5] A[0] A[1] A[2] A[3] A[4]

3 1 ..... 5 6 7 ...... 11 24 25 29 A[0][0] int A[5][6]; A[0][1] A[0] 数组声明 int A[D1][D2]; 确定了第i维的宽度 Di=Upi-Lowi+1 假设起始地址为零Addr(A[E1][E2]) =E1×S1+E2×S2 S1=D2×S2 S2=sizeof(int) A[0][5] A[1][0] A[1][1] A[1] A[1][5] Int A[D1][D2]; Adr(A[E1][E2])=E1*S1+E2*S2 S1=D2 S2=1 A[4][0] A[4][1] A[4] A[4][5]

4 1 ..... 5 6 7 ...... 11 24 25 29 int A[3][5][6]; A[0][0][0] A[0][0][1] A[0][0] A[0][0][5] A[0][1][0] A[0][1][1] A[0][1] A[0] A[0][1][5] Int A[D1][D2]; Adr(A[E1][E2])=E1*S1+E2*S2 S1=D2 S2=1 A[0][4][0] A[0][4][1] A[0][4] A[0][4][5]

5 S1=D2×D3×sizeof(int)=D2×S2 S2=D3×sizeof(int)=D3×S3 S3=sizeof(int)
int A[3][5][6]; A[0] int A[D1][D2][D3]; Addr(A[E1][E2][E3]) =E1×S1+E2×S2+E3×S3 其中Si为第i维占用的地址空间 S1=D2×D3×sizeof(int)=D2×S2 S2=D3×sizeof(int)=D3×S3 S3=sizeof(int) A[1]

6 …………………….. …………………….. 假设有数组类型的变量声明如下：
A :array [L1..U1] [L2 .. U2]…[Ln ..Un] of T ;（n  1） 数组类型的内部表示 其中Di=Ui-Li+1 Size Kind Low Up ElemType D1 × D2×…. × Dn-1 × Dn × Size(T) ArrayTy L1 U1 D2 × D3×…. × Dn-1 × Dn × Size(T) ArrayTy L2 U2 …………………….. Dk × Dk+1×…. × Dn-1 × Dn × Size(T) ArrayTy Lk Uk …………………….. Dn-1 × Dn × Size(T) ArrayTy Ln-1 Un-1 Dn × Size(T) ArrayTy Ln Un Size(T) Ptr(T) ……. ArrayTy

7 将size转化为S则有： …………………….. …………………….. 假设有数组类型的变量声明如下：
A :array [L1..U1] [L2 .. U2]…[Ln ..Un] of T ;（n  1） 将size转化为S则有： Size Kind Low Up ElemType S0 ArrayTy L1 U1 S1 ArrayTy L2 U2 …………………….. Sk-1 ArrayTy Lk Uk …………………….. Sn-2 ArrayTy Ln-1 Un-1 Sn-1 ArrayTy Ln Un Sn Ptr(T) ……. ArrayTy

8 6.1 下标变量的地址 E1→ t1 ( SUBI, t1 , L1, t2) ( MULTI , t2 , S1 , t3 )
文法G： V → id A A → [ E ] B B →  | [ E ] B 假设有数组类型的变量声明如下： A :array [L1..U1] [L2 .. U2]…[Ln ..Un] of T ; Si = Di+1 ×Si+1 =(Ui+1 -Li+1 +1) × Si+1 Sn = Size ( T ) E1→ t1 ( SUBI, t1 , L1, t2) ( MULTI , t2 , S1 , t3 ) ( AADD , A , t3 , t4 ) …… Ek→ tn ( SUBI, tn , Lk, tn+1) ( MULTI , tn+1 , Sk , tn+2 ) ( AADD , ad, tn+2, tn+3 ) 注：ad为保存k-1维地址偏移累加结果的临时变量 Addr ( A [ E1] [E2] …… [Ek] ) = Addr ( A ) + ( E1 - L1 )×S1 + ( E2 – L2 )×S2 + ( E3 – L3 )×S3 …… + ( Ek - Lk )×Sk 注: Li:取自符号表中标识符A的数组类型 内部表示当前维度i的下界项“Low”; Si:取自当前维度i的ElemType类型的 “size”属性。

9 6.2 下标变量的中间代码生成 下标变量的LL(1)动作文法可以写成： (1)V → #Init#id#PUSH(Addr(id))#A
(2)A → [E]#AddNext#B (3)B → (4)B → [E]#AddNext#B 文法定义为： V → id A A → [ E ] B B →  | [ E ] B Init 下标计数器k = 0 AddNext k := k+1； 语义栈E计算结果 -> tn； ( SUBI, tn, Lk, tn+1) ( MULTI , tn+1 , Sk , tn+2 ) 取出语义栈地址累加结果 -> ad ； (AADD , ad , tn+3 , tn+4) 把累加后的地址结果tn+4 -> 语义栈；

10 S1=5; S2=1; 练习题： i,j:integer; a : array[1..10][1..5] of integer ;
写出表达式a [ i +1] [ j*i-2 ]+10的 中间代码 : S1=5; S2=1; (ADDI，i，1，t1) ( SUBI, t1 ,1, t2) ( MULTI , t2 , 5 , t3) ( AADD , a , t3 , t4) (MULI，j，i，t5) (SUBI，t5，2，t6) ( SUBI, t6,1, t7) ( MULTI , t7 , 1 , t8) ( AADD , t4 , t8 , t9) 10. (ADDI, t9,10,t10) Addr ( a [ E1] [E2] …… [En] ) = Addr ( a ) + ( E1 - L1 )×S1 + ( E2 – L2 )×S2 + ( E3 – L3 )×S3 …… + ( En - Ln )×Sn Si = Di+1 ×Si+1 =(Ui+1 -Li+1 +1) × Si+1 Sn = Size ( T )

11 7 赋值语句的中间代码 赋值语句的形式为：Left := Right， 赋值语句的四元式结构为： Left 的中间代码
(FLOAT ,Right , ─,t ) 需要转换时 (ASSIG ,Right或t,- ,Left )

12 赋值语句中间代码生成动作文法如下： S → V:= E #Assig# 执行Assign动作符前，V和表达式E结果语义信息已经压入栈中。 Assig只需要做如下处理： 1.从语义栈中取出赋值号左右分量的语义信息； 2.比较类型是否相同，如果不同，则生成类型转换中间代码； (FLOAT ,Right , ─,t ) 3.生成赋值四元式： (ASSIG , Right 或t, - , Left )

13 8 控制语句的中间代码生成 GOTO语句和标号定位的中间代码 条件语句的中间代码 While语句的中间代码

14 8.1 GOTO语句和标号定位的中间代码 Pascal中： 标号声明格式： LABEL L1， L2，…， Ln 标号定位: Li : S
转向语句: goto Li 标号的处理原则：设立标号表，用于存储声明标号的语义信息。 标号的语义信息:所标识的代码地址,但该地址只有在生成目标代码时才能确定。所以一般会为标号Li定义其内部标号（Li,LLi）,其中LLi表示为其分配的一个存储单元，用来存储它所标识的代码地址。 跳转指令采用间接寻址方式，从对应存储单元LLi中读取该标号定位的地址。 语义动作: (1)分配一个内部标号空间 LLi （ Li， LLi) 填入标号表. (2)( LABEL , — , — , LLi ) ； (3)( JMP , — , — , LLi ) 。

15 对于没有说明语句来定义标号的语言（C语言）
在处理整个程序之前，需要建立一个数组ArrayL来记录当前遇到的所有标号及其语义信息或内部标号，初始时为空。 转向语句: goto Li 标号定位: Li : S ArrayL结构： 标号名Li 定位与否标志 语义信息

16 （1）每当遇到转向语句“goto Li ”，先查一下ArrayL， 如果没有查到该标号： 则产生一条缺欠（需回填）转移地址的中间代码:
定位与否标志 语义信息 （1）每当遇到转向语句“goto Li ”，先查一下ArrayL， 如果没有查到该标号： 则产生一条缺欠（需回填）转移地址的中间代码: ( JMP , — , — , — )， 并把标号Li、该四元式的地址作为Li的语义信息以及表示该标号为未定位的标记，添加到ArrayL 。 若查到标号Li: ①Li是已经定位的了，则从ArrayL中取出它的地址LLi， 然后产生中间代码 ： ( JMP , — , — , LLi ) ； ②Li是未定位的，则从ArrayL中取出它的地址LLi， 然后产生需回填转移地址的中间代码 ： ( JMP , — , — , LLi ) ； 并且将该四元式的地址填入ArrayL（ Li ）的语义信息。 这样可以检测出哪些跳转语句为使用未定义标号。如果不检测错误位置，可以在第一次出现标号Li时直接分配空间LLi。该方法也可用于目标代码。

17 （2）每当遇到标号定位“ Li : …” ，首先给每个 Li分配一个内部标号 LLi，产生中间代码: ( LABEL , — , — , LLi )；然后查ArrayL，如果没有标号Li则把该标号及LLi作为语义信息加入中ArrayL，并且标记为已定位；如果有标号Li并标为未定位，则往对应的所有四元式回填地址。

18 GOTO语句和标号定位中间代码的示例： …. 10 goto L1; 20 goto L1; 30 goto L1; 40 L1：S;
例如有下列程序： …. 10 goto L1; 20 goto L1; 30 goto L1; 40 L1：S; 50 goto L1; ArrayL结构： 标号名 定位与否标志 语义信息 L1 未定位 已定位 m p n LL1 (m) ( JMP , — , — , LL1) (m) ( JMP , — , — , — ) (m) ( JMP , — , — , LL1) ……………………….. (n) ( JMP , — , — , m) (n) ( JMP , — , — , LL1) (n) ( JMP , — , — , LL1) ……………………….. (p) ( JMP , — , — , n) (p) ( JMP , — , — , LL1) (p) ( JMP , — , — , LL1) ……………………….. (q) (LABEL , — , — , LL1) ……………………….. (w) (JMP, — , — , LL1)

19 8.2 条件语句的中间代码 一般来说，条件语句有如下两种形式：
<S> → if <E> then <S1> else <S2> <S> → if <E> then <S1> if E then S1 else S2中间代码结构: E 的中间代码 ( THEN , E.FORM , — , — ) S1 的中间代码 (ELSE , — , — , — ) S2 的中间代码 (ENDIF , — , — , — )

20 if E then S1中间代码结构: E 的中间代码 ( THEN , E.FORM , — , — ) S1 的中间代码 (ENDIF , — , — , — )

21 条件语句生成中间代码的动作文法： <S>→if <E> then #ThenIf# <S> <ElsePart> #EndIf# < ElsePart > → else #ElseIf# <S> < ElsePart > →  ThenIf: ⑴ 类型检查：检查E类型Sem [ top ].type是否为boolean类型 ⑵ 产生中间代码： ( THEN , Sem [ top ].FORM , — , — )； ⑶ E弹栈：pop(1) EndIf:　产生(ENDIF , — , — , — ) ElseIf: 产生(ELSE , — , — , — )

22 8.3 While语句的中间代码 While语句形式为： <S> → while <E> do <S>
( DO , E . FORM , — , — ) S的中间代码 (ENDWHILE , — , — , — )

23 <S> → while #StartWhile# <E> do
#DoWhile# <S> #EndWhile# 其中动作子程序 StartWhile:产生中间代码: (WHILE , — , — , — ) DoWhile: ⑴ 类型检查：检查E类型Sem [ top ].type是否为boolean类型 ⑵ 产生中间代码：( DO , Sem [ top ].FORM , — , — ) ⑶ E弹栈：pop(1) EndWhile:产生中间代码 ： (ENDWHILE , — , — , — )

24 9 过程调用和函数调用的中间代码 过程调用和函数调用的形式 ProcFunCall → id (E1, …… , En)
过程和函数调用的中间代码结构： E1 的中间代码 ….………… En 的中间代码 ( VarACT / ValACT ,t1 ,Offset1 ,Size1) …………. (VarACT / ValACT , tn ,Offsetn ,Sizen) (CALL , <f> ,true/false ,[Result ]) 注：true静态确定转向地址；false:动态确定转向地址； Name Kind TypePtr Level off Parm Class Code Size Forward offx L+1 dir intPtr varKind x offy y 实参表达式的计算 实参的计算 结果传递到 相应的形参 变量 调用过程/函数体执行

25 ( CALL , <f> , true , t2 )
例：假设有实在函数调用 f(X+1,Y),并且 X 是一般整型变量，Y 是变参整型变量，f函数名，同时假定 f 的两个形参第一个是值参、整数类型，第二个是变参、整数类型，则对应的中间代码如下： ( ADDI , X , 1 , t1 ) ( ValACT , t1 , Offset1, 1 ) ( VarACT , Y , Offset1+1 , 1 ) ( CALL , <f> , true , t2 ) 注：其中Offset1和Offset1+1分别示表函数f的第1、2个参数的偏移量。

26 过程 ⁄ 函数调用的中间代码生成动作文法 <ProcFunCall> → id #CallHead#
( <ParamList> ) #CallTail# <ParamList> →  | <ExpList> <ExpList> → E #ActParam# <NextList> <NextList> →  | , <ExpList> 其中 CallHead:当遇到过程 ⁄ 函数名id时，将其符号表地址压入Sem栈，令实参计数器为0 。 ActParam:对每个实参 Ei ：产生它的中间代码，将结果的类型和语义信息压入Sem栈，实参计数器加1 。

27 检查形、实参个数是否一致，检查形、实参类型是否相容；
Sem （ En . type ， En 语义信息 ） ………………… （ E1 . type ， E1 语义信息） ( — , id ) CallTail: 取出id的所有语义信息。 检查形、实参个数是否一致，检查形、实参类型是否相容； 产生送实参信息到形参信息的ValAct/VarAct中间代码； 根据f是实在过程(函数)名或形式过程(函数)名产生相应的CALL代码； 删除当前过程 ⁄ 函数调用语句所占的语义栈单元，如果f是函数，则把返回值的类型和语义信息压入Sem栈。

28 10 过程∕函数声明的中间代码生成 程序的声明部分包括：标号声明、常量声明、类型声明、变量声明和过程 ⁄ 函数声明。只有可变长度类型变量和过程/函数声明可能产生中间代码。 过程∕函数声明的形式可定义为： ProcFunDec → ProcDec | FunDec ProcDec → Procedure id ( ParamList) Declaration ProgramBody FunDec → Function id ( ParamList) : Type 其中ParamList对应参数声明，Declaration对应整个声明部分，ProgramBody对应程序体，而Type对应函数类型定义。

29 Name TypePtr Kind Level off Parm Class Code Size Forward
内部 标号 Size Forward 对应过程∕函数声明的中间代码有: 过程∕函数入口： ( ENTRY , LabelQ , SizeQ , LevelQ ) 过程∕函数出口： ( ENDPROC , — , — , — ) 或 ( ENDFUNC , — , — , — ) 其中: LabelQ 是给过程Q分配的代码入口标号； SizeQ 是过程(函数)Q的活动记录AR空间大小，该空间暂时不包括临时变量部分，此时SizeQ实际是临时变量的初始Offset ，在代码生成阶段处理完临时变量时才可完全确定； LevelQ是过程Q的层数； ENTRY和ENDPROC（或ENDFUNC）分别表示子程序的入口和出口。

30 动作文法为： ProcFunDec → ProcDec | FunDec ProcDec → Procedure id#Entry#(ParamList) ; Declaration ProgramBody #EndProc# FunDec → Function id#Entry#(ParamList) : Type; Declaration ProgramBody#EndFunc# Entry: 给子程序Q分配新标号LabelQ ，并将它填到Q的符号表项中；产生入口中间代码： ( ENTRY ,LabelQ ,SizeQ ,LevelQ ) EndProc和EndFunc: 产生出口中间代码: ( ENDPROC , — , — , — ) 或 ( ENDFUNC , — , — , — )

31 例 过程声明的中间代码 (ADDF, k, k, t0) (ASSIG, t0,-,f) (ENDFUNC,_ ,_ ,_)
(ENTRY, LabelQ, SizeQ, LevelQ) (ENTRY, Labelf, Sizef,Levelf) (ADDF, k, k, t0) (ASSIG, t0,-,f) (ENDFUNC,_ ,_ ,_) (FLOAT, 50,_, t1) (VALACT, t1,offk,2) (CALL, Labelf,true,t2) (ASSIG, t2,-, u) (MULTF, u,x, t3) (ASSIG, t3,2, y) (ENDPROC, _ ,_ ,_) procedure Q( x: real ); var u : real ; function f( k: real ):real; begin f := k +k end; u := f(50); y:= u * x end；

32 P138-3:给出如下程序段的四元式序列(四元式的操作符可用自身代替)。其中:A：Array of [1
P138-3:给出如下程序段的四元式序列(四元式的操作符可用自身代替)。其中:A：Array of [1..10] of integer, a,b:integer。 a:=1; while a<=10 do begin if a<>b then A[a]:=A[b]+2 else a:=a+1; b:=b+1; end (=, 1,-,a) ( WHILE , — , — , — ) (<= ，a,10,t0) ( DO , t0 , — , — ) S的中间代码 (ENDWHILE ,— , — , — ) ( - ,a , 1 , t2 ) (* , t2 , 1 , t3) ([ ], A , t3, t4 ) ( - ,b , 1 , t5 ) (* , t5 , 1 , t6) ([ ], A , t6, t7 ) (+, t7 , 2, t8 ) (=, t8,-,t4) a=1; while (a<=10) { if (a!=b) A[a]=A[b]+2; else a=a+1; b=b+1; }; (<> ，a,b,t1) ( THEN , t1 , — , — ) then中间代码 ( ELSE , — , — , — ) a:=a+1; ( ENDIF , — , — , — ) b:=b+1 (+, a , 1, t9 ) (=, t9,-,a ) (+, b , 1, t10 ) (=, t10,-,b )

33 (=, 1,—,a) ( WHILE , — , — , — ) (<= ，a,10,t0) ( DO , t0 , — , — )
(<> ，a,b,t1) ( THEN , t1 , — , — ) ( - ,a , 1 , t2 ) (* , t2 , 1 , t3) ([], A , t3, t4 ) ( - ,b , 1 , t5 ) (*, t5 , 1 , t6) ([], A , t6, t7 ) (+, t7 , 2, t8 ) a:=1; while a<=10 do begin if a<>b then A[a]:=A[b]+2 else a:=a+1; b:=b+1; end (=, t8,—,t4) ( ELSE , — , — , — ) (+, a , 1, t9 ) (=, t9, —,a ) ( ENDIF , — , — , — ) (+, b , 1, t10 ) (=, t10, —, b ) (ENDWHILE ,— , — , — )