第七章语义分析和中间代码生成

编译原理第七章语义分析和中间代码生成制作人：李明新共56页第1页19-12-21第七章语义分析和中间代码生成知识结构：语义分析语法分析概述语法制导翻译逆波兰式表示三元式表示语义分析和中中间语言图型表示间代码生成四元式表示三地址语句表示赋值语句的翻译布尔表达式的翻译中间代码生成控制语句的翻译说明语句的翻译过程语句的翻译第一节语法制导翻译概述一、语义分析的任务在词法分析和语法分析的基础上进一步分析其含义，主要的工作是进行静态语义检查和翻译。二、语义分析的功能1、类型检查检查运算的合法性（运算对象的一致性）。编译原理第七章语义分析和中间代码生成制作人：李明新共56页第2页19-12-212、一致性检查一个对象（标识符等）在一个分程序中只能被定义一次。3、相关名字检查如果一个名字必须出现多次，检查使用的名字是否相同的。4、控制流检查控制流语句必须使控制转移到合法的地方。5、确定类型确定标识符所关联得数据类型。6、识别含义确认程序中各种成分组合到一起的含义，并作相应的语义处理，对可执行的语句生成中间语言或目标语言。三、生成的语言1、直接生成目标语言根据源程序中各语法成分的语义，直接生成机器语言或汇编语言。其特点：⑴编译时间较短；⑵存储空间较大；⑶目标语言的质量较差。2、生成中间语言介于源程序语言和机器语言之间的机内表示形式。其特点：⑴编译程序的逻辑结构简单；⑵有利于编译程序的移植；编译原理第七章语义分析和中间代码生成制作人：李明新共56页第3页19-12-21⑶便于目标语言的优化。四、语义分析方法1、语法制导翻译方法在语法分析过程中，使用语法规则进行归约的同时，根据每个产生式的语义动作进行翻译（在语法规则的制导下，通过对语义规则的计算，完成对输入字符串的翻译）的方法。2、属性翻译方法指明语义规则的计算次序，陈述一些实现细节，以表达语义动作在语法分析过程中的执行时刻。五、语义规则为文法中的每一条产生式配置计算属性的计算规则。六、语法制导翻译为文法中每个产生式配备一组语义规则。1、语义规则语义规则计算包括：产生代码、在符号表中存放信息、在分析工作栈中填写语义值（属性值）,并生成相应的中间代码。2、自上而下分析用一条产生式与输入符号匹配成功时,执行相应语义子程序生成中间代码。3、自下而上分析用一条产生式进行的归约时,执行相应语义子程序生成中间代码。编译原理第七章语义分析和中间代码生成制作人：李明新共56页第4页19-12-21七、翻译简例表达式文法和相应的翻译模式：（P179）S→id:=E{p:=Lookup(id.name);ifpnilthenemit(p‘:=’E.place)elseerror}E.place为属性值(语义变量)，代表存放E值的变量名在符号表的入口地址或指向代表E值的临时变量的整数值。E→E1+E2{E.place:=newtemp;emit(E.place‘:=’E1.place‘+’E2.place)}语法分析工作栈进行扩充,增加相应的语义值，语法分析同时(如归约时)，执行语义规则(语义子程序)。例：x:=y+z的语法制导翻译⑴用E→E1+E2归约执行语义规则E2E2.place{E.place:=T1;+-归约后EE.placeemit(T1:=’y‘+’z)}E1E1.place符号语义值生成一条中间代码符号语义值⑵用S→id:=E归约执行语义规则EE.place{p:=Lookup(x);:=-归约后sE.placeemit(x‘:=’T1)}idid.place符号语义值生成一条中间代码。编译原理第七章语义分析和中间代码生成制作人：李明新共56页第5页19-12-21符号语义值这样语法分析结束时也就生成了中间代码：（0）T1:=y+z（1）x:=T1注意：语义工作栈中的值与状态工作栈中的值一一对应，某些符号可能无相应的语义值，如上例“+”，保留语义栈位是用“—”表示。归约时符号和语义值同时退出工作栈，同时进入工作栈。例A→XYZZZ.zYY.y归约后AA.aXX.x符号语义值符号语义值八、语义值（属性）和语义规则（语义子程序）1、语义值代表文法符号的类型、值、符号表地址等语义子程序需要的信息。如E.place（符号表指针）。2、语义规则对语义值（属性）进行计算，或其它加工处理过程。⑴属性文法翻译使用语义规则进行属性值的计算。⑵语法制导翻译给出使用语义规则进行计算的顺序（用{}括号起来）。九、理解语法制导翻译的若干关键问题编译原理第七章语义分析和中间代码生成制作人：李明新共56页第6页19-12-211、语义值（属性）代表的含义2、语义子程序（语义规则）3、语法制导翻译过程⑴翻译的顺序与语义子程序执行的顺序相关；⑵子程序执行的顺序与应用产生式进行归约的顺序相关；⑶归约的顺序与中间代码的顺序相关；第二节中间语言一、中间语言的表示形式1、后缀式（逆波兰表示）（P167定义）2、图表示法（DAG无环路有向图，抽象语法树）3、三地址代码⑴三地址语句⑵四元式⑶三元式⑷间接三元式二、后缀式（逆波兰表示）1、表达式表示形式⑴中缀形式二目运算的运算符总是置于两个运算对象之间。例：a*（b+c）⑵后缀形式把运算符置于运算对象之后，将中缀式中的算符，按优先编译原理第七章语义分析和中间代码生成制作人：李明新共56页第7页19-12-21级或结合律重新排序。⑶后缀形式表达式E的定义①如果E是一个变量或常量，则E的后缀形式是E自身。②如果E是E1OPE2形式的表达式，这里的OP是任何二元操作符，则E的后缀形式是E1E2OP，这里E1和E2分别为E1和E2的后缀形式。③如果E是（E1）形式的表达式，则E1的后缀形式就是E的后缀形式。例：中缀形式：a*（b+c），而后缀形式：abc+*2、中缀形式转换后缀形式的算法建立两个工作栈，存放运算对象和经处理后的运算符（逆波兰区）；另一个存放运算符，首先将“#”压入工作栈顶。⑴若输入的符号是运算对象，送入波兰区。⑵若输入的符号是运算符，送入运算符工作栈，操作过程：①工作栈顶运算符的优先级高于当前输入的运算符，将工作栈顶运算符弹出，送入逆波兰区，并把当前输入的运算符压入运算符工作栈；②工作栈顶运算符的优先级低于当前输入的运算符，将当前输入的运算符压入运算符工作栈；③若当前输入的符号是“#”，将运算符工作栈的符号依次弹出，送入逆波兰区。3、转换的语义规则编译原理第七章语义分析和中间代码生成制作人：李明新共56页第8页19-12-21⑴属性定义（语义变量）E．code：表示E的后缀式，定义了识别的标识符（指针）。OP表示任意的二元操作符。“‖”表示后缀形式的连接。⑵语义规则的描述（P167）对同一产生式重复出现的文法符号用角标进行区分。例a+b*（c+d*b）+d43215后缀式：abcdb*+*+d+产生式语义动作EidE.code≔idEE1OPE2E.code≔E1.code‖E2.code‖op三、图表示法1、抽象语法树语法树可以作为一种合适的中间语言形式。在语法树中去掉那些对翻译无效的信息，从而获得更有效的源程序中间表示。这种变换后的语法树为抽象语法树。抽象语法树的表示形式：⑴操作符和关键字作为内部结点。⑵运算对象作为叶子结点。例：3×5＋4的抽象语法树编译原理第七章语义分析和中间代码生成制作人：李明新共56页第9页19-12-21＋×4352、DAG图（无环路有向图）与抽象语法树一样，对表达式的每个子表达式，DAG都有一个结点。DAG图的结构：⑴内部结点为运算符。⑵子结点为操作对象。3、DAG与抽象语法树的区别（P168）⑴DAG图的公共子表达式的结点具有多个父结点。⑵抽象语法树的公共子表达式对应重复子树。四、三地址代码1、三地址代码一般形式X:=YopZ结果操作数操作符操作数例：X+Y*Z中间代码为：T1:=Y*ZT2:=X+T1T1,T2为临时变量（由编译生成）2、三地址语句的种类(P170)：⑴二目运算的赋值语句x:=yopz。⑵单目运算的赋值语句x:=opy。编译原理第七章语义分析和中间代码生成制作人：李明新共56页第10页19-12-21⑶复制语句x:=y。⑷无条件转移语句gotoL（中间代码地址）。⑸条件转移语句ifxrelopygotoL或ifagotoL。⑹调用语句paramx和callp,n，返回语句returny。⑺索引赋值x:=y[i]和x[i]:=y（数组元素）。⑻地址和指针赋值x:=&y，x:=*y和*x:=y。3、三地址代码的几种表示⑴四元式（op，arg1，arg2，result）例：x:=yopz的四元式(op，y，z，x)例：a:=b*-c+b*-c(@，c，_，T1)(*，b，T1，T2)(@，c，_，T3)(*，b，T3，T4)(+，T2，T4，T5)(:=，T5，_，a)⑵三元式为了避免把临时变量填入符号表，用中间代码地址（指针）代表运算对象。（op，arg1，arg2）例：a:=b*-c+b*-c(0)(@，c，_)(1)(*，b，(0))(2)(@，c，_)(3)(*，b，(2))编译原理第七章语义分析和中间代码生成制作人：李明新共56页第11页19-12-21(4)(+，(1)，(3))(5)(:=，a，(4))例：x[i]:=y(0)(=[]，x，i)(1)(:=，y,（0）)用两条三元式表示索引赋值。例：x:=y[i](0)([]=，y，i)(1)(:=，x，(0))(3)间接三元式(P173)为了便于代码优化处理，不直接使用三元式的指针，而是另设一张间接代码表，按先后顺序列出三元式在三元式代码表中的位置。例：x:=(A+B)*cy:=D↑(A+B)三元式代码表间接代码表OPARG1ARG2(1)(1)+AB(2)(2)*(1)C(3)(3)≔X(2)(1)(4)↑D(1)(4)(5)≔Y(1)(5)⑷比较几种形式的三地址代码a:=b*-c+b*-c编译原理第七章语义分析和中间代码生成制作人：李明新共56页第12页19-12-21三地址码四元式三元式间接三元式T1:=-c(@,c,-,T1)(@,c,-)(0)(@,c,-)(0)T2:=b*T1(*,b,T1,T2)(*,b,(0))(1)(*,b,(0))(1)T3:=-c(@,c,-,T3)(@,c,-)(2)(+,①,①)(0)T4:=b*T3(*,b,T3,T4)(*,b,②)(3)(：=，a,②)(1)T5:=T2+T4(+,T2,T4,T5)(+,①,③)(4)(2)A:=T5(:=,T5,-,a)(：=，a,④)(5)(3)第三节赋值语句的翻译一、简单算术表达式及赋值语句1、语义函数（子程序）P178Lookup(id.name)：查找id.name在符号表中的入口地址。emit()：生成三地址语句（中间代码）发送到输出文件中。例：emit(X‘:=’‘uminus’T)产生中间代码。newtemp：产生一个新临时变量名的整数码。如T1，T2，T3…。2、语义变量（属性）E.place：代表存放E值在符号表的入口地址或临时变量。id.name：以存在的变量名。⑶赋值语句的翻译模式（P179）S→id:=E{p:=Lookup(id.name);ifpnilthenemit(p‘:=’E.place)elseerror}E→E1+E2{E.place:=newtemp;emit(E.place‘:=’E1.place‘+’E2.place)}E→E1*E2{E.place:=newtemp;编译原理第七章语义分析和中间代码生成制作人：李明新共56页第13页19-12-21emit(E.place‘:=’E1.place‘*’E2.place)}E→-E1{E.place:=newtemp;emit(E.place‘:=’‘uminus’E1.place)}E→(E1){E.place:=E1.place}E→id{p:=lookup(id.name)ifpnilthenE.place:=pElseerror}例：X:=-B*(C+D)的语法