第六章—属性文法和语法制导翻译

一、属性文法

1、属性文法： 是在上下文无关文法的基础上为每个文法符号（终结符或非终结符）配备若干个相关的“值”（称为属性）。

2、属性：代表与文法符号相关的信息，和变量一样，可以进行计算和传递。

3、属性的分类：综合属性、继承属性

4、语义规则：

在一个属性文法中，对应于每个产生式A都有一套与之相关联的语义规则，每条语义规则的形式为：b:=f(c1,c2,…,ck)  

这里f是一个函数，而且或者

(1)b是A的一个综合属性并且c1,c2,…ck是产生式右边文法符号的属性；或者。

在这两种情况下，我们都说属性b依赖于属性c1,c2,…,ck.

二、属于属性文法的处理方法

1、处理过程：输入串→语法树→依赖图→语义规则计算次序→计算结果，这种由源程序的语法结构所驱动的处理办法就是语法制导翻译法。

2、依赖图：在一颗语法树中的结点的继承属性和综合属性之间的相互依赖关系可以用称作依赖图的一个有向图来描述。

3、一遍扫描的处理方法：一遍扫描的处理方法是在语法分析的同时计算属性值，而不是语法分析构造语法树之后进行属性的计算，而且无需构造实际的语法树。

三、S-属性文法的自下而上计算

S—属性文法，它只含有综合属性。综合属性可以在分析符号串的同时由自上而下的分析器来构造。分析器可以保存与栈中文法符号有关的综合属性值。每当进行归约时，新的属性值就由栈中正在归约的产生式右边符号的属性值来计算。可以通过扩充分析器中的栈来存放这些综合属性值。S-属性文法的翻译器通常可借助于LR分析器实现。

S属性的自下而上计算：

将LR分析器增加一个域来保存综合属性值 val[top] = Z.z  val[top-1] = Y.y val[top-2] = X.x

若产生式A →XYZ的语义规则是：A.a := f (X.x, Y.y, Z.z)，

那么归约后：val[top-2] = f (val[top-2] , val[top-1] , val[top] )     top = top - 2

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

一、中间代码产生

1、逆波兰式：把运算量（操作数写在前面），把算符写在后面，所以也成为后缀式。

用逆波兰表示法表示表达式，最大的优点是易于计算机处理表达式。

2、图表示法：包括抽象语法树与无循环有向图（DAG）。

      DAG与抽象语法树基本上一样，对表达式中的每个子表达式，DAG中都有一个结点。一个内部结点表示一个操作符，它的孩子表示操作数。两者所不同的是，在一个DAG中代表公共子表达式的结点具有多个父结点，而在一棵抽象语法树中公共子表达式被表示为重复的子树。

3、三元式：

（1）、三元式由三个部分组成：           算符：OP  、  第一运算分量：ARG1   、   第二运算分量：ARG2（2）、各种语句都可表示成一组三元式     例1：              OP   ARG1   ARG2      x+y*z      (1)     *       y         z

                     (2)     +      x        (1)

4、四元式：

四元式的4个组成成分为：操作符OP、第一运算分量ARG1、第二运算分量ARG2、操作结果Result。

二、基于语法制导的翻译

1、条件跳转的三地址实现方法：

    对于跳转采用四元式的形式实现。把四元式存入一个数组中，数组下标就代表四元式的符号，并约定：

    四元式（jnz,a,_,p）  表示 if a goto p

    四元式（jrop,x,y,p）表示 if x rop y goto p

    四元式（j,_,_,p）      表示 goto p

2、控制语句中布尔表达式的翻译：

    出现在条件语句if-then，if-else-end，while-do的布尔表达式E，它的作用仅在于控制对S1和S2的选择。

    作为条件转移的E，仅把E翻译成代码：一串条件转移和无条件转移的四元式。

    生成代码为：if E goto E.true

                       goto E.false

3、数组元素的赋值过程中的中间代码的描述

（1）、数组元素的地址计算过程

           若数组A的元素存放在一片连续单元里，则可以较容易的访问数组的每个元素。假定数组的每个元素的宽度为w，则一维数组A[i] 这个元素的起始地址为：base + (i – low)*w             其中，low为数组下标的下界， base是分配给数组的相对地址，即base为A的第一个元素A[low]的相对地址。        base + (i – low)*w   可整理为：  i*w + (base –low*w)  其中：     （1） i*w  是随数组下标变量而变化的部分,记为VARPART ;

    （2）（base – low*w)是在数组中不变化的常数记为CONSPART

（2）、二维数组

    若二维数组A按行存放，则可用如下公式计算A[i1,i2]的相对地址：base + (( i1 – l1)*d2 + i2 – l2) *w    其中，l1、l2分别为i1、i2的下界；di界差。若ui为i的上界，则di=ui – li +1.假定i1,i2是编译时唯一尚未知道的值，我们可以重写上述表达式为：( base –（ (l1 *d2) + l2) *w）+ ( (i1*d2) + i2) *w。( base –（ (l1 *d2) + l2) *w）为CONSPART，( (i1*d2) + i2) *w为 VARPART。                             其中:前一项子表达式( base – （(l1 *d2) + l2) *w ）的值是可以在编译时确定的记为常数CONSPART。

     后一子项随i1, i2 而改变是一个变数记VARPART。

课后习题：

学习心得：

第六章和第七章重点部分跟前几章比较来说不多，也不是很难，所以理解上比较容易。第七章的逆波兰、三元式、四元式以及将程序翻译为四元式这些题，在理解的基础上并不难做题，主要靠认真细心。通过做题来巩固对知识的理解，加强运用，毕竟实践出真知。