随笔-341  评论-2670  文章-0  trackbacks-0

就像之前的博客文章所说的,(主要还是)因为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" };

上面的语法树声明借用的C#语法,描述起来特别简单。但是要在C++里面达到可以使用的程度,肯定要有一个自带的visitor模式。所以出来之后的代码大概就类似于下面这个样子:

class Expression;
class NumberExpression;
class BinaryExpression;
class FunctionExpression;

class Expression : public ParsingTreeCustomBase
{
public:
    class IVisitor : public Interface
    {
    public:
        virtual void Visit(NumberExpression* node)=0;
        virtual void Visit(BinaryExpression* node)=0;
        virtual void Visit(FunctionExpression* node)=0;
    };

    virtual void Accept(IVisitor* visitor)=0;
};

class NumberExpression : public Expression
{
public:
    TokenValue value;

    void Accept(IVisitor* visitor){visitor->Visit(this);}
};

class BinaryExpression : public Expression
{
public:
    enum BinaryOperator
    {
        Add, Sub, Mul, Div,
    };
    Ptr<Expression> firstOperator;
    Ptr<Expression> secondOperator;
    BinaryOperator binaryOperator;

    void Accept(IVisitor* visitor){visitor->Visit(this);}
};

class FunctionExpression : public Expression
{
public:
    TokenValue functionName;
    List<Ptr<Expression>> arguments;

    void Accept(IVisitor* visitor){visitor->Visit(this);}
};

为什么要这样做呢?学习过面向对象开发方法的都知道,把一个明显是继承结构的东西写成一堆union/struct和一个enum来判断他们,是不对的。第一个不好的地方就是,如果其中的成员需要构造函数和析构函数,那union就用不了了,struct就一定会造成大量的内存浪费。因为一颗语法树是可以很大的。其次,当语法树的结构(主要是添加删除了新的语法树类型)之后,我们根本不可能保证我们所有的swtich(node->enumType)语句都接受到了正确的更新。

那要如何解决这两个问题呢?答案之一就是使用visitor模式。尽管刚开始写起来的时候可能会有点别扭,但是我们只要把原本是swtich结构的代码做一下Continuation Passing Style变换,就可以写出使用visitor的版本了。在这里我做一个小小的演示,如何把一个“把上面的语法树还原成四则运算式子的函数”给用Expression::IVisitor的框架下实现出来:

class FunctionExpression : public Expression
{
public:
    TokenValue functionName;
    List<Ptr<Expression>> arguments;

    void Accept(IVisitor* visitor){visitor->Visit(this);}
};

class ExpressionPrinter : public Expression::IVisitor
{
public:
    WString result;

    void Visit(NumberExpression* node)
    {
        result+=node->value.stringValue;
    }

    void Visit(BinaryExpression* node)
    {
        result+=L"(";
        node->firstOperand->Accept(this);
        switch(binaryOperator)
        {
        case Add: result+=L" + "; break;
        case Sub: result+=L" - "; break;
        case Mul: result+=L" * "; break;
        case Div: result+=L" / "; break;
        }
        node->secondOperand->Accept(this);
        result+=L")";
    }

    void Visit(FunctionExpression* node)
    {
        result+=node->functionName.stringValue+L"(";
        for(int i=0;i<arguments.Count();i++)
        {
            if(i>0) result+=L", ";
            arguments[i]->Accept(this);
        }
        result+=L")";
    }
};

WString PrintExpression(Ptr<Expression> expression)
{
    ExpressionPrinter printer;
    expression->Accept(&printer);
    return printer.result;
}

其实大家可以看到,使用了visitor模式,代码量其实也没有多大变化,本来是递归的地方还是递归,本来该计算什么还计算什么,唯一不同的就是原本这个“函数”的参数和返回值都跑到了一个visitor类的成员变量里面去了。当然,为了便于使用,一般来说我们会把原本的函数的原型写出来,并且在里面调用visitor模式,就像上面的PrintExpression函数一样。如果我们高兴的话,完全可以在ExpressionPrinter这个visitor类里面使用PrintExpression,无非就是在里面构造新的ExpressionPrinter然后获取结构罢了。一般来说,visitor类都是非常的轻量级的,在现今的CPU性能下面,构造多几个完全不会带来多大影响。

可配置语法分析器既然拥有一个描述性语法,那么我肯定也针对这个描述性语法写了一颗语法树的。这颗语法树的代码在Common\Source\Parsing\ParsingDefinition.h里面,而ParsingLogging.cpp则是跟上面说的一样,用visitor的方法写了一个庞大的把语法树转回描述性语法的函数。这个函数非常有用,不仅可以用来打log,还可以用来保存程序生成的一个语法规则(反正可以parse回来,所以保存成文本是一件特别方便的事情),甚至是生成错误消息的片段等等。

今天就先讲到这里了。现在的可配置语法分析器的开发进度是正在写语义分析的部分。等到语义分析写完了,我会再写一篇纪事来说明开发语义分析程序和构造符号表的一般做法。

posted on 2012-11-21 22:42 陈梓瀚(vczh) 阅读(9376) 评论(6)  编辑 收藏 引用 所属分类: C++

评论:
# re: 可配置语法分析器开发纪事(一)&mdash;&mdash;构造语法树 2012-11-21 23:34 | Ooseven
哈,早就该这样做了,我比较幸运,没有走那么多弯路,一开始就是奔着类似yacc的思路来设计语法生成器的。不过虽然是这样,设计完了之后还是有点遗憾,脑袋里只有c++了,所以没有考虑到别的语言,其实完全可以再大胆一点,用c++设计一个可以方便的生成任何语言的语法分析器框架,java,c#,pascal等等,非常重要的一点是生成对任何语言的支持应该非常的方便,不需要修改已经写好的代码,只需要增加类似插件的机制才是完美的设计。

如果您的第四版没有考虑到这一点,那我估计你还需要来个第五版。希望我的提醒对你有用。

  回复  更多评论
  
# re: 可配置语法分析器开发纪事(一)&mdash;&mdash;构造语法树 2012-11-21 23:50 | 陈梓瀚(vczh)
@Ooseven
其实我的目标只有生成语法树的代码,至于分析过程,还是在类库里面自己搞定的,所以我不考虑其它语言了。  回复  更多评论
  
# re: 可配置语法分析器开发纪事(一)&mdash;&mdash;构造语法树 2012-11-22 00:08 | ooseven
作为语法分析生成器而言,其实是分析用户编写的bnf脚本,而后产生语法栈并让用户在脚本里定义的相应的动作正确的入栈与出栈,至于用户写bnf脚本里的动作定义是要生成语法树,还是要直接进行其他操作都可以,为啥要定死一定要生成语法树呢。
而且语法树是啥结构根本跟语法生成器没有半毛钱关系,建议解耦。您的目标是生成语法树的代码,那么只要语法生成器些好了,就只在bnf脚本里折腾就行了
  回复  更多评论
  
# re: 可配置语法分析器开发纪事(一)&mdash;&mdash;构造语法树[未登录] 2012-11-22 12:11 | 陈梓瀚(vczh)
@ooseven
这,因为我需要的就是语法树啊。如果你的原始目的是直接计算表达是结果的话,你打可以自己实现Expression::IVisitor,里面就已经隐含了入栈出栈的含义了。而且这还更maintainable,因为突然有一天你发现你还要干点其他事情,譬如说求导数,这个时候才来做语法树然后写两个visitor分别求值和求导,何苦呢。所以不如一开始就让你自己设计好语法树,visitor接口替你生成了,然后你要做的事情,就是实现一个visitor。这样的话,你并没有比“直接求值”多写什么代码,而且还给你的未来带来了方便,多好啊。

而且对于我个人来说,我的确在大部分情况下都是需要语法树的。  回复  更多评论
  
# re: 可配置语法分析器开发纪事(一)&mdash;&mdash;构造语法树[未登录] 2012-11-22 12:13 | 陈梓瀚(vczh)
@ooseven
不过话说回来,语法树是什么结构如果不写进文法的话,会带来更大的噪音。参考yacc(如果你要产生语法树还要在{里面自己new多麻烦啊}),和Antlr(同理)。所以在大部分情况下都需要语法树的时候,你给出必须生成语法树的实现,带来的结构就是,这个描述起来特别他妈的简洁。而且在你不打算生成语法树的时候其实也不会造成什么麻烦。反过来就不一样了。  回复  更多评论
  
# re: 可配置语法分析器开发纪事(一)&mdash;&mdash;构造语法树 2013-08-24 22:08 | RexfieldVon
《编程语言实现模式》是本好书,每当我思路卡壳的时候都会翻出来查。  回复  更多评论
  

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理