第?12?章?詞法分析器 · Boost C++ 庫

# 第?12?章?詞法分析器 ### 目錄 * [12.1 概述](parser.html#parser_general) * [12.2 擴展BNF范式](parser.html#parser_ebnf) * [12.3 語法](parser.html#parser_grammar) * [12.4 動作](parser.html#parser_actions) * [12.5 練習](parser.html#parser_exercises) [![](https://box.kancloud.cn/2016-02-29_56d41c2d6e214.gif)](http://creativecommons.org/licenses/by-nc-nd/3.0/de/deed.zh) 該書采用 [Creative Commons License](http://creativecommons.org/licenses/by-nc-nd/3.0/de/deed.zh) 授權 ## 12.1.?概述詞法分析器用于讀取各種格式的數據，這些數據可以具有靈活但可能非常復雜的結構。關于"格式"的一個最好的例子就是 C++ 代碼。編譯器的詞法分析器必須理解 C++ 的各種可能的語言結構組合，以將它們翻譯為某種二進制形式。開發詞法分析器的主要問題是所分析的數據的組成結構具有大量的規則。例如，C++ 支持很多的語言結構，開發一個相應的詞法分析器可能需要無數個 `if` 表達式來識別任意所能想象到的 C++ 代碼是否有效。本章所介紹的 [Boost.Spirit](http://www.boost.org/libs/spirit/) 庫將詞法分析器的開發放到了桌面上來。無需將明確的規則轉換為代碼并使用無數的 `if` 表達式來驗證代碼，Boost.Spirit 可以使用一種被稱為擴展BNF范式的東西來表示規則。通過使用這些規則，Boost.Spirit 就可以對一個 C++ 源代碼進行分析。 Boost.Spirit 的基本思想類似于正則表達式。即不用 `if` 表達式來查找指定模式的文本，而是將模式以正則表達式的方式指定出來。然后就可以使用象 Boost.Regex 這樣的庫來執行相應的查找國，因此開發者無需關心其中的細節。本章將示范如何用 Boost.Spirit 來讀入正則表達式不再適用的復雜格式。由于 Boost.Spirit 是一個功能非常全的庫，引入了多個不同的概念，所以在本章我們將開發一個 [JSON 格式](http://www.json.org/) 的簡單的詞法分析器。 JSON 是被如 Ajax 一類的應用程序用于在程序之間交換數據的格式，類似于 XML，可以在不同平臺上運行。雖然 Boost.Spirit 簡化了詞法分析器的開發，但是還沒有人能夠成功地基于這個庫寫出一個 C++ 詞法分析器。這類詞法分析器的開發仍然是 Boost.Spirit 的一個長期目標，不過，由于 C++ 語言的復雜性，目前還未能實現。 Boost.Spirit 目前還不能很好地適用于這種復雜性或二進制格式。 ## 12.2.?擴展BNF范式 Backus-Naur 范式，簡稱 BNF，是一種精確描述規則的語言，被應用于多種技術規范。例如，眾多互聯網協議的許多技術規范，稱為 RFC，除了文字說明以外，都包含了以 BNF 編寫的規則。 Boost.Spirit 支持擴展BNF范式(EBNF)，可以用比 BNF 更簡短的方式來指定規則。 EBNF 的主要優點就是簡短，從而寫法更簡單。請注意，EBNF 有幾種不同的變體，它們的語法可能有些差異。本章以及 Boost.Spirit 所使用的 EBNF 語法類似于正則表達式。要使用 Boost.Spirit，你必須懂得 EBNF。多數情況下，開發者已經知道 EBNF，因此才會選擇 Boost.Spirit 來重用以前用 EBNF 表示的規則。以下是對 EBNF 的一個簡短介紹；如果需要對本章當中以及 Boost.Spirit 所使用的語法有一個快速的參考，請查看 W3C XML 規范，其中包含了一個 [短摘要](http://www.w3.org/TR/2004/REC-xml-20040204/#sec-notation)。 | `digit` | = | "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" | 嚴格地講，EBNF 以生成規則來表示規則。可以將任意數量的生成規則組合起來，描述一個特定的格式。以上格式只包含一個生成規則。它定義了一個 `digit` 是由0至9之間的任一數字組成。象 `digit` 這樣的定義被稱為非終結符號。以上定義中的數字 0 到 9 則被稱為終結符號。這些符號不具有任意特定意義，而且很容易識別出來，因為它們是用雙引號引起來的。所有數字值是用豎直符相連的，其意義與 C++ 中的 `||` 操作符一樣：多選一。一句話，這個生成規則指明了0至9之間的任一數字都是一個 `digit`。 | `integer` | = | ("+" | "-")? `digit`+ | 這個新的非終結符 `integer` 包含至少一個 `digit`，而且可選地以一個加號或減號開頭。 `integer` 的定義用到了多個新的操作符。圓括號用于創建一個子表達式，就象它在數學中的作用。其它操作符可應用于這些子表達式。問號表示這個子表達式只能出現一次或不出現。 `digit` 之后的加號表示相應的表達式必須出現至少一次。這個新的生成規則定義了一個任意的正或負的整數。一個 `digit` 正好是一個數字，而一個 `integer` 則可以由多個數字組成，且可以被標記為無符號的或有符號的。因此 5 即是一個 `digit` 也是一個 `integer`，而 +5 則只是一個 `integer`。同樣地，169 或 -8 也只是 `integer`。通過定義和組合各種非終結符，可以創建越來越復雜的生成規則。 | `real` | = | `integer` "." `digit`* | `integer` 的定義表示的是整數，而 `real` 的定義則表示了浮點數。這個規則基于前面已定義的非終結符 `integer` 和 `digit`，以一個句點號分隔。 `digit` 之后的星類表示點號之后的數字是可選的：可以有任意多個數字或沒有數字。浮點數如 1.2, -16.99 甚至 3\. 都符合 `real` 的定義。但是，當前的定義不允許浮點數不帶前導的零，如 .9。正如本章開始的時候所提到的，接下來我們要用 Boost.Spirit 開發一個 JSON 格式的詞法分析器。為此，需要用 EBNF 來給出 JSON 格式的規則。 | `object` | = | "{" `member` ("," `member`)* "}" | | `member` | = | `string` ":" `value` | | `string` | = | '"' `character`* '"' | | `value` | = | `string` | `number` | `object` | `array` | "true" | "false" | "null" | | `number` | = | `integer` | `real` | | `array` | = | "[" `value` ("," `value`)* "]" | | `character` | = | "a" | "b" | "c" | "d" | "e" | "f" | "g" | "h" | "i" | "j" | "k" | "l" | "m" | "n" | "o" | "p" | "q" | "r" | "s" | "t" | "u" | "v" | "w" | "x" | "y" | "z" | JSON 格式基于一些包含了鍵值和值的成對的對象，它們被花括號括起來。其中鍵值是普通的字符串，而值可以是字符串、數字值、數組、其它對象或是字面值 `true`, `false` 或 `null`。字符串是由雙引號引起來的連續字符。數字值可以是整數或浮點數。數組包含以逗號分隔的值，并以方括號括起來。請注意，以上定義并不完整。一方面，`character` 的定義缺少了大寫字母以及其它字符；另一方面，JSON 還特別支持 Unicode 或控制字符。這些現在都可以先忽略掉，因為 Boost.Spirit 定義了常用的非終結符號，如字母數字字符，以減少你打字的次數。另外，稍后在代碼中，字符串被定義為除雙引號以外的任意字符的連續串。由于雙引號用于結束一個字符串，所以其它所有字符都在字符串中使用。上述 EBNF 并不如此表示，因為 EBNF 要求定義一個包含除單個字符外的所有字符的非終結符號，應該定義一個例外來排除。以下是使用了上述定義的 JSON 格式的一個例子。 ``` { "Boris Sch?ling" : { "Male": true, "Programming Languages": [ "C++", "Java", "C#" ], "Age": 31 } } ``` 整個對象由最外層的花括號給出，它包含了一個鍵-值對。鍵值是 "Boris Sch?ling"，值則是一個新的對象，包含多個鍵-值對。其中所有鍵值均為字符串，而值則分別為字面值 `true`，一個包含幾個字符串的數組，以及一個數字值。以上所定義的 EBNF 規則現在就可用于通過 Boost.Spirit 開發一個可以讀取以上 JSON 格式的詞法分析器。 ## 12.3.?語法繼上一節中以 EBNF 為 JSON 格式定義了相關規則后，現在要將這些規則與 Boost.Spirit 一起使用。 Boost.Spirit 實際上允許以 C++ 代碼來定義 EBNF 規則，方法是重載各個由 EBNF 使用的不同操作符。請注意，EBNF 規則需要稍作修改，才能創建出合法的 C++ 代碼。在 EBNF 中各個符號是以空格相連的，在 C++ 中需要用某個操作符來連接。此外，象星號、問號和加號這些操作符，在 EBNF 中是置于對應的符號后面的，在 C++ 中必須置于符號的前面，才能作為單參操作符來使用。以下是在 Boost.Spirit 中為表示 JSON 格式，用 C++ 代碼寫的 EBNF 規則。 ``` #include <boost/spirit.hpp> struct json_grammar : public boost::spirit::grammar<json_grammar> { template <typename Scanner> struct definition { boost::spirit::rule<Scanner> object, member, string, value, number, array; definition(const json_grammar &self) { using namespace boost::spirit; object = "{" >> member >> *("," >> member) >> "}"; member = string >> ":" >> value; string = "\"" >> *~ch_p("\"") >> "\""; value = string | number | object | array | "true" | "false" | "null"; number = real_p; array = "[" >> value >> *("," >> value) >> "]"; } const boost::spirit::rule<Scanner> &start() { return object; } }; }; int main() { } ``` * [下載源代碼](src/12.3.1/main.cpp) 為了使用 Boost.Spirit 中的各個類，需要包含頭文件 `boost/spirit.hpp`。所有類均位于名字空間 `boost::spirit` 內。為了用 Boost.Spirit 創建一個詞法分析器，除了那些定義了數據是如何構成的規則以外，還必須創建一個所謂的語法。在上例中，就創建一個 `json_grammar` 類，它派生自模板類 `boost::spirit::grammar`，并以該類的名字來實例化。 `json_grammar` 定義了理解 JSON 格式所需的完整語法。語法的一個最重要的組成部分就是正確讀入結構化數據的規則。這些規則在一個名為 `definition` 的內層類中定義 - 這個名字是強制性的。這個類是帶有一個模板參數的模板類，由 Boost.Spirit 以一個所謂的掃描器來進行實例化。掃描器是 Boost.Spirit 內部使用的一個概念。雖然強制要求 `definition` 必須是以一個掃描器類型作為其模板參數的模板類，但是對于 Boost.Spirit 的日常使用來說，這些掃描器是什么以及為什么要定義它們，并不重要。 `definition` 必須定義一個名為 `start()` 的方法，它會被 Boost.Spirit 調用，以獲得該語法的完整規則和標準。這個方法的返回值是 `boost::spirit::rule` 的一個常量引用，它也是一個以掃描器類型實例化的模板類。 `boost::spirit::rule` 類用于定義規則。非終結符號就以這個類來定義。前面所定義的非終結符號 `object`, `member`, `string`, `value`, `number` 和 `array` 的類型均為 `boost::spirit::rule`。所有這些對象都被定義為 `definition` 類的屬性，這并非強制性的，但簡化了定義，尤其是當各個規則之間有遞歸引用時。正如在上一節中所看到的 EBNF 例子那樣，遞歸引用并不是一個問題。乍一看，在 `definition` 的構造函數內的規則定義非常類似于在上一節中看到的 EBNF 生成規則。這并不奇怪，因為這正是 Boost.Spirit 的目標：重用在 EBNF 中定義的生成規則。由于是用 C++ 代碼來組成 EBNF 中建立的規則，為了寫出合法的 C++，其實是有一點點差異的。例如，所有符號間的連接是通過 `>>` 操作符完成的。 EBNF 中的一些操作符，如星號，被置于相應符號的前面而非后面。盡管有這樣一些語法上的修改，Boost.Spirit 還是盡量在將 EBNF 規則轉換至 C++ 代碼時不進行太多的修改。 `definition` 的構造函數使用了由 Boost.Spirit 提供的兩個類：`boost::spirit::ch_p` 和 `boost::spirit::real_p`。這些以分析器形式提供的常用規則可以很方便地重用。一個例子就是 `boost::spirit::real_p`，它可以用于保存正或負的整數或浮點數，無需定義象 `digit` 或 `real` 這樣的非終結符號。 `boost::spirit::ch_p` 可用于創建一個針對單個字符的分析器，相當于將字符置于雙引號中。在上例中，`boost::spirit::ch_p` 的使用是強制性的，因為波浪號和星號是要應用于雙引號之上的。沒有這個類，代碼將變為 `*~"\""`，這會被編譯器拒絕為非法代碼。波浪號實際上是實現了前一節中提到的一個技巧：在雙引號之前加上波浪號，可以接受除雙引號以外的所有其它字符。定義完了識別 JSON 格式的規則后，以下例子示范了如何使用這些規則。 ``` #include <boost/spirit.hpp> #include <fstream> #include <sstream> #include <iostream> struct json_grammar : public boost::spirit::grammar<json_grammar> { template <typename Scanner> struct definition { boost::spirit::rule<Scanner> object, member, string, value, number, array; definition(const json_grammar &self) { using namespace boost::spirit; object = "{" >> member >> *("," >> member) >> "}"; member = string >> ":" >> value; string = "\"" >> *~ch_p("\"") >> "\""; value = string | number | object | array | "true" | "false" | "null"; number = real_p; array = "[" >> value >> *("," >> value) >> "]"; } const boost::spirit::rule<Scanner> &start() { return object; } }; }; int main(int argc, char *argv[]) { std::ifstream fs(argv[1]); std::ostringstream ss; ss << fs.rdbuf(); std::string data = ss.str(); json_grammar g; boost::spirit::parse_info<> pi = boost::spirit::parse(data.c_str(), g, boost::spirit::space_p); if (pi.hit) { if (pi.full) std::cout << "parsing all data successfully" << std::endl; else std::cout << "parsing data partially" << std::endl; std::cout << pi.length << " characters parsed" << std::endl; } else std::cout << "parsing failed; stopped at '" << pi.stop << "'" << std::endl; } ``` * [下載源代碼](src/12.3.2/main.cpp) Boost.Spirit 提供了一個名為 `boost::spirit::parse()` 的自由函數。通過創建一個語法的實例，就會相應地創建一個詞法分析器，該分析器被作為第二個參數傳遞給 `boost::spirit::parse()`。第一個參數表示要進行分析的文本，而第三個參數則是一個表明在給定文本中哪些字符將被跳過的詞法分析器。為了跳過空格，要將一個類型為 `boost::spirit::space_p` 的對象作為第三個參數傳入。這只是表示在被捕獲的數據之間 - 換句話說，就是規則中使用了 `>>` 操作符的地方 - 可以有任意數量的空格。這其中包含了制表符和換行符，令數據的格式可以更為靈活。 `boost::spirit::parse()` 返回一個類型為 `boost::spirit::parse_info` 的對象，該對象提供了四個屬性來表示文本是否被成功分析。如果文本被成功分析，則屬性 `hit` 被設置為 `true`。如果文本中的所有字符都被分析完了，最后沒有剩余空格，則 `full` 也被設置為 `true`。僅當 `hit` 為 `true` 時，`length` 是有效的，其中保存了被成功分析的字符數量。如果文本未能分析成功，則屬性 `length` 不能被訪問。此時，可以訪問屬性 `stop` 來獲得停止分析的文本位置。如果文本被成功分析，`stop` 也是可訪問的，只不過沒什么意義，因為此時它肯定是指向被分析文本之后。 ## 12.4.?動作到目前為止，你已經知道了如何定義一個語法，以得到一個新的詞法分析器，用于識別一個給定的文本是否具有該語法的規則所規定的結構。但是此刻，數據的格式仍未被解釋，因為從結構化格式如 JSON 中所讀取的數據并沒有被進一步處理。要對由分析器識別出來的符合某個特定規則的數據進行處理，可以使用動作(action)。動作是一些與規則相關聯的函數。如果詞法分析器識別出某些數據符合某個特定的規則，則相關聯的動作會被執行，并把識別得到的數據傳入進行處理，如下例所示。 ``` #include <boost/spirit.hpp> #include <string> #include <fstream> #include <sstream> #include <iostream> struct json_grammar : public boost::spirit::grammar<json_grammar> { struct print { void operator()(const char *begin, const char *end) const { std::cout << std::string(begin, end) << std::endl; } }; template <typename Scanner> struct definition { boost::spirit::rule<Scanner> object, member, string, value, number, array; definition(const json_grammar &self) { using namespace boost::spirit; object = "{" >> member >> *("," >> member) >> "}"; member = string[print()] >> ":" >> value; string = "\"" >> *~ch_p("\"") >> "\""; value = string | number | object | array | "true" | "false" | "null"; number = real_p; array = "[" >> value >> *("," >> value) >> "]"; } const boost::spirit::rule<Scanner> &start() { return object; } }; }; int main(int argc, char *argv[]) { std::ifstream fs(argv[1]); std::ostringstream ss; ss << fs.rdbuf(); std::string data = ss.str(); json_grammar g; boost::spirit::parse_info<> pi = boost::spirit::parse(data.c_str(), g, boost::spirit::space_p); if (pi.hit) { if (pi.full) std::cout << "parsing all data successfully" << std::endl; else std::cout << "parsing data partially" << std::endl; std::cout << pi.length << " characters parsed" << std::endl; } else std::cout << "parsing failed; stopped at '" << pi.stop << "'" << std::endl; } ``` * [下載源代碼](src/12.4.1/main.cpp) 動作被實現為函數或函數對象。如果動作需要被初始化或是要在多次執行之間維護某些狀態信息，則后者更好一些。以上例子中將動作實現為函數對象。類 `print` 是一個函數對象，它將數據寫出至標準輸出流。當其被調用時，重載的 `operator()()` 操作符將接受一對指向數據起始點和結束點的指針，所指范圍即為被執行該動作的規則所識別出來的數據。這個例子將這個動作關聯至在 `member` 之后作為第一個符號出現的非終結符號 `string`。一個類型為 `print` 的實例被放在方括號內傳遞給非終結符號 `string`。由于 `string` 表示的是 JSON 對象的鍵-值對中的鍵，所以每次找到一個鍵時，類 `print` 中的重載 `operator()()` 操作符將被調用，將該鍵寫出到標準輸出流。我們可以定義任意數量的動作，或將它們關聯至任意數量的符號。要把一個動作關聯至一個字面值，必須明確給出一個詞法分析器。這與在非終結符號 `string` 的定義中指定 `boost::spirit::ch_p` 類沒什么不同。以下例子使用了 `boost::spirit::str_p` 類來將一個 `print` 類型的對象關聯至字面值 `true`。 ``` #include <boost/spirit.hpp> #include <string> #include <fstream> #include <sstream> #include <iostream> struct json_grammar : public boost::spirit::grammar<json_grammar> { struct print { void operator()(const char *begin, const char *end) const { std::cout << std::string(begin, end) << std::endl; } void operator()(const double d) const { std::cout << d << std::endl; } }; template <typename Scanner> struct definition { boost::spirit::rule<Scanner> object, member, string, value, number, array; definition(const json_grammar &self) { using namespace boost::spirit; object = "{" >> member >> *("," >> member) >> "}"; member = string[print()] >> ":" >> value; string = "\"" >> *~ch_p("\"") >> "\""; value = string | number | object | array | str_p("true")[print()] | "false" | "null"; number = real_p[print()]; array = "[" >> value >> *("," >> value) >> "]"; } const boost::spirit::rule<Scanner> &start() { return object; } }; }; int main(int argc, char *argv[]) { std::ifstream fs(argv[1]); std::ostringstream ss; ss << fs.rdbuf(); std::string data = ss.str(); json_grammar g; boost::spirit::parse_info<> pi = boost::spirit::parse(data.c_str(), g, boost::spirit::space_p); if (pi.hit) { if (pi.full) std::cout << "parsing all data successfully" << std::endl; else std::cout << "parsing data partially" << std::endl; std::cout << pi.length << " characters parsed" << std::endl; } else std::cout << "parsing failed; stopped at '" << pi.stop << "'" << std::endl; } ``` * [下載源代碼](src/12.4.2/main.cpp) 另外，這個例子還將一個動作關聯至 `boost::spirit::real_p`。大多數分析器會傳遞一對指向被識別數據起始點和結束點的指針，而 `boost::spirit::real_p` 則將所找到的數字作為 `double` 來傳遞。這樣可以使對數字的處理更為方便，因為這些數字不再需要被顯式轉換。為了傳遞一個 `double` 類型的值給這個動作，我們相應地增加了一個重載的 `operator()()` 操作符給 `print`。除了在本章中介紹過的分析器，如 `boost::spirit::str_p` 或 `boost::spirit::real_p` 以外，Boost.Spirit 還提供了很多其它的分析器。例如，如果要使用正則表達式，我們有 `boost::spirit::regex_p` 可用。此外，還有用于驗證條件或執行循環的分析器。它們有助于創建動態的詞法分析器，根據條件來對數據進行不同的處理。要對 Boost.Spirit 提供的這些工具有一個大概的了解，你應該看一下這個庫的文檔。 ## 12.5.?練習 You can buy [solutions to all exercises](http://en.highscore.de/shop/index.php?p=boost-solution) in this book as a ZIP file. 1. 開發一個可以對任意整數和浮點數進行加減的計算器。這個計算器接受形如 **`=-4+8 + 1.5`** 的輸入，并顯示結果 `5.5`。