手把手教你写脚本引擎（四）——简单的高级语言（2，处理语法）

萧闫子

陈梓瀚

华南理工大学软件本科05级

vczh@163.com

http://www.cppblog.com/vczh/

    有了全盘的计划之后，我们必须先处理输入的脚本，才能够进行下一步的工作。字符串处理方面可以参照一下三篇文章：《构造可配置语法分析器》、《构造正则表达式引擎》以及《如何手写语法分析器》。作为补充，这里再说一说其他的办法。

    首先是词法分析器。我们仍然能够使用《构造可配置语法分析器》前半部分的方法人脑画出一张合适的DFA，这个时候我们可以手工来实现。用于词法分析器的DFA只有两种状态，一种是普通状态，另一种是终结状态。所以我们可以很机械地将DFA用C++写出来。

    我们要为状态编号。编号要连续，而且要从0开始，这样的话C++的编译器一般都会为switch-case的代码生成一张表，用于快速跳转。然后用下面的方法。

    1：将输入的指针Input复制出一个副本，叫Current；给出一个同类型的指针Last，将其赋值为NULL；使用一个变量Status来记录当前的状态。初始化状态，一般为了方便我们把初始状态编号成0。

    2：做一个死循环不断的计算新Status。对于某个Status我们总是能够知道输入什么字符跳转到什么新的Status上去。不同的人写出来的DFA可能会有所区别。我们首先判断当前的Status是不是终结状态，如果是的话将Current赋值给Last，然后继续往下走。我们从Current指针拿出一个字符，然后计算新Status。如果Current不满足要求那么结束循环，如果Current满足要求那么改变Status并让Current指向新的位置。

    3：因为字符串总是有限的，所以这个循环总是会结束。结束了之后，我们检查Last。如果Last仍然是NULL，那么代表输入的字符串是有问题的。如果不是，那么我们所需要的一个记号就从Input开始到Last结束了。如果记号的类型有需要保留的话，那么我们只需要添加一个新的代表类型的变量，在每一次修改Last的时候修改这个保存类型的变量就行了。因为一个终结状态只能代表一种类型的结束（反过来不成立，一种类型可能有好几个终结状态）。

    然后是语法分析。一般来说，使用《如何手写语法分析器》中描述的方法实现一个语法分析器的话是很容易的，但是一个主要问题就是如果一门语言很复杂，特别是操作符特别多的话，这些函数写起来会很乱，因此每一个文法产生式的处理函数的命名和注释就变得相当重要了。为了简化这件事情，我们还有另一种专门用来处理操作符的方法，而且是高度可配置的。为了简化，我仅给出二元操作符和前缀操作符的处理方法。后缀操作符不常见，需要的话自己想办法吧，在上一篇文章中的语法定义中并没有出现后缀操作符。

    在这种方法中，我们把重点放在不包含修改优先级的括号的表达式中。遇到一个用于修改优先级的括号的时候，只要递归一下就好了。现在，我们通过词法分析，已经得到了很多记号，然后就使用以下的方法来生成一颗正确的语法树：

    1：我们需要定义两个指针，第一个用于保存根节点，第二个用于保存当前节点。在分析的过程中，根节点会经常变化，当前节点也是。

    2：取出一个单元。一个单元指的是一个用括号包括起来的完整的表达式、一个函数调用、一个常量或变量和仅由前缀操作符与单元组成的整体。举个例子，1是单元，a是单元，function(param1,param2+param3)是单元，(a*b+c*d)是单元，-(a+b)也是单元。但是-a+b就不是单元了。单元内部可能有表达式，我们可以递归下去。取出单元以后，就把根节点和当前节点指向这个单元。

    3：一个正确的表达式总是由单元和二元操作组成的，如果在以下的步骤中出错的话，那么可以直接确定输入的表达式的语法不正确。我们做一个死循环一直到遇到右括号、逗号等这些结束表达式的记号为止，对于每一个输入执行第4步。

    4：取出一个二元操作符和一个单元。然后从当前节点往父节点找，一直到根节点或者父节点优先级比当前的二元操作符小的二元操作符为止。如果找到根节点，那么整个根节点将作为二元操作符的左操作数，单元作为右操作数，根节点更新，当前节点指向单元。如果不是的话，将找到的节点（这个节点的父节点的优先级比自己小）从父节点脱离，整个节点作为操作符的左操作数，单元作为右操作数，然后用这个二元操作符接上父节点。

    5：当3与4进行不下去的时候，我们就得到了一棵完整的表达式语法树了。当然，如果中间出错的话，我们应当输出错误信息。这个时候要不要继续往下走就自己看着办吧，因为进行错误恢复的话，接下去的错误信息会很难看，就像VC++一样。

    我给一个例子来说明如何处理这些事情。现在我们要分析1+2*3+4。这个算法将会产生一个正确的语法树”1”，然后修改为正确的语法树”1+2”，然后修改为正确的语法树”1+2*3”，最后产生完整的正确的语法树。

    第一步，产生一个单元的正确的语法树：

                               
登录/注册后可看大图

    第二步，获得一个二元操作符，并产生一个单元的语法树”2”。因为当前节点往上就没有了，所以执行4中的第一种情况：

                               
登录/注册后可看大图

    第三步，获得操作符”*”和一个单元的语法树”3”。因为2的父节点的优先级比”*”小，因此执行4的第二种情况：

                               
登录/注册后可看大图

    第四步，获得操作符”+”和一个单元的语法树”4”。这个时候3的父节点的优先级大于或等于”+”的优先级，因此一直往上找，一直到根节点。因为根节点的优先级仍然大于或等于”+”的优先级，因此再也上不了了，执行4的第一种情况：

                               
登录/注册后可看大图

    字符串结束了，中间也没有出错，代表输入的表达式”1+2*3+4”是正确的，我们也得到了一棵正确的语法树。

    通过之前的文章与上述两种简单的方法的学习，我想分析一门语言的语法也就没什么困难的了。不过分析字符串是次要的，得到语法树才是主要的。就算用了一种猥琐的处理字符串的办法得到了语法树，那也没关系，以后有时间再改就行了。现在我们要讨论一下语法树的数据结构问题。

    在这里我们需要大胆地使用虚函数。使用单一的一个class来表达整棵语法树是不好的，因为我们的语法树要表达unit、表达类型声明、函数声明、还有各种复杂的语句。类型是递归的，语句是递归的，表达式也是递归的。对于一组递归的结构，我们要定义一个几类，并派生出各种子类来表达各种类型的结构。这样做的好处是我们可以很方便地处理类型检查、其它语义分析以及生成指令。多态在这里是相当好用的，比省掉一点虚函数的空间（若干个同类型的对象只共享一张虚函数表）和一点调用的时候牺牲的速度好多了。我想用复杂的if或函数指针来代替多态估计也没有多态快。

    因为类型、表达式和语句的处理方式是类似的，因此我只为表达式建模。我们的表达式有四则运算、数组访问以及函数调用。首先我们给出一个基类ExpBase：

    class ExpBase

    {

    public:

       TypeBase* GetType(vector<ErrorMessage>& Errors);

    };

    我们拿到了一个表达式之后，转换成表达式树，就会得到一个ExpBase了，这个时候我们进行类型检查，只需要调用GetType就行了。各种不同的检查由子类实现。

    然后我们为运算符定义表达式节点：

    enum BinOpType

    {

        Plus,

        Minus,

        Multiply,

        Division,

        ……

    };

    enum SinOpType

    {

        Negative,

        Not,

        ……

    };

    class ExpBinOp : public ExpBase

    {

    public:

        ExpBase*  ParamA;

        ExpBase*  ParamB;

        BinOpType Operator;

    };

    class ExpSinOp : public ExpBase

    {

    public:

        ExpBase* Param;

        SinOpType Operator;

    };

    数组访问可以加进二元操作符也可以不加，不过我个人还是倾向于不加的，因为后续的处理逻辑有很大的不同。

接下来是函数调用的表达式节点：

    class ExpInvoke : public ExpBase

    {

    public:

        ExpBase* Name;

        vector<ExpBase*> Params;

    };

    所有的符合表达式就构造完了，但是我们仍然需要一个代表单一记号的表达式，譬如变量名啊数字等等。我们直接把一个记号放进去就好了，因为记号里面有常量的类型信、也有变量名：

    class ExpToken : public ExpBase

    {

    public:

        Token* Content;

    };

    表达式的数据结构就构造完了，然后我们把剩下的类型信息与语句构造万，给出单元结构以后就结束了。

    鉴于实习期间较忙，自己的时间不多，完整的代码我就不给出来了。要是大家愿意的话可以去这里看Vczh Free Script 2.0 beta的语法树结构。虽然少了类型族，但也还是能看得。

    下一篇文章讲述语义分析以及符号表的事情。语法树不仅要代表源代码，还需要附带额外的信息，譬如表达式的类型、重载的选择等等。这些在语法分析的时候很难一起产生，所以我们借助多态来简化这个任务。