编译原理(清华)-第八章-语法制导和中间代码生成

第八章语法制导翻译和中间代码生成学习目标：掌握：常见语法成分的中间代码形式；常见语法成分的属性文法或翻译方案理解：属性文法、语法制导翻译方法目标程序源程序词法分析语法分析语义分析中间代码生成代码优化目标代码生成表格管理出错处理语义分析基础语义分析的内容主要是类型相容检查，有以下几种：1)各种条件表达式的类型是不是boolean型？2)运算符的分量类型是否相容？3)赋值语句的左右部的类型是否相容？4)形参和实参的类型是否相容?5)下标表达式的类型是否为所允许的类型？6)函数说明中的函数类型和返回值的类型是否一致？其它语义检查：1)V[E]中的V是不是变量，而且是数组类型？2)V.i中的V是不是变量，而且是记录类型？i是不是该记录的域名？3)x+f(…)中的f是不是函数名？形参个数和实参个数是否一致？4)每个使用性标识符是否都有声明？有无标识符的重复声明？在语义分析同时产生中间代码，在这种模式下，语义分析的主要功能如下：语义审查在扫描声明部分时构造标识符的符号表在扫描语句部分时产生中间代码语义分析方法语法制导翻译方法使用属性文法为工具来说明程序设计语言的语义。8.1属性文法8.2语法制导翻译概论8.3中间代码形式8.4基本语言成分的自下而上语法制导翻译8.5自上而下的语法制导翻译8.1属性文法(AttributeGrammar)属性对文法的每一个符号，引进一些属性，这些属性代表与文法符号相关的信息，如类型、值、存储位置等。语义规则为文法的每一个产生式配备的计算属性的计算规则，称为语义规则。属性文法是带属性的一种文法它的主要思想：首先对于每个文法符号引进相关的属性符号；其次对于每个产生式写出计算属性值的语义规则属性文法的形式定义一个属性文法是一个三元组,A＝(G,V,F)G是一个上下文无关文法；V是属性的有穷集；F是关于属性的断言的有穷集。说明：1.每个属性与文法符号相联，N.t表示文法符号N的属性t。属性值又称语义值。存储属性值的变量又称语义变量。2.每个断言与文法的某个产生式相联，写在{}内。属性的断言又称语义规则，它所描述的工作可以包括属性计算、静态语义检查、符号表的操作、代码生成等，有时写成函数或过程段。例完成类型检查的属性文法1)E→T1+T2{T1.t＝intANDT2.t＝int}2)E→T1orT2{T1.t＝boolANDT2.t＝bool}3)T→num{T.t:＝int}4)T→true{T.t:＝bool}5)T→false{T.t:＝bool}属性的分类：1.综合属性：从语法树的角度来看，如果一个结点的某一属性值是由该结点的子结点的属性值计算来的，则称该属性为综合属性。内在属性是综合属性。用于“自下而上”传递信息2.继承属性从语法树的角度来看，若一个结点的某一属性值是由该结点的兄弟结点和（或）父结点的属性值计算来的，则称该属性为继承属性。用于“自上而下”传递信息说明：终结符只有综合属性，它们由词法分析器提供非终结符既有综合属性也有继承属性，但文法开始符没有继承属性例简单算术表达式求值的属性文法1)L→E{Print(E.val)}2)E→E1+T{E.val:＝E1.val+T.val}3)E→T{E.val:＝T.val}4)T→T1*F{T.val:＝T1.val*F.val}5)T→F{T.val:＝F.val}6)F→(E){F.val:＝E.val}7)F→digit{F.val:＝digit.lexval}E.val、T.val、F.val都是综合属性终结符digit只有综合属性，它的值由词法分析提供例描述变量类型说明的属性文法1)D→TL{L.in:＝T.type}2)T→int{T.type:＝int}3)T→real{T.type:＝real}4)L→L1,id{L1.in:＝L.in；addtype(id.entry，L.in)}5)L→id{addtype(id.entry，L.in)}id1DTLL1id2，intL.in是继承属性T.type是综合属性intid1,id2的语法树:用→表示属性的传递情况8.2语法制导翻译概论1.语法制导翻译基本思想：在语法分析过程中，随着分析的步步进展，每当使用一条产生式进行推导（对于自上而下分析）或归约（对于自下而上分析），就执行该产生式所对应的语义动作，完成相应的翻译工作。语法制导翻译法不论对自上而下分析或自下而上分析都适用例简单算术表达式求值的属性文法1)E→E1+T{E.val:＝E1.val+T.val}2)E→T{E.val:＝T.val}3)T→T1*digit{T.val:＝T1.val*digit.lexval}4)T→digit{T.val:＝digit.lexval}2+3*5的语法树：EE1+TT1*5T23T.val=2T.val=3T.val=15E.val=2E.val=17自下而上语法制导翻译过程：一旦语法分析确认输入符号串是一个句子，它的值也同时由语义规则计算出来2.语法制导翻译的实现途径以自下而上（LR分析）的语法制导翻译来说明将LR分析器能力扩大，增加在归约后调用语义规则的功能增加语义栈，语义值放到与符号栈同步操作的语义栈中，多项语义值可设多个语义栈，栈结构为：状态栈符号栈语义栈SmXmXm.val………S1X1X1.valS0#-例简单算术表达式求值的属性文法1)L→E{print(E.val)}2)E→E1+T{E.val:＝E1.val+T.val}3)E→T{E.val:＝T.val}4)T→T1*digit{T.val:＝T1.val*digit.lexval}5)T→digit{T.val:＝digit.lexval}状态ACTIONGOTOd+*#ET0S3121S4acc2r3S5r333r5r5r54S375S66r4r4r47r2S5r2步骤状态栈语义栈符号栈剩余输入串ActionGOTO00-#2＋3*5＃S3103--#2＋3*5＃r52202-2#T＋3*5＃r31301-2#E＋3*5＃S44014-2-#E+3*5＃S350143-2--#E+3*5＃r5760147-2-3#E+T*5＃S5701475-2-3-#E+T*5＃S68014756-2-3-5#E+T*5＃r4790147-2-15#E+T#r211001-17#E#acc分析并计算2＋3*5的过程如下:8.3中间代码的形式定义：中间代码是一种复杂性介于源程序语言和机器语言之间的一种表示形式。使用中间代码的好处：中间代码与具体机器无关对中间代码进行与机器无关的优化形式：逆波兰记号、三元式、间接三元式、四元式和树形表示8.3.1逆波兰记号逆波兰表示法将运算对象写在前面，把运算符写在后面，因而也称后缀式。例如：程序设计语言中的表示逆波兰表示a+bab+a+b*cabc*+(a+b)*cab+c*后缀式的计算机处理后缀式的最大优点是易于计算机处理处理过程：从左到右扫描后缀式，每碰到运算对象就推进栈；碰到运算符就从栈顶弹出相应目数的运算对象施加运算，并把结果推进栈。最后的结果留在栈顶。bt1dct1t2t1t3t1=-bt2=c*dt3=t1+t2例：表达式－b＋c*d的后缀式b@cd*+的计值过程逆波兰表示法的扩充逆波兰表示法很容易扩充到表达式以外的范围例如：语句逆波兰表示备注a:=b+cabc+:=:=看作二目运算符GOTOLLjumpjump看成一目运算符，表示GOTOIfEthenS1elseS2ES1S2￥把￥看成三目运算符，表示if–then–else8.3.2三元式和树形表示三元式(算符op，第一个运算对象ARG1,第二个运算对象ARG2)说明：三元式的某些运算对象是另一个三元式的编号（代表其结果）一目算符只需选用一个运算对象（ARG1）多目算符可用连续几个三元式表示例：a:＝b*c+b*d表示为(1)(*,b,c)(2)(*,b,d)(3)(+,(1),(2))(4)(:＝,(3),a)间接三元式和三元式类似，只是合并相同的三元式，并在三元式后面加一列执行序列例如：a:＝b*c+b*c树形表示二目运算对应二叉子树，多目运算对应多叉子树，但通常通过引入新结点表示成二叉子树。例如：a:＝b*c+b*d表示成:=a+**bcbd8.3.3四元式四元式表示四元式是一种比较普遍采用的中间代码形式(算符op，ARG1，ARG2，运算结果RESULT）例如：a:＝b*c+b*d的四元式表示如下：1)(*,b,c,t1)2)(*,b,d,t2)3)(+,t1,t2,t3)4)(:＝,t3,－,a)其中ti（i＝1,2,3）是编译程序引入的临时变量四元式的优点：四元式比三元式更便于优化。优化要求改变运算顺序或删除某些运算，引起编号的变化。三元式通过编号引用中间结果，编号的变化引起麻烦；四元式通过临时变量引用中间结果，编号变化无影响。四元式对生成目标代码有利。四元式表示很类似于三地址指令，很容易转换成机器代码。四元式的另一种表示有时为了更直观，把四元式写成简单赋值形式或更易理解的形式四元式直观形式（1）（*,b,c,t1）（1）t1:＝b*c（2）（*,b,d,t2）（2）t2:＝b*d（3）（+,t1,t2,t3）（3）t3:＝t1+t2（4）（:＝,t3,－,a）（4）a:＝t3(jump,－，－，L)gotoL(jrop,B，C，L)ifBropCgotoL8.4基本语言成分的自下而上语法制导翻译8.4.1简单赋值语句的翻译8.4.2布尔表达式的翻译8.4.3控制结构的翻译8.4.4简单说明语句的翻译8.4.1简单赋值语句的翻译简单赋值语句是指不含复杂数据类型（如数组，记录等）的赋值语句。赋值语句的语义审查包括：1.每个使用性标识符是否都有声明？2.运算符的分量类型是否相容？3.赋值语句的左右部的类型是否相容？赋值语句的翻译目标：在赋值语句右部表达式产生的四元式序列后加一条赋值四元式1．属性和语义规则中用到的变量、过程和函数属性：用id.name表示单词id的名字。用E.place表示存放E值的变量名在符号表的入口地址或临时变量编码。变量、函数和过程：用nextstat变量给出在输出序列中下一个四元式的序号用lookup（id.name）函数审查id.name是否出现在符号表中，是则返回id的入口地址，否则返回nil。用emit过程向输出序列输出一个四元式，emit每调用一次，nextstat的值增加1用newtemp函数生成临时变量，每次调用生成一个新的临时变量，如t1,t2,……用error过程进行错误处理。(1)S→id:＝E{p:＝lookup(id.name);ifp≠nilthenemit(:＝,E.place,-,p)elseerror}2．简单赋值语句的翻译（假定变量只有一种类型）(2)E→E1+E2{E.place:＝newtemp;emit(+,E1.place,E2.place,E.place)}此情况下的语义审查只有：每个使用性标识符是否都有声明？(4)E→－E1{E.place:＝newtemp;emit(@,E1.place,-,E.place)}(5)E→(E1){E.place:＝E1.place}(6)E→id{p:＝lookup(id.name);ifp≠nilthenE.place:＝pelseerror}(3)E→E1*E2{E.place:＝newtemp;emit(*,E1.place,E2.place,E.place)}例翻译赋值语句A:＝B+CE1.place＝BE2.place＝CE.place＝t1；(＋,B,C,t1)(:＝,t1,-,A)SA:=EBE1+E2C(为了直观，用B和C分别表示B和C在符号表的入口地址)表达式中可能出现不同类型的变量和常量语义审查包括：1.每个使用性标识符是否都有声明？2.运算符的分量类型是否相容？•若不接受不同类型的运算对象混合运算，