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

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

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

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

    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);

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

============================無(wú)恥的分割線====================================

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

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

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

    現(xiàn)在我們做一個(gè)簡(jiǎ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' ')'

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

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