Vczh Library++ 語法分析器開發(fā)指南

陳梓瀚

 

前言

在日常的開發(fā)工作中我們總是時不時需要寫一些語法分析器。語法分析器不一定指的是一門語言的編譯器前端，也有可能僅僅是一個自己設(shè)計格式的配置文件的讀寫程序，或者是一門用來簡化我們開發(fā)的DSL（領(lǐng)域?qū)Ｓ谜Z言）。我們可以選擇使用XML，不過因?yàn)?/span>XML的噪音實(shí)在是太多，所以自己寫語法分析器在有些情況下是必要的，特別是那種經(jīng)常需要修改的文件，使用XML有時候會增加我們的負(fù)擔(dān)，除非我們專門為此開發(fā)一個編輯器程序。

 

這篇文章將緊密結(jié)合一個帶函數(shù)的四則運(yùn)算計算器的例子（Documentation\Samples\ExpressionCalculator\ExpressionCalculator.sln）來說明如何使用Vczh Library++提供的工具來大幅度簡化我們的語法分析器的開發(fā)，并最終給出一個可以編譯的例子。雖然這個例子實(shí)在是老掉牙了，不過開發(fā)一個四則運(yùn)算計算器可以覆蓋大部分開發(fā)語法分析的過程中會遇到的問題，所以也不失為一個好的例子。

 

這個例子可以在Vczh Library++的代碼里面找到。

制定語法

我們需要對帶函數(shù)的四則運(yùn)算計算器下一個定義，這樣我們才可以有目的地完成這個任務(wù)。我們對四則運(yùn)算式子是很熟悉的，一個四則運(yùn)算式子包含加減乘除、括號和數(shù)字。我們還可以支持負(fù)號：-a，其實(shí)是(0-a)的簡寫形式。那么什么是支持函數(shù)呢？這里我們只考慮單參數(shù)函數(shù)的情況，譬如說三角函數(shù)和對數(shù)指數(shù)等等。譬如說下面的式子就是滿足定義的帶函數(shù)的四則運(yùn)算式子：

 

sin(1+2) + cos(3*-4)

 

Vczh Library++使用語法的角度來對待一個字符串，因此我們可以把上面的定義轉(zhuǎn)換成語法。一個語法用來表示字符串的一個子集。我們可以通過語法來表達(dá)什么樣的字符串是滿足規(guī)定的，什么樣的字符串是不滿足規(guī)定的。不過一個具有現(xiàn)實(shí)意義的語法總是會有一些局限性的，譬如說你很難用上下文無關(guān)的文法來表達(dá)一個字符串：a…ab…bc…c，其中三種字母的數(shù)量都相等。幸好在絕大多數(shù)情況下我們都不需要去面對這些高難度的問題，因此可以用一些簡單的規(guī)則來處理：

 

RULE = EXPRESSION

 

RULE是這個規(guī)則的名字，而EXPRESSION是這個規(guī)則的定義。語法可以由一條規(guī)則組成，也可以由很多條規(guī)則組成。當(dāng)所有的規(guī)則都列出來之后，那么每一個規(guī)則的名字都是一個字符串的集合。大部分情況下你需要指定一個“總?cè)肟?#8221;來代表整個語法。

 

舉個例子，假設(shè)我們判斷一個字符串是不是無符號整數(shù)。一個無符號整數(shù)只能由數(shù)字字符組成。于是我們可以先用一條規(guī)則來代表“數(shù)字字符”。這里我們可以使用“|”來代表“或”，那么下面的規(guī)則就表示DIGIT是’0’或’1’或…或’9’：

DIGIT = ‘0’ | ‘1’ | ‘2’ | ‘3’ | ‘4’ | ‘5’ | ‘6’ | ‘7’ | ‘8’ | ‘9’

那么，無符號整數(shù)就是“很多數(shù)字字符”：

INTEGER = DIGIT | INTEGER DIGIT

無符號整數(shù)INTEGER要么是一個數(shù)字字符，要么就是一個合法的無符號整數(shù)后面再加上一個數(shù)字字符。無符號整數(shù)加上一個數(shù)字字符仍然是一個無符號整數(shù)。

 

現(xiàn)在可以來檢驗(yàn)一下。譬如說“1”是一個無符號整數(shù)，那么從INTEGER開始，分析“1”所走的路徑就是

INTEGER

= DIGIT                                          (INTEGER = DIGIT)

= ‘1’                                                (DIGIT = ‘1’)

字符串“123”顯然也應(yīng)該是一個無符號整數(shù)。“123”是一些數(shù)字字符組成的，因此走的路徑跟單個字符稍微有些不同。這里將會交替使用INTEGER的兩條路徑來模擬循環(huán)：

INTEGER

= INTEGER DIGIT                        (INTEGER = INTEGER DIGIT)

= INTEGER DIGIT DIGIT            (INTEGER = INTEGER DIGIT)

= DIGIT DIGIT DIGIT                  (INTEGER = DIGIT)

= ‘1’ DIGIT DIGIT                        (DIGIT = ‘1’)

= ‘1’ ‘2’ DIGIT                              (DIGIT = ‘2’)

= ‘1’ ‘2’ ‘3’                                    (DIGIT = ‘3’)

在使用INTEGER分析“123”的時候，我們可以交替使用INTEGER = DIGIT和INTEGER = INTEGER DIGIT這兩條規(guī)則來將一個INTEGER替換成恰好三個DIGIT，然后再將DIGIT替換成’1’、’2’和’3’三個字符，從而確信“123”滿足INTEGER的定義，因此“123”是一個無符號整數(shù)。

 

替換的過程并不是唯一的，我們完全可以使用另一種順序來將INTEGER替換成“123”：

INTEGER

= INTEGER DIGIT                        (INTEGER = INTEGER DIGIT)

= INTEGER ‘3’                              (DIGIT = ‘3’)

= INTEGER DIGIT ‘3’                  (INTEGER = INTEGER DIGIT)

= INTEGER ‘2’ ‘3’                        (DIGIT = ‘2’)

= DIGIT ‘2’ ‘3’                              (INTEGER = DIGIT)

= ‘1’ ‘2’ ‘3’                                    (DIGIT = ‘1’)

這正是語法的一個特點(diǎn)：替換順序與結(jié)果無關(guān)。

 

現(xiàn)在我們將這個例子再深入一點(diǎn)，如何用語法規(guī)則來描述一個逗號分隔的無符號整數(shù)列表呢？逗號分隔的無符號整數(shù)列表可以是一個整數(shù)“123”，也可以使多個整數(shù)“1,23,456”。這也是重復(fù)的一種，只是跟INTEGER的那種重復(fù)有所區(qū)別——多了一個逗號。根據(jù)上面的描述可以知道，逗號分隔的無符號整數(shù)列表有兩種情況，第一種是單獨(dú)的一個整數(shù)，第二種是一個已經(jīng)完成的列表后面跟著一個逗號和一個整數(shù)。那么事情就變得簡單了。假設(shè)我們使用LIST來代表這個列表，那么根據(jù)上面的描述我們可以用類似的技巧來描述它：

LIST = INTEGER | LIST ‘,’ INTEGER

用LIST來分析一個數(shù)字列表的過程與用INTEGER分析一個無符號整數(shù)是相似的。因?yàn)槠鶈栴}，這里只展示使用LIST處理“1,23,456”的其中一種方法：

LIST

= LIST ‘,’ INTEGER                                                  (LIST = LIST ‘,’ INTEGER)

= LIST ‘,’ INTEGER ‘,’ INTEGER                                     (LIST = LIST ‘,’ INTEGER)

= INTEGER ‘,’ INTEGER ‘,’ INTEGER                            (LIST = INTEGER)

= DIGIT ‘,’ INTEGER ‘,’ INTEGER                         (INTEGER = DIGIT)

= ‘1’ ‘,’ INTEGER ‘,’ INTEGER                               (DIGIT = ‘1’)

= ‘1’ ‘,’ INTEGER DIGIT ‘,’ INTEGER                            (INTEGER = INTEGER DIGIT)

= ‘1’ ‘,’ DIGIT DIGIT ‘,’ INTEGER                         (INTEGER = DIGIT)

= ‘1’ ‘,’ ‘2’ DIGIT ‘,’ INTEGER                               (DIGIT = ‘2’)

= ‘1’ ‘,’ ‘2’ ‘3’ ‘,’ INTEGER                                              (DIGIT = ‘3’)

= ‘1’ ‘,’ ‘2’ ‘3’ ‘,’ INTEGER DIGIT                         (INTEGER = INTEGER DIGIT)

= ‘1’ ‘,’ ‘2’ ‘3’ ‘,’ INTEGER DIGIT DIGIT             (INTEGER = INTEGER DIGIT)

= ‘1’ ‘,’ ‘2’ ‘3’ ‘,’ DIGIT DIGIT DIGIT                            (INTEGER = DIGIT)

= ‘1’ ‘,’ ‘2’ ‘3’ ‘,’ ‘4’ DIGIT DIGIT                         (DIGIT = ‘4’)

= ‘1’ ‘,’ ‘2’ ‘3’ ‘,’ ‘4’ ‘5’ DIGIT                               (DIGIT = ‘5’)

= ‘1’ ‘,’ ‘2’ ‘3’ ‘,’ ‘4’ ‘5’ ‘6’                                              (DIGIT = ‘6’)

 

在開發(fā)實(shí)際的語法分析器的時候，我們總是需要考慮空格的問題。人們用空格讓一個具有嚴(yán)格限制的字符串變得更加易讀，譬如說將“1,23,456”變成“1,  23,  456”會讓密密麻麻的一堆字符變得非常容易看懂。空格也不是亂加的，有些地方可以加空格，有些地方不能加空格。

 

在上面這個例子里面，如果要支持空格，那么空格除了不能插在INTEGER中間，應(yīng)該可以放在任何的地方。這個時候就帶來麻煩了，帶空格的語法不是太好寫。如果我們讓LIST支持空格，那會把LIST變成下面這個樣子：

SPACES = <EMPTY> | SPACES ‘ ’

LIST = SPACES INTEGER SPACES | LIST ‘,’ SPACES INTEGER SPACES

這里<EMPTY>代表空字符串，所以SPACES就是沒有空格、一個空格或者很多空格了。因此我們必須在LIST里面所有可以加入空格的地方寫空格，這會讓我們的語法膨脹得很厲害。因此我們必須使用一種方法來讓我們免除空格帶來的困擾。

詞法分析

引入詞法分析的目的是讓我們的語法更加簡潔。我們可以將處理空格、注釋和分割字符串的工作與語法分析完全分開，那么代碼寫起來就會更加容易，維護(hù)起來也會更加簡單了。我們總是傾向于讓我們的程序越來越容易理解和維護(hù)。

 

詞法分析的目標(biāo)是將輸入的字符串適當(dāng)分割并拋棄處理掉沒有用的部分。“適當(dāng)分割”一般來說沒有一個明確的規(guī)則，應(yīng)該根據(jù)具體情況而定，越方便越好。在大部分情況下我們僅把輸入的字符串簡單的劃分為符號、數(shù)字、操作符、字符串、空格和注釋等等的簡單部分。這些劃分一般代表“插入空格會改變意義”。比如說“1234”變成“12 34”之后，就從一個整數(shù)變成兩個整數(shù)了。字符串的情況有點(diǎn)特別，雖然字符串中間插入一個空格還是一個字符串，但是插入空格后的字符串已經(jīng)不是插入空格前的字符串了，因?yàn)閮?nèi)容已經(jīng)發(fā)生了變化。與此同時，在一個整數(shù)列表里面，往逗號后面插入一個空格不會影響這個列表所要表達(dá)的意義，因此將字符串轉(zhuǎn)換成“整數(shù)列表”的工作一般劃分在語法分析而不是詞法分析里。

 

處理詞法分析的方法一般是使用正則表達(dá)式。Vczh Library++提供了一個使用正則表達(dá)式來開發(fā)詞法分析器的類庫。關(guān)于正則表達(dá)式的語法請參考Documentation\Chinese\Vczh Library++\Regex\Regex.htm#Grammar，關(guān)于這個詞法分析器類的內(nèi)容請參考Documentation\Chinese\Vczh Library++\Regex\Regex.htm#RegexToken。

 

在使用Vczh Library++進(jìn)行詞法分析的開發(fā)之前需要掌握正則表達(dá)式的簡單用法。這里我們假設(shè)讀者對正則表達(dá)式已經(jīng)入門了。精通是沒有必要的，因?yàn)樵~法分析使用到的正則表達(dá)式的內(nèi)容十分簡單。我們回到之前的“帶函數(shù)的四則運(yùn)算計算器”。經(jīng)過簡單的整理，我們知道一個帶函數(shù)的四則運(yùn)算計算器由數(shù)字、函數(shù)名、操作符和符號組成。

 

加號與減號的優(yōu)先級一樣，對于語法分析來說他們其實(shí)沒有區(qū)別。乘號與除號也類似。當(dāng)語法分析結(jié)束，語義分析開始的時候，加號與減號的區(qū)別才會出現(xiàn)。因此在詞法分析里面我們可以把他們當(dāng)成同樣的東西來對待，因此有：

BLANK = \s+                                 ：空格

ADD = \+|-                                    ：加減號

MUL = \*|/                                   ：乘除號

NUMBER = \d+(.\d+)?               ：數(shù)字

ID = [a-zA-Z_]\w*                       ：函數(shù)名

OPEN = \(                                      ：開括號

CLOSE = \)                                     ：閉括號

 

我們把分類后的結(jié)果叫記號類型。一個字符串可以被分成很多記號，每一個記號屬于一個記號類型。如果一個記號不屬于任何記號類型的話（譬如問號“?”），那么遇到了詞法分析的錯誤。這個時候我們需要報告錯誤了。

 

Vczh Library++有一個簡單的方法讓我們是用正則表達(dá)式表達(dá)記號類型，并使用他們來構(gòu)造詞法分析器：

 

     List<WString> patterns;

     const int BLANK        = patterns.Add(L"/s+");

     const int ADD           = patterns.Add(L"/+|-");

     const int MUL           = patterns.Add(L"/*|//");

     const int NUMBER        = patterns.Add(L"/d+(./d+)?");

     const int ID            = patterns.Add(L"[a-zA-Z_]/w*");

     const int OPEN         = patterns.Add(L"/(");

     const int CLOSE        = patterns.Add(L"/)");

     RegexLexer lexer(patterns.Wrap());

 

為了方便書寫正則表達(dá)式，Vczh Library++同時支持兩種轉(zhuǎn)義符：“\”和“/”。因?yàn)?/span>C++使用了“\”作為字符串的轉(zhuǎn)義符，所以在這里我們可以使用“/”，這樣寫起來會比較清晰。

 

構(gòu)造詞法分析器的方法很簡單，我們將所有正則表達(dá)式放到一個字符串列表List<WString>，然后交給詞法分析器RegexLexer，我們就得到了一個詞法分析器了。在分析字符串的時候，每一個記號的類型其實(shí)就是該記號的正則表達(dá)式描述在字符串列表中的位置。如果發(fā)生錯誤的話，記號類型會變成-1。因?yàn)榱斜淼?/span>Add函數(shù)返回添加的元素在列表中的位置，因此就可以使用上面的寫法來簡單地構(gòu)造一個詞法分析器了。

 

我們可以用一種簡單的方法來使用這個詞法分析器。RegexLexer輸出的記號存放在RegexToken類型里面，我們可以使用任何容器來存放記號，在這里我們?nèi)匀皇褂?/span>RegexToken。

 

RegexToken的定義如下：

     class RegexToken

     {

     public:

         int                start;

         int                length;

         int                token;

         const wchar_t*     reading;

         int                lineIndex;

         int                lineStart;

         int                codeIndex;

};

RegexToken記錄了一個記號在輸入的字符串中的位置、所在的行和在該行內(nèi)的位置、記號類型和指向該位置的指針。這些信息可以用來做很多事情，譬如在產(chǎn)生錯誤信息的時候可以精確指定錯誤發(fā)生的位置。

 

在這里我們需要過濾空格，也就是過濾掉BLANK記號，因此我們需要寫一個過濾函數(shù)：

bool IsNotBlank(RegexToken token)

{

          return token.token!=0;

}

我們知道BLANK就是0，因此這里直接以0代替。有了這個函數(shù)之后，我們就可以將輸入切割成記好了：

List<RegexToken> tokens;

CopyFrom(tokens.Wrap(), lexer.Parse(L"(1 + 2) * abs(-3 - 4)")>>Where(IsNotBlank));

執(zhí)行了這段代碼之后，我們就將字符串切割成記號了。這里只用了15行就完成了詞法分析器的定義并使用詞法分析器來分析一個字符串的任務(wù)了。

 

注意：如果將一個字符指針傳入lexer.Parse的話，在獲得記號列表之后將這個字符指針刪除，那么所有記號中的reading將全部變成野指針。lexer.Parse的參數(shù)是WString類型，所以這個例子在執(zhí)行之后，臨時的字符串對象會被刪除，因此記號列表中的所有reading成員將全部變成野指針。因此在實(shí)踐過程中最好先使用一個WString變量去保存輸入的字符串，然后將這個變量傳入lexer.Parse，之后所有reading成員將指向這個變量內(nèi)部的一個有效指針。

 

這個時候我們就可以使用tokens里面的信息來做處理了。不過Vczh Library++還提供了語法分析器的類庫，讓我們可以不用親自遍歷這些記號。

帶函數(shù)四則運(yùn)算式子的語法

到了這里，我們可以把數(shù)字、函數(shù)名和符號當(dāng)成已經(jīng)存在的東西來看待了，而且再也不需要考慮空格的問題了。于是我們可以仔細(xì)組織帶函數(shù)四則運(yùn)算式子的語法：

FACTOR = NUMBER

FACTOR = ‘-‘ FACTOR

FACTOR = ‘(‘ EXP ‘)’

FACTOR = ID ‘(‘ EXP ‘)’

TERM = FACTOR | TERM MUL FACTOR

EXP = TERM | EXP ADD TERM

 

語法的設(shè)計直接反映了我們的思考過程。這是一個帶有遞歸的語法。當(dāng)我們考慮下面的式子的時候

1*(2+2)*3+4*5*sin(6)+7*8*9

我們首先使用加減法將式子分割為三個部分

1*(2+2)*3  +  4*5*sin(6)  +  7*8*9

然后使用乘除法將式子分割為九個部分，然后我們發(fā)現(xiàn)(2+2)和sin(6)他們是一個整體。不過整體仍然是由部分構(gòu)成的，因此內(nèi)部還包含表達(dá)式。所以不難看出，這里的FACTOR代表“整體”，TERM代表乘除法構(gòu)成的“第二層表達(dá)式”，EXP代表加減法構(gòu)成的“第一層表達(dá)式”。這個語法同時還代表“先乘除后加減”的計算原則。

 

但是這里還有一個問題，我們觀察一下EXP = TERM | EXP ADD TERM這條規(guī)則。我們不難發(fā)現(xiàn)他們其實(shí)是獨(dú)立的兩條規(guī)則的組合：

EXP = TERM

EXP = EXP ADD TERM

第二條EXP的規(guī)則仍然從EXP開始，這種遞歸稱為左遞歸。左遞歸直接處理起來比較困難，因?yàn)槟惴治龅?/span>EXP的時候很容易陷入一個死循環(huán)，因此我們需要拆開它們。

 

我們引入擴(kuò)展規(guī)則的機(jī)制來解決這個問題。如果我們想表達(dá)一個循環(huán)的話，我們不得不專門為它建立一條規(guī)則并命名：

LIST = ITEM | LIST ITEM

如果我們可以簡化成LIST = ITEM+的話，就不需要專門為它起一個名字LIST了，而可以直接在各個地方使用ITEM+。跟正則表達(dá)式一樣，我們使用+和*來代表循環(huán)。因此EXP就可以被改寫成EXP = TERM ( ADD TERM)*了。注意(與’(‘的區(qū)別，’(‘代表一個字符，而(跟平常一樣用來規(guī)定優(yōu)先級，譬如這里代表重復(fù)“*”的范圍。于是我們可以重新組織語法：

FACTOR = NUMBER

FACTOR = ‘-‘ FACTOR

FACTOR = ‘(‘ EXP ‘)’

FACTOR = ID ‘(‘ EXP ‘)’

TERM = FACTOR (MUL FACTOR)*

EXP = TERM (ADD TERM)*

語法類型與C++表達(dá)

Vczh Library++允許我們直接把語法在C++的框架下表達(dá)出來，因此我們不得不對語法的表達(dá)形式做一點(diǎn)修改使之可以滿足C++的要求。所以這里我們需要做兩件事情，第一件事情是規(guī)則的類型，第二件事情是如何用C++語句來表達(dá)規(guī)則。

 

規(guī)則的類型含義比較復(fù)雜，一個規(guī)則的類型不僅取決于它自身，還取決于它的產(chǎn)出。如果我們用語法規(guī)則來將記號直接轉(zhuǎn)換成計算結(jié)果，那么一般來說規(guī)則的類型就是計算結(jié)果的類型，譬如說數(shù)字。如果我們用語法規(guī)則來講記號轉(zhuǎn)換成四則運(yùn)算式子的語法樹，那么規(guī)則的類型就是語法樹節(jié)點(diǎn)的指針。

 

如果我們把規(guī)則看成一個函數(shù)的話，那應(yīng)該會更加容易理解。一個語法規(guī)則將輸入的記號列表轉(zhuǎn)換成我們需要的結(jié)果，所以規(guī)則的類型至少包含兩個部分，一個是輸入記號的類型，一個是輸出類型。Vczh Library++專門為規(guī)則定義了一個模板類，而且這里FACTOR、TERM和EXP將會作為C++的變量直接聲明出來。在這里我們希望語法規(guī)則能直接將輸入轉(zhuǎn)換成計算結(jié)果，結(jié)果的類型是double，輸入的類型是RegexToken，因此我們可以這么聲明三個規(guī)則的名字：

Rule<TokenInput<RegexToken>, double> factor, term, exp;

TokenInput是輸入的其中一種表達(dá)形式，它可以將一個指針和長度轉(zhuǎn)換成符合Rule輸入的類型。Vczh Library++還同時提供了StringInput<T>和EnumerableInput<T>，但是我們已經(jīng)將記號保存在List<RegexToken>里面了，因此使用TokenInput<T>是最合適的。

 

StringInput<T>也好，EnumerableInput<T>也好，TokenInput<T>也好，其實(shí)都是一個迭代器。Vczh Library++的語法分析器類庫為迭代器規(guī)定了一個接口，這三種迭代器都是在那個接口的框架下實(shí)現(xiàn)的。我們可以簡單的把一個把TokenInput<RegexToken>套在List<RegexToken>上：

TokenInput<RegexToken> input(&tokens[0], tokens.Count());

TokenInput在內(nèi)部只保存了一個指針、長度和當(dāng)前位置，所以是一個相當(dāng)輕量級的類，可以到處復(fù)制并且不會有多少性能上的損失。不過TokenInput<T>的生命周期不應(yīng)該比List<T>長，不然TokenInput<T>指向的對象會因?yàn)橐呀?jīng)被釋放掉而發(fā)生問題。同樣的道理，在TokenInput<T>已經(jīng)被套在List<T>上的時候，List<T>最好不要被修改。

 

現(xiàn)在輸入的類型已經(jīng)清楚了，可以開始研究輸出的類型了。上面的factor的聲明是Rule<TokenInput<RegexToken>, double>，因此factor可以看成是一個輸入迭代器TokenInput<RegexToken>，修改迭代器位置并輸出double作為結(jié)果的函數(shù)。不過其實(shí)返回的實(shí)際類型是ParsingResult<double>，因?yàn)橐粋€規(guī)則在分析一個迭代器輸入的時候可能會產(chǎn)生錯誤，這個時候不能修改輸入迭代器的位置，而且還要返回錯誤的標(biāo)志。因此這里使用ParsingResult<double>，它能告訴你成功還是失敗，而且成功的話會帶有一個真正的double類型的返回值，并且修改迭代器的位置，讓它指向跳過一個factor后的位置以便繼續(xù)分析。

 

規(guī)則有許多種組合方法。假設(shè)有規(guī)則：

Rule<I, A> a, a2;

Rule<I, B> b;

那么可以組合出以下各種新的規(guī)則：

a+b：類型Rule<I, ParsingPair<A, B>>，代表a和b應(yīng)該按順序出現(xiàn)。

*a：類型Rule<I, ParsingList<A>>，代表a應(yīng)該連續(xù)出現(xiàn)0或多次。

+a：類型Rule<I, ParsingList<A>>，代表a應(yīng)該連續(xù)出現(xiàn)1或多次。

a|a2：類型Rule<I, A>，代表要么是a，要么是a2。這里a和a2類型應(yīng)該一致。

a>>b：類型Rule<I, B>，代表a和b應(yīng)該按順序出現(xiàn)，并且拋棄a只保留b的結(jié)果。

a<<b：類型Rule<I, A>，代表a和b應(yīng)該按順序出現(xiàn)，并且拋棄b只保留a的結(jié)果。

opt(a)：類型Rule<I, A>，代表a應(yīng)該出現(xiàn)0或1次。

 

還有另外兩種組合方法，分別用于轉(zhuǎn)換分析結(jié)果和進(jìn)行錯誤恢復(fù)。在這里先介紹轉(zhuǎn)換分析結(jié)果的組合方法。下面舉EXP的例子：

EXP = TERM (ADD TERM)*

寫成C++應(yīng)該是：

EXP = TERM + *(tk(ADD) + TERM);

這里ADD的類型是const int，因此我們需要一個函數(shù)把它轉(zhuǎn)換成一個規(guī)則。這里使用tk函數(shù)。tk函數(shù)將一個int轉(zhuǎn)換成Rule<TokenInput<RegexToken>, RegexToken>，用于匹配一個輸入是ADD類型的記號。于是我們可以慢慢解開這個規(guī)則的最終類型。這里我們不關(guān)心輸入類型，只關(guān)心輸出類型，因?yàn)樗械囊?guī)則的類型都是Rule<TokenInput<RegexToken>, T>。根據(jù)上文，我們知道TERM與EXP的類型一樣，都是返回double。

tk(ADD)                                                            ：T == RegexToken

tk(ADD) + TERM                                            ：T == ParsingPair<RegexToken, double>

*(tk(ADD) + TERM)                                       ：T == ParsingList<ParsingPair<RegexToken, double>>

TERM + *(tk(ADD) + TERM)                       ：T == ParsingPair<double, ParsingList<ParsingPair<RegexToken, double>>>

 

這里問題就來了，EXP的類型跟TERM + *(tk(ADD) + TERM)類型不一樣，那必然需要一個函數(shù)來幫我們做轉(zhuǎn)換。假如我們已經(jīng)有了一個函數(shù)：

double Operator(const ParsingPair<double, ParsingList<ParsingPair<RegexToken, double>>>& input)

這個函數(shù)勇于將輸入的那一大串東西，經(jīng)過計算最終轉(zhuǎn)換成一個double類型的結(jié)果，那么我們就可以使用這個Operator函數(shù)最終將EXP和TERM + *(tk(ADD) + TERM)連起來：

EXP = (TERM + *(tk(ADD) + TERM))[Operator];

 

ParsingPair<double, ParsingList<ParsingPair<RegexToken, double>>>的內(nèi)容實(shí)際上是一個操作數(shù)，加上一個操作符連著操作數(shù)的列表。于是當(dāng)我們真的需要把它轉(zhuǎn)成一個double的時候，就要去遍歷所有“操作符連著操作數(shù)”的列表，最后將計算結(jié)果全部累加到第一個操作數(shù)身上。記得我們之前表達(dá)EXP的方法跟現(xiàn)在不一樣嗎？以前是

EXP = TERM | EXP ADD TERM

因?yàn)?/span>Vczh Library++無法處理左遞歸，才需要我們手動拆解成

EXP = TERM (ADD TERM)*

于是為了讓我們處理起來更簡單，Vczh Library++提供了一個lrec函數(shù)，讓我們可以享受左遞歸帶來的方便。

 

lrec把類型ParsingPair<T, ParsingList<U>>通過一個函數(shù)T(const T&, const U&)轉(zhuǎn)換成T。這就意味著一個輸入T U U U … ，加上一個把一個T跟U加起來變成T的函數(shù)，最終把整個序列處理成T：

T U U U

=> T U U

=> T U

=> T

如果把他們套到我們的EXP上面，就可以做下面的計算

TERM (ADD TERM) (ADD TERM) (ADD TERM)        1+2+3+4

=> TERM (ADD TERM) (ADD TERM)                           3+3+4

=> TERM (ADD TERM)                                                    6+4

=> TERM                                                                            10

這個轉(zhuǎn)換函數(shù)跟處理EXP ADD TERM是一樣的！

 

因此，只要有了lrec函數(shù)，我們可以把

EXP = TERM | (EXP + tk(ADD) + TERM) [F1]

這種Vczh Library++不支持的左遞歸語法表示處理成

EXP = lrec(TERM + *(tk(ADD) + TERM), F2)

其中F1的類型是double (const ParsingPair<ParsingPair<double, RegexToken>, double>&)

而F2的類型是double (const double&, const ParsingPair<RegexToken, double>&)

我們不會因?yàn)樾枰鸾庾筮f歸而帶來任何不便！

實(shí)現(xiàn)

現(xiàn)在開始進(jìn)入激動人心的時刻了，我們可以借助Vczh Library++來實(shí)現(xiàn)一個帶函數(shù)四則運(yùn)算式子的計算器了。現(xiàn)在回顧一下我們的語法：

FACTOR = NUMBER

FACTOR = ‘-‘ FACTOR

FACTOR = ‘(‘ EXP ‘)’

FACTOR = ID ‘(‘ EXP ‘)’

TERM = FACTOR (MUL FACTOR)*

EXP = TERM (ADD TERM)*

把它轉(zhuǎn)換成C++就應(yīng)該是：

Rule<TokenInput<RegexToken>, double> factor, term, exp;

factor   = tk(NUMBER) [Convert]

              | (tk(L"-") >> factor)[Negative]

              | (tk(L"(") >> exp << tk(L")"))

              | (tk(ID) + (tk(L"(") >> exp << tk(L")")))[Call]

              ;

     term      = lrec(factor + *(tk(MUL) + factor), Operator);

exp      = lrec(term + *(tk(ADD) + term), Operator);

 

讓我們來逐個閱讀規(guī)則，并分析出結(jié)果轉(zhuǎn)換函數(shù)Convert、Negative、Call和Operator的類型。

 

第一個是tk(NUMBER)[Convert]。這個規(guī)則將一個數(shù)字記號轉(zhuǎn)換為一個真正的數(shù)字。因?yàn)?/span>tk(NUMBER)的類型是RegexToken，因此Convert的類型是double (const RegexToken&)。

 

第二個是(tk(L”-“) >> factor)[Negative]。tk(L”-“)的類型是RegexToken，factor的類型是double，所以RegexToken>>double其實(shí)就是double。因此Negative的類型是double (const double&)。

 

第三個是tk(L”(“) >> exp << tk(L”)”)。實(shí)際上分析了兩個括號和exp之后，括號被丟掉了，剩下exp的類型是double。因此這一行規(guī)則不需要任何轉(zhuǎn)換函數(shù)。

 

第四個是(tk(ID) + (tk(L”(“) >> exp << tk(L”)”)))[Call]，我們很容易知道Call的類型是double(const ParsingPair<RegexToken, double>&)。

 

最后一個是Operator，這個之前已經(jīng)討論過了，類型是double (const double&, const ParsingPair<RegexToken, double>&)。

 

知道了這個之后，我們就可以實(shí)現(xiàn)這些函數(shù)了：

double Convert(const RegexToken& input)

{

          return wtof(WString(input.reading, input.length));

}

 

double Negative(const double& input)

{

          return -input;

}

 

double Operator(const double& left, const ParsingPair<RegexToken, double>& right)

{

          switch(*right.First().reading)

          {

          case L'+':

              return left+right.Second();

          case L'-':

              return left-right.Second();

          case L'*':

              return left*right.Second();

          case L'/':

              return left/right.Second();

          default:

              return 0;

          }

}

 

double Call(const ParsingPair<RegexToken, double>& input)

{

          WString name(input.First().reading, input.First().length);

          double parameter=input.Second();

    

          if(name==L"sin")

          {

              return sin(parameter);

          }

          else if(name==L"cos")

          {

              return cos(parameter);

          }

          else if(name==L"tan")

          {

              return tan(parameter);

          }

          else if(name==L"cot")

          {

              return 1/tan(parameter);

          }

          else if(name==L"sec")

          {

              return 1/cos(parameter);

          }

          else if(name==L"csc")

          {

              return 1/sin(parameter);

          }

          else if(name==L"exp")

          {

              return exp(parameter);

          }

          else if(name==L"ln")

          {

              return log(parameter);

          }

          else if(name==L"abs")

          {

              return abs(parameter);

          }

          else if(name==L"sqrt")

          {

              return sqrt(parameter);

          }

          else if(name==L"sqr")

          {

              return parameter*parameter;

          }

          else

          {

              throw Exception(L"Function "+name+L" not exists.");

          }

}

 

然后我們就可以用這些函數(shù)來構(gòu)造一個語法分析器了：

     List<WString> patterns;

     const int BLANK        = patterns.Add(L"/s+");

     const int ADD           = patterns.Add(L"/+|-");

     const int MUL           = patterns.Add(L"/*|//");

     const int NUMBER        = patterns.Add(L"/d+(./d+)?");

     const int ID            = patterns.Add(L"[a-zA-Z_]/w*");

     const int OPEN         = patterns.Add(L"/(");

     const int CLOSE        = patterns.Add(L"/)");

     RegexLexer lexer(patterns.Wrap());

 

     Rule<TokenInput<RegexToken>, double> factor, term, exp;

 

     factor   = tk(NUMBER)[Convert]

              | (tk(L"-") >> factor)[Negative]

              | (tk(L"(") >> exp << tk(L")"))

              | (tk(ID) + (tk(L"(") >> exp << tk(L")")))[Call]

              ;

     term      = lrec(factor + *(tk(MUL) + factor), Operator);

exp      = lrec(term + *(tk(ADD) + term), Operator);

 

WString line=Console::Read();

List<RegexToken> tokens;

CopyFrom(tokens.Wrap(), lexer.Parse(line)>>Where(IsNotBlank));

     TokenInput<RegexToken> input(&tokens[0], tokens.Count());

     double result=exp.ParseFull(input, false);

Console::WriteLine(L"Result is "+ftow(result));

 

是不是很容易寫出來呢？不僅exp可以用來做分析，其實(shí)任何的Rule<I, T>都有一個ParseFull函數(shù)用來分析輸入的記號列表。

錯誤恢復(fù)和定制錯誤信息

Vczh Library++對語法分析提供了強(qiáng)大的錯誤處理的支持。我們可以自由定制在語法規(guī)則的任意一點(diǎn)發(fā)生錯誤的時候應(yīng)該采取的處理方法。我們可以

l  記錄一個錯誤并控制錯誤信息的文字內(nèi)容

l  決定恢復(fù)或者不恢復(fù)（構(gòu)造一個假的分析結(jié)果）

l  為了恢復(fù)錯誤，決定當(dāng)前的迭代器應(yīng)該跳過多少個記號

 

還是以那個例子為基礎(chǔ)，對于tk(NUMBER)[Convert]，如果我們想在輸入的迭代器所指向的位置不是一個數(shù)字的時候，想讓分析立刻失敗（分析器會自動嘗試接下來的三個同一等級的規(guī)則，如果都失敗，那么會采用這里的分析結(jié)果），那么可以將系統(tǒng)為這個錯誤自動生成的錯誤信息清除并使用我們自己的信息，然后返回一個值告訴系統(tǒng)說我不僅要自己定制錯誤信息，而且還不準(zhǔn)備恢復(fù)：

ParsingResult<RegexToken> NeedExpression(TokenInput<RegexToken>& input, Types<TokenInput<RegexToken>>::GlobalInfo& globalInfo)

{

          globalInfo.errors.Clear();

          globalInfo.errors.Add(new CombinatorError<TokenInput<RegexToken>>(L"Here needs an expression.", input));

          return ParsingResult<RegexToken>();

}

于是我們可以在這個地方使用這個錯誤處理函數(shù)：

tk(NUMBER)(NeedExpression)[Convert]

Vczh Library++使用中括號插入結(jié)果轉(zhuǎn)換函數(shù)，用小括號插入錯誤處理函數(shù)。因此我們可以挑選所有需要定制錯誤的地方，寫出這些函數(shù)然后應(yīng)用在規(guī)則上：

ParsingResult<RegexToken> NeedOpenBrace(TokenInput<RegexToken>& input, Types<TokenInput<RegexToken>>::GlobalInfo& globalInfo)

{

          globalInfo.errors.Clear();

          globalInfo.errors.Add(new CombinatorError<TokenInput<RegexToken>>(L"Here needs a \"(\".", input));

          return ParsingResult<RegexToken>();

}

 

ParsingResult<RegexToken> NeedCloseBrace(TokenInput<RegexToken>& input, Types<TokenInput<RegexToken>>::GlobalInfo& globalInfo)

{

          globalInfo.errors.Clear();

          globalInfo.errors.Add(new CombinatorError<TokenInput<RegexToken>>(L"Here needs an \")\".", input));

          return ParsingResult<RegexToken>();

}

 

ParsingResult<RegexToken> NeedOperator(TokenInput<RegexToken>& input, Types<TokenInput<RegexToken>>::GlobalInfo& globalInfo)

{

          globalInfo.errors.Clear();

          globalInfo.errors.Add(new CombinatorError<TokenInput<RegexToken>>(L"Here needs an operator.", input));

          return ParsingResult<RegexToken>();

}

 

     factor   = tk(NUMBER)(NeedExpression)[Convert]

              | (tk(L"-") >> factor)[Negative]

              | (tk(L"(") >> exp << tk(L")")(NeedCloseBrace))

              | (tk(ID) + (tk(L"(")(NeedOpenBrace) >> exp << tk(L")")(NeedCloseBrace)))[Call]

              ;

     term      = lrec(factor + *(tk(MUL)(NeedOperator) + factor), Operator);

exp      = lrec(term + *(tk(ADD)(NeedOperator) + term), Operator);

 

并不是所有的地方都需要我們親自處理錯誤，我們只需要在需要自己定制錯誤消息的地方寫上錯誤處理函數(shù)就好了。我們有一些簡單的原則來尋找需要處理錯誤的地方。

 

首先，一個規(guī)則的非第一分支的第一個記號不需要處理錯誤。這個很好處理，我們看factor，一共有四個分支。首先tk(NUMBER)是第一分支的第一個記號，而tk(L”-“)、tk(L”(“)和tk(ID)是非第一分支的的第一個記號。因?yàn)橹灰谝粋€分支處理了錯誤，那么非第一分支全部在第一個記號就失敗的話，那么結(jié)果顯然是采取第一個分支的錯誤結(jié)果。

 

第二，大部分錯誤都集中在記號規(guī)則上。記號規(guī)則說的是tk函數(shù)產(chǎn)生的規(guī)則。因?yàn)榻^大多數(shù)錯誤信息都是在描述“這里需要XXX但是卻沒出現(xiàn)”，因此只需要在第一個原則所說的不需要錯誤信息的地方以外的所有記號規(guī)則出現(xiàn)的地方都寫上自己的錯誤處理就可以了。

 

第三，因?yàn)榈谝缓偷诙€原則，因此所有非記號規(guī)則能產(chǎn)生的所有錯誤都被我們定制過了，因此非記號規(guī)則不需要任何錯誤處理，除非我們想定制能提供更多有用信息的錯誤信息，或者執(zhí)行我們自己的錯誤恢復(fù)以便盡可能在錯誤產(chǎn)生的時候繼續(xù)分析并產(chǎn)生多條有用的錯誤信息。

 

因此根據(jù)這三條原則，再加上我們這個例子只需要第一個錯誤信息，因此選中了那6個標(biāo)記了紅色的地方進(jìn)行錯誤處理并輸出我們自己的錯誤信息。

捕捉錯誤

最后的問題就是如何捕捉錯誤了。每一個Rule<I, T>都提供了一個Parse函數(shù)和ParseFull函數(shù)。Parse函數(shù)用于在輸入的迭代器中尋找一個滿足語法要求的最長前綴或者在遇到錯誤的時候給出有意義的錯誤列表。ParseFull則假定迭代器中的完整內(nèi)容滿足語法要求，然后進(jìn)行分析或者在遇到錯誤的時候給出有意義的錯誤列表。

 

Vczh Library++內(nèi)部有一套用于將所有用戶自定義的錯誤恢復(fù)機(jī)制所產(chǎn)生的錯有可恢復(fù)錯誤挑選并組合起來的算法。因此在捕捉到錯誤的時候，第一個錯誤總是處于一個盡可能元的位置，而且基本上都是有意義的。Parse和ParseFull函數(shù)都直接返回我們需要的分析結(jié)果，或者在遇到錯誤的時候拋出一個CombinatorException<I>類型的異常。

 

Parse和ParseFull的參數(shù)和結(jié)果如下：

     template<typename I, typename O>

     class Rule

     {

         O Parse(const I& input, bool allowError, I* remain=0)const;

         O ParseFull(const I& input, bool allowError)const;

};

input參數(shù)是輸入的迭代器。一般來說輸入的迭代器的當(dāng)前位置是第一個記號的位置，當(dāng)然你也可以自己讀了幾個記號之后再傳給Parse。 allowError為true的時候，如果分析出了錯誤但是所有錯誤都被用戶自定義的錯誤恢復(fù)函數(shù)恢復(fù)了，也會返回分析結(jié)果而不會拋出異常。allowError為false的時候，只要有錯誤出現(xiàn)就會拋出異常。remain參數(shù)僅在Parse函數(shù)中有用，在分析結(jié)束之后，如果傳入的指針不是空，那么對象會被修改為分析結(jié)束后迭代器的狀態(tài)。

 

如果分析出現(xiàn)錯誤并且需要被處理的話，那么Parse和ParseFUll都會拋出一個CombinatorException<I>的異常。CombinatorException<I>的定義如下：

     template<typename I>

     class CombinatorException : public Exception

     {

         const I& GetInput()const;

         const typename Types<I>::GlobalInfo& GetGlobalInfo()const;

};

GetInput返回迭代器的當(dāng)前狀態(tài)。在所有錯誤都被恢復(fù)的時候，迭代器的當(dāng)前狀態(tài)是分析結(jié)束的時候迭代器的位置。一旦出現(xiàn)了沒有被恢復(fù)的錯誤，那么迭代器的當(dāng)前狀態(tài)是Parse或者ParseFull輸入的迭代器狀態(tài)。GetGlobalInfo返回的對象有errorList與candidateErrorList兩個列表，分別是錯誤和備選錯誤。他們的元素類型都是Ptr<CombinatorError<I>>。

 

CombinatorError<I>的定義如下：

     template<typename I>

     class CombinatorError : public Exception

     {

     public:

         typedef typename Types<I>::Input          InputType;

 

         const InputType& GetPosition();

};

而Exception的定義如下：

     class Exception : public Object

     {

     public:

         const WString& Message()const;

};

我們可以通過Message()函數(shù)獲得錯誤信息的文字內(nèi)容，然后通過GetPosition()函數(shù)獲得錯誤發(fā)生的時候迭代器的狀態(tài)。于是我們不僅可以知道出現(xiàn)了多少錯誤，還能知道這些錯誤時分別在什么地方出現(xiàn)的。

 

于是讓我們來看一看帶函數(shù)的四則運(yùn)算計算器應(yīng)該如何處理用戶輸入的表達(dá)式在分析過程中產(chǎn)生的錯誤：

     Console::Write(L"\r\nexpression>");

     WString line=Console::Read();

     if(line==L"")

     {

         break;

     }

 

     try

     {

         List<RegexToken> tokens;

         CopyFrom(tokens.Wrap(), lexer.Parse(line)>>Where(IsNotBlank));

         for(int i=0;i<tokens.Count();i++)

         {

              if(tokens[i].token==-1)

              {

                   throw Exception(L"Syntax error. Unknown token: \""+WString(tokens[i].reading, tokens[i].length)+L"\".");

              }

         }

         if(tokens.Count()==0)

         {

              throw Exception(L"Syntax error. Expression cannot be empty.");

         }

         try

         {

              TokenInput<RegexToken> input(&tokens[0], tokens.Count());

              double result=exp.ParseFull(input, false);

              Console::WriteLine(L"Result is "+ftow(result));

         }

         catch(const CombinatorException<TokenInput<RegexToken>>& e)

         {

              Ptr<CombinatorError<TokenInput<RegexToken>>> error=e.GetGlobalInfo().errors.Get(0);

              const TokenInput<RegexToken>& position=error->GetPosition();

              if(position.Available())

              {

                   throw Exception(L"Syntax error. "+error->Message()+L" First occurs at \""+WString(position.Current().reading)+L"\".");

              }

              else

              {

                   throw Exception(L"Syntax error. Expression is not complete.");

              }

         }

     }

     catch(const Exception& e)

     {

         Console::SetColor(true, false, false, true);

         Console::WriteLine(e.Message());

         Console::SetColor(true, true, true, false);

}

結(jié)束

使用Vczh Library++開發(fā)語法分析器的指南就到此結(jié)束了。如果在閱讀過程中有什么疑問的話可以使用如下方法來找到我：

電子郵件：vczh@163.com

博客：http://www.shnenglu.com/vczh

Vczh Library++項目主頁：http://vlpp.codeplex.com