当前位置：天才代写 > tutorial > C语言/C++ 教程 > 可设置语法阐明器开拓纪事（一） 结构语法树

可设置语法阐明器开拓纪事（一） 结构语法树

2017-11-02 08:00 星期四 所属： C语言/C++ 教程 浏览：1137

副标题#e#

就像之前的博客文章所说的，（主要照旧）因为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" };

本栏目


#p#副标题#e#

上面的语法树声明借用的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);}
};
//本栏目
#p#分页标题#e#
那要如何办理这两个问题呢？谜底之一就是利用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返来，所以生存成文本是一件出格利便的工作），甚至是生成错误动静的片断等等。


本日就先讲到这里了。此刻的可设置语法阐明器的开拓进度是正在写语义阐明的部门。比及语义阐明写完了，我会再写一篇纪事来说明开拓语义阐明措施和结构标记表的一般做法。
 

    关键字：

天才代写-代写联系方式