因為GacUI需要實現(xiàn)一個文本描述的窗口描述格式，再加上C++經(jīng)常需要處理xml和json等常用數(shù)據(jù)結(jié)構(gòu)，還有自己還要時不時開發(fā)一些語言來玩一玩之類的理由，每一次遇到自己的技術(shù)革新的時候，總是免不了要對可配置語法分析器做出修改。上一個版本的可配置語法分析器可以見之前的博客文章《Vczh Library++ 語法分析器開發(fā)指南》。

為什么要重寫vlpp的這一部分呢？因為經(jīng)過多次可配置語法分析器的開發(fā)，我感覺到了C++直接用來表達文法有很多弱點：

1、C++自身的類型系統(tǒng)導(dǎo)致表達出來的文法會有很多噪音。當(dāng)然這并不是C++的錯，而是通用的語言做這種事情總是會有點噪音的。無論是《Monadic Parser Combinators using C# 3.0》也好，我大微軟研究院的基于Haskell的Parsec也好，還是boost的spirit也好，甚至是F#的Fsyacc也好，都在展示了parser combinator這個強大的概念的同時，也暴露出了parser combinator的弱點：在語法分析結(jié)果和語言的數(shù)據(jù)結(jié)構(gòu)的結(jié)合方面特別的麻煩。這里的麻煩不僅在于會給文法造成很多噪音，而且復(fù)雜的parser還會使得你的結(jié)構(gòu)特別的臃腫（參考Antlr的某些復(fù)雜的應(yīng)用，這里就不一一列舉了）。

2、難以維護。如果直接用C++描述一個強類型文法的話，勢必是要借助parser combinator這個概念的。概念本身是很厲害的，而且實現(xiàn)的好的話開發(fā)效率會特別的高。但是對于C++這種非函數(shù)式語言來說，parser combinator這種特別函數(shù)式的描述放在C++里面就會多出很多麻煩，譬如閉包的語法不夠漂亮啦、沒有垃圾收集器的問題導(dǎo)致rule與rule的循環(huán)引用問題還要自行處理啦（在很早以前的一篇博客論證過了，只要是帶完整閉包功能的語言，都一定不能是用引用計數(shù)來處理內(nèi)存，而必須要一個垃圾收集器的）。盡管我一直以來都還是沒做出過這方面的bug，但是由于（主要是用來處理何時應(yīng)該delete對象部分的）邏輯復(fù)雜，導(dǎo)致數(shù)據(jù)結(jié)構(gòu)必須為delete對象的部分讓步，代碼維護起來也相當(dāng)?shù)牡疤邸?/p>

3、有些優(yōu)化無法做。舉個簡單的例子，parser combinator就根本沒辦法處理左遞歸。沒有左遞歸，寫起某些文法來也是特別的蛋疼。還有合并共同前綴等等的優(yōu)化也不能做，這導(dǎo)致我們必須為了性能犧牲本來就已經(jīng)充滿了噪音的文法的表達，轉(zhuǎn)而人工作文法的共同前綴合并，文法看起來就更亂了。

當(dāng)然上面三個理由看起來好像不太直觀，那我就舉一個典型的例子。大家應(yīng)該還記得我以前寫過一個叫做NativeX的語言，還給它做了一個帶智能提示的編輯器（還有這里和這里）。NativeX是一個C++實現(xiàn)的C+template+concept mapping的語言，語法分析器當(dāng)然是用上一個版本的可配置語法分析器來做的。文法規(guī)則很復(fù)雜，但是被C++這么以表達，就更加復(fù)雜了（.\Library\Scripting\Languages\NativeX\NativeXParser.cpp），已經(jīng)到了不仔細看就無法維護的地步了。

綜上所述，做一個新的可配置語法分析器出來理由充分，勢在必得。但是形式上是什么樣子的呢？上面說過我以前給NativeX寫過一個帶智能提示的編輯器。這個編輯器用的是WinForm，那當(dāng)然也是用C#寫的，因此那個對性能要求高到離譜的NativeX編輯器用的語法分析器當(dāng)然也是用C#寫的。流程大概如下：
1、用C#按照要求聲明語法樹結(jié)構(gòu)
2、使用我的庫用C#寫一個文法
3、我的庫會執(zhí)行這個文法，生成一大段C#寫的等價的遞歸下降語法分析器的代碼
當(dāng)時我把這個過程記錄在了這篇博客文章里面。

因此現(xiàn)在就有一個計劃，這個新的可配置語法分析器當(dāng)然還是要完全用C++，但是這就跟正則表達式一樣：
1、首先語法樹結(jié)構(gòu)和文法都聲明在一個字符串里面
2、可配置語法分析器可以在內(nèi)存中動態(tài)執(zhí)行這段文法，并按照給定的語法樹結(jié)構(gòu)給出一個在內(nèi)存中的動態(tài)的數(shù)據(jù)結(jié)構(gòu)
3、可配置語法分析器當(dāng)然還要附帶一個命令行工具，用來讀文法生成C++代碼，包括自帶Visitor模式的語法樹結(jié)構(gòu)，和C++寫的遞歸下降語法分析器

所以現(xiàn)在就有一個草稿，就是那個“聲明在字符串里面”的語法樹結(jié)構(gòu)和文法的說明。這是一個很有意思的過程。

首先，這個可配置語法分析器需要在內(nèi)存中表達語法樹結(jié)構(gòu)，和一個可以執(zhí)行然后產(chǎn)生動態(tài)數(shù)據(jù)結(jié)構(gòu)的文法。因此我們在使用它的時候，可以選擇直接在內(nèi)存中堆出語法樹結(jié)構(gòu)和文法的描述，而不是非得用那個字符串的表達形式。當(dāng)然，字符串的表達形式肯定是十分緊湊的，但這不是必須的，只是推薦的。

其次，parse這個“語法樹結(jié)構(gòu)和文法都聲明”當(dāng)然也需要一個語法分析器是不是？所以我們可以用上面的方法，通過直接在內(nèi)存中堆出文法來用自己構(gòu)造出一個自己的語法分析器。

再者，有了一個內(nèi)存中的語法分析器之后，我就可以將上面第三步的命令行工具做出來，然后用它來描述自己的文法，產(chǎn)生出一段C++寫的遞歸下降語法分析器，用來分析“語法樹結(jié)構(gòu)和文法都聲明”，然后就有了一對C++代碼文件。

最后，把產(chǎn)生出來的這對C++代碼文件加進去，我們就有了一個C++直接寫，而不是在內(nèi)存中動態(tài)構(gòu)造出來的“語法樹結(jié)構(gòu)和文法都聲明”的分析器了。然后這個分析器就可以替換掉命令行工具里面那個原先動態(tài)構(gòu)造出來的語法分析器。當(dāng)然那個動態(tài)構(gòu)造出來的語法分析器這個時候已經(jīng)沒用了，因為有了生成的C++語法分析器，我們就可以直接使用“語法樹結(jié)構(gòu)和文法都聲明”來描述自己，得到這么一個描述的字符串，然后隨時都可以用這個字符串來動態(tài)生成語法分析器了。

總而言之就是
1、實現(xiàn)可配置語法分析器，可以直接用數(shù)據(jù)結(jié)構(gòu)做出一個產(chǎn)生動態(tài)數(shù)據(jù)結(jié)構(gòu)的parser combinator，記為PC。
2、用PC做一個“語法樹結(jié)構(gòu)和文法都聲明”的語法分析器。這個“語法樹結(jié)構(gòu)和文法都聲明”記為PC Grammar。
3、PC Grammar當(dāng)然可以用來表達PC Grammar自己，這樣我們就得到了一個專門用來說明什么是合法的“語法樹結(jié)構(gòu)和文法都聲明”的描述的字符串的這么個文法，記為PC Grammar Syntax Definition。
4、通過這份滿足PC Grammar要求的PC Grammar Syntax Definition，我們就可以用PC來解釋PC Grammar Syntax Definition，動態(tài)產(chǎn)生一個解釋PC Grammar的語法分析器
5、有了PC Grammar的語法分析器PC Grammar Parser (in memory version)，之后我們就可以把“文法->C++代碼”的代碼生成器做出來，稱之為PC Grammar C++ Codegen。
6、有了PC Grammar C++ Codegen，我們就可以用他讀入PC Grammar Syntax Definition，產(chǎn)生一個直接用C++寫的PC Grammar的語法分析器，叫做PC Grammar Parser (C++ version)。

到此為止，我們獲得的東西有
1、PC （Parser Combinator）
2、PC Grammar
3、PC Grammar Syntax Definition
4、PC Grammar Parser (in memory version)
5、PC Grammar Parser (C++ version)
6、PC Grammar C++ Codegen

其中，1、3、4、5、6都是可以執(zhí)行的，2是一個“標準”。到了這一步，我們就可以用PC Grammar Parser (C++ version)來替換掉PC Grammar C++ Codegen里面的PC Grammar Parser (in memory version)了。這就跟gcc要編譯一個小編譯器來編譯自己得到一個完整的gcc一樣。這個過程還可以用來測試PC Grammar C++ Codegen是否寫的足夠好。

那么“語法樹結(jié)構(gòu)和文法都聲明”到地是什么樣子的呢？我這里給出一個簡單的文法，就是用來parse諸如int、vl::collections::List<WString>、int*、int&、int[]、void(int, WString, double*)的這些類型的字符串了。下面首先展示如何用這個描述來解決上面的“類型”的語法書聲明：

class Type{}

class DecoratedType : Type
{
    enum Decoration
    {
        Pointer,
        Reference,
        Array,
    }
    Decoration        decoration;
    Type            elementType;
}

class PrimitiveType : Type
{
    token            name;
}

class GenericType : Type
{
    Type            type;
    Type[]            arguments;
}

class SubType : Type
{
    Type            type;
    token            name;
}

class FunctionType : Type
{
    Type            returnType;
    Type[]            arguments;
}

然后就是聲明語法分析器所需要的詞法元素，用正則表達式來描述：

token SYMBOL        = <|>|\[|\]|\(|\)|,|::|\*|&
token NAME            = [a-zA-Z_]\w*

這里只需要兩種token就可以了。接下來就是兩種等價的對于這個文法的描述，用來展示全部的功能。

========================================================

Type SubableType    = NAME[name] as PrimitiveType
                    = SubableType[type] '<' Type[arguments] { ',' Type[arguments] } '>' as GenericType
                    = SubableType[type] '::' NAME[name] as SubType

Type Type            = @SubableType
                    = Type[elementType](
                            ( '*' {decoration = DecoratedType::Pointer}
                            | '&' {decoration = DecoratedType::Reference}
                            | '[' ']' {decoration = ecoratedType::Array}
                            )
                        ) as DecoratedType
                    = Type[returnType] '(' Type[arguments] { ',' Type[arguments] } ')' as FunctionType

========================================================

rule PrimitiveType    PrimitiveType    = NAME[name]
rule GenericType    GenericType        = SubableType[type] '<' Type[arguments] { ',' Type[arguments] } '>'
rule SubType        SubType            = SubableType[type] :: NAME[name]
rule Type            SubableType        = @PrimitiveType | @GenericType | @SubType

rule DecoratedType    DecoratedType    = Type[elementType] '*' {decoration = DecoratedType::Pointer}
                                    = Type[elementType] '&' {decoration = DecoratedType::Reference}
                                    = Type[elementType] '[' ']' {decoration = DecoratedType::Array}
rule FunctionType    FunctionType    = Type[returnType] '(' Type[arguments] { ',' Type[arguments] } ')'
rule Type            Type            = @SubableType | @DecoratedType | @FunctionType

========================================================

如果整套系統(tǒng)開發(fā)出來的話，那么我就會提供一個叫做ParserGen.exe的命令行工具，把上面的字符串轉(zhuǎn)換為一個可讀的、等價與這段文法的、使用遞歸下降方法來描述的、C++寫出來的語法分析器和語法樹聲明了。