发篇技术文章吧……最近除了去银川玩了一趟以外没别的新鲜事,再就是听取毛继同学汇报的关于他们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之类)如何消去函数过程。如果递归的话则使用了更多的内存,不递归的话就得人为定义一些运算符如函数运算符、类型检查运算符,把数据类型压入存储器中,增加了代码构造的难度。关于后缀式就说这么多了,我去看书想办法解决我的问题去……
全站熱搜
留言列表