程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> 可配置語法分析器開發紀事（一）構造語法樹

可配置語法分析器開發紀事（一）構造語法樹

編輯：關於C++

就像之前的博客文章所說的，（主要還是）因為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);}
};
//本欄目