浅谈表达式的求值（Vol.3 使用AST进行代码解析和运行）

本文同步发布于[Github Blog](https://tiger2005.github.io/post/qian-tan-biao-da-shi-de-qiu-zhi-vol3/)和[Zhihu](https://zhuanlan.zhihu.com/p/108698849) --- Update: 2020/5/29 22:45 本作为此系列的第三部分，前两部分可以从下面的索引进入。 [> Vol.1 后缀表达式](https://www.luogu.com.cn/blog/tiger2005/qian-tan-biao-da-shi-di-qiu-zhi-hou-zhui-biao-da-shi-post) [> Vol.2 进阶](https://www.luogu.com.cn/blog/tiger2005/qian-tan-biao-da-shi-di-qiu-zhi-jin-jie-post) **强烈建议** 先弄懂`Vol.1`的知识，`Vol.2`在此文中未被用到。 Update: 2020/5/29 23:01 加入关于 [P5067](https://www.luogu.com.cn/problem/P5067) 的思考以及模糊解决思路，详见文章末尾。 --- > 哪个OIer不想做出模拟C++解析器([UOJ 98](http://uoj.ac/problem/98))呢？ 我也有过这个梦想。 打开这道题的统计，稍稍扫过前10，虽然我们不能像第一一样使用很风骚的方式 AC 这一道题，但是我们可以利用表达式树解决（这个东西虽然慢，但是很鲁棒好想，对于没有接触过这种大模拟的人是不二之选）。 **前方高能，请务必确认你知道(抽象)表达式树**（**A**bstract **S**yntax **T**ree，简称 AST） 。如果不知道，看看这个系列的 `Vol.1` 就可以了。 那么，开始吧。 --- 首先，我们可以在题目的最后获得一份上下文无关文法，地址如下：[here](https://www.luogu.com.cn/paste/b7s6rtl0) 这看起来很头疼。我在这里给大家一个入门介绍（P.S.:其他上下文无关文法可能和这个有点不一样，但本质相同）。 举个例子吧。 ```cpp FUNC_AND_VAR ::= | ε | int NAME ( OPTPARAMS ) { STATEMENTS } FUNC_AND_VAR | int DEFINEVAR DEFINEVARS ; FUNC_AND_VAR ``` 这一块中，`::=`前面的是符号名字，这里是`FUNC_AND_VAR` 之后三行是 `FUNC_AND_VAR` 可能出现的三种情况，相当于 OR 运算。在其他上下文无关文法中会遇到用 `|` 分开的几种情况，本质是相同的。 第一行，$ε$ 字符代表“空空如也”，也就是空串。 第二行的意思是，开头是字符串 `int`，之后一个名字（也就是函数名），括号内装着函数的参数列表，之后大括号内装着一些语句。再然后又是 `FUNC_AND_VAR`。 第三行是变量定义，具体在后面一点会讲到。 在这里用比较形象的方式解释一下为什么后面要加 `FUNC_AND_VAR`。 当我们拿到一个 `FUNC_AND_VAR` 的时候，我们可以选择将它变成一个空串结束分裂，或者将它变成一个函数紧跟着一个 `FUNC_AND_VAR`，这个 `FUNC_AND_VAR` 还可以继续分解回到上面的情况…… 由于分裂可以产生一个函数或者一个变量定义。所以， `FUNC_AND_VAR` 将会产生一个由函数和变量定义组合而成的代码——这就是一份 C++ 代码除去头文件、define等东西之后剩下的了。 之后看看 `DEFINEVARS`： ```cpp DEFINEVARS ::= | ε | , DEFINEVAR DEFINEVARS ``` 和上面的道理一样，`DEFINEVARS` 将会产生由一堆`, DEFINEVAR` 构成的语句。 那么 `int DEFINEVAR DEFINEVARS ;` 就是： 一个字符串 `int`，之后一个变量，然后是若干个 `, [变量]`，最后一个`;`。 --- 利用上面的信息，我们大概可以读懂上下文无关文法了。 但是，按照表达式树的概念来说，我们应该找到运算符并让它成为根。 两者如何兼容呢？ 此时我们有三种思路。 ### 1:类递归 假设现在来到了只有 `+`,`-` 或者更高运算级的运算符（你可以理解为只有 `+,-,*,/,%` 的表达式）。 我们找到对应的文法： ```cpp UNIT3 ::= | UNIT2 | UNIT3 + UNIT2 | UNIT3 - UNIT2 ``` 我们可以按照这三种情况分别考虑： 从左到右扫这个序列，跳过括号。 如果找到 `+` 或者 `-`，说明有运算符符合条件2和条件3，那么： 按照`UNIT3 [OPERATOR] UNIT2`的规则，等效替换成`UNIT2 [OPERATOR] UNIT3`（你可以尝试一下，这两个是真的一样的！）之后就可以递归了。 新建一个该运算符的节点，左儿子连运算符左边的式子用 `UNIT2` 文法匹配出的 AST，右儿子连运算符右边的式子用 `UNIT3` 文法匹配出的 AST。这就是这个表达式代表的 AST 了（请多读几遍这句话）。 之后我们就可以得到伪代码： ```cpp Unit3 ( string Exp ) N = Exp的长度 for c from 1 to N if(Exp[c]=='(') 寻找和c匹配的括号下标c1 c = c1 continue else if(Exp[c]=='+' || Exp[c]=='-') 定义ret为一个新AST 将Exp[c]的信息填入ret //这里的信息指的是加号或者减号 //这是AST在非叶子节点储存的状态 //详见Vol.1 的AST定义 ret的第一个参数设为Unit2(Exp在位置c前面的字符串) ret的第二个参数设为Unit3(Exp在位置c后面的字符串) return ret return Unit2(Exp) ``` P.S.：真正的题目中会遇到中括号，也是直接跳过就行了。或者在对变量处理之后再计算 AST。 递归的终止状态就是名字、数字等不会延申、数值一定的东西。 ### 2:类分治 还是假设现在来到了只有 `+`,`-`或者更高运算级的运算符（你可以理解为只有 `+,-,*,/,%` 的表达式）。 对应的文法： ```cpp UNIT3 ::= | UNIT2 | UNIT3 + UNIT2 | UNIT3 - UNIT2 ``` 我们直接分析这段代码的本质。 这份代码实际上是把字符串按照将要运算（不在括号中）的 `+` 和 `-`，之后将代码分成几个小块，在计算值后带回原式子计算。 在 AST 的眼中就是：将表达式按照将要运算的 `+,-` 分开，求出每一个小块的 AST，之后用左结合的方式将它们合并在一起（ `=` 是右结合） 简单解释一下左结合和右结合： ``` a + b + c <-> ( a + b ) + c a = b = c <-> a = ( b = c ) ``` 之后我们就可以得到伪代码（注：表达式的基础层相当于无括号包围，是我自己定义的说法）： ```cpp Unit3 ( string Exp ) if(在Exp的基础层中没有'+'或'-') return Unit2(Exp) 将Exp按照 Exp基础层中的'+'和'-' 分割为若干个字符串 并储存在S集合中 对S的所有元素运行Unit2函数 并储存在ASTSet集合中 while(ASTSet.size()>1) 从ASTSet中取出第一个元素和第二个元素 并设为u1和u2 定义v为一个新AST 将Exp中u1和u2中间的符号储存在v中 //这里的符号就是'+'或者'-' 将v的第一个参数设为u1 将v的第二个参数设为u2 将v储存为ASTSet的第一个元素 return ASTSet的唯一一个元素 ``` ### 3:中后树 实际上就是将表达式转换为后缀表达式，之后变成AST，不需要递归，也不用分治。具体的方法可以参考该系列的 Vol.2，那里已经够清楚了。 大概画一下最后的树。 例子1： `1+2-3` ``` - / \ + 3 / \ 1 2 ``` 例子2： `a=b=c` ``` = / \ a = / \ b c ``` 在多参数的运算中，使用多叉树（或说，一个指针列表）储存参数，这样就可以将一个运算符所需要的所有参数都储存下来。 这是在敲完代码后的函数一览（这说明 AST 实际上是很麻烦的，但可以视情况使用 Ctrl+C/V 让自己轻松一点）：  --- 在你实现的过程中，可能会出现如下问题（这些问题在程序分析里很常见）： Q1 : 如何判断 `+,-` 在表达式中是加减号还是正负号？ A1 : 这是我在代码中的方法：如果前一个字符是运算符而且非 `)` 或 `]`，那么这个字符是正负号，否则为加减号。如果有 hacker 的可以直接告诉我。 Q2 : 如何将表达式分割成名字、运算符、数字呢？ A2 : 使用**贪婪匹配**原则。在出现字母和下划线开头说明这是变量，直接匹配到运算符或者空格；在出现数字开头时说明是数字，打法和快读差不多；出现运算符说明就是运算符，往下数一两个字符，看看是不是符合的运算符，取最长的就行了。 Q3 : 直接使用 struct 赋值会爆炸啊！怎么处理啊…… A3 : 使用指针。~~我之前就犯了这个错误还用替换换了半个小时才变成指针……~~ --- 接下来是设计变量值的储存载体。 对于一个变量来说，有以下几个重要的参数： 名字、指针位置、数组维度，以及值。 我们有两种设计思路。 一是选择将信息用一个 struct 打包起来，之后用字符串- struct 映射获取。 ```cpp class Var string name int index vector < int > dimensionality define MemoryPool as map < string , Var > ``` 二是直接用一个大 struct，里面装着四个映射，分别对应变量的四个参数。 ```cpp class MemoryPool map < string , int > indexMap map < string , vector < int > > dimensionalityMap ``` 具体的值使用 vector 就行了，每一次根据变量大小开对应数量的内存。 关于多维度值的获取就要有点讲究了。 假设要取值的参数存在 `A` 数组，变量维度存在 `B` 数组，维度大小为 `N`。 我们先处理后缀积：$C_x=\Pi_{i=x+1}^NB_i$ 之后需要的值位置就是：$\Sigma_{i=1}^NC_i \times A_i$ 换句话说，我们得到了一个长为 `N` 的数字 `A`，每一位遵循 $B_i$ 进制原则，满 $B_i$ 进一。我们需要求 `A` 代表的数字。 我们在运算后将会得到一个数字，这个加上变量的参数指针后就是一个独一无二的位置了。 ……好像这样讲优点不清楚。我们直接上代码。 这是我的内存载体中找值的函数： ```cpp int findNum(string name,vector<int> argv){ // Var_name A int id=index[name],qwq=1; vector<int> rr=info[name]; // B for(int i=argv.size()-1;i>=0;i--){ id+=qwq*argv[i]; qwq*=rr[i]; } return memory[id]; } ``` 之后是变量的重名。 在 UOJ98 中，作者很贴心的给了一个条件： > 没有函数和变量重名 但这还不够。我们还要处理全局变量和局部变量的重名。 首先，在运行 AST 求值时，要加入一个内存载体作为参数。这个内存载体在运行函数时新建一个，新建的时候要加入函数的参数。 其次，找值的时候，要现在局部变量（就是刚刚的内存载体参数）中查看有没有该变量，之后去全局变量查看。 最后，`for` 和代码块（就是用 `{}` 包起来的语句）内的变量在运行结束后要清空（也就是开一个 string 为元素的数组，将变量名存进去，最后在内存载体内直接销毁）。请牢牢记住这一点 ~~，我在这个上面调了大半天~~。 --- 变量都不成问题了，最后就是运行求值了。 这一部分十分简单，但写起来会有一点痛苦。 这一部分只需要按照当前的 AST 节点的属性分类就行了。 伪代码显示代码的一部分： ```cpp runAST ( AST x ) if x是数字 return x代表的数字 if x是加号 then 将a设为runAST(x的第一个参数) 将b设为runAST(x的第二个参数) return a + b if x是减号 then 将a设为runAST(x的第一个参数) 将b设为runAST(x的第二个参数) return a - b ``` 这时候，你会遇到最后一个问题。 Q : 函数返回值怎么处理？ A : 将函数的返回值设为二元组，一个设定为是否为 `return` 发出的值，一个设定为有用的值（如果前者为 `true` 则设为为返回值，为 `false` 则为运算结果）。传参在遇到 `FUNCTION` 类型的 AST 节点结束，否则清空临时变量后直接返回。 --- 最后，拿着辛辛苦苦敲出来的代码，完成最后的调试。 这个时候你就要有足够的耐心调试了。（笑） 如果你凭自己成功拿到深绿色答复的话，你已经掌握了一种表达式求值方法，并且可以运用它分析、运行代码。现在，你可以尝试将它改成一个更开放的程序，使得你可以根据客户给出的上下文无关文法和运算法则运行代码，或是自己创造一种编程语言并用这份代码改编成解释器。 Last Question : 这不是只是讲了一遍 UOJ98 吗？标题党实锤！ A : 实际上，这道题的解题过程和使用AST进行代码解析和运行的本质一样。这道题的解题流程是：找到上下文无关文法 $\rightarrow$ 根据文法写出 AST 构造函数 $\rightarrow$ 通过 AST 节点类型计算、修改值。实际上，表达式可以通过一个上下文无关文法构造，根据这个方法也可以计算表达式的值。 虽然在前面的学习中可以用后缀表达式快速计算出表达式的值，但是一些区间表达式求值的题目上就可能需要 $O(n^2)$ 的复杂度。但是，在 AST 进行树高处理使得表达式树的高度在 $O(\log(n))$ 的复杂度后，可以只用 $O(n\log(n))$ 的复杂度解决问题。（`from 2020/5/29 22:48` 此方法 **仅供参考** ，本人将会深入分析并努力找寻方案，为[P5067](https://www.luogu.com.cn/problem/P5067)寻找解题方法）（`from 2020.5.29 23:00` 方法已找到，具体为 FHQ-Treap 基于表达式的改造，感觉是一个很好玩的主题，考虑出一个`Vol.(3.5)`） `Vol.4`是简单正则表达式和带输出类有限状态机，是一种快速、灵活计算 AST 的方法，可以学习一下 Trie，理解 Trie 随字符而定的状态转移。