Topic 3：抽象语法¶
约 740 个字 1 张图片 预计阅读时间 2 分钟
1. 属性文法¶
编程语言由两个基本部分组成：语法/Syntax 和语义/Semantics。语法定义了什么样的字符序列是合法的程序，关注的是程序的结构和形式；语义定义了一个合法程序的行为和意义，关注的是程序的功能和逻辑，基本分为三种：
- 操作语义/Operational Semantics：关注程序如何执行/How can we execute a program?
- 公理语义/Axiomatic Semantics：关注可以通过逻辑证明的程序属性/What can we prove about a program?
- 指称语义/Denotational Semantics：关注程序所计算的数学函数/What math function does the program compute?
编译器的职责就是在将程序从一种语言翻译到另外一种语言的同时，必须保持其原始的语义。
属性文法/Attribute Grammar 简单说来是上下文无关文法、属性和属性计算规则的结合，核心思想是使用属性描述语义信息，使用语义规则描述属性之间的关系，将语义规则和语法规则相结合：
- 属性：描述文法符号的语义特征，比如变量类型和值，比如非终结符 \(E\) 的属性 \(\mathrm{val}\)；
- 属性计算规则/语义规则：和产生式相关联，反映文法符号属性间关系的规则，比如如何计算非终结符 \(E\) 的属性 \(\mathrm{val}\)。
- 可以通过 Parser 生成器支持的语义动作/Semantic Action 实现。
属性文法的潜在应用：
- 推导类应用：类似程序分析，在语法分析的同时，推导出程序的语义属性；
- 生成类应用：抽象语法树生成，中间代码甚至汇编代码生成。
2. 语义活动¶
每一个终结符和非终结符都可以关联自己的都可以有自己的语义值/Semantic Value，将其语义值类型称为其关联类型，比如对于 \(A \rightarrow B C D\)，语义动作返回值的类型必须是 \(A\) 的关联类型，这个值可以从 B、C、D 的语义值计算得到。在编译期可以直接计算下面的值：
在递归下降解析中，语义动作其实是 Parsing Function 返回的值，或者是这些函数的副作用，或者干脆两者都有。我们在 Yacc 中，在花括号里面写的就是语义动作。
对于语义动作的实现方面，Yacc 生成的解析器保持一个栈存放语义值，这个栈和状态栈其实是平行/同步的。当解析器执行一次规约的时候，其必须执行对应的 C 语言实现的语义动作。至于同步的含义，当状态站弹出 k 次的时候，语义栈也弹出 k 次，并且同步压入新的语义值。