Shell's Home

Oct 20, 2005 - 1 minute read - Comments

表达式解析算法

表达式解析的本质是什么?是树的构造和消解。其他算法本质上都是树算法。

首先,我们使用Token算法来获得一个Token和Object混合的列表。然后我们将列表展开成为一颗树。这个树符合以下条件。

  1. 树的所有叶子都是Object,无论是数据还是变量。
  2. 树的节点上都是算符或函数,其分支数目和算符目或函数参数相等。
  3. 单根,无()。

那么我提出一种构造方法。我们假定一种算符passby,然后用Token算法切分表达式并且转换成合适的对象,放置在passby上面。然后我们根据(,,)的规则将整个列表递归表达成同级树。树的每层都是同级的。而后每层都根据优先级从高到低的顺序来计算结果,反馈到上层。由此我们可以得到有效的结果。

但是我没有按照上述方法写解析器。原因是太麻烦,运算时间长,不容易看懂。代码大,维护困难。我问一个同学,你是喜欢精致小巧但是有瑕疵的东西呢?还是庞大严谨没有错误的东西。结果回答说是精致小巧的。好,这就是解析器算法来源。我用了数据结构中的堆栈算法。这种算法在解析正确的式子的时候没有问题,但是精心构造的“看起来”不正确“的式子也可以解析。而且不容易检查堆栈问题。但是谁管呢?喜欢就好。