Vincent Chan 的巴士站 🚉

编译原理学习笔记 1:解析数学表达式

说到编译原理,是计算机科学里面很重要的一个学科,你可以说编译原理无处不在。但是一般人很少可以接触到这样的理论。编译原理分前端和后端,前端包括文本解析和类型检查,后端包括优化和代码生成等等。这篇日志里我主要讨论文本解析中一个最为简单的部分:数学表达式。

数学表达式: 1 + 1 * 3 * 3 + 4 / 4 * 5

要求出这个表达式的值,不禁让我想起了当时学习数据结构时候的习题,这样的表达式用栈来解决。

我们先要列出一个表,包括各种算术符的优先级

符号 优先级
+ 1
- 1
* 2
/ 2

然后我们需要两个栈,一个操作符的栈名为OP_STACK 一个数字的栈,名为NUM_STACK

因为我们的操作符都是耳目操作符,就是操作符左右都为值,比如说 1 * 1里面 1* 或者 *1 都是没有意义的,所以我们是一个数字,一个符号这样间隔读入的,这样就好办了:

  1. 把第一个数字入NUM_STACK
  2. 这时,读入(SHIFT)的是一个操作符,如果OP_STACK顶为空,则入栈OP_STACK,如果不为空,则和OP_STACK栈顶比较,如果比OP_STACK栈顶优先级高,则入栈OP_STACK,否则的执行REDUCE操作,OP_STACK栈顶操作符出栈,NUM_STACK出栈两个数字,然后运算结果,再将结果入栈NUM_STACK,循环操作

操作流程如下:

表达式 NUM_STACK OP_STACK 对比结果 对应的操作
1+1*3*3+4 NUL NUL SHIFT
*3*3+4/4*5 1 1 + > SHIFT
*3+4/4*5 1 1 3 + * = REDUCE
*3+4/4*5 1 3 + > SHIFT
+4/4*5 1 3 3 + * = REDUCE
+4/4*5 1 9 + = REDUCE
+4/4*5 10 NUL SHIFT
/4*5 10 4 + > SHIFT
*5 10 4 4 + / >= REDUCE
*5 10 1 + > SHIFT
NUL 10 1 5 + * REDUCE
NUL 10 5 + REDUCE
NUL 15 NUL

这样马上我们就算出结果了,然而编译有时并不要求我们马上算出结果,有时只需要我们保存解析的结果,以便以后运行,或者生成代码等等操作,请看下面的表达式:

a + b * c

显然我们没办法马上算出结果,但是我们可以把它变成一棵树

parse tree

显然这样就容易多了,这就是我们要说的解析(parsing),如何解析呢?方法其实和上面是一样的,不过要做一点点改动,我们知道乘法优先级比较高,当我们计算b * c的时候,我们并不是真的相乘,我们只是创建一个新的结点,把b和c作为子节点,然后把这个新结点入栈,就可以了。

有了这科语法树之后,当我们知道a b c的值之后,就可以递归算出结果了,我们要计算根节点的结果,就要首先计算子节点的结果,最后回溯可得答案。当然,从另一方面,你可以通过这棵树生成中间代码,或者机器码,这样就编译出真正的程序了。