[toc]
## 基础知识
- 属性：编程语言的任意特性，包括数据类型、值、目标代码等
- 静态属性如有效位数
- 动态属性如动态分配的变量位置
- 属性联编（绑定）
- 属性计算及将计算值与语言结构联系的过程花费的时间称为联编时间
- 语义规则与产生式相联系的两种表示方式
- 语法制导定义：属性直接与语言的文法符号相联系。抽象、无需指明计算次序、易于理解。
- 翻译方案：将语义动作嵌入产生式右部合适的位置。指明语义规则计算次序，实现更高效
- L-属性分析：所有不用显示构造分析树而完成的翻译。从左向右，包括所有在语法分析过程中完成的翻译方案
- S-属性分析：自底向上分析，是L-属性可处理文法的子集
- 属性与CFG文法符号关联，规则与CFG产生式关联
- 综合属性：子结点属性值的综合。所有符号都有。
- 继承属性：父、兄结点的属性计算得到。仅开始符以外的非终结符拥有。
- 语义规则通过计算次序决定了属性的依赖关系
- 每个文法符号的继承属性集和综合属性集的交集为空
- 语义规则函数通常是表达式（也可以是过程调用或程序段来产生副作用，如打印和标注）
- 只包含综合属性的SDD称为S属性的SDD
- 属性文法：语义规则函数无副作用的语法定义。以表格表示，下标区分同名文法符号，一个产生式可能对应0或多个语义规则
- 一个文法符号可以有多个属性值，不是所有文法符号都要为相同属性计算属性值
- 注释语法分析树标注属性值
- 自底向上可以注释综合属性
- 同时具有继承属性和综合属性的SDD可能需要多次遍历
- 对SDD的一个有向无环图（DAG）子类，可以用拓扑排序确定求值顺序
- 依赖图
- 由分析树上的依赖关系决定
- 有向边的终点属性依赖于起点属性
- S属性的SDD适应于自底向上的过程；L属性的SDD适应于自顶向下的过程。都确定是无环
- S属性的SDD
- 每个属性都是综合属性
- 可以按照任何自底向上的顺序计算各个属性值（后序遍历，属性中间值存放于分析栈）
- L属性的SDD
- 产生关联的每个属性间，边总是从左到右
- 也即每个继承属性只依赖于父节点关联的继承属性、左侧文法符号实例相关的继承或综合属性、来自同一实例的无环属性
- 属性文法没有副作用，支持与依赖图一致的顺序；翻译方案从左到右求值，允许包括程序片段
- 语义动作同样受限于位置依赖。可以通过添加隐式约束（如从左向右计算）或避免约束求值来控制副作用
- 抽象语法树的构造
- 语法树不同于分析树，后者只是一个抽象的概念，后者是实际的构造
- 每个结点都有一个标号字段op
- 结点创建时需要有相应个数附加字段
- S属性构建中，非终结符都有一个综合属性结点
- L属性构建中，子表达式元素出现在不同子树时需要引入继承属性
- 语法分析树和抽象语法树的差异也会引入继承属性，如类型表达式
- 语义动作表示为{动作}，其中的文法符号需要加引号，执行时间为（在产生式右部中）其左边所有的文法符号已匹配后
- 任何SDT都可以通过先序遍历语法树实现：LL分析实现L属性SDD；LR分析实现S属性SDD
- 后缀SDT中，综合属性可以通过自下而上的分析器在分析时完成
- 前缀SDT可能无法在自底向上或自顶向下的语法分析中实现（但可以在得到语法树后先根遍历实现）
- 产生式内部带有语义动作时，如对于产生式$B\rightarrow X{a}Y$
- 若语法分析过程自底向上，则当X出现在栈顶时执行a
- 若语法分析过程自顶向下，则在试图展开非终结符Y或检测到输入终结符Y时执行a
- 标记非终结符：$B\rightarrow XNY, N\rightarrow\epsilon {a}$
- 使所有嵌入动作都变为后缀，但会引入额外结点表示动作
- 语法分析过程可以实现S属性及L属性SDT
- 对任意SDT，可以先忽略语义动作产生语法分析树，再对每个结点一致地加入产生式右部的各个动作。之后先序遍历即可
- 消除左递归
- 简单情况下可以看成终结符处理
- 复杂情况下参考表达式文法的构造，先对文法本身消除左递归，再对新变量引入综合属性和继承属性
- 对L属性定义的SDT
- 语义动作附加在语法分析树上，前序遍历时执行动作
- 对L属性的SDD，把非终结符A继承属性的计算动作插入紧靠A之前的位置，把产生式左部综合属性的计算动作放在产生式右部最右端
- 每个非终结符都有一个输入参数为继承属性、返回值为综合属性的函数，函数体中将产生式体非终结符的继承属性、产生式头非终结符的综合属性作为局部变量保存（但可能要反复传递大体积属性）
- 边扫描边生成代码的前提是：存在一个是综合属性的属于一个或多个非终结符的主属性，且主属性将各个非终结符按序连接。
- 要求基础文法是LL文法
- 在分析栈增加记录动作记录（即将被执行的语义动作）和综合记录（非终结符的综合属性值）
- 非终结符的继承属性放在该终结符的栈记录中，计算继承属性的代码放在紧靠于上的动作记录中
- 非终结符的综合属性放在紧靠于下的单独位置作为综合记录
- 动作记录存放被执行动作代码指针，或存放在综合记录内。动作可以包括拷贝属性至栈内任意位置记录
- 局限：不能处理LR文法产生式。考虑$A\rightarrow BC$，$B$的继承属性$B.i$可能依赖于$A$的属性，但此时$A$的继承属性未知
- 引入标记非终结符及其产生式，从而所有动作都位于产生式最右端
- 假设$a$被关联到$M\rightarrow\epsilon$上，则将$a$需要的所有属性拷贝为$M$的继承属性，按$a$中方法计算出的所有属性作为$M$的综合属性
- 综合属性记录在符号对应的记录中，继承属性出现在紧靠对应符号的下方（或存放于该位置的非终结符记录中）