原子语句的中间代码
输入输出语句：
S ?Write(E) E.tuple
(WRITE,E.Arg);
S ? Read(V) V.tuple
（ READ,V.Arg）
语法制导：
S ? Read(V) #READ
S ? Write(E) #WRITE
赋值语句：
赋值语句形式：
V:=E Vptr:=V1ptr f:=E Vstr:=V1str
赋值语句的中间代码形式,(ASSIGN,Arg1,Arg2,n)
或 (FLOAT,Arg1,Arg2)
S ? L:= R L.tuple
R.tuple
(ASSIGN,R,Arg,L.Arg,size)
或 (FLOAT,R.Arg,L.Arg)
语法制导,S ?L:=R #ASSIGN
过函调用语句
S ? id(E1,E2,…, En) E1.tuple
…
En.tuple
(ACT,E1.Arg)
…
(ACT,En.Arg)
(CALL,<f>,result)
或 (CALL,<f>)
传给形参
形参实参结合中间代码,
(VALACT,Ei.Arg,offseti,sizei)…… 值参
(VARACT,Ei.Arg,offseti,sizei)…… 变参
(FUNCACT,Ei.Arg,offseti,sizei)…… 函数参数
(PROACT,Ei.Arg,offseti,sizei)…… 过程参数
过 /函调用代码：
(call,<f>,true,result) 静态转向地址
(call,<f>,false,result) 动态转向地址
GOTO语句和标号语句的中间代码
LABEL L1,L2,...,Ln 空
S?GOTO Li （ JUMP,ARG(Li) )
S?Li:S ( LABEL,ARG(Li) )
S.tuple
结构语句的中间代码
? 条件语句的中间代码
? While语句的中间代码
? Repeat语句的中间代码
? For语句的中间代码
? Case语句的中间代码
条件语句的中间代码
IF E THEN S1 ELSE S2
E.Tuple
(JUMP0,E.Arg,S.ElseL)
S1.Tuple
(JUMP,S.OutL)
(LABEL,S.ElseL)
S2.Tuple
(LABEL,S.OutL)
IF E THEN S
E.Tuple
(JUMP0,E.Arg,S.OutL)
S1.Tuple
(LABEL,S.OutL)
条件语句代码生成原理
? 在 if处,
产生标号 S.ElseL和 S.OutL;
? 在 then处,
产生中间代码 (JUMP0,E.Arg,S.ElseL) ；
? 在 else处,
产生中间代码 (JUMP,S.OutL)
( LABEL,S.ElseL)
? 在 S出口处, (LABEL,S.OutL ).
条件语句代码生成的 LL文法
S → if #StartIF E then #TestIF S1 ElsePart
ElsePart → else #GenJump #GenElseL S2 #GenOutL
ElsePart → ? #GenElseL
#StartIF,生成两个标号 S.ElseL,S.OutL
#TestIF, Generate(JUMP0,E.Arg,S.ElseL )
#GenJump, Generate(JUMP,ElsePart.OutL )
#GenElseL, Generate(LABEL,ElsePart.ElseL)
#GenOutL, Generate(LABEL,ElsePart.OutL )
While语句的中间代码
S ? WHILE E DO S1
E.Tuple
(JUMP0,E.Arg,S.OutL)
S1.Tuple
(JUMP,S.StartL)
(LABEL,S.OutL)
(LABEL,S.StartL)
While语句代码生成原理
? 当遇 While时：
产生新标号 S.StartL和 S.OutL，
产生代码 (LABEL,S.StartL)
? 当遇 Do时：
产生代码 (JUMP0,E.Arg,S.OutL )
? 当遇 结束符 时：
产生代码 (JUMP,S.StartL)
(LABEL,S.OutL )
While语句代码生成的 LL文法
S → while #StartWhile E do #WhileTest
S1 #FinishWhile
#StartWhile,产生新标号 S.StartL,S.OutL
# WhileTest,Generate(JUMP0,E.Arg,S.OutL)
# FinishWhile,Generate(JUMP,S.StartL)
Generate(LABEL,S.OutL)
Repeat语句的中间代码
S ? repeat SL until E
SL.Tuple
(JUMP0,E.Arg,S.StartL)
E.Tuple
(LABEL,S.StartL)
代码生成原理和 LL动作文法
? 循环入口处,(LABEL,S.StartL)
? 循环出口处,(JUMP0,E.Arg,S.StartL)
S → repeat #StartRepeat SL do E #FinishRepeat
#StartRepeat,生成 S.StartL
Generate(LABEL,S.StartL )
#FinishRepeat,Generate(JUMP0,E.Arg,S.StartL)
For语句的中间代码
for V:=E1 to E2 do S
E1.Tuple
E2.Tuple
(GT,E1.Arg,E2.Arg,t1)
(JUMP1,t1,S.OutL)
(ASSIG,E1.Arg,V.Arg)
S1.Tuple
(NE,V.Arg,E2.Arg,t3)
(ADDI,V.Arg,1,t2)
(ASSIG,t2,V.Arg)
(JUMP1,t3,S.LoopL)
(LABEL,S.OutL)
(LABEL,S.LoopL)
for V:=E1 downto E2 do S
E1.Tuple
E2.Tuple
(LT,E1.Arg,E2.Arg,t1)
(JUMP1,t1,S.OutL)
(ASSIG,E1.Arg,V.Arg)
S1.Tuple
(NE,V.Arg,E2.Arg,t3)
(SUBI,V.Arg,1,t2)
(ASSIG,t2,V.Arg)
(JUMP1,t3,S.LoopL)
(LABEL,S.OutL)
(LABEL,S.LoopL)
For语句代码生成原理
? 当遇到 For时：
产生新标号 S.LoopL和 S.OutL
? 当遇到 To或 downto时,记住循环种类；
? 当遇到 do时：
产生是否进入循环体的条件转移代码；
? 当循环体结束时：
根据循环种类产生循环变量加 /减 1的代码；
产生判断循环是否结束的代码。
For语句的 LL动作文法
S → for #StartFOR V:=E FORKIND E do #ForDO
S #FinishFOR
FORKIND → to #ToKind
FORKIND → downto #DownKind
StarFOR,产生新标号 S.LoopL和 S.OutL;
ToKind/DownKind,标记循环种类；
ForDO,Generate(GT/LT,E1.Arg,E2.Arg,t1)
Generate(JUMP1,t1,S.OutL)
Generate(ASSIG,E1.Arg,V.Arg)
FinishFOR:
Case语句的中间代码
E.tuple
(JUMP,Search)
C1:S1的中间代码
(JUMP,OutL）
.,.....
Cn:Sn 的中间代码
(JUMP,OutL)
Search:
OutL:
case E of C1:S1;… ;Cn:Sn;Other:S* end
■ E.tuple
■ ( JUMP,Search )
■ L1,S1的中间代码 ； (JUMP,OutL)
...................................................
■ Ln,Sn的中间代码 ； (JUMP,OutL)
■ OtherL,S*的中间代码 ； (JUMP,OutL)
■ Table,( C1,L1 )(C2,L2)....(Cn,Ln)(_,OtherL)
■ Search, { 用 E.Arg查 Table表并转向相应 Sj }
■ OutL:
搜索表模式下 CASE语句的中间代码结构
使用转向表实现 CASE语句的中间代码生成
思想：构造一个转向表，表的大小为 MaxC-MinC+1,每
个表项记录对应 case常量的转向地址。
计算 case表达式的值，与 MinC,MaxC比较，如
在 [MinC,MaxC]范围之外，则转向 OtherL分支；否则用
特殊的转向指令 (JUMPX,E.Arg,Table,MinC),这条指令
的含义是沿着转向表移动,E.Arg-MinC”长的距离，实
际上就是找到对应的转向地址。
关键,MinC,MaxC的值的确定。
(JUMP,LL1)
(JUMP,LL2)
……
(JUMP,LLn)
Table
■ E的中间代码 ; ( JUMP,OptionL )
■ L1, S1的的中间代码 ； (JUMP,OutL)
..................................................
■ Ln, Sn的的中间代码 ； (JUMP,OutL)
■ OtherL,S* 的的中间代码 ； (JUMP,OutL)
■ Table,( JUMP,LL1 )
..........
( JUMP,LLn )
■ OptionL:
( LT,E.Arg,MinC,t1 ) ( JUMP1,t1,OtherL )
( GT,E.Arg,MaxC,t2) ( JUMP1,t2,OtherL )
( JUMPX,E.Arg,Table,MinC )
■ OutL,
转向表模式下的 CASE语句的中间代码结构
结构语句代码生成的例子
While x>0 do while y>0 do begin y:=y-x;x:=x-1 end
(LABEL,S.StartL0)
(GT,x,0,t1)
(JUMP0,t1,S.OutL0)
(LABEL,S.LoopL0)
(LABEL,S.StartL1)
(GT,y,0,t2)
(JUMP0,t2,S.OutL1)
(LABEL,S.LoopL1)
(SUBI,y,x,t3)
(ASSIGN,t3,y)
(SUBI,x,1,t4)
(ASSIGN,t4,x)
(JUMP,S.StartL1)
(LABEL,S.OutL1)
(JUMP,S.StartL0)
(LABEL,S.OutL0)
声明的中间代码
? 变量声明的中间代码
? 过 /函声明的中间代码
过 /函声明的中间代码
形式：
Procedure P(FormDecList)
LabelDec
ConstDec
TypeDec
VarDec
ProDec1
……
ProDecn
Body
中间代码结构：
( Entry,Label,Size,Level)
ProDec1.Tuple
……
ProDecn.Tuple
Body.Tuple
( EndProc/EndFunc,-,-,-)
过程声明的例子
procedure Q( x,real );
var u, real ;
function f( k,real );
begin f,= k +k end;
begin u,= f(50); y:= u * x end； ( y是
实型非局部变量 )
生成的中间代码
( ENTRY,Labelf,Sizef,Levelf )
( ADDF,k,k,t0)
( ASSIG,t0,f )
( ENDFUNC,.............,)
( ENTRY,LabelQ,SizeQ,LevelQ)
( VALACT,50,0,1)
( CALL,Labelf,t1)
( ASSIG,t1,u )
( MULTF,u,x,t2 )
( ASSIG,t2,y )
( ENDPROC,..,)
输入输出语句：
S ?Write(E) E.tuple
(WRITE,E.Arg);
S ? Read(V) V.tuple
（ READ,V.Arg）
语法制导：
S ? Read(V) #READ
S ? Write(E) #WRITE
赋值语句：
赋值语句形式：
V:=E Vptr:=V1ptr f:=E Vstr:=V1str
赋值语句的中间代码形式,(ASSIGN,Arg1,Arg2,n)
或 (FLOAT,Arg1,Arg2)
S ? L:= R L.tuple
R.tuple
(ASSIGN,R,Arg,L.Arg,size)
或 (FLOAT,R.Arg,L.Arg)
语法制导,S ?L:=R #ASSIGN
过函调用语句
S ? id(E1,E2,…, En) E1.tuple
…
En.tuple
(ACT,E1.Arg)
…
(ACT,En.Arg)
(CALL,<f>,result)
或 (CALL,<f>)
传给形参
形参实参结合中间代码,
(VALACT,Ei.Arg,offseti,sizei)…… 值参
(VARACT,Ei.Arg,offseti,sizei)…… 变参
(FUNCACT,Ei.Arg,offseti,sizei)…… 函数参数
(PROACT,Ei.Arg,offseti,sizei)…… 过程参数
过 /函调用代码：
(call,<f>,true,result) 静态转向地址
(call,<f>,false,result) 动态转向地址
GOTO语句和标号语句的中间代码
LABEL L1,L2,...,Ln 空
S?GOTO Li （ JUMP,ARG(Li) )
S?Li:S ( LABEL,ARG(Li) )
S.tuple
结构语句的中间代码
? 条件语句的中间代码
? While语句的中间代码
? Repeat语句的中间代码
? For语句的中间代码
? Case语句的中间代码
条件语句的中间代码
IF E THEN S1 ELSE S2
E.Tuple
(JUMP0,E.Arg,S.ElseL)
S1.Tuple
(JUMP,S.OutL)
(LABEL,S.ElseL)
S2.Tuple
(LABEL,S.OutL)
IF E THEN S
E.Tuple
(JUMP0,E.Arg,S.OutL)
S1.Tuple
(LABEL,S.OutL)
条件语句代码生成原理
? 在 if处,
产生标号 S.ElseL和 S.OutL;
? 在 then处,
产生中间代码 (JUMP0,E.Arg,S.ElseL) ；
? 在 else处,
产生中间代码 (JUMP,S.OutL)
( LABEL,S.ElseL)
? 在 S出口处, (LABEL,S.OutL ).
条件语句代码生成的 LL文法
S → if #StartIF E then #TestIF S1 ElsePart
ElsePart → else #GenJump #GenElseL S2 #GenOutL
ElsePart → ? #GenElseL
#StartIF,生成两个标号 S.ElseL,S.OutL
#TestIF, Generate(JUMP0,E.Arg,S.ElseL )
#GenJump, Generate(JUMP,ElsePart.OutL )
#GenElseL, Generate(LABEL,ElsePart.ElseL)
#GenOutL, Generate(LABEL,ElsePart.OutL )
While语句的中间代码
S ? WHILE E DO S1
E.Tuple
(JUMP0,E.Arg,S.OutL)
S1.Tuple
(JUMP,S.StartL)
(LABEL,S.OutL)
(LABEL,S.StartL)
While语句代码生成原理
? 当遇 While时：
产生新标号 S.StartL和 S.OutL，
产生代码 (LABEL,S.StartL)
? 当遇 Do时：
产生代码 (JUMP0,E.Arg,S.OutL )
? 当遇 结束符 时：
产生代码 (JUMP,S.StartL)
(LABEL,S.OutL )
While语句代码生成的 LL文法
S → while #StartWhile E do #WhileTest
S1 #FinishWhile
#StartWhile,产生新标号 S.StartL,S.OutL
# WhileTest,Generate(JUMP0,E.Arg,S.OutL)
# FinishWhile,Generate(JUMP,S.StartL)
Generate(LABEL,S.OutL)
Repeat语句的中间代码
S ? repeat SL until E
SL.Tuple
(JUMP0,E.Arg,S.StartL)
E.Tuple
(LABEL,S.StartL)
代码生成原理和 LL动作文法
? 循环入口处,(LABEL,S.StartL)
? 循环出口处,(JUMP0,E.Arg,S.StartL)
S → repeat #StartRepeat SL do E #FinishRepeat
#StartRepeat,生成 S.StartL
Generate(LABEL,S.StartL )
#FinishRepeat,Generate(JUMP0,E.Arg,S.StartL)
For语句的中间代码
for V:=E1 to E2 do S
E1.Tuple
E2.Tuple
(GT,E1.Arg,E2.Arg,t1)
(JUMP1,t1,S.OutL)
(ASSIG,E1.Arg,V.Arg)
S1.Tuple
(NE,V.Arg,E2.Arg,t3)
(ADDI,V.Arg,1,t2)
(ASSIG,t2,V.Arg)
(JUMP1,t3,S.LoopL)
(LABEL,S.OutL)
(LABEL,S.LoopL)
for V:=E1 downto E2 do S
E1.Tuple
E2.Tuple
(LT,E1.Arg,E2.Arg,t1)
(JUMP1,t1,S.OutL)
(ASSIG,E1.Arg,V.Arg)
S1.Tuple
(NE,V.Arg,E2.Arg,t3)
(SUBI,V.Arg,1,t2)
(ASSIG,t2,V.Arg)
(JUMP1,t3,S.LoopL)
(LABEL,S.OutL)
(LABEL,S.LoopL)
For语句代码生成原理
? 当遇到 For时：
产生新标号 S.LoopL和 S.OutL
? 当遇到 To或 downto时,记住循环种类；
? 当遇到 do时：
产生是否进入循环体的条件转移代码；
? 当循环体结束时：
根据循环种类产生循环变量加 /减 1的代码；
产生判断循环是否结束的代码。
For语句的 LL动作文法
S → for #StartFOR V:=E FORKIND E do #ForDO
S #FinishFOR
FORKIND → to #ToKind
FORKIND → downto #DownKind
StarFOR,产生新标号 S.LoopL和 S.OutL;
ToKind/DownKind,标记循环种类；
ForDO,Generate(GT/LT,E1.Arg,E2.Arg,t1)
Generate(JUMP1,t1,S.OutL)
Generate(ASSIG,E1.Arg,V.Arg)
FinishFOR:
Case语句的中间代码
E.tuple
(JUMP,Search)
C1:S1的中间代码
(JUMP,OutL）
.,.....
Cn:Sn 的中间代码
(JUMP,OutL)
Search:
OutL:
case E of C1:S1;… ;Cn:Sn;Other:S* end
■ E.tuple
■ ( JUMP,Search )
■ L1,S1的中间代码 ； (JUMP,OutL)
...................................................
■ Ln,Sn的中间代码 ； (JUMP,OutL)
■ OtherL,S*的中间代码 ； (JUMP,OutL)
■ Table,( C1,L1 )(C2,L2)....(Cn,Ln)(_,OtherL)
■ Search, { 用 E.Arg查 Table表并转向相应 Sj }
■ OutL:
搜索表模式下 CASE语句的中间代码结构
使用转向表实现 CASE语句的中间代码生成
思想：构造一个转向表，表的大小为 MaxC-MinC+1,每
个表项记录对应 case常量的转向地址。
计算 case表达式的值，与 MinC,MaxC比较，如
在 [MinC,MaxC]范围之外，则转向 OtherL分支；否则用
特殊的转向指令 (JUMPX,E.Arg,Table,MinC),这条指令
的含义是沿着转向表移动,E.Arg-MinC”长的距离，实
际上就是找到对应的转向地址。
关键,MinC,MaxC的值的确定。
(JUMP,LL1)
(JUMP,LL2)
……
(JUMP,LLn)
Table
■ E的中间代码 ; ( JUMP,OptionL )
■ L1, S1的的中间代码 ； (JUMP,OutL)
..................................................
■ Ln, Sn的的中间代码 ； (JUMP,OutL)
■ OtherL,S* 的的中间代码 ； (JUMP,OutL)
■ Table,( JUMP,LL1 )
..........
( JUMP,LLn )
■ OptionL:
( LT,E.Arg,MinC,t1 ) ( JUMP1,t1,OtherL )
( GT,E.Arg,MaxC,t2) ( JUMP1,t2,OtherL )
( JUMPX,E.Arg,Table,MinC )
■ OutL,
转向表模式下的 CASE语句的中间代码结构
结构语句代码生成的例子
While x>0 do while y>0 do begin y:=y-x;x:=x-1 end
(LABEL,S.StartL0)
(GT,x,0,t1)
(JUMP0,t1,S.OutL0)
(LABEL,S.LoopL0)
(LABEL,S.StartL1)
(GT,y,0,t2)
(JUMP0,t2,S.OutL1)
(LABEL,S.LoopL1)
(SUBI,y,x,t3)
(ASSIGN,t3,y)
(SUBI,x,1,t4)
(ASSIGN,t4,x)
(JUMP,S.StartL1)
(LABEL,S.OutL1)
(JUMP,S.StartL0)
(LABEL,S.OutL0)
声明的中间代码
? 变量声明的中间代码
? 过 /函声明的中间代码
过 /函声明的中间代码
形式：
Procedure P(FormDecList)
LabelDec
ConstDec
TypeDec
VarDec
ProDec1
……
ProDecn
Body
中间代码结构：
( Entry,Label,Size,Level)
ProDec1.Tuple
……
ProDecn.Tuple
Body.Tuple
( EndProc/EndFunc,-,-,-)
过程声明的例子
procedure Q( x,real );
var u, real ;
function f( k,real );
begin f,= k +k end;
begin u,= f(50); y:= u * x end； ( y是
实型非局部变量 )
生成的中间代码
( ENTRY,Labelf,Sizef,Levelf )
( ADDF,k,k,t0)
( ASSIG,t0,f )
( ENDFUNC,.............,)
( ENTRY,LabelQ,SizeQ,LevelQ)
( VALACT,50,0,1)
( CALL,Labelf,t1)
( ASSIG,t1,u )
( MULTF,u,x,t2 )
( ASSIG,t2,y )
( ENDPROC,..,)
