ct1317(更新).ppt

第七章第七章 中间代码生成中间代码生成 中间语言中间语言 语法制导方法语法制导方法 简单表达式的中间代码生成简单表达式的中间代码生成 原子语句的中间代码生成原子语句的中间代码生成 结构语句的中间代码生成结构语句的中间代码生成 声明的中间代码声明的中间代码7.17.1中间语言中间语言后缀式后缀式-逆波兰式逆波兰式特别是表达式的内部表示特别是表达式的内部表示图结构中间代码图结构中间代码抽象语法树抽象语法树有向不循环图有向不循环图三地址中间代码三地址中间代码三元式三元式四元式四元式7.1.17.1.1后缀表达式相关后缀表达式相关中缀变后缀算法中缀变后缀算法1.初始化一个空堆栈，将结果字符串变量置空。2.从左到右读入中缀表达式，每次一个字符。3.如果字符是操作数，将它添加到结果字符串。4.如果字符是个操作符，弹出操作符，直至遇见开括号、优先级较低的操作符或者同一优先级的右结合符号。把这个操作符压入栈。5.如果字符是个开括号，把它压入堆栈。6.如果字符是个闭括号，在遇见开括号前，弹出所有操作符，然后把它们添加到结果字符串。7.如果到达输入字符串的末尾，弹出所有操作符并添加到结果字符串。后缀计算算法后缀计算算法7.1.27.1.2抽象语法树抽象语法树AGTAGT和和有向不循环图有向不循环图DAGDAG抽象语法树抽象语法树表达式的表达式的AGTAGT中间节点：运算符中间节点：运算符叶节点：操作数叶节点：操作数推广到程序推广到程序有向不循环图有向不循环图共享子树共享子树7.1.37.1.3三地址中间代码三地址中间代码 三元式：三元式：i:(i:(,op1,op2),op1,op2)四元式四元式：（,op1,op2,op1,op2，result)result)如：如：a:=a:=b bc+bc+bd d 三元式三元式 四元式四元式(1)(,b,c)(1)(,b,c,t1)(2)(,b,d)(2)(,b,d,t2)(3)(+,(1),(2)(3)(+,t1,t2,t3)(4)(:=,(3),a)(4)(:=,t3,a,)四元式操作符分类四元式操作符分类算术、逻辑、关系运算符算术、逻辑、关系运算符IOIO操作操作类型转换类型转换赋值赋值(ASSIG,id1,n,id2)(ASSIG,id1,n,id2)地址加地址加(AADD,id1,id2,id3)(AADD,id1,id2,id3)标号标号(LABEL,-,-,label)(LABEL,-,-,label)转移转移过程调用过程调用传送参数传送参数7.27.2语法制导方法语法制导方法语法制导方法语法制导方法 基于文法结构，在每个产生式的右部基于文法结构，在每个产生式的右部增加增加语义动作语义动作，在语法分析过程中，如遇语义，在语法分析过程中，如遇语义动作，就完成对应的语义处理。动作，就完成对应的语义处理。属性文法属性文法属性直接与文法的符号相联系属性直接与文法的符号相联系若若X X为一文法符号，为一文法符号，a a为为X X的一个属性，用的一个属性，用X.aX.a表示与表示与X X关联的关联的a a的值的值对于每个文法规则对于每个文法规则X X0 0-X-X1 1X Xn n,X,Xi i的属性的属性X Xi i.a.aj j与规则的其他符号的属性与规则的其他符号的属性a a1 1,a ak k有关有关X Xi i.a.aj j =f=fijij(X(X0 0.a.a1 1,X Xn n.a.ak k)动作文法动作文法文法规则与语义函数相联系文法规则与语义函数相联系每个产生式的右部附着相应的语义动作每个产生式的右部附着相应的语义动作每个动作对应一个函数每个动作对应一个函数动作文法的定义由动作文法的定义由语法分析的实现方式语法分析的实现方式决决定定实例实例VT=0,1,aVN=Z,LS=ZP:Z L L 0 L L 1 L L a VT=0,1,aVN=Z,D,LS=ZP:Z L L DL D 1 D 0 L ainit()sum0=0;sum1=0;add1()sum1+;print()printf(sum0,sum1);add0()sum0+;类型检查和类型转换类型检查和类型转换各种条件表达式的类型是否是布尔类型？各种条件表达式的类型是否是布尔类型？运算符的运算分量是否相容？运算符的运算分量是否相容？赋值语句的左、右部类型是否相容？赋值语句的左、右部类型是否相容？实参与形参的类型是否相容？实参与形参的类型是否相容？下标表达式的类型是否为所允许的类型？下标表达式的类型是否为所允许的类型？函数说明中的函数类型与返回值的类型是函数说明中的函数类型与返回值的类型是否一致？否一致？中间代码生成中的几个问题中间代码生成中的几个问题语义信息的获取与保存语义信息的获取与保存标识符的语义信息标识符的语义信息类型检查、转换类型检查、转换目标代码生成保留相关运算分量和结果的语义目标代码生成保留相关运算分量和结果的语义信息信息地址表示地址表示语义栈及其操作语义栈及其操作用途：变量和表达式的处理时存放运算分量和用途：变量和表达式的处理时存放运算分量和结果的类型和语言信息结果的类型和语言信息(层数、偏移、访问方式层数、偏移、访问方式等，用一个记录等，用一个记录FORMFORM表示表示)toptop、push(xpush(x)、pop(npop(n)常用的语义子程序常用的语义子程序申请存储单元申请存储单元New_dir(tNew_dir(t)New_indir(tNew_indir(t)存放中间代码存放中间代码GenerateGenerate（,op1,op2,op1,op2，resultresult）生成中间代码生成中间代码GenCodeGenCode（）类型转换？类型转换？生成中间代码生成中间代码清理语义栈清理语义栈7.37.3简单表达式的中间代码生成简单表达式的中间代码生成E E T E T Es s/Es是一个符号是一个符号E Es s +T +T$GenCodeGenCode(+)(+)E Es s E Es s T T PTPTs sT Ts s *P *P$GenCodeGenCode()()T Ts sT Ts s P P id id$Push(idPush(id)P P C C$Push(CPush(C)/C/C表示常量表示常量P P(E)(E)7.47.4下标变量中间代码生成下标变量中间代码生成(1)V$Init id$PUSH(Addr(id)A(2)A E$AddNext B(3)B (4)B E$AddNext B$Init：用来初始化下标计数器：用来初始化下标计数器 n=0；$Push：把把id首地址压入栈中；首地址压入栈中；$AddNext：1)下标计数器加下标计数器加1，即，即 n:=n+1；2)从语义栈中取出下标表达式计算结果从语义栈中取出下标表达式计算结果r；3)生成计算第生成计算第n维下标需要累加的地址偏移的四元式组：维下标需要累加的地址偏移的四元式组：(SUBI,r,Ln,tn+1)(MULTI,tn+1,Sk,tn+2)(MULT,tn+2,ele_size,tn+3)4)从语义栈中取出地址累加结果从语义栈中取出地址累加结果ad；5)生成地址累加四元式生成地址累加四元式(ADDI,ad,tn+3,tn+4)6)把累加后的地址结果把累加后的地址结果tn+4压入语义栈；压入语义栈；中间代码生成实例中间代码生成实例intint i,mi,m;float z;float z;structstruct rtrt intint y;float x;y;float x;rtrt a100;a100;a5+i.x+m*za5+i.x+m*z 1.1.(ADDI,5,i,t1)(ADDI,5,i,t1)2.2.(SUBI,t1,0,t2)(SUBI,t1,0,t2)3.3.(MULTI,t2,6,t3)(MULTI,t2,6,t3)4.4.(AADD,a,t3,t4)(AADD,a,t3,t4)5.5.(AADD,t4,2,t5)(AADD,t4,2,t5)6.(6.(FLOAT,m,t6)FLOAT,m,t6)7.(MULTF,t6,z,t7)7.(MULTF,t6,z,t7)8.(ADDF,t5,t7,t8)8.(ADDF,t5,t7,t8)赋值语句的形式为赋值语句的形式为：Left:=Right 赋值语句的四元式结构赋值语句的四元式结构：Left 的中间代码的中间代码 Right 的中间代码的中间代码(FLOAT,right,t)(ASSIG,Right（即（即t）,n,Left)语法制导：语法制导：S S L:=RL:=R$ASSIGN$ASSIGN$ASSIGN$ASSIGN：从语义栈中取出赋值号左右分量的语义信息；从语义栈中取出赋值号左右分量的语义信息；比较类型是否相同，如果不同，则生成类型转换中比较类型是否相同，如果不同，则生成类型转换中间代码；间代码；生成赋值四元式生成赋值四元式(ASSIG,Right（t）,n,Left)。赋值语句中间代码赋值语句中间代码过函调用的中间代码过函调用的中间代码 f(E f(E1 1，E E2 2，E En n):E):E1 1.tuple.tuple E En n.tuple.tuple(ACT,E(ACT,E1 1.Arg).Arg)(ACT,EACT,En n.Arg.Arg)(CALL,(CALL,，result)result)或或(CALL,CALL,，)传给形参传给形参形参实参结合中间代码形参实参结合中间代码:(VALACTVALACT,E Ei i.Arg.Arg,offsetoffseti i,sizesizei i)值参值参(VARACTVARACT,E Ei i.Arg.Arg,offsetoffseti i,sizesizei i)变参变参(FUNCACTFUNCACT,E Ei i.Arg.Arg,offsetoffseti i,sizesizei i)函数参数函数参数(PROACTPROACT,E Ei i.Arg.Arg,offsetoffseti i,sizesizei i)过程参数过程参数过过/函调用代码：函调用代码：(call,call,truetrue,result),result)静态转向地址静态转向地址(call,call,falsefalse,result),result)动态转向地址动态转向地址例：例：x+f(H(10),x+f(H(10),g(Yg(Y)其中其中x x是整型变量，是整型变量，H H为返回值为整型的形式函数名，为返回值为整型的形式函数名，H H的形参为整型值参，的形参为整型值参，f f、g g为实在函数名，为实在函数名，f f的参数的参数均为整型值参，均为整型值参，g g的参数为字符型变参。约定整型的参数为字符型变参。约定整型和指针型（变参）存储占和指针型（变参）存储占2 2字节，字符型占字节，字符型占1 1字节，字节，布尔型占布尔型占1 1字节，实型占字节，实型占4 4字节。字节。（VALACT,10,VALACT,10,0,20,2）(CALL,H,false,t1)(CALL,H,false,t1)(VARACT,Y,(VARACT,Y,0,20,2)(CALL,g,true,t2)(CALL,g,true,t2)(VALACT,t1,(VALACT,t1,0,2 0,2)(VALACT,t2,(VALACT,t2,2,2 2,2)(CALL,f,true,t3)(CALL,f,true,t3)(ADDI,x,t3,t4)(ADDI,x,t3,t4)过过/函调用中间代码的生成函调用中间代码的生成遇到过遇到过/函名：函名：在符号表中的地址压栈，实参计数器为在符号表中的地址压栈，实参计数器为0 0；遇到实参遇到实参EiEi：产生计算表达式产生计算表达式EiEi的中间代码，实参的语义信息压栈，的中间代码，实参的语义信息压栈，计数器加计数器加1 1。实参结束：实参结束：根据过根据过/函的语义信息，检查形参与实参个数一致？类型函的语义信息，检查形参与实参个数一致？类型相容？种类符合？过相容？种类符合？过/函？函？产生参数传送的中间代码；产生参数传送的中间代码；产生调用的中间代码；产生调用的中间代码；删除语义栈中过删除语义栈中过/函名及实参的内容，如果是函数将返回函名及实参的内容，如果是函数将返回值的语义信息压入栈中。值的语义信息压入栈中。CallHeadCallHeadActParamActParamCallTailCallTail过过/函调用的语法制导函调用的语法制导ProcFunCallProcFunCall id id$CallHeadCallHead (ParamListParamList)$CallTailCallTailParamListParamList|ExpListExpListExpListExpList E E$ActParamActParam NextListNextListNextListNextList|,|,ExpListExpList LABEL LLABEL L1 1,L,L2 2,.,.,L Ln n 空空S SGOTO LGOTO Li i （JUMP,-,-,JUMP,-,-,ARG(LARG(Li i)S SL Li i:S:S (LABEL,-,-,(LABEL,-,-,ARG(LARG(Li i)S.tupleS.tupleGOTOGOTO语句和标号语句的中间代码语句和标号语句的中间代码条件语句的中间代码条件语句的中间代码条件语句的文法条件语句的文法：SifSif E then S E then S ElsePartElsePart ElsePartelseElsePartelse S|S|条件语句的中间代码形式条件语句的中间代码形式if E then Sif E then S1 1 else S else S2 2 if E then Sif E then S E的中间代码(THEN,E.FORM,_)S1的中间代码(ELSE,_,_,_)S2的中间代码(ENDIF,_,_,_)E的中间代码(THEN,E.FORM,_)S的中间代码(ENDIF,_,_,_)条件语句中间代码的条件语句中间代码的语法制导生成方法语法制导生成方法S if E then S if E then$ThenIfThenIf S S ElsePartElsePart$EndIfEndIfElsePartElsePart else else$ElseIfElseIf S SElsePartElsePart$ThenIfThenIf检查检查SemtopSemtop 的值的类型是否为的值的类型是否为booleanboolean类型，如类型，如果是则产生中间代码果是则产生中间代码(THEN,SemtopTHEN,Semtop,_,_),_,_)。$ElseIfElseIf产生中间代码产生中间代码 (ELSE,_,_,_)(ELSE,_,_,_)$EndIfEndIf产生中间代码产生中间代码 (ENDIF,_,_,_)(ENDIF,_,_,_)条件语句的中间代码条件语句的中间代码2 2IF E THEN S1 ELSE S2E.Tuple(JUMP0,E.Arg,-,S.ElseL)S1.Tuple(JUMP,-,-,S.OutL)(LABEL,-,-,S.ElseL)S2.Tuple(LABEL,-,-,S.OutL)S IF E THEN S1E.Tuple(JUMP0,E.Arg,-,S.OutL)S1.Tuple(LABEL,-,-,S.OutL)条件语句代码生成条件语句代码生成2(LL2(LL文法文法)SSifif#StartIF#StartIF E E thenthen#TestIF#TestIF S S1 1 ElsePart ElsePart#EndIF#EndIFElsePart ElsePart elseelse#GenJump#GenJump#GenElseL#GenElseL S S2 2#GenOutL#GenOutLElsePart ElsePart#GenOutL#GenOutL#StartIF#StartIF:PUSH(S.ElseL);PUSH(S.OutL);:PUSH(S.ElseL);PUSH(S.OutL);#TestIF#TestIF:Generate(JUMP0,Semtop.Arg,Semtop-2);POP(1)Generate(JUMP0,Semtop.Arg,Semtop-2);POP(1)#GenJump#GenJump:Generate(JUMP,Semtop.Arg):Generate(JUMP,Semtop.Arg)#GenElseL#GenElseL:Generate(LABEL,Semtop-1.Arg):Generate(LABEL,Semtop-1.Arg)#GenOutL#GenOutL:Generate(LABEL,Semtop.Arg):Generate(LABEL,Semtop.Arg)#EndIF#EndIF:POP(2):POP(2)WhileWhile语句的中间代码语句的中间代码whilewhile语句的文法：语句的文法：S while E do SS while E do S whilewhile语句的中间代码形式语句的中间代码形式(WHILE,_,_,_)E的中间代码的中间代码(DO,E.FORM,_,_)S的中间代码的中间代码(ENDWHILE,_,_,_)whilewhile语句的中间代码的语句的中间代码的语法制导生成方法语法制导生成方法SwhileSwhile$StartWhile$StartWhileE E do do$DoWhileDoWhileS S$EndWhile$EndWhile$StartWhileStartWhile产生中间代码产生中间代码 (WHILE,_,_,_)(WHILE,_,_,_)$DoWhileDoWhile遇遇dodo时（表达式时（表达式E E已经处理完，值在已经处理完，值在SemtopSemtop 中）：中）：1.1.类型检查：检查类型检查：检查E E是否为是否为booleanboolean类型；类型；2.2.产生中间代码产生中间代码 (DO,E.FORM,_,_)(DO,E.FORM,_,_)；3.3.E E弹栈：弹栈：pop(1)pop(1)；$EndWhileEndWhile产生中间代码产生中间代码 (ENDWHILE,_,_,_)(ENDWHILE,_,_,_)过程过程/函数声明的中间代码函数声明的中间代码过程过程/函数的文法定义：函数的文法定义：ProcFunDecProcDecProcFunDecProcDec|FunDecFunDecProcDecProcedureProcDecProcedure id(id(ParamListParamList)Declaration Declaration ProgramBodyProgramBodyFunDecFunctionFunDecFunction id(id(ParamList):TypeParamList):Type Declaration Declaration ProgramBodyProgramBody 过过/函声明的中间代码形式函声明的中间代码形式形式：形式：Procedure Procedure P(FormDecListP(FormDecList)LabelDecLabelDec ConstDecConstDec TypeDecTypeDec VarDecVarDec ProDec ProDec1 1 ProDecProDecn n Body Body中间代码结构：中间代码结构：(Entry,Label,Size,LevelEntry,Label,Size,Level)ProDec ProDec1 1.tuple.tuple ProDecProDecn n.tuple.tuple Body.TupleBody.Tuple(EndProc/EndFuncEndProc/EndFunc,-,-,-),-,-,-)函数声明中间代码生成实例函数声明中间代码生成实例procedure Q(x:real);procedure Q(x:real);varvar u:real;u:real;function function f(k:real):realf(k:real):real;begin begin f:=k+k f:=k+k end;end;beginbegin u:=f(50);u:=f(50);y:=u*x y:=u*x endend；(EntryEntryQ Q,Label,LabelQ Q,Size,SizeQ Q,L,LQ Q)(EntryEntryf f,Label,Labelf f,Size,Sizef f,L,Lf f)(ADDF,k,k,t0)(ADDF,k,k,t0)(ASSIG,t0,f)(ASSIG,t0,f)(ENDFUNC,(ENDFUNC,)(VALACT,50,(VALACT,50,1 1,1),1)(CALL,Label(CALL,Labelf f,true,t1),true,t1)(ASSIG,t1,u)(ASSIG,t1,u)(MULTF,(MULTF,u,xu,x,t2),t2)(ASSIG,t2,y)(ASSIG,t2,y)(ENDPROC,(ENDPROC,)函数声明的中间代码的函数声明的中间代码的语法制导生成方法语法制导生成方法ProcFunDecProcFunDec ProcDecProcDec|FunDecFunDecProcDecProcDec Procedure id(Procedure id(ParamListParamList)DeclarationDeclaration$Entry$Entry ProgramBodyProgramBody$EndProc$EndProcFunDecFunDec Function id(Function id(ParamListParamList):Type ):Type DeclarationDeclaration$Entry$Entry ProgramBodyProgramBody$EndFunc$EndFunc$Entry$Entry给子程序给子程序Q Q分配新标号分配新标号LevelLevelQ Q，并将它填到，并将它填到Q Q的符号表项中的符号表项中产生入口中间代码产生入口中间代码(ENTRY,(ENTRY,LabelLabelQ Q,SizeSizeQ Q,LevelLevelQ Q)$EndProcEndProc 和和$EndFuncEndFunc在遇到在遇到endend时产生出口中间代码时产生出口中间代码(ENDPROC,_,_,_)(ENDPROC,_,_,_)或或 (ENDFUNC,_,_,_)(ENDFUNC,_,_,_)