6.2 语义分析——属性文法

形式文法描述形式语言的基本想法是，从一个特殊的初始符号出发，不断的应用一些产生式规则，从而生成出一个字串的集合。产生式规则指定了某些符号组合如何被另外一些符号组合替换。

所有的文法分成四种类型：无限制文法、上下文相关文法、上下文无关文法和**正规文法**

对于规则 V->w，上下文无关文法取名为“上下文无关”的原因就是因为字符 V 总可以被字串 w 自由替换，而无需考虑字符 V 出现的上下文。一个形式语言是上下文无关的，如果它是由上下文无关文法生成的。

上下文无关文法重要的原因在于它们拥有足够强的表达力来表示大多数程序设计语言的语法；实际上，几乎所有程序设计语言都是通过上下文无关文法来定义的。另一方面，上下文无关文法又足够简单，使得我们可以构造有效的分析算法来检验一个给定字串是否是由某个上下文无关文法产生的。例子可以参见LR 分析器和LL 分析器。

属性文法：为上下文无关文法赋予语义

上下文无关文法是不含任何语义的，其中的语义是我们赋给它的，比如对于一个 ID，想知道它的类型，那么就赋于它一个类型属性

上下文无关文法在表达语法方面是足够的，但在表达语义方面是不够的，要表达语义，那么需要使用到上下文相关文法，比如一个变量我们要求先声明才能使用，即这个变量依赖于之前它有没有被声明。

但是上下文相关文法的复杂度很高，即使上下文无关文法不够用了，也不愿意去用前者，因此引入了属性文法：在上下文无关文法的节点上赋予一个属性，在构建语法树的过程中计算属性，从而得到了语义。

关键：安排好语义信息在语法分析树上的流动【DFS】

之前在 Antlr 都是离线遍历，即先构造了语法树，再去遍历一遍。

属性文法的想法是在构建的过程中就处理属性，减少一次对语法树的遍历：下面的 {a} 就是要执行的动作 ，相当于在离线处理中在 exitX() 后进行动作 a

例子1

对 exp 赋予 val 值，因为每个 exp 的 val 都依赖它的子节点，那么要计算得到 exp 的值，只需要在 exp 文法的右部最右部执行动作即可，也即当子节点都完成后再执行动作

code

上面的 members 会在编译后完全地拷贝到生成的 parser 文件中，因为是生成 java 文件，所以这里也是用 java 写的内容【但没有代码提示】，这样我们就能在 g4 文件中使用这嵌入的 java 代码了

同时插入的动作都是写 java 代码

expr 有 val 属性，要引用时，使用 $expr.val 即可。前提是在 expr 文法处写明它的返回值 expr returns [int val]，用中括号

直接 $val 表示在引用左部的 expr 的 val

其中的 getOrDefault 是 java8 开始的 HashMap 中的方法：取不到就返回默认值

在 main 中不需要 listener,visitor，而是在构建语法分析树的过程中就把上面的动作执行了

例子2

CSV 解析器

要求第一行是表格的列名，后面是表格的内容

​

因为要得到总的行数，所以每个 row 被识别出来后就要有个统计行号++，并在最后输出这个行数的动作

要输出每行的 values，只有 row 不能得到列名，列名信息在 hdr 中，因此需要使用继承属性来传递列名

code

文法：

动作：

+= 所以最终 rows 可以得到一个 row 节点的 list

locals 表示局部变量

@init 表示在还没有匹配 row 的时候进行初始化动作

@after 是在匹配一次后执行的操作

继承属性是通过参数的形式传递的，如 row[$hdr.text.split(",")] 就是把 hdr 分隔得到的 String[] 传递给 row ，因此在 row 处会用 row[String[] columns] 表示传入的参数

事实上，实践中将 java 和 g4 分开来写更好，即使用之前的离线分析（listener,visitor）更好，上面这样的属性文法，会导致 g4 文件可读性很差，因此 Antlr4 作者也不建议这种方式，但工业上为了性能，还是会有人这样来写。

理论

SDD

• SDD 唯一确定了语法分析树上每个非终结符节点的属性值

• SDD 没有规定以什么方式、什么顺序计算这些属性值

S 属性定义的依赖图刻画了属性实例之间自底向上的信息流动

上面是乘法的文法规则的右递归写法【因为T→T*T会有歧义，不确定是左结合还是右结合】；其中第二行的 T₁ 只是与左边的 T 相区分，并不是一个新的终结符

右递归的乘法会导致乘法是右结合的，但是我们可以通过调整语义规则来达到左结合的效果，如下使用继承属性和综合属性：【即在向下传递信息的过程中就已经开始计算了】

到 X_i 的时候，前面的节点都已经计算完了，因此可以依赖它们

例子1：

例子2：

例子3：

只使用 S 属性即可

例子4：

SDT

左边即 SDD，右边为 SDT，即将 SDD 描述的语义规则翻译成动作嵌入

S 属性后缀翻译方案

例子：

因为节点属性的计算仅仅取决于子节点或本身

实践代码见上面的 CSV 例子

L 属性翻译方案

对于 L 属性定义：

原则: 从左到右处理各个 X_i 符号 对每个 X_i , 先计算继承属性, 后计算综合属性

递归下降子过程 A → X1 · · · Xi · · · Xn

1. 在调用 Xi 子过程之前, 计算 Xi 的继承属性

   • 实践中：以 Xi 的继承属性为参数调用 Xi 子过程

2. 在 Xi 子过程返回之前, 计算 Xi 的综合属性

   • 实践中：在 Xi 子过程结束时返回 Xi 的综合属性

例子：XY*

伪代码：

关于右递归

对于不支持其他左递归的生成器，要想生成编译器，那么需要改写文法为右递归。

但是在左递归中的 S 属性定义，会在改写后的右递归中变成 L 属性定义。示例如下：

继承属性来计算，综合属性往回传