第七章 属性文法和语法制导翻译
第一部分：属性文法及属性计算方法
1 属性文法
以上下文无关文法为基础；
为每个文法符号（终结符或非终结符）配备若干相关的“值”（称为属性），代表与文法符号相关信息，如类型、值、代码序列、符号表内容等；
对于文法的每个产生式都配备了一组属性的语义规则，对属性进行计算和传递。
2 综合属性
自下而上传递信息；
语法规则：根据右部候选式中的符号的属性计算左部被定义符号的综合属性；
语法树：根据子结点的属性和父结点自身的属性计算父节点的综合属性。
3 继承属性
自上而下传递信息；
语法规则：根据右部候选式中的符号的属性和左部被定义符号的属性计算右部候选式中的符号的继承属性；
语法树：根据父结点和兄弟节点的属性计算子结点的继承属性。
4 属性依赖
对应于每个产生式A→α都有一套与之相关联的语义规则，每条规则的形式为(f是一个函数)：
b:=f(c1,c2,…,ck)
属性b依赖于属性c1,c2,…,ck：
b是A的一个综合属性并且c1,c2,…,ck是产生式右边文法符号的属性，或者
b是产生式右边某个文法符号的一个继承属性并且c1,c2,…,ck是A或产生式右边任何文法符号的属性。
终结符只有综合属性，由词法分析器提供；
非终结符既可有综合属性也可有继承属性，文法开始符号的所有继承属性作为属性计算前的初始值。
5 语义规则
对出现在产生式右边的继承属性和出现在产生式左边的综合属性都必须提供一个计算规则。属性计算规则中只能使用相应产生式中的文法符号的属性。
出现在产生式左边的继承属性和出现在产生式右边的综合属性不由所给的产生式的属性计算规则进行计算，由其它产生式的属性规则计算或者由属性计算器的参数提供。
语义规则所描述的工作可以包括属性计算、静态语义检查、符号表操作、代码生成等。
6 带注释的语法树
在语法树中，一个结点的综合属性的值由其子结点和它本身的属性值确定，使用自底向上的方法在每一个结点处使用语义规则计算综合属性的值，仅使用综合属性的属性文法称S－属性文法。
在语法树中，一个结点的继承属性由其父结点、其兄弟结点和其本身的某些属性确定，用继承属性来表示程序设计语言结构中的上下文依赖关系很方便。
7 基于属性文法的处理方法
语义规则的计算：
产生代码；
在符号表中存放信息；
给出错误信息；
执行任何其它动作。
对输入串的翻译就是根据语义规则进行计算。
由源程序的语法结构所驱动的处理办法就是语法制导翻译法。
基于属性文法的处理方法有依赖图、 树遍历、一遍扫描。
8 依赖图
在一棵语法树中的结点的继承属性和综合属性之间的相互依赖关系可以由依赖图(有向图)来描述。
为每一个包含过程调用的语义规则引入一个虚综合属性b，这样把每一个语义规则都写成b:=f(c1,c2,…,ck)的形式。
依赖图中为每一个属性设置一个结点，如果属性b依赖于属性c，则从属性c的结点有一条有向边连到属性b的结点。
依赖图的构建算法：
1 | for 语法树中每一结点n do |
依赖图示例:
如果一属性文法不存在属性之间的循环依赖关系，则称该文法为良定义的；
一个依赖图的任何拓扑排序都给出一个语法树中结点的语义规则计算的有效顺序。
属性的计算次序：
基础文法用于建立输入符号串的语法分析树；
根据语义规则建立依赖图；
根据依赖图的拓扑排序，得到计算语义规则的顺序。
9 树遍历
通过树遍历的方法计算属性的值：
假设语法树已建立，且树中已带有开始符号的继承属性和终结符的综合属性，以某种次序遍历语法树，直至计算出所有属性。
深度优先，从左到右的遍历。
树遍历算法：
1 | While 还有未被计算的属性 do |
树遍历算法示例：
考虑属性的文法G(S)，其中，
S有继承属性a，综合属性b，
X有继承属性c、综合属性d，
Y有继承属性e、综合属性f，
Z有继承属性h、综合属性g。
10 一遍扫描（效率较高）
一遍扫描在语法分析的同时计算属性值，取决于所采用的语法分析方法和属性的计算次序。
所谓语法制导翻译法，直观上说就是为文法中每个产生式配上一组语义规则，并且在语法分析的同时执行这些语义规则。
语义规则被计算的时机：
自上而下分析，一个产生式匹配输入串成功时；
自下而上分析，一个产生式被用于进行归约时 。
抽象语法树：
抽象语法树(Abstract Syntax Tree，AST)，在语法树中去掉那些对翻译不必要的信息，从而获得更有效的源程序中间表示。
建立表达式的抽象语法树：
mknode(op, left, right) 建立一个运算符号结点，标号是op，两个域left和right分别指向左子树和右子树；
mkleaf(id, entry) 建立一个标识符结点，标号为id，一个域entry指向标识符在符号表中的入口；
mkleaf(num, val) 建立一个数结点，标号为num，一个域val用于存放数的值。
建立抽象语法树的语义规则：
E→E1+T 转换为 E.nptr := mknode('+', E1.nptr, T.nptr )
E→E1-T 转换为 E.nptr := mknode('-', E1.nptr, T.nptr )
E→T 转换为 E.nptr := T.nptr
T→id 转换为 T.nptr := mkleaf ( id, id.entry )
T→num 转换为 T.nptr := mkleaf ( num, num.val )
示例：
第二部分：语法制导翻译方法和翻译模式的设计
11 S-属性文法
S-属性文法：只含有综合属性。
在自下而上的分析器分析输入符号串的同时计算综合属性，
分析栈中保存语法符号和有关的综合属性值，
每当进行归约时，新的语法符号的属性值就由栈中正在归约的产生式右边符号的属性值来计算。
示例：
12 L-属性文法
S－属性文法适合一遍扫描的自下而上分析；
L－属性文法适合一遍扫描的自上而下分析。
一个属性文法称为L-属性文法，如果对于每个产生式A→X1X2…Xn，其每个语义规则中的每个属性或者是综合属性，或者是Xi(1≤i≤n)的一个继承属性且这个继承属性仅依赖于：
(1) 产生式中Xi左边符号X1，X2，…，Xi-1的属性；
(2) A的继承属性。
S-属性文法一定是L-属性文法
L－属性文法按照深度优先遍历语法树，计算所有属性值，与LL(1) 自上而下分析方法结合，深度优先建立语法树，按照语义规则计算属性。
13 翻译模式
语义规则：给出了属性计算的定义，没有属性计算的次序等实现细节。
翻译模式：给出使用语义规则进行计算的次序，把实现细节表示出来。
在翻译模式中，和文法符号相关的属性和语义规则（也称语义动作），用花括号{ }括起来，插入到产生式右部的合适位置上。
设计翻译模式的原则：
设计翻译模式时，必须保证当某个动作引用一个属性时它必须是有定义的，L-属性文法本身就能确保每个动作不会引用尚未计算出来的属性。
当只需要综合属性时，为每一个语义规则建立一个包含赋值的动作，并把这个动作放在相应的产生式右边的末尾。
如果既有综合属性又有继承属性，在建立翻译模式时就必须保证：
- 产生式右边的符号的继承属性必须在这个符号以前的动作中计算出来；
- 一个动作不能引用这个动作右边的符号的综合属性；
- 产生式左边非终结符的综合属性只有在它所引用的所有属性都计算出来以后才能计算，计算这种属性的动作通常可放在产生式右端的末尾。
14 语义动作执行时机统一
把所有的语义动作都放在产生式的末尾，语义动作的执行时机统一。
转换方法：
加入新产生式M→𝜀，
把嵌入在产生式中的每个语义动作用不同的非终结符M代替，并把这个动作放在产生式M→的末尾。
15 消除翻译模式中的左递归
语义动作是在相同位置上的符号被展开（匹配成功）时执行的，为了构造不带回溯的自顶向下语法分析，必须消除文法中的左递归。
当消除一个翻译模式的基本文法的左递归时同时考虑属性计算，适合带综合属性的翻译模式。
假设有翻译模式：
A → A1Y {A.a:=g(A1.a, Y.y) }
A → X {A.a:=f(X.x) }
它的每个文法符号都有一个综合属性，用小写字母表示，g和f是任意函数。
基础文法消除左递归：
A → XR
R → YR
翻译模式消除左递归：
A → X {R.i:=f (X.x) }
R {A.a:=R.s}
R → Y {R1.i:=g(R.i, Y.y) } R1 {R.s:=R1.s}
R → 𝜀 {R.s:=R.i}
16 递归下降翻译器的设计
分析程序由一组递归子程序(函数)组成，每个非终结符对应一个子程序(函数)。
对每个非终结符A构造一个函数过程：
A的属性实现为参数和变量：
继承属性：对A的每个继承属性设置为函数的一个形式参数；
综合属性：实现为函数的返回值，若有多个综合属性，打包成作为结构或记录记录返回，为了简单，我们假设每个非终结只有一个综合属性；
A的产生式中的每一个文法符号的每一个属性：实现为A对应的函数过程中的局部变量。
非终结符A对应的函数过程中，根据当前的输入符号决定使用哪个产生式候选。
按照产生式右部从左到右的，对于单词符号（终结符）、非终结符和语义动作，分别实现：
对于带有综合属性x的终结符X，把x的值存入为X.x设置的变量中。然后产生一个匹配X的调用，并继续读入一个输入符号。
对于每个非终结符B，产生一个右边带有函数调用的赋值语句c=B(b1,b2,…,bk)，其中，b1,b2,…,bk是为B的继承属性设置的变量，c是为B的综合属性设置的变量。
对于语义动作，把动作的代码抄进分析器中，用代表属性的变量来代替对属性的每一次引用。