编译原理(四):语义分析

本文最后更新于:3 个月前

编译原理系列第四篇,完结!

编译原理(四):语义分析

介绍

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

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

以 Python 举例来说:

  1. 'a' + 'a' 是符合语法规则、语义规则的
  2. 0 + 'a' 虽然也符合语法规则,但是不符合语义规则,因为整数与字符串不能相加。
  3. 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> 组成,这样来辅助语义动作的计算。我们来看看整个语法制导翻译的过程(注意,这里应该要先做个分析表,我懒得再写了,这里省略,直接看图做计算):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
输入: 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,然后给语义分析器分析,生成中间表示,继续后面的流程。

最后再来看这个图:

我们把前端部分讲完了,编译原理后面还有一些其他内容,就是后端相关的,在我的这个系列中就不多说了,包括什么代码生成啊、代码优化啊,主要还是如果源程序是翻译为汇编语言的话,会有很多细节与技术需要掌握,橘友们要是有兴趣可以自己查找资料学习,不管是公开课啊,还是龙书、虎书、鲸书,需要的话都可以啃啃。

这里放出思维导图,供橘友们参考:

完结,撒花!


下个系列回归到网络安全相关
准备搞点好玩的事情