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

背景

為 GacUI 開發第四代可配置輕量級語法分析器。推薦《編程語言實現模式》一書。

語法樹核心：訪問者模式

成熟語法樹必附帶 Visitor 機制。本分析器採用描述性語法：文本文件定義樹結構與文法，工具生成 C++ 樹聲明/實現及內存分析器。

描述性語法示例（四則運算）

class Expression { }
class NumberExpression : Expression { token value; }
class BinaryExpression : Expression {
    enum BinaryOperator { Add, Sub, Mul, Div }
    Expression firstOperand, 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 "*" Factor : secondOperand as BinaryExpression with { binaryOperator = "Mul" };
    = Term : firstOperand "/" Factor : 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++ 代碼骨架

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); }
};
// ... 其他節點類似

工具自動生成訪問者雙分派機制，手寫僅需實現具體 Visitor。