手把手教你写脚本引擎（四）——简单的高级语言（2，处理语法）
首先是词法分析器。我们仍然能够使用《构造可配置语法分析器》前半部分的方法人脑画出一张合适的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：取出一个二元操作符和一个单元。然后从当前节点往父节点找，一直到根节点或者父节点优先级比当前的二元操作符小的二元操作符为止。如果找到根节点，那么整个根节点将作为二元操作符的左操作数，单元作为右操作数，根节点更新，当前节点指向单元。如果不是的话，将找到的节点（这个节点的父节点的优先级比自己小）从父节点脱离，整个节点作为操作符的左操作数，单元作为右操作数，然后 |
凌众科技专业提供服务器租用、服务器托管、企业邮局、虚拟主机等服务，公司网站：http://www.lingzhong.cn 为了给广大客户了解更多的技术信息，本技术文章收集来源于网络,凌众科技尊重文章作者的版权，如果有涉及你的版权有必要删除你的文章，请和我们联系。以上信息与文章正文是不可分割的一部分,如果您要转载本文章,请保留以上信息，谢谢! |
