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

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;
};

所有的符合表达式就构造完了，但是我们仍然需要一个代表单一记号的表达式，譬如变量名啊数字等等。我们直接把一个记号放进去就

凌众科技专业提供服务器租用、服务器托管、企业邮局、虚拟主机等服务，公司网站：http://www.lingzhong.cn 为了给广大客户了解更多的技术信息，本技术文章收集来源于网络,凌众科技尊重文章作者的版权，如果有涉及你的版权有必要删除你的文章，请和我们联系。以上信息与文章正文是不可分割的一部分,如果您要转载本文章,请保留以上信息，谢谢!