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

第4章语义分析和中间代码生成第4章语义分析和中间代码生成4.1概述4.2属性文法4.3几种常见的中间语言4.4表达式及赋值语句的翻译4.5控制语句的翻译4.6数组元素的翻译4.7过程或函数调用语句的翻译4.8说明语句的翻译4.9递归下降语法制导翻译方法简介第4章语义分析和中间代码生成4.1概述4.1.1语义分析的概念一个源程序经过词法分析、语法分析之后，表明该源程序在书写上是正确的，并且符合程序语言所规定的语法。但是语法分析并未对程序内部的逻辑含义加以分析，因此编译程序接下来的工作是语义分析，即审查每个语法成分的静态语义。如果静态语义正确，则生成与该语言成分等效的中间代码，或者直接生成目标代码。第4章语义分析和中间代码生成直接生成机器语言或汇编语言形式的目标代码的优点是编译时间短且无需中间代码到目标代码的翻译，而中间代码的优点是使编译结构在逻辑上更为简单明确，特别是使目标代码的优化比较容易实现。第4章语义分析和中间代码生成如同在进行词法分析、语法分析的同时也进行着词法检查、语法检查一样，在语义分析时也必然要进行语义检查。动态语义检查需要生成相应的目标代码，它是在运行时进行的；静态语义检查是在编译时完成的，它涉及以下几个方面：(1)类型检查，如参与运算的操作数其类型应相容。(2)控制流检查，用以保证控制语句有合法的转向点。如C语言中不允许goto语句转入case语句流；break语句需寻找包含它的最小switch、while或for语句方可找到转向点，否则出错。第4章语义分析和中间代码生成(3)一致性检查，如在相同作用域中标识符只能说明一次、case语句的标号不能相同等。语义分析阶段只产生中间代码而不生成目标代码的方法使编译程序的开发变得较为容易，但语义分析不像词法分析和语法分析那样可以分别用正规文法和上下文无关文法描述。由于语义是上下文有关的，因此语义的形式化描述是非常困难的，目前较为常见的是用属性文法作为描述程序语言语义的工具，并采用语法制导翻译的方法完成对语法成分的翻译工作。第4章语义分析和中间代码生成4.1.2语法制导翻译方法语法制导翻译的方法就是为每个产生式配上一个翻译子程序(称语义动作或语义子程序)，并在语法分析的同时执行这些子程序。语义动作是为产生式赋予具体意义的手段，它一方面指出了一个产生式所产生的符号串的意义，另一方面又按照这种意义规定了生成某种中间代码应做哪些基本动作。在语法分析过程中，当一个产生式获得匹配(对于自上而下分析)或用于归约(对于自下而上分析)时，此产生式相应的语义子程序就进入工作，完成既定的翻译任务。第4章语义分析和中间代码生成语法制导翻译分为自下而上语法制导翻译和自上而下语法制导翻译，我们重点介绍自下而上语法制导翻译。假定有一个自下而上的LR分析器，我们可以把这个LR分析器的能力加以扩大，使它能在用某个产生式进行归约的同时调用相应的语义子程序进行有关的翻译工作；每个产生式的语义子程序执行之后，某些结果(语义信息)必须作为此产生式的左部符号的语义值暂时保存下来，以便以后语义子程序引用这些信息。第4章语义分析和中间代码生成此外，原LR分析器的分析栈也加以扩充，以便能够存放与文法符号相对应的语义值。这样，分析栈可以存放三类信息：分析状态、文法符号及文法符号对应的语义值。扩充后的分析栈如图4–1所示。作为一个例子，我们考虑下面的文法及语义动作所执行的程序：第4章语义分析和中间代码生成产生式语义动作(0)S'→Eprintval[TOP](1)E→E(1)+E(2)val[TOP]=val[TOP]+val[TOP+2](2)E→E(1)*E(2)val[TOP]=val[TOP]*val[TOP+2](3)E→(E(1))val[TOP]=val[TOP+1](4)E→ival[TOP]=lexval(注：lexval为i的整型内部值)这个文法的LR分析表见表3.20。第4章语义分析和中间代码生成我们扩充分析栈工作的总控程序功能，使其在完成语法分析的同时也能完成语义分析工作(这时的语法分析栈已成为语义分析栈)；即在用某一个规则进行归约之后，调用相应的语义子程序完成与所用产生式相应的语义动作，并将每次工作后的语义值保存在扩充后的“语义值”栈中。图4–2表示算术表达式7＋9*5#的语法树及各结点值，而表4.1则给出了根据表3.20用LR语法制导翻译方法得到的该表达式的语义分析和计值过程。第4章语义分析和中间代码生成skXkVk·vals1X1V1·val………s0#—状态文法符号语义值TOP图4–1扩充后的LR分析栈第4章语义分析和中间代码生成E·val＝52E·val＝7E·val＝45＋7E·val＝9*E·val＝595图4–2语法制导翻译计算表达式7＋9*5#的语法树第4章语义分析和中间代码生成表4.1表达式7＋9*5#的语义分析和计值过程步骤状态栈符号栈语义栈输入串主要动作10#_7＋9*5#s3203#7__＋9*5#r4301#E_7＋9*5#s44014#E+_7_9*5#s350143#E+9_7__*5#r460147#E+E_7_9*5#s5701475#E+E*_7_9_5#s38014753#E+E*5_7_9__#r49014758#E+E*E_7_9_5#r2100147#E+E_7_45#r11101#E_52#acc第4章语义分析和中间代码生成4.2属性文法4.2.1文法的属性属性是指与文法符号的类型和值等有关的一些信息，在编译中用属性描述处理对象的特征。随着编译的进展，对语法分析产生的语法树进行语义分析，且分析的结果用中间代码描述出来。对于一棵等待翻译的语法树，它的各个结点都是文法中的一个符号X，该X可以是终结符或非终结符。根据语义处理的需要，在用产生式A→αXβ进行归约或推导时，应能准确而恰当地表达文法符号X在归约或推导时的不同特征。第4章语义分析和中间代码生成例如，判断变量X的类型是否匹配，要用X的数据类型来描述；判断变量X是否存在，要用X的存储位置来描述；而对X的运算，则要用X的值来描述；因此，语义分析阶段引入X的属性，如X.type、X.place、X.val等来分别描述变量X的类型、存储位置以及值等不同的特征。文法符号的属性可分为继承属性与综合属性两类。继承属性用于“自上而下”传递信息。继承属性由相应语法树中结点的父结点属性计算得到，即沿语法树向下传递，由根结点到分枝(子)结点，它反映了对上下文依赖的特性。继承属性可以很方便地用来表示程序语言上下文的结构关系。第4章语义分析和中间代码生成综合属性用于“自下而上”传递信息。综合属性由相应语法分析树中结点的分枝结点(即子结点)属性计算得到，其传递方向与继承属性相反，即沿语法分析树向上传递，从分枝结点到根结点。第4章语义分析和中间代码生成4.2.2属性文法属性文法是一种适用于定义语义的特殊文法，即在语言的文法中增加了属性的文法，它将文法符号的语义以“属性”的形式附加到各个文法的符号上(如上述与变量X相关联的属性X.type、X.place和X.val等)，再根据产生式所包含的含义，给出每个文法符号属性的求值规则，从而形成一种带有语义属性的上下文无关文法，即属性文法。属性文法也是一种翻译文法，属性有助于更详细地指定文法中的代码生成动作。第4章语义分析和中间代码生成例如，简单算术表达式求值的属性文法如下：产生式语义规则(1) S→Eprint(E.val)(2) E→E(1)+TE.val=E(1).val+T.val(3) E→TE.val=T.val(4) T→T(1)*FT.val=T(1).val*F.val(5) T→T(1)T.val=T(1).val(6) F→(E)F.val=E.val(7) F→iF.val=i.lexval第4章语义分析和中间代码生成上面的一组产生式中，每一个非终结符都有一个属性val来表示整型值，如E.val表示E的整型值，而i.lexval则表示i的整型内部值。与产生式关联的每一个语义规则的左部符号E、T、F等的属性值的计算由其各自相应的右部符号决定，这种属性也称为综合属性。与产生式S→E关联的语义规则是一个函数print(E.val)，其功能是打印E产生式的值。S在语义规则中没有出现，可以理解为其属性是一个虚属性。我们再举一例说明属性文法。一简单变量类型说明的文法G[D]如下：G[D]：D→intL∣floatLL→L,id∣id第4章语义分析和中间代码生成其对应的属性文法为：产生式语义规则(1) D→TLL.in=T.type(2) T→intT.type=int(3) T→floatT.type=float(4) L→L(1)，idL(1).in=L.in;addtype(id.entry,L.in)(5) L→idaddtype(id.entry,L.in)注意到与文法G[D]相应的说明语句形式可为intid1，id2,…，idn或者floatid1，id2,…，idn第4章语义分析和中间代码生成非终结符T有一个综合属性type，其值为int或float。语义规则L.in=T.type表示L.in的属性值由相应说明语句指定的类型T.type决定；属性L.in被确定后将随语法树的逐步生成而传递到下边的有关结点使用，这种结点属性称为继承属性。由此可见，标识符的类型可以通过继承属性的复写规则来传递。例如，对输入串inta,b，根据上述的语义规则，可在其生成的语法树中看到用“→”表示的属性传递情况，如图4–3所示。第4章语义分析和中间代码生成图4–3属性信息传递情况示意DTLintL，id2id1第4章语义分析和中间代码生成4.3几种常见的中间语言4.3.1抽象语法树抽象语法树也称图表示，是一种较为流行的中间语言表示形式。在抽象语法树表示中，每一个叶结点都表示诸如常量或变量这样的运算对象，而其它内部结点则表示运算符。抽象语法树不同于前述的语法树，它展示了一个操作过程并同时描述了源程序的层次结构。第4章语义分析和中间代码生成注意，语法规则中包含的某些符号可能起标点符号作用也可能起解释作用。如赋值语句语法规则：S→V=e其中的赋值号“=”仅起标点符号作用，其目的是把V与e分开；而条件语句语法规则：S→if(e)S1;elseS2第4章语义分析和中间代码生成其中的保留字符号if和else起注释作用，说明当布尔表达式e为真时执行S1，否则执行S2；而“；”仅起标点符号作用。可以看出，上述语句的本质部分是V、e和Si。当把语法规则中本质部分抽象出来而将非本质部分去掉后，便得到抽象语法规则。这种去掉不必要信息的做法可以获得高效的源程序中间表示。上述语句的抽象语法规则为：第4章语义分析和中间代码生成(1)赋值语句：左部表达式(2)条件语句：表达式语句1语句2与抽象语法相对应的语法树称为抽象语法树或抽象树，如赋值语句x=a−b*c的抽象语法树如图4–4(a)所示，而图4–4(b)则是该赋值语句的普通语法树。第4章语义分析和中间代码生成图4–4x=a−b*c的语法树assignx－a*bc(a)SVE＝xEE－EE*abc(b)第4章语义分析和中间代码生成抽象语法树的一个显著特点是结构紧凑，容易构造且结点数较少。图4–4(b)所示的普通语法树的结点为14个；而图4–4(a)所示的抽象语法树的结点仅有7个，且每个内部结点最多只有两个分支，因此可以将每个赋值语句或表达式表示为一棵二叉树。对于含有多元运算的更为复杂的语法成分，相应的抽象语法树则为一棵多叉树，但我们总可以将其转变为一棵二叉树。第4章语义分析和中间代码生成4.3.2逆波兰表示法逆波兰表示法是波兰逻辑学家卢卡西维奇(Lukasiewicz)发明的一种表示表达式的方法，这种表示法把运算量(操作数)写在前面，把运算符写在后面，因而又称后缀表示法。例如，把a+b写成ab+，把a*(b+c)写成abc+*。第4章语义分析和中间代码生成1．表达式的逆波兰表示表达式E的后缀表示的递归定义如下：(1)如果E是变量或常数，则E的后缀表示即E