之前曾經(jīng)為Parser Combinator寫過一篇教程。這次為了處理Vczh Library++新設(shè)計(jì)的ManagedX托管語言，我為Parser Combinator新增了三個組合子。

    第一個是def，第二個是let。它們組合使用。def(pattern, defaultValue)的意思是，如果pattern成功了那么返回pattern的分析結(jié)構(gòu)，否則返回defaultValue。let(pattern, value)的意思是，如果pattern成功了則返回value，否則失敗。因此他們可以一起使用。舉個例子，ManagedX跟C#一樣具有5種type accessor：public, protected, protected internal, private, internal。其中四種accessor的文法類型是token，剩下的protected internal則是tuple<token, token>。因此我們無法很方便地為它寫一個記號到語法樹的轉(zhuǎn)換函數(shù)。而且對于缺省情況要返回private的這種行為，在EBNF+handler上直接表達(dá)出來也比較困難。當(dāng)def和let還不存在的時候，我們需要這么寫：

    accessor = (PUBLIC[ToAccessor] | PROTECTED[ToAccessor] | PRIVATE[ToAccessor] | INTERNAL[ToAccessor] | (PROTECTED + INTERNAL)[ToProtectedInternal])[ToAccessorWithDefault];

    這個時候我們需要創(chuàng)建三個函數(shù)，分別是ToAccessor、ToProtectedInternal和ToAccessorWithDefault。因?yàn)閍ccessor本身不是一個重要的語法元素，所以我們不需要為accessor記錄一些源代碼的位置信息。表達(dá)式則需要位置信息，這可以在我們產(chǎn)生錯誤信息的時候知道錯誤發(fā)生在源代碼中的位置。而accessor總是直接屬于某一個重要的語法元素的，所以不需要保存。如果不需要保存位置信息的話，那么一個ToXXX的函數(shù)其實(shí)就是沒有必要的。這個時候可以讓def和let來簡化操作：

    accessor = def(let(PUBLIC, acc::Public) | let(PROTECTED, acc::Protected) | let(PRIVATE, acc::Private) | let(INTERNAL, acc::Internal) | let(PROTECTED+INTERNAL, acc::ProtectedInternal), acc::Private);

    看起來好像差不多，但實(shí)際上我們已經(jīng)減少了那三個不需要存在的函數(shù)。

============================無恥的分割線====================================

    第三個是binop。做這個主要是因?yàn)槟莻€通用的lrec（左遞歸組合子）在對付帶大量括號的表達(dá)式的時候性能表現(xiàn)不好。這里稍微解釋一下原因。假設(shè)我們的語言有>、+、*和()四種操作符，那文法一般都寫成：

    exp0 = NUMBER | '(' exp3 ')'
    exp1 = exp1 '*' exp0 | exp0
    exp2 = exp2 '+' exp1 | exp1
    exp3 = exp3 '>' exp2 | exp2

    因此可以很容易的知道，當(dāng)我們分析1*2*3的時候，走的是下面的路子：
    exp3
    = exp2
    = exp1
    = exp1 '*' exp0
    = exp1 '*' exp1 '*' exp0
    = '1' '*' '2' '*' '3'

    現(xiàn)在我們做一個簡單的變換，把1*2*3變成((1*2)*3)。意義不變，但是分析的路徑卻完全改變了：
    exp3
    = exp2
    = exp1
    = exp0
    = '(' exp3 ')'
    = '(' exp2 ')'
    = '(' exp1 ')'
    = '(' exp1 '*' exp0 ')'
    = '(' exo0 '*' exp0 ')'
    = '(' '(' exp3 ')' '*' exp0 ')'
    = '(' '(' exp2 ')' '*' exp0 ')'
    = '(' '(' exp1 ')' '*' exp0 ')'
    = '(' '(' exp1 '*' exp0 ')' '*' exp0 ')'
    = '(' '(' exp0 '*' exp0 ')' '*' exp0 ')'
    = '(' '(' '1' '*' '2' ')' '*' '3' ')'

    咋一看好像沒什么區(qū)別，但是對于ManagedX這種有十幾個優(yōu)先級的操作符的語言來說，如果給一個復(fù)雜的表達(dá)式的每一個節(jié)點(diǎn)都加上括號，等于一下子增加了上千層文法的遞歸分析。由于Parser Combinator是遞歸向下分析器，因此路徑有這么長，那么遞歸的層次也會有這么長。而且為了避免boost::Spirit那個天殺的超慢編譯速度的問題，這里犧牲了一點(diǎn)點(diǎn)性能，將組合字的Parse函數(shù)做成了虛函數(shù)，所以編譯速度提高了超多。一般來說一個需要編譯一個半小時的boost::Spirit語法分析器用我的庫只需要幾秒鐘就可以編譯完了。不過現(xiàn)在卻帶來了問題。括號一多，性能下降的比較明顯。但是我們顯然不能因噎廢食，因此我決定往Parser Combinator提供一個手寫的帶優(yōu)先級的左右結(jié)合一二元操作符語法分析器。為了將這個手寫的分析器插入框架并變得通用，我決定采用下面的結(jié)構(gòu)。下面的代碼是從ManagedX的語法分析器中截取出來的：
    binop組合子的參數(shù)代表整個帶優(yōu)先級的最高優(yōu)先級表達(dá)式組合字（參考上面給出的>+*()文法，可以知道這里的exp0是什么意思）。binop給出了四個子組合子，分別是pre（前綴一元操作符）、post（后綴一元操作符）、lbin（左結(jié)合二元操作符）和rbin（右結(jié)合二元操作符）。precedence代表一個優(yōu)先級的所有操作符定義結(jié)束。這里我做了一個小限制，也就是每一個precedence只能包含pre、post、lbin和rbin的其中一種。實(shí)踐表明這種限制不會帶來任何問題。因此這里我們得到了一張操作符和優(yōu)先級的關(guān)系表。到了這里我們就可以在Parser Combinator的框架下寫一個手寫的語法分析器（下載源代碼并打開Library\Combinator\_Binop.h）來做了。至于如何手寫語法分析器，我之前給出了一篇文章，大家可以參考這個來閱讀_Binop.h。

    binop比起簡單的用lrec做同樣的事情，性能在debug下提高了100多倍，release下面則少一點(diǎn)。到了這里，Parser Combinator重新滿足了性能要求，我們可以放心大膽的用一點(diǎn)點(diǎn)無所謂的性能換取一千多倍的編譯時間了。在這里貼出當(dāng)binop還沒出現(xiàn)的時候我用lrec給出的操作符文法的實(shí)現(xiàn)：