在一個魔法世界里，你是一個會魔法的法師。我的意思是，作為一個法師，你什么都會了，也什么都有了，施法材料，法袍，魔杖，法術(shù)書。甚至你連成功后的慶祝動作都想好了。你以為你會“魔法”了。只可惜，這里還缺少了一樣?xùn)|西，那就是，魔法的口訣。
而在這里，我們什么都有了。用來分析的Token，語法樹到OP CODE的翻譯，虛擬機(jī)，什么都有了。但是我們還是缺一樣口訣，那就是，如何從Token到語法樹的口訣。
在我們進(jìn)行詞法分析的時(shí)候，遵從的是Spirit這本頗有難度的《圣經(jīng)》。不過，我們只瀏覽了如《使徒行傳》般流暢而松散的Spirit.Lex。在這里，我們依然沿用Spirit，這是我們編譯器前端的原旨。不過現(xiàn)在，我們要講解的是環(huán)環(huán)相扣、蕩氣回腸的《Exodus》——Spirit.Qi。
嘛，這段神叨叨的引子，只是為了強(qiáng)調(diào)語法分析的地位而已。在繼續(xù)閱讀本章之前，需要你看的明白BNF。有關(guān)于BNF方面的信息，你可以在任何一本講述編譯原理的書籍上找到。
仍然是以一個簡單的A+B為例。由于我們已經(jīng)有了詞法“l(fā)iteral_int”和“l(fā)iteral_add”，因此A+B這樣一個表達(dá)式，用BNF來表示，就是：
Expr ::= literal_int literal_add literal_int
在Spirit.Qi里，語法的表達(dá)也類似于BNF的形式。只要你設(shè)計(jì)出語言的BNF，就很容易的翻譯成Spirit.Qi支持的語法定義。我們這里，就可以寫成：
template <typename IteratorT>
struct binary_expression: qi::grammar<IteratorT>{
template <typename TokenDefT> binary_expression(const TokenDefT& tok): binary_expression::base_type(start)
{
start = ( literal_int >> literal_op >> literal_int );
literal_int = tok.littok_int;
literal_op = tok.optok_add;
}
qi::rule<IteratorT> literal_op, literal_int, start;
};
在Spirit.Qi中，一個Rule就等于EBNF的一個非終結(jié)符。一個Grammar相當(dāng)于一組Rule的集合，并且可以擁有一個或者多個的起始Rule作為入口。本質(zhì)上我們可以把Grammar看成一個Rule（準(zhǔn)確的說，是Parser，若要了解相關(guān)概念，請參閱Spirit的自定義Parser部分）。等號用于連接非終結(jié)符（Rule）及其推導(dǎo)式；使用“>>”（輸入流/右位移運(yùn)算符）連接語法要素之間的連接符號。更多的符號請參閱Spirit.Qi文檔。
至于為什么不將Rule合并到一起，而提供一個Grammar的中間層，主要有兩方面的考慮，一個是提供了一個抽象層，例如我們可以把Statement和Expression分開來寫，使得層次上更加清晰；還有一個方面在于節(jié)省編譯時(shí)間。因?yàn)镾pirit使用了大量的源編程技術(shù)，如果把所有的Rule合并到一起編譯，會占用大量的編譯時(shí)間。在使用了Grammar之后，可以運(yùn)用C++編譯器在一個編譯過程里對相同的模板特化只進(jìn)行一次的Tricks，大大節(jié)省了編譯時(shí)間。
在上一章里，咱們最后還留了一個問題，就是空白符號的處理方法。這里，我們將于空白符號一起，來走一下Spirit的語法和詞法分析的流程。
首先，我們建立好詞法，將源代碼字符流組織成更加容易被語法分析識別的Token流。
| template <typename BaseLexerT> struct sasl_tokens : public boost::spirit::lex::lexer< BaseLexerT > { sasl_tokens(){ this->self.add_pattern("SPACE", "[ \\t\\v\\f]+"); littok_int = "[0-9]+"; optok_add = "[\\+]"); whitetok_space = "{SPACE}"; this->self = littok_int | optok_add; this->self("SKIPPED") = whitetok_space; } boost::spirit::lex::token_def<> littok_int, optok_add, whitetok_space; }; |
這里，我們將詞法分為兩組，對語法分析有效的Tokens組和無效的空白組，空白組用”Skipped”作為狀態(tài)以示區(qū)別。這里我們需要說明一下，Spirit.LEX的詞法分析的“狀態(tài)”與詞法分析工具“Lex/Flex”中的狀態(tài)概念是相同的。
在Lex類的詞法分析工具里，有一個專門的狀態(tài)。一般而言，這些狀態(tài)都用字符串表示。Lex的默認(rèn)是“INITIAL”，Spirit.Lex的默認(rèn)狀態(tài)是空（如果我沒記錯的話）。在指定詞法的時(shí)候，可以告訴詞法分析器，此文法在什么狀態(tài)下，這條詞法才發(fā)揮作用。詞法分析器的狀態(tài)可以由外部程序自由指定。
我們將表示空白的詞法都放在Skipped狀態(tài)下后，我們就可以對每個單詞，用Skipped狀態(tài)去匹配。如果發(fā)現(xiàn)是在Skipped狀態(tài)下匹配成功的單詞，在進(jìn)入語法分析前就可以先丟棄，進(jìn)而實(shí)現(xiàn)過濾空白符的目的。
考慮表達(dá)式“55_+38”（‘_’代表空格），在分析成Token流之后，會變成以下的形式：
| State | INITIAL | SKIPPED | INITIAL | INITIAL |
| Token | Literal_int | Literal_ws | Literal_op | Literal_int |
| Literal | 55 | _ | + | 38 |
然后撰寫我們的Grammar。由于我們需要指定Skipper來跳過我們不需要的Token，因此我們的Grammar在模板參數(shù)里，也要加入這個Skipper的類型參數(shù)。
| template <typename IteratorT, typename LexerT> struct binary_expression: qi::grammar<IteratorT, qi::in_state_skipper<LexerT> > { template <typename TokenDefT> binary_expression(const TokenDefT& tok): binary_expression::base_type(start) { start = ( literal_int >> literal_op >> literal_int ); literal_int = tok.littok_int; literal_op = tok.optok_add; } boost::spirit::qi::in_state_skipper<LexerT> skipper_type; qi::rule<IteratorT, skipper_type> literal_op, literal_int, start; }; |
并在咱們的驅(qū)動代碼里面，這樣寫：
| typedef sasl_tokenizer::iterator_type sasl_token_iterator; typedef sasl_tokenizer::lexer_def sasl_skipper; sasl_tokenizer sasl_tok; binary_expression<sasl_token_iterator, sasl_skipper> g( sasl_tok ); lex::tokenize_and_phrase_parse( first, last, sasl_tok, g, qi::in_state("SKIPPED")[sasl_tok.self] ); |
喏，看到了指定skipper的代碼了不？這就提示parser，遇到了skipped狀態(tài)解析出來的token，就自己吃了吧，不要拿去匹配了。這樣就達(dá)到了過濾掉空白符的目的。
不過呢，盡管我們parse通過了，但是仍然沒有提取出我們想要的信息來。到目前為止，我們還沒能讓parser構(gòu)造出咱們之前手工構(gòu)建并傳遞給Code Generator的語法樹來。這仍然是橫亙在出埃及的我們面前的紅海。
下一次，我們將仍然相信Spirit這本Bible，相信它給我們的一章叫 “Semantic Action”的啟示錄。它將告訴我們，如何把Parser分析出的結(jié)果轉(zhuǎn)化為我們要的語法樹，以引領(lǐng)我們走向流OP CODE之地。
God bless programmers and p2p sites except gfw’s developers and Cisco. Amen