语义分析和中间代码生成

《语义分析和中间代码生成》由会员分享，可在线阅读，更多相关《语义分析和中间代码生成（118页珍藏版）》请在金锄头文库上搜索。

1、第6章 语义分析与 中间代码生成本章在编译程序中的地位表格管理词法分析器语法分析器语义分析与中间代码产生优化器目标代码生成器源程序单词符号语法单位中间代码中间代码目标代码出错处理6.1 概述 6.2 属性文法 6.3 几种常见的中间语言 （*四元式） 6.4 表达式及赋值语句的翻译 6.5 控制语句的翻译 6.6 数组元素的翻译 6.7 过程或函数调用语句的翻译 *6.8 说明语句的翻译内容安排6.1 概 述 6.1.1 语义分析的概念一个源程序经过词法分析、语法分析之后， 表明该源程序在书写上是正确的，并且符合程序 语言所规定的语法。但是语法分析并未对程序内 部的逻辑含义加以分析，因此编译程

2、序接下来的 工作是语义分析，即审查每个语法成分的静态语 义。如果静态语义正确，则生成与该语言成分等 效的中间代码，或者直接生成目标代码。 l 直接生成目标代码 直接生成机器语言或汇编语言形式的目标 代码的优点是编译时间短且无需中间代码到目 标代码的翻译。 l 生成中间代码生成中间代码的优点是使编译结构在逻辑 上更为简单明确，特别是使目标代码的优化比 较容易实现。语义分析时语义检查的分类：u动态语义检查需要生成相应的目标代码，它是在运行时进行的；例如：除零溢出错误。u静态语义检查在编译时完成的，它涉及以下几个方面：(1) 类型检查(2) 控制流检查(3) 一致性检查各种条件表达式的类型不是布尔类

3、型; 运算符的分量类型不相容; 赋值语句左右类型不相容; 形、实参类型不相容; 函数说明和函数返回类型不相容; int x;float f();x = f();符合变量声明的语法、语义符合函数声明的语法、语义符合赋值语句的语法、不符合语义(1) 类型检查(2) 控制流检查用以保证控制语句有合法的转向点。如C语言中不允许goto语句转入case语句流；break语句需寻找包含它的最小 switch、while或for语句方可找到转向点，否则出错。(3) 一致性检查如在相同作用域中标识符只能说明一次、case语句的标 号不能相同、函数调用参数个数要相同等。 常见的语义错误声明和使用相关的语义错误

4、标识符没有声明; 重复声明; 如何检查? 每当遇到新声明的标识符,查符号表 如果当前有效的所有标识符中有相同名字的,则 是重复声明错误; 否则生成它的属性信息,保存到符号表中; 每当遇到标识符的使用,查符号表 如果没有找到,说明该标识符没有声明; 否则, 得到该标识符的属性,进行进一步分析;语义分析阶段只产生中间代码而不生成目 标代码的方法使编译程序的开发变得较为容易 ，但语义分析不像词法分析和语法分析那样可 以分别用正规文法和上下文无关文法描述。由于语义是上下文有关的，因此语义的形 式化描述是非常困难的，目前较为常见的是用 属性文法作为描述程序语言语义的工具，并采 用语法制导翻译的方法完成对

5、语法成分的翻译 工作。语法制导翻译的方法就是为每个规则配上一个翻 译子程序(称语义动作或语义子程序)，并在语法分析的同时执行这些子程序。语义动作是为规则赋予具体意义的手段，它一方面指出了一个规则所产生的符号串的意义，另一方面 又按照这种意义规定了生成某种中间代码应做哪些基 本动作。在语法分析过程中，当一个规则获得匹配(对于自 上而下分析)或用于归约(对于自下而上分析)时，此规则相应的语义子程序就进入工作，完成既定的翻译任 务。6.1.2 语法制导翻译方法语法制导翻译分为自下而上语法制导翻 译和自上而下语法制导翻译，我们重点介绍 自下而上语法制导翻译。假定有一个自下而上的LR分析器，我们 可以把

6、这个LR分析器的能力加以扩大，使它 能在用某个规则进行归约的同时调用相应的 语义子程序进行有关的翻译工作；每个规则 的语义子程序执行之后，某些结果(语义信息) 必须作为此规则的左部符号的语义值暂时保 存下来，以便以后语义子程序引用这些信息 。此外，原LR分析器的分析栈也加以扩充 ，以便能够存放与文法符号相对应的语义值 。这样，分析栈可以存放三类信息：分析状 态、文法符号及文法符号对应的语义值。扩 充后的分析栈如图61所示。图61 扩充后的LR分析栈 作为一个例子，我们考虑下面的文法及语义 动作所执行的程序：规则 语义动作(0) SE print valTOP(1) EE(1)+E(2)valT

7、OP=valTOP+valTOP+2(2) EE(1)*E(2)valTOP=valTOP*valTOP+2(3) E(E(1) valTOP= valTOP+1(4) Ei valTOP=lexval (注：lexval为i的整型 内 部值)我们扩充分析栈工作的总控程序功能， 使其在完成语法分析的同时也能完成语义分 析工作(这时的语法分析栈已成为语义分析栈) ；即在用某一个规则进行归约之后，调用相 应的语义子程序完成与所用规则相应的语义 动作，并将每次工作后的语义值保存在扩充 后的“语义值”栈中。图62表示算术表达式79*5#的语法树 及各结点值，而表6.1则给出了根据分析表用 LR语法制导

8、翻译方法得到的该表达式的语义 分析和计值过程。图62 语法制导翻译计算表达式79*5#的语法树表6.1 表达式79*5#的语义分析和计值过程步骤状态栈符号栈语义栈输入串动作10#_79*5#s3203# 7_ _9*5#r4301# E_79*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#acc6.2 属 性 文 法6.2.1

9、文法的属性属性是指与文法符号的类型和值等有关的一些信息，在编译中用属性描述处理对象的特征。随着编译的进展，对语法分析产生的语法树进行语义分析，且分析的结果用中间代码描述出来。对于一棵 等待翻译的语法树，它的各个结点都是文法中的一个符 号X，该X可以是终结符或非终结符。根据语义处理的需 要，在用规则AX进行归约或推导时，应能准确而恰 当地表达文法符号X在归约或推导时的不同特征。 例如:判断变量X的类型是否匹配，要用X的数据类型来描述 ；判断变量X是否存在，要用X的存储位置来描述；而对X的运算，则要用X的值来描述；因此，语义分析阶段引入X的属性，如X.type、 X.place、X.val等来分别

10、描述变量X的类型、存储位置以 及值等不同的特征。文法符号属性分：n 继承属性 n 综合属性继承属性用于“自上而下”传递信息。继承属性由 相应语法树中结点的父结点属性计算得到， 即沿语法树向下传递，由根结点到分枝(子)结 点，它反映了对上下文依赖的特性。继承属 性可以很方便地用来表示程序语言上下文的 结构关系。 综合属性用于“自下而上”传递信息。综合属性由 相应语法分析树中结点的分枝结点(即子结点) 属性计算得到，其传递方向与继承属性相反 ，即沿语法分析树向上传递，从分枝结点到 根结点。属性文法是一种适用于定义语义的特殊文法，即在 语言的文法中增加了属性的文法，它将文法符 号的语义以“属性”的形

11、式附加到各个文法的 符号上(如上述与变量X相关联的属性X.type、 X.place和X.val等)，再根据规则所包含的含 义，给出每个文法符号属性的求值规则，从而 形成一种带有语义属性的上下文无关文法，即 属性文法。属性文法也是一种翻译文法，属性有助于 更详细地指定文法中的代码生成动作。6.2.2 属性文法例如，简单算术表达式求值的属性文法如下：规则 语义规则 (1) SE print (E.val) (2) EE(1)+TE.val=E(1).val+T.val(3) ET E.val=T.val (4) TT(1)*F T.val=T(1).val*F.val (5) TT(1) T.v

12、al=T(1).val (6) F(E) F.val=E.val (7) Fi F.val=i.lexval上面的一组规则中，每一个非终结符都有 一个属性val来表示整型值，如E.val表示E的整 型值，而i.lexval则表示i的整型内部值。与规则 关联的每一个语义规则的左部符号E、T、F等 的属性值的计算由其各自相应的右部符号决定 ，这种属性也称为综合属性。与规则SE关联 的语义规则是一个函数print(E.val)，其功能是打 印E规则的值。S在语义规则中没有出现，可以 理解为其属性是一个虚属性。简单变量类型说明的文法GD如下： GD：Dint Lfloat LLL, idid其对应的属

13、性文法为：规则 语义规则 (1) DTL L.in=T.type (2) TintT.type=int(3) Tfloat T.type=float (4) LL(1)，id L(1).in=L.in; addtype(id.entry,L.in) (5) Lid addtype(id.entry,L.in) 注意到与文法GD相应的说明语句形式可为 int id1，id2,，idn 或者 float id1，id2,，idn非终结符T有一个综合属性type，其值为 int或float。语义规则L.in=T.type表示L.in的属 性值由相应说明语句指定的类型T.type决定； 属性L.in被

14、确定后将随语法树的逐步生成而传 递到下边的有关结点使用，这种结点属性称 为继承属性。由此可见，标识符的类型可以 通过继承属性的复写规则来传递。例如，对输入串int a,b，根据上述的语义 规则，可在其生成的语法树中看到用“”表 示的属性传递情况，如图63所示。 图63 属性信息传递情况示意属性翻译文法（属性文法）如语法分析方法是自下而上的，在用某一规则进行规约的 同时就执行相应的语义，在分析出一个句子时，这个句子 的“值”也就同时产生了。对于文法的每个规则都配备了一组属性的计算规则，称为 语义规则。属性与变量一样，可以进行计算和传递。属性加工的过程即是语义处理的过程。6.3 几种常见的中间语言

15、6.3.1 抽象语法树 6.3.2 逆波兰表示法 6.3.3 三地址代码6.3.1 抽象语法树语法制导翻译既可以基于语法分析树也可以基于抽象语法 树进行，采用的基本方法是一样的。现在对语法树进行改造，去掉那些对翻译不必要的信息， 将语法树进行抽象 - 抽象语法树。在表达式的抽象语法树中，运算符、关键字不作叶子结点 而作为内部结点，叶子结点只是运算量。语法制导翻译以语法树作基础, 实际上, 语法树可以作为一 种合适的中间语言形式。抽象语法树也可以属性化，给结点加上属性变成带属性的 抽象语法树。当把语法规则中本质部分抽象出来而将非本质部分 去掉后，便得到抽象语法规则。这种去掉不必要信息的 做法可以获得高效的源程序中间表示。如赋值语句x=ab*c的抽象语法树如图64(a)所示， 而图64(b)则是该赋值语句的普通语法树。图64 x=ab*c的语法树 抽象语法树的一个显著特点是结构紧凑，容 易构造且结点数较少。图64(b)所示的普通语法树的结点为14个； 而图64(a)所示的抽象语法树的结点仅有7个，且 每个内部结点最多只有两个分支，因此可以