在一个魔法世界里，你是一个会魔法的法师。我的意思是，作为一个法师，你什么都会了，也什么都有了，施法材料，法袍，魔杖，法术书。甚至你连成功后的庆祝动作都想好了。你以为你会“魔法”了。只可惜，这里还缺少了一样东西，那就是，魔法的口诀。
而在这里，我们什么都有了。用来分析的Token，语法树到OP CODE的翻译，虚拟机，什么都有了。但是我们还是缺一样口诀，那就是，如何从Token到语法树的口诀。
在我们进行词法分析的时候，遵从的是Spirit这本颇有难度的《圣经》。不过，我们只浏览了如《使徒行传》般流畅而松散的Spirit.Lex。在这里，我们依然沿用Spirit，这是我们编译器前端的原旨。不过现在，我们要讲解的是环环相扣、荡气回肠的《Exodus》——Spirit.Qi。
嘛，这段神叨叨的引子，只是为了强调语法分析的地位而已。在继续阅读本章之前，需要你看的明白BNF。有关于BNF方面的信息，你可以在任何一本讲述编译原理的书籍上找到。
仍然是以一个简单的A+B为例。由于我们已经有了词法“literal_int”和“literal_add”，因此A+B这样一个表达式，用BNF来表示，就是：
Expr ::= literal_int literal_add literal_int
在Spirit.Qi里，语法的表达也类似于BNF的形式。只要你设计出语言的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的一个非终结符。一个Grammar相当于一组Rule的集合，并且可以拥有一个或者多个的起始Rule作为入口。本质上我们可以把Grammar看成一个Rule（准确的说，是Parser，若要了解相关概念，请参阅Spirit的自定义Parser部分）。等号用于连接非终结符（Rule）及其推导式；使用“>>”（输入流/右位移运算符）连接语法要素之间的连接符号。更多的符号请参阅Spirit.Qi文档。
至于为什么不将Rule合并到一起，而提供一个Grammar的中间层，主要有两方面的考虑，一个是提供了一个抽象层，例如我们可以把Statement和Expression分开来写，使得层次上更加清晰；还有一个方面在于节省编译时间。因为Spirit使用了大量的源编程技术，如果把所有的Rule合并到一起编译，会占用大量的编译时间。在使用了Grammar之后，可以运用C++编译器在一个编译过程里对相同的模板特化只进行一次的Tricks，大大节省了编译时间。
在上一章里，咱们最后还留了一个问题，就是空白符号的处理方法。这里，我们将于空白符号一起，来走一下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”作为状态以示区别。这里我们需要说明一下，Spirit.LEX的词法分析的“状态”与词法分析工具“Lex/Flex”中的状态概念是相同的。
在Lex类的词法分析工具里，有一个专门的状态。一般而言，这些状态都用字符串表示。Lex的默认是“INITIAL”，Spirit.Lex的默认状态是空（如果我没记错的话）。在指定词法的时候，可以告诉词法分析器，此文法在什么状态下，这条词法才发挥作用。词法分析器的状态可以由外部程序自由指定。
我们将表示空白的词法都放在Skipped状态下后，我们就可以对每个单词，用Skipped状态去匹配。如果发现是在Skipped状态下匹配成功的单词，在进入语法分析前就可以先丢弃，进而实现过滤空白符的目的。
考虑表达式“55_+38”（‘_’代表空格），在分析成Token流之后，会变成以下的形式：
| State | INITIAL | SKIPPED | INITIAL | INITIAL |
| Token | Literal_int | Literal_ws | Literal_op | Literal_int |
| Literal | 55 | _ | + | 38 |
然后撰写我们的Grammar。由于我们需要指定Skipper来跳过我们不需要的Token，因此我们的Grammar在模板参数里，也要加入这个Skipper的类型参数。
| 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; }; |
并在咱们的驱动代码里面，这样写：
| 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状态解析出来的token，就自己吃了吧，不要拿去匹配了。这样就达到了过滤掉空白符的目的。
不过呢，尽管我们parse通过了，但是仍然没有提取出我们想要的信息来。到目前为止，我们还没能让parser构造出咱们之前手工构建并传递给Code Generator的语法树来。这仍然是横亘在出埃及的我们面前的红海。
下一次，我们将仍然相信Spirit这本Bible，相信它给我们的一章叫 “Semantic Action”的启示录。它将告诉我们，如何把Parser分析出的结果转化为我们要的语法树，以引领我们走向流OP CODE之地。
God bless programmers and p2p sites except gfw’s developers and Cisco. Amen