tiger2005
2020-02-15 21:54:06
本文同步发布于Github Blog和Zhihu
Update: 2020/5/29 22:45
本作为此系列的第三部分，前两部分可以从下面的索引进入。
> Vol.1 后缀表达式
> Vol.2 进阶
强烈建议 先弄懂Vol.1的知识，Vol.2在此文中未被用到。
Update: 2020/5/29 23:01
加入关于 P5067 的思考以及模糊解决思路，详见文章末尾。
哪个OIer不想做出模拟C++解析器(UOJ 98)呢？
我也有过这个梦想。
打开这道题的统计，稍稍扫过前10，虽然我们不能像第一一样使用很风骚的方式 AC 这一道题，但是我们可以利用表达式树解决（这个东西虽然慢，但是很鲁棒好想，对于没有接触过这种大模拟的人是不二之选）。
前方高能，请务必确认你知道(抽象)表达式树（Abstract Syntax Tree，简称 AST） 。如果不知道，看看这个系列的 Vol.1 就可以了。
那么，开始吧。
首先，我们可以在题目的最后获得一份上下文无关文法，地址如下：here
这看起来很头疼。我在这里给大家一个入门介绍（P.S.:其他上下文无关文法可能和这个有点不一样，但本质相同）。
举个例子吧。
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：
DEFINEVARS ::=
| ε
| , DEFINEVAR DEFINEVARS和上面的道理一样，DEFINEVARS 将会产生由一堆, DEFINEVAR 构成的语句。
那么 int DEFINEVAR DEFINEVARS ; 就是：
一个字符串 int，之后一个变量，然后是若干个 , [变量]，最后一个;。
利用上面的信息，我们大概可以读懂上下文无关文法了。
但是，按照表达式树的概念来说，我们应该找到运算符并让它成为根。
两者如何兼容呢？
此时我们有三种思路。
假设现在来到了只有 +,- 或者更高运算级的运算符（你可以理解为只有 +,-,*,/,% 的表达式）。
我们找到对应的文法：
UNIT3 ::=
| UNIT2
| UNIT3 + UNIT2
| UNIT3 - UNIT2我们可以按照这三种情况分别考虑：
从左到右扫这个序列，跳过括号。
如果找到 + 或者 -，说明有运算符符合条件2和条件3，那么：
按照UNIT3 [OPERATOR] UNIT2的规则，等效替换成UNIT2 [OPERATOR] UNIT3（你可以尝试一下，这两个是真的一样的！）之后就可以递归了。
新建一个该运算符的节点，左儿子连运算符左边的式子用 UNIT2 文法匹配出的 AST，右儿子连运算符右边的式子用 UNIT3 文法匹配出的 AST。这就是这个表达式代表的 AST 了（请多读几遍这句话）。
之后我们就可以得到伪代码：
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。
递归的终止状态就是名字、数字等不会延申、数值一定的东西。
还是假设现在来到了只有 +,-或者更高运算级的运算符（你可以理解为只有 +,-,*,/,% 的表达式）。
对应的文法：
UNIT3 ::=
| UNIT2
| UNIT3 + UNIT2
| UNIT3 - UNIT2我们直接分析这段代码的本质。
这份代码实际上是把字符串按照将要运算（不在括号中）的 + 和 -，之后将代码分成几个小块，在计算值后带回原式子计算。
在 AST 的眼中就是：将表达式按照将要运算的 +,- 分开，求出每一个小块的 AST，之后用左结合的方式将它们合并在一起（ = 是右结合）
简单解释一下左结合和右结合：
a + b + c <-> ( a + b ) + c
a = b = c <-> a = ( b = c )之后我们就可以得到伪代码（注：表达式的基础层相当于无括号包围，是我自己定义的说法）：
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的唯一一个元素实际上就是将表达式转换为后缀表达式，之后变成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 映射获取。
class Var
string name
int index
vector < int > dimensionality
define MemoryPool as map < string , Var >二是直接用一个大 struct，里面装着四个映射，分别对应变量的四个参数。
class MemoryPool
map < string , int > indexMap
map < string , vector < int > > dimensionalityMap具体的值使用 vector 就行了，每一次根据变量大小开对应数量的内存。
关于多维度值的获取就要有点讲究了。
假设要取值的参数存在 A 数组，变量维度存在 B 数组，维度大小为 N。
我们先处理后缀积：
之后需要的值位置就是：
换句话说，我们得到了一个长为 N 的数字 A，每一位遵循 A 代表的数字。
我们在运算后将会得到一个数字，这个加上变量的参数指针后就是一个独一无二的位置了。
……好像这样讲优点不清楚。我们直接上代码。
这是我的内存载体中找值的函数：
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 节点的属性分类就行了。
伪代码显示代码的一部分：
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进行代码解析和运行的本质一样。这道题的解题流程是：找到上下文无关文法
虽然在前面的学习中可以用后缀表达式快速计算出表达式的值，但是一些区间表达式求值的题目上就可能需要 from 2020/5/29 22:48 此方法 仅供参考 ，本人将会深入分析并努力找寻方案，为P5067寻找解题方法）（from 2020.5.29 23:00 方法已找到，具体为 FHQ-Treap 基于表达式的改造，感觉是一个很好玩的主题，考虑出一个Vol.(3.5)）
Vol.4是简单正则表达式和带输出类有限状态机，是一种快速、灵活计算 AST 的方法，可以学习一下 Trie，理解 Trie 随字符而定的状态转移。