发篇技术文章吧……最近除了去银川玩了一趟以外没别的新鲜事，再就是听取毛继同学汇报的关于他们bt的学院派他们集体去ms打工的事情有点意思。最近还在犹豫要不要继续我只写了两篇的delphi教程，不过borland前途未卜，实在是……算了，直入正题吧。
这几天心血来潮，突然又想把原来没写完的jass语法分析工具完成。之前的版本除了数据结构设计的有些混乱外（打算重写做一个数据结构，现在有点想用c写的冲动，不过不知道没有oop维护起来会不会太累，用c++的话接口还是个问题），就是原来对表达式的求运算结果类型了。第一版设计的时候怎么维护类型运算的现在是想不起来了，不过可以肯定的是乱的一塌糊涂。第二版的设计是采用下面一个树：
每个item存有Parent、lChild、rChild三个指针，根的Parent为nil，用一个Current表示当前item，根据读入的元素处理链表。基本思路：
1. 如果读入数据，Cur为空，那么Cur填入数据；如果Cur为运算符，那么填入Child里；如果是符号，根据符号的优先级爬升树，在正确的位置上插入
2. 如果读入运算符，Cur为数据，那么拆开Cur与其Parent的连接，插入一个新item并设为Cur，填入符号
这种处理方法在遇到特殊运算（如表示负数的减号、not运算这种单数运算符）的时候判断非常复杂，而且有的时候数据的移动或交换导致混乱（比如某个item的parent并没有正确的指向），而且频繁的new、dispose也会导致效率的降低。
虽然以前读过编译原理，也明白E->E+t|t;t->t*F|F;F->(E)|i的大概原理，不过一直没有搞清楚到底应该怎样处理。
众所周知，计算机处理表达式的难点在于括号的处理（运算符的优先级已经是次要的了），虽然我前面的方法可以很好的处理括号的问题，但是对付单目运算符却很头疼。
逆波兰表达式又称后缀式，是波兰逻辑学家J.Lukasiewicz于1929提出的一种后缀表达运算式的方法。区别于我们所熟悉的中缀式，后缀式的特点就是运算量在前，运算符在后，如a+b表达为ab+。这种后缀表达式非常方便去掉运算符优先级的影响与括号，甚至是单目运算符：
1. a*b+c*(d+e) => ab*cde+*+
2. -a+-b*+c => a!b!c#*+ （注：为区别与减法运算与加法运算，这里用!表示负号，#表示正号）
那么计算机怎样通过后缀式来进行运算呢？这里首先假设读取分析表达式的准备工作都已经做好了，那么首先需要做的是把表达式转换成后缀式，也就是逆波兰表达式的构建过程。
构建器由两个主要组件组成，一个是目标表达式的存储器，另一个是一个符号栈。与源表达式的扫描顺序一样，存储器是从左向右储存数据的，而符号栈则遵守后进先出的原则：
* 读入一个数据
1. 如果是单目运算符，直接入符号栈；
2. 如果是运输量，则直接写入存储器；检查符号栈顶是否有单目运算符，有的话则全部出栈，并写入存储器；
3. 如果是左括号"("，则直接入符号栈；
4. 如果是右括号")"，则弹出符号栈数据，写入存储器，直到左括号弹出；
5. 如果是普通运算符，则与栈顶符号比较优先级，弱大于栈顶优先级，则入栈；否则弹出栈顶符号并写入存储器，直到栈顶符号的运算优先级较小为止；
6. 如果是结束符（表示表达式已全部读完），则符号栈全部弹出并写入存储器，否则读取数据进入下个过程。
此外还有一些处理的技巧，比如定义一个优先级最低的运算符作为表达式结束的标志，在符号栈里首先加入一个结束标志，那么表达式读完时则自动弹出栈中所有符号，并写入存储器结尾表示成功。
下面用一个表格表示构建的过程：
| Token | Expression | Dest Data | LIFO stack | Description |
| a*b+c*(d+-e)# | # | # is Ending Sign | ||
| a | *b+c*(d+-e)# | a | # | Value -> Data |
| * | b+c*(d+-e)# | a | #* | * > # |
| b | +c*(d+-e)# | ab | #* | Value -> Data |
| + | c*(d+-e)# | ab* | # | + < * |
| c*(d+-e)# | ab* | #+ | + > # | |
| c | *(d+-e)# | ab*c | #+ | Value -> Data |
| * | (d+-e)# | ab*c | #+* | * > + |
| ( | d+-e)# | ab*c | #+* | LPar( -> Stack |
| d | +-e)# | ab*cd | #+*( | Value -> Data |
| + | -e)# | ab*cd | #+*(+ | + > ( |
| ! | e)# | ab*cd | #+*(+! | ! -> Stack |
| e | )# | ab*cde! | #+*(+ | Value -> Data, Pop ! |
| ) | # | ab*cde!+ | #+* | RPar) -> Pop Until ( |
| # | ab*cde!+*+# | # -> Pop Until # |
接下来是计算的过程。计算的时候除了刚才构建的数据外，还需要另外一个数据栈。首先是从左至右扫描数据段，如果读出的是数据则压入数据栈，遇到符号时从数据栈中弹出相应的数据进行运算，再把结果压回数据栈。依然拿上面的结果做表格列示：
| Token | Expression | Data Stack | Compute | Description |
| ab*cde!+*+# | ||||
| a | b*cde!+*+# | a | Value -> Stack | |
| b | *cde!+*+# | ab | Value -> Stack | |
| * | cde!+*+# | a*b | Pop a, b | |
| cde!+*+# | m | set m = a*b | ||
| c | de!+*+# | mc | Value -> Stack | |
| d | e!+*+# | mcd | Value -> Stack | |
| e | !+*+# | mcde | Value -> Stack | |
| ! | +*+# | mcd | !e | Pop e |
| +*+# | mcdn | set n = !e | ||
| + | *+# | mc | d+n | Pop d, n |
| *+# | mco | set o = c+n | ||
| * | +# | m | c*o | Pop c, o |
| +# | mp | set p = c*o | ||
| + | # | m+p | Pop m, p | |
| # | r | set r = m+p | ||
| # | r | check | Accept! |
这样，返回结果就是栈中唯一的数据，我们完成了逆波兰表达式的全部计算过程。
此外还要注意处理的一些过程中的问题包括：
构建时，保存上次的数据类型，在得到数据时与上次数据进行对比，例如当读入运算量时如果上次数据也是运算量就出错了，例如这样的表达式“a b+”如果不注意处理的话则会“合法 ”压入数据栈并得到运算结果。
计算时，要注意检查数据栈中的数据数量，如果数量不对则中断计算过程并报错。
相对来说，逆波兰表达式在处理运算的时候还是非常容易的，现在我还要处理的一个过程是当加上函数运算的时候（形如a+f1(b+c, d)*e之类）如何消去函数过程。如果递归的话则使用了更多的内存，不递归的话就得人为定义一些运算符如函数运算符、类型检查运算符，把数据类型压入存储器中，增加了代码构造的难度。关于后缀式就说这么多了，我去看书想办法解决我的问题去……
全站熱搜
留言列表
