可配置语法分析器开发纪事（一） 构造语法树

就像之前的博客文章所说的，（主要还是）因为GacUI的原因，我决定开发一个更好的可配置轻量级语法分析器来代替之前的落后的版本。在说这个文章之前，我还是想在此向大家推荐一本《编程语言实现模式》，这的确是一本好书，让我相见恨晚。

其实说到开发语法分析器，我从2007年就已经开始在思考类似的问题了。当时C++还处于用的不太熟练的时候，难免会做出一些傻逼的事情，不过总的来说当年的idea还是能用的。从那时候开始，我为了锻炼自己，一直在实现各种不同的语言。所以给自己开发一个可配置语法分析器也是在所难免的事情了。于是就有：    

第一版：http://hi.baidu.com/geniusvczh/archive/tag/syngram%E6%97%A5%E5%BF%97

第二版：http://www.cppblog.com/vczh/archive/2009/04/06/79122.html

第三版：http://www.cppblog.com/vczh/archive/2009/12/13/103101.html

还有第三版的教程：http://www.cppblog.com/vczh/archive/2010/04/28/113836.html

上面的所有分析器都致力于在C++里面可以通过直接描述文法和一些语义行为来让系统可以迅速构造出一个针对特定目的的用起来方便的语法分析器，而“第三版”就是到目前为止还在用的一个版本。至于为什么我要做一个新的——也就是第四版——之前的文章已经说了。

而今天，第四版的开发已经开始了有好几天。如果大家关心进度的话，可以去GacUI的Codeplex页面下载代码，然后阅读Common\Source\Parsing下面的源文件。对应的单元测试可以在Common\UnitTest\UnitTest\TestParsing.cpp里找到。

于是今天就说说关于构造语法树的事情。

用C++写过parser的人都知道，构造语法树以及语义分析用的符号表是一件极其繁琐，而且一不小心就容易写出翔的事情。但是根据我写过无穷多棵语法树以及构造过无穷多个符号表以及附带的副作用，翔，啊不，经验，做这个事情还是有一些方法的。

在介绍这个方法之前，首先要说一句，人肉做完下面的所有事情是肯定要疯掉的，所以这一次的可配置语法分析器我已经决定了一定要TMD写出一个生成语法树的C++代码的工具。

一颗语法树，其实就是一大堆互相继承的类。一切成熟的语法树结构所具有的共同特征，不是他的成员怎么安排，而是他一定会附带一个visitor模式的机制。至于什么是visitor模式，大家请自行参考设计模式，我就不多说废话了。这一次的可配置语法分析器是带有一个描述性语法的。也就是说，跟Antlr或者Yacc一样，首先在一个文本文件里面准备好语法树结构和文法规则，然后我的工具会帮你生成一个内存中的语法分析器，以及用C++描述的语法树的声明和实现文件。这个描述性语法就类似下面的这个大家熟悉到不能再熟悉的带函数的四则运算表达式结构：

class Expression
{
}

class NumberExpression : Expression
{
    token value;
}

class BinaryExpression : Expression
{
    enum BinaryOperator
    {
        Add,
        Sub,
        Mul,
        Div,
    }

    Expression firstOperand;
    Expression secondOperand;
    BinaryOperator binaryOperator;
}

class FunctionExpression : Expression
{
    token functionName;
    Expression[] arguments;
}

token NAME = "[a-zA-Z_]/w*";
token NUMBER = "/d+(./d+)";
token ADD = "/+";
token SUB = "-";
token MUL = "/*";
token DIV = "//";
token LEFT = "/(";
token RIGHT = "/)";
token COMMA = ",";

rule NumberExpression Number
        = NUMBER : value;

rule FunctionExpression Call
        = NAME : functionName "(" [ Exp : arguments { "," Exp : arguments } ] ")";

rule Expression Factor
        = !Number | !Call;

rule Expression Term
        = !Factor;
        = Term : firstOperand "*" Factory : secondOperand as BinaryExpression with { binaryOperator = "Mul" };
        = Term : firstOperand "/" Factory : secondOperand as BinaryExpression with { binaryOperator = "Div" };

rule Expression Exp
        = !Term;
        = Exp : firstOperand "+" Term : secondOperand as BinaryExpression with { binaryOperator = "Add" };
        = Exp : firstOperand "-" Term : secondOperand as BinaryExpression with { binaryOperator = "Sub" };

本栏目更多精彩内容：http://www.bianceng.cn/Programming/cplus/

以上是小编为您精心准备的的内容，在的博客、问答、公众号、人物、课程等栏目也有的相关内容，欢迎继续使用右上角搜索按钮进行搜索c++
， token
， 语法
， 语法分析
， 文本 编辑器 语义 c++
， expression
， 一个
配置语法
语法树构造、编译原理构造语法树、lex yacc 构造语法树、语法树、抽象语法树，以便于您获取更多的相关知识。