编译原理系列第四篇，完结！

编译原理（四）：语义分析

介绍

语义分析也称为类型检查、上下文相关分析。它负责检查程序（抽象语法树）的上下文
相关的属性，这是具体语言相关的，典型的情况包括：

变量在使用前先进行声明
每个表达式都有合适的类型
函数调用和函数的定义一致

以 Python 举例来说：

'a' + 'a' 是符合语法规则、语义规则的
0 + 'a' 虽然也符合语法规则，但是不符合语义规则，因为整数与字符串不能相加。
x += 1，符合语法规则，但是如果 x 之前没有“定义”过，那么就不能自加 1，不符合语义规则。

语法制导翻译

这里以自底向上的技术为例进行讨论，自顶向下的技术与此类似

概念

对于一个编译器来说，不仅仅只能回答一个输入 S 是否符合语法规则，应该还要做具体的处理，对于一个四则运算的语法分析器来说，要能计算出最后的答案。

回顾上一篇中，LR 算法在规约的时候，具体的操作是，弹出规则 2 的右部与栈中的状态，紧接着会有 goto 的动作，会有一个新的状态压入。那么很明显，刚才说的“计算”操作就应该在规约的时候之前完成，所以我们可以在每一条规则后面，新增一个“计算”操作。

所以语法制导翻译做起来非常简单，就是给每条产生式规则附加一个语义动作（本质上是一个代码片段）。语义动作在产生式归约的时候执行，即由右部的值计算左部的值。

实现原理

来看个例子：

1
2
3

0: S -> E      {S = E}
1: E -> E + E  {E = E1 + E2}
2:    | n      {E = n}

这里直接使用 LR(0) 算法即可，对于二义性的冲突，我们通过提示语法分析器来解决。

那么对应的状态转移图如下：

假设输入 S = 7+8+9。我们可以维护一个栈，栈里面是一个个三元组：<state, symbol, value> 组成，这样来辅助语义动作的计算。我们来看看整个语法制导翻译的过程（注意，这里应该要先做个分析表，我懒得再写了，这里省略，直接看图做计算）：

输入: S = 7+8+9$

stack = [(S, None, 0)]  # S 就是符号了，None 是 S 的值，0 是状态转移图的节点号
stack = [(S, None, 0), (7, 7, 1)]  # 读入 7，移进，此时符号是 7，那么值也就是 7，这个时候走到了节点 1
stack = [(S, None, 0), (E, 7, 2)]  # 这个时候，要开始规约了，弹出规则 2 右部，压入规则 2 的左部，这个时候需要注意，在弹出之前，要执行语义动作
stack = [(S, None, 0), (E, 7, 2), ('+', '+', 3)]  # 读入 +，移进，走到节点 3
stack = [(S, None, 0), (E, 7, 2), ('+', '+', 3), (8, 8, 1)]  # 读入 8，移进，走到节点 1
stack = [(S, None, 0), (E, 7, 2), ('+', '+', 3), (E, 8, 4)]  # 开始规约了，弹出规则 2 右部，压入规则 2 的左部，这个时候需要注意，在弹出之前，要执行语义动作
stack = [(S, None, 0), (E, 15, 2)]  # 我们提示语法分析器，+ 法具有做结合性，于是这个时候要开始规约，弹出规则 1 右部，压入规则 1 的左部，这个时候需要注意，在弹出之前，要执行语义动作
stack = [(S, None, 0), (E, 15, 2), ('+', '+', 3)]  # 读入 +，移进，走到节点 3
stack = [(S, None, 0), (E, 15, 2), ('+', '+', 3), (9, 9, 1)]  # 读入 9，移进，走到节点 1
stack = [(S, None, 0), (E, 15, 2), ('+', '+', 3), (E, 9, 4)]  # 开始规约，弹出规则 2 右部，压入规则 2 的左部，这个时候需要注意，在弹出之前，要执行语义动作
stack = [(S, None, 0), (E, 24, 2)]  # 开始规约，弹出规则 1 右部，压入规则 1 的左部，这个时候需要注意，在弹出之前，要执行语义动作
stack = [(S, None, 0), (E, 24, 2)]  # 读入 $，结束，不但可以得出接受这个结论，还可以得出 E = 24

总结

先说一些必要的解释。我思来想去，还是把语法制导翻译放在语义分析里讲比较合适，我认为，语法制导翻译是语义分析里比较特殊的一种，因为可以直接集成在语法分析器里。

或者这么说，如果一个编译器比较简单，比如上面那个只能做加法的计算器，那么语法制导翻译就可以胜任从语义分析器之后的所有功能，并且语法分析器就不需要生成 AST 了，改为集成语法制导翻译即可。但如果我们想写一门全新的编程语言，有各种骚操作，比如我想搞个 T 语言，那么目标代码就是汇编了，这个时候就比较复杂，因为各种语法规则繁多，如果集成在语法分析里，那么就会比较臃肿，这个时候最好老老实实地生成 AST，然后给语义分析器分析，生成中间表示，继续后面的流程。

最后再来看这个图：