《自己动手写 Python 虚拟机》_更理解虚拟机的意义_2.3 文法分析

【摘要】 本书摘自《自己动手写 Python 虚拟机》一书中第2章，第3节，海纳编著。

2.3 文法分析

从文本文件中分析出程序的基本元素——token 以后，编译器就要尝试着去理 解这些 token 之间的关系。我们知道 token 之间是有其内在的逻辑关系的，例如加 法符号的前后都必须是一个可以执行加法操作的目标，可以是一个数字，也可以是一 个变量，但加号后面却一定不能紧跟一个乘号。编译器要分析这些 token 组成的序 列是否有意义，是由文法分析完成的。

文法分析主要有两大类算法， 一种是自顶向下的分析方法， 一种是自底向上的分 析方法。其中，自顶向下的分析方法的算法简单直接，易于理解和编写。因此，这里 就以自顶向下的分析方法为主来介绍文法分析器是如何工作的。自顶向下的分析方 法也被称为递归下降的分析方法。

做软件设计的时候， 一直在做的一件事情，就是把一个大的问题化解为各个小的 问题。比如，设计一个网站服务器，也是把它分成不同的模块，然后每个模块下面再 设计各个不同的组件，组件下面再进行更细的划分。这就是一种自顶向下的任务分 解。在文法分析中，本质上也采用了同样的分析思路。

1. 拆分化简问题

最顶部的任务，算一个表达式。 一个表达式，也就是多项式，是由每个项求和(差 与和的原理一样，为了描述方便，只说和的情况)得到的。可以简化为一个 expres- sion 如下：

expression:=term +term +. +term

等式右边的 term 是一个求和式中的各个加数。例如，2+3*4+5,可以把这个 式子看成2与3*4与5的求和。其中，2是一个 term,3*4 也是一个 term,5 也是 一个 term。

同样的，拆分 term,term 可以看成是多个因子的积。按上面的方法，可以化简 term 的规模如下：

term:=factor *factor ...*factor

左边的 term 是一个规模比较大的积，而右边的一个 factor 代表一个因子。这 样，就把 term 这个结构拆成了规模更小的因子了。因子 factor 又怎么定义，从而进

行规模的化简呢? factor 定义如下：

facotr:=NUMBER|(expression)

中间的竖线表示“或”的关系，也就是说， 一个 factor 可以是一个整数，也可以是 一个包在括号里的表达式。反过来说，当遇到一个整数，就可以认为它是一个 fac- tor, 或者用括号括起来的表达式也是一个 factor。

注意，尝试使用 term 去解构 expression, 使用 factor 去解构 term, 结果又发现 factor 还要 expression 去解构，绕了一圈又绕回来了。这种用自己的定义来定义自 己的情况就是递归。

但是递归不能没有终止，要使得递归的定义变得完整，就必须满足以下两个 条件：

① 子问题必须与原始问题同样性质，且规模更小，更简单；

② 不能无限制地调用本身，须有个出口，化简为非递归状况处理。

例子中，子问题的规模是不断缩小的，这一点没有问题。第二点，必须有个出口， 这个出口是什么呢?其实就是 factor 的定义，当把问题拆到只有一个整数的时候，递 归就终止了，也就是条件②中所说的出口。

2. 转换成代码

定义这样的三个函数：expr、term 和 factor,expr 表示对表达式求值，term 表示 对表达式中的某一项求值，factor 表示对某一个因子求值。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们 18664393530@aliyun.com 处理，核实后本网站将在24小时内删除侵权内容。