第六、七章属性文法与语法制导翻译+语义分析和中间代码产生
知识点
第六章
1.属性文法
①为文法符号E引进属性符号val，用E.val表示E的值
②属性计算规则以赋值语句的形式给出，附在每个产生式后，用花括号括出
③为表明同一符号不同的出现位置，用上角标区分
④终结符的值由词法分析程序提供
2.属性及分类
属性代表与文法符号相关信息（例如其类型，值，代码序列……）
属性分为综合属性与继承属性
综合属性
①用于“自下而上”传递信息
②在语法树中，一个结点的综合属性的值，由其子结点的属性值确定
继承属性
①用于“自上而下”传递信息。
②在语法树中，一个结点的继承属性由此结点的父结点和/或兄弟结点的某些属性确定
3.语义规则
属性计算的过程即是语义处理的过程
对于文法的每一个产生式配备一组属性的计算规则，则称为语义规则
在一个属性文法中，对应于每个产生式A都有一套与之相关联的语义规则，每条语义规则的形式为：
b:=f(c1,c2,…,ck)
这里f是一个函数，而且或者
(1)b是A的一个综合属性并且c1,c2,…ck是产生式右边文法符号的属性；或者
(2)b是产生式右边某个文法符号的一个继承属性并且c1,c2,…ck是A或产生式右边任何文法符号的属性在这两种情况下，我们都说属性b依赖于属性c1,c2,…,ck.
①终结符只有综合属性，它由词法分析器提供
②非终结符既可以有综合属性也可以有继承属性，文法开始符号的所有继承属性作为属性计算前的初始值
③ 产生式右边符号的继承属性和产生式左边符号的综合属性都必须提供一个计算规则
④产生式左边符号的继承属性和产生式右边符号的综合属性不由所给的产生式的属性计算规则进行计算，它们由其它产生式的属性规则计算
4. 语法制导翻译法：这种由源程序的语法结构所驱动的处理办法就是语法制导翻译法
5.依赖图
在一颗语法树中的结点的继承属性和综合属性之间的相互依赖关系可以用称作依赖图的一个有向图来描述
如果在一棵语法树中一个结点的属性b依赖于属性c，那么这个结点处计算b的属性规则必须在确定c的语义规则之后使用
在为一棵语法树构造依赖图以前，我们为每一个包含过程调用的语义规则引入一个虚综合属性b，这样把每一个语义规则都写成
b:= f(c1,c2, …ck)依赖图中为每一个属性设置一个结点，如果属性b依赖属性c，则从属性c的结点有一条有向边连到属性b的结点
6.依赖图的构造算法
for分析树中每一个结点n
for 结点的文法符号的每一个属性a
为a在依赖图中建立一个结点；
for分析树中每一个结点n
for结点n所用产生式对应的每一个语义规则
b:=f(c1,c2,…ck)
for i :=1 to k
从ci结点到b结点构造一条有向边7.如果一属性文法不存在属性之间的循环依赖关系，那么该文法为良定义的。为了设计编译程序，我们只处理良定义的属性文法
8.属性的计算次序
一个有向非循环图的拓扑序是图中结点的任何顺序m1,m2, …mk,使得边必须是从序列中前面的结点指向后面的结点。也就是
说，如果mi→mj是mi到mj的一条边，那么在序列中mi必须出现在mj之前
一个依赖图的任何拓扑排序都给出一个语法树中结点的语义规则计算的有效顺序。这就是说，在拓扑排序中，在一个结点上，语
义规则b:=f（c1,c2,…ck)中的属性c1,c2…ck在计算b以前都是可用的
9. S属性的自下而上计算
S—属性文法，它只含有综合属性
综合属性可以在分析符号串的同时由自上而下的分析器来构造
分析器可以保存与栈中文法符号有关的综合属性值
每当进行归约时，新的属性值就由栈中正在归约的产生式右边符号的属性值来计算
可以通过扩充分析器中的栈来存放这些综合属性值
S-属性文法的翻译器通常可借助于LR分析器实现
10.L-属性文法的自顶向下翻译
L-属性文法
如果每个产生式A →X1 X2 … Xn 的每条语义规则计算的属性是A的综合属性；或者是Xj 的继承属性， 1 ≦j ≦ n, 但它仅依赖：该
产生式中Xj左边符号X1, X2, …, Xj-1的属性；A的继承属性
11. 翻译模式
翻译模式是语法制导定义的一种便于翻译的书写形式。其中属性与文法符号相对应，语义规则或语义动作用花括号｛ ｝括起来，
可被插入到产生式右部的任何合适的位置上
这是一种语法分析和语义动作交错的表示法，他表达在按深度优先遍历分析树的过程中何时执行语义动作
翻译模式给出了使用语义规则进行计算的顺序。可看成是分析过程中翻译的注释
12.设计翻译模式（根据语法制导定义）
条件：语法制导定义是L-属性定义
保证语义动作不会引用还没有计算的属性值
(1)只需要综合属性的情况
为每一个语义规则建立一个包含赋值的动作，并把这个动作放在相应的产生式右边的末尾
(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。
应用
总结
第六章感觉是学过编译原理最难最难理解的部分，做题也很难理解；对于第七章就很简单了，概念很好理解，只不过就是概念挺多，不过做起题来就很容易。