Chapter4 语义分析

Chiichen原创大约 9 分钟

介绍

又叫语义规则(Semantic Rule)
给定属性集合 $a_{1} ， . . ., a_{k}$
对于每个语法规则 $X_{0} \to X_{1} X_{2} . . . X_{n}$ ，每个语法符号 $X_{i}$ 的属性 $X_{i} . a_{j}$ 的值与规则中其他符号的属性值相关
属性等式就是如下格式 $X_{i} . a_{j} = f_{i j} (X_{0} . a_{1}, . . ., X_{0} . a_{k}, X_{1} . a_{1}, . . ., X_{1} . a_{k}, . . ., X_{n} . a_{1}, . . ., X_{n} . a_{k})$

Grammar Rule	Semantic Rules
Rule1	Associated attribute equations
...
Rule n	Associated attribute equations

[属性示意图.png]
[无符号数和数字属性.png]

[变量声明和数据类型属性1.png]
[变量声明和数据类型属性2.png]

依赖图的生成和计算顺序的确定
- 每一个属性等式对应一个依赖图(有向图，边代表属性值计算的计算依赖顺序)
- 多个属性等式构成一个组合依赖图，通过这个附着在抽象语法树或者分析树的依赖图可以对计算次序进行计算
综合(Synthesized)属性和继承(Inherited)属性
- 综合属性：属性由子节点属性决定(如果所有属性都是综合属性，那这个文法是一个综合属性文法 S-attributed grammar)，在 bottom-up 的过程中，可以边分析边计算属性(从叶子节点生成父节点)
- 继承属性：属性由兄弟节点或兄弟和子节点属性决定(不是综合就是继承)
在分析的过程中计算属性
- 属性计算的困难：
  - 属性语法是一种抽象规范，属性方程可以按任意顺序编写而不影响其有效性，它们不指定属性计算的顺序
  - 问题主要在于找到属性计算和分配的顺序，以确保每次计算中使用的所有属性值在执行每次计算时都可用
  - 属性方程本身表明属性计算的顺序约束。我们将使用依赖图来明确顺序约束

依赖图：
- 每个符号的每个属性 $X_{i} . a_{j}$ 对应一个节点
- 对于每个属性方程 $X_{i} . a_{j} = f_{i j} (\dots, X_{m} . a_{k}, \dots)$ 都有一条从右侧的每个节点 $X_{m} . a_{k}$ 到节点 $X_{i} . a_{j}$ 的边（表示 $X_{i} . a_{j}$ 对 $X_{m} . a_{k}$ 的依赖关系)

[依赖图和计算顺序1.png]
[依赖图和计算顺序2.png]

如果解析树中的所有依赖项都从子级指向父级，那么就是综合属性。
等价地，如果给定语法规则 $A \to X_{1} X_{2} \dots X_{n}$ ，左侧带有 $a$ 的唯一(不能存在另一个可能为从非子节点获取属性的属性方程)关联属性方程的形式为以下所示，那么 $a$ 就是综合属性 $A . a = f (x_{1} . a_{1}, . . X_{1} . a_{k}, \dots, X_{n} . a_{1}, \dots X_{n} . a_{k})$
[综合属性定义.png]

procedure PostEval(T:treenode)
begin
 for each child C of T do
 PostEval(C);
 compute all synthesized attributes of T;
end;

procedure PreEval(T:treenode);
begin
 for each child C of T do
 compute all inherited attributes of C;
 PreEval(C);
end;

[属性计算dtype1.png]
[属性计算dtype2.png]

[属性计算dtype3.png]
[属性计算dtype4.png]

属性的存储有三种方法：一是跟上面的一样，与属性节点绑定，二是作为函数的参数和返回值，三是存储在外部的数据结构中
有一些值在计算的过程中反复使用，如果用上面的方法，会在分析树中占用大量的空间来存储这些相同的属性值。
例如：
可以把属性作为函数的参数和返回值
事实上，一个单个递归遍历的函数中，通过前序遍历计算继承属性，后序遍历计算综合属性，可以将继承属性值作为参数传递给子级的递归调用，并接收综合属性值作为这些相同调用的返回值
例如，在十进制和八进制的语法中，base 是继承属性而 val 是综合属性，递归的属性计算函数为：

[属性计算basenum4.png]
[属性计算basenum5.png]

base 值作为一个共享的属性值，在每个节点都保存一个值会占用大量的空间，因此可以通过把这个属性作为参数进行传递
当属性值具有重要结构并且在翻译过程中的任意点可能需要时，数据结构（例如查找表、图表和其他结构）可能有助于属性值的正确行为和可访问性。主要数据结构之一是符号表，它存储与程序中声明的常量、变量和过程相关的属性

所有属性都是由综合属性或者满足特定条件的继承属性决定
L-Attributed grammar：满足从左至右计算，即对于一个语法规则： $\begin{matrix} X_{0} \to X_{1} X_{2} . . . X_{n} \\ 那么每个属性 X_{i} . a_{i} 都只能由比它靠前的属性计算出来 \\ 即 X_{i} . a_{i} = f (X_{0} . a_{1}, \dots, X_{0} . a_{k}, X_{1} . a_{1}, \dots X_{1} . a_{k}, \dots X_{i} - 1. a_{1}, \dots X_{i} - 1. a_{k}) \end{matrix}$
把综合属性作为返回值，继承属性作为传入参数