可配置語法分析器開發紀事（一）——構造語法樹
就像之前的博客文章所說的，（主要還是）因為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 = "http://";
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回來，所以保存成文本是一件特別方便的事情），甚至是生成錯誤消息的片段等等。
今天就先講到這里了。現在的可配置語法分析器的開發進度是正在寫語義分析的部分。等到語義分析寫完了，我會再寫一篇紀事來說明開發語義分析程序和構造符號表的一般做法。
浙公網安備 33010602011771號