Vczh Library++ 語法分析器開發指南

陳梓瀚

 

前言

在日常的開發工作中我們總是時不時需要寫一些語法分析器。語法分析器不一定指的是一門語言的編譯器前端，也有可能僅僅是一個自己設計格式的配置文件的讀寫程序，或者是一門用來簡化我們開發的DSL（領域專用語言）。我們可以選擇使用XML，不過因為XML的噪音實在是太多，所以自己寫語法分析器在有些情況下是必要的，特別是那種經常需要修改的文件，使用XML有時候會增加我們的負擔，除非我們專門為此開發一個編輯器程序。

 

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

 

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

制定語法

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

 

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

 

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

 

RULE = EXPRESSION

 

RULE是這個規則的名字，而EXPRESSION是這個規則的定義。語法可以由一條規則組成，也可以由很多條規則組成。當所有的規則都列出來之后，那么每一個規則的名字都是一個字符串的集合。大部分情況下你需要指定一個“總入口”來代表整個語法。

 

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

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

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

INTEGER = DIGIT | INTEGER DIGIT

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

 

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

INTEGER

= DIGIT                                          (INTEGER = DIGIT)

= ‘1’                                                (DIGIT = ‘1’)

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

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這兩條規則來將一個INTEGER替換成恰好三個DIGIT，然后再將DIGIT替換成’1’、’2’和’3’三個字符，從而確信“123”滿足INTEGER的定義，因此“123”是一個無符號整數。

 

替換的過程并不是唯一的，我們完全可以使用另一種順序來將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’)

這正是語法的一個特點：替換順序與結果無關。

 

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

LIST = INTEGER | LIST ‘,’ INTEGER

用LIST來分析一個數字列表的過程與用INTEGER分析一個無符號整數是相似的。因為篇幅問題，這里只展示使用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’)

 

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

 

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

SPACES = <EMPTY> | SPACES ‘ ’

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

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

詞法分析

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

 

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

 

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

 

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

 

加號與減號的優先級一樣，對于語法分析來說他們其實沒有區別。乘號與除號也類似。當語法分析結束，語義分析開始的時候，加號與減號的區別才會出現。因此在詞法分析里面我們可以把他們當成同樣的東西來對待，因此有：

BLANK = \s+                                 ：空格

ADD = \+|-                                    ：加減號

MUL = \*|/                                   ：乘除號

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

ID = [a-zA-Z_]\w*                       ：函數名

OPEN = \(                                      ：開括號

CLOSE = \)                                     ：閉括號

 

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

 

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

 

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

 

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

 

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

 

我們可以用一種簡單的方法來使用這個詞法分析器。RegexLexer輸出的記號存放在RegexToken類型里面，我們可以使用任何容器來存放記號，在這里我們仍然使用RegexToken。

 

RegexToken的定義如下：

     class RegexToken

     {

     public:

         int                start;

         int                length;

         int                token;

         const wchar_t*     reading;

         int                lineIndex;

         int                lineStart;

         int                codeIndex;

};

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

 

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

bool IsNotBlank(RegexToken token)

{

          return token.token!=0;

}

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

List<RegexToken> tokens;

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

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

 

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

 

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

帶函數四則運算式子的語法

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

FACTOR = NUMBER

FACTOR = ‘-‘ FACTOR

FACTOR = ‘(‘ EXP ‘)’

FACTOR = ID ‘(‘ EXP ‘)’

TERM = FACTOR | TERM MUL FACTOR

EXP = TERM | EXP ADD TERM

 

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

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

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

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

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

 

但是這里還有一個問題，我們觀察一下EXP = TERM | EXP ADD TERM這條規則。我們不難發現他們其實是獨立的兩條規則的組合：

EXP = TERM

EXP = EXP ADD TERM

第二條EXP的規則仍然從EXP開始，這種遞歸稱為左遞歸。左遞歸直接處理起來比較困難，因為你分析到EXP的時候很容易陷入一個死循環，因此我們需要拆開它們。

 

我們引入擴展規則的機制來解決這個問題。如果我們想表達一個循環的話，我們不得不專門為它建立一條規則并命名：

LIST = ITEM | LIST ITEM

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

FACTOR = NUMBER

FACTOR = ‘-‘ FACTOR

FACTOR = ‘(‘ EXP ‘)’

FACTOR = ID ‘(‘ EXP ‘)’

TERM = FACTOR (MUL FACTOR)*

EXP = TERM (ADD TERM)*

語法類型與C++表達

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

 

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

 

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

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

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

 

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

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

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

 

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

 

規則有許多種組合方法。假設有規則：

Rule<I, A> a, a2;

Rule<I, B> b;

那么可以組合出以下各種新的規則：

a+b：類型Rule<I, ParsingPair<A, B>>，代表a和b應該按順序出現。

*a：類型Rule<I, ParsingList<A>>，代表a應該連續出現0或多次。

+a：類型Rule<I, ParsingList<A>>，代表a應該連續出現1或多次。

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

a>>b：類型Rule<I, B>，代表a和b應該按順序出現，并且拋棄a只保留b的結果。

a<<b：類型Rule<I, A>，代表a和b應該按順序出現，并且拋棄b只保留a的結果。

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

 

還有另外兩種組合方法，分別用于轉換分析結果和進行錯誤恢復。在這里先介紹轉換分析結果的組合方法。下面舉EXP的例子：

EXP = TERM (ADD TERM)*

寫成C++應該是：

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

這里ADD的類型是const int，因此我們需要一個函數把它轉換成一個規則。這里使用tk函數。tk函數將一個int轉換成Rule<TokenInput<RegexToken>, RegexToken>，用于匹配一個輸入是ADD類型的記號。于是我們可以慢慢解開這個規則的最終類型。這里我們不關心輸入類型，只關心輸出類型，因為所有的規則的類型都是Rule<TokenInput<RegexToken>, T>。根據上文，我們知道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)類型不一樣，那必然需要一個函數來幫我們做轉換。假如我們已經有了一個函數：

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

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

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

 

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

EXP = TERM | EXP ADD TERM

因為Vczh Library++無法處理左遞歸，才需要我們手動拆解成

EXP = TERM (ADD TERM)*

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

 

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

這個轉換函數跟處理EXP ADD TERM是一樣的！

 

因此，只要有了lrec函數，我們可以把

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

我們不會因為需要拆解左遞歸而帶來任何不便！

實現

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

FACTOR = NUMBER

FACTOR = ‘-‘ FACTOR

FACTOR = ‘(‘ EXP ‘)’

FACTOR = ID ‘(‘ EXP ‘)’

TERM = FACTOR (MUL FACTOR)*

EXP = TERM (ADD TERM)*

把它轉換成C++就應該是：

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

 

讓我們來逐個閱讀規則，并分析出結果轉換函數Convert、Negative、Call和Operator的類型。

 

第一個是tk(NUMBER)[Convert]。這個規則將一個數字記號轉換為一個真正的數字。因為tk(NUMBER)的類型是RegexToken，因此Convert的類型是double (const RegexToken&)。

 

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

 

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

 

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

 

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

 

知道了這個之后，我們就可以實現這些函數了：

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

          }

}

 

然后我們就可以用這些函數來構造一個語法分析器了：

     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可以用來做分析，其實任何的Rule<I, T>都有一個ParseFull函數用來分析輸入的記號列表。

錯誤恢復和定制錯誤信息

Vczh Library++對語法分析提供了強大的錯誤處理的支持。我們可以自由定制在語法規則的任意一點發生錯誤的時候應該采取的處理方法。我們可以

l  記錄一個錯誤并控制錯誤信息的文字內容

l  決定恢復或者不恢復（構造一個假的分析結果）

l  為了恢復錯誤，決定當前的迭代器應該跳過多少個記號

 

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

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

}

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

tk(NUMBER)(NeedExpression)[Convert]

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

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

 

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

 

首先，一個規則的非第一分支的第一個記號不需要處理錯誤。這個很好處理，我們看factor，一共有四個分支。首先tk(NUMBER)是第一分支的第一個記號，而tk(L”-“)、tk(L”(“)和tk(ID)是非第一分支的的第一個記號。因為只要第一個分支處理了錯誤，那么非第一分支全部在第一個記號就失敗的話，那么結果顯然是采取第一個分支的錯誤結果。

 

第二，大部分錯誤都集中在記號規則上。記號規則說的是tk函數產生的規則。因為絕大多數錯誤信息都是在描述“這里需要XXX但是卻沒出現”，因此只需要在第一個原則所說的不需要錯誤信息的地方以外的所有記號規則出現的地方都寫上自己的錯誤處理就可以了。

 

第三，因為第一和第二個原則，因此所有非記號規則能產生的所有錯誤都被我們定制過了，因此非記號規則不需要任何錯誤處理，除非我們想定制能提供更多有用信息的錯誤信息，或者執行我們自己的錯誤恢復以便盡可能在錯誤產生的時候繼續分析并產生多條有用的錯誤信息。

 

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

捕捉錯誤

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

 

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

 

Parse和ParseFull的參數和結果如下：

     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參數是輸入的迭代器。一般來說輸入的迭代器的當前位置是第一個記號的位置，當然你也可以自己讀了幾個記號之后再傳給Parse。 allowError為true的時候，如果分析出了錯誤但是所有錯誤都被用戶自定義的錯誤恢復函數恢復了，也會返回分析結果而不會拋出異常。allowError為false的時候，只要有錯誤出現就會拋出異常。remain參數僅在Parse函數中有用，在分析結束之后，如果傳入的指針不是空，那么對象會被修改為分析結束后迭代器的狀態。

 

如果分析出現錯誤并且需要被處理的話，那么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返回迭代器的當前狀態。在所有錯誤都被恢復的時候，迭代器的當前狀態是分析結束的時候迭代器的位置。一旦出現了沒有被恢復的錯誤，那么迭代器的當前狀態是Parse或者ParseFull輸入的迭代器狀態。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()函數獲得錯誤信息的文字內容，然后通過GetPosition()函數獲得錯誤發生的時候迭代器的狀態。于是我們不僅可以知道出現了多少錯誤，還能知道這些錯誤時分別在什么地方出現的。

 

于是讓我們來看一看帶函數的四則運算計算器應該如何處理用戶輸入的表達式在分析過程中產生的錯誤：

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

}

結束

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

電子郵件：vczh@163.com

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

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