语义：从分析树到语法树（一）

在1-7章里，我们已经建立了一个编译器所需要的绝大部分环节：词法分析、语法分析、代码生成、代码执行。前两个阶段，将会生成分析树（Parse Tree）后两个阶段，则是用语法树生成的。我们多希望语法分析后的分析树，直接就能用作语法树啊！

从结构上看，分析树和语法树几乎是如出一辙的。只可惜，如果我们再仔细的观察会发现，从分析树到语法树有一条深深的鸿沟。是的，你猜得没错，这条鸿沟，就是语义。只要有了语义，我们就可以将我们的分析树，变成可以产生代码的语法树。

本质上讲，语法树（Syntax Tree）是含有语义的。仍然用A+B这个表达式的语法树来举例子。在这里，A和B都是一个Int32的常量，例如我们这里A是5，B是10。这个语法树里面A节点，它具有以下的语义：

• A是一个常量。
• A是一个整型值。
• A是5。

这些语义信息在语法树里面都具备，而在语法分析之后的分析树里面，只有“5”这样一个字符串。所以实际上，从分析树到语法树的建立，还需要经历一个附加语义的过程。

在一个常见的编译流程里，语义分析可以分为两个部分。其中一部分会跟随在词法和语法分析中，用于解析一些最基本的语义。例如输入的是不是关键字啦，是不是字面量啦，是不是运算符啦一类的信息，这些语义信息还可能用来指导后一阶段的语法分析。

还有一个部分就是例如类型推导、符号设置、函数签名分析一类的语义分析。这些分析的结果通常并不影响语法树的结构，而放在语法分析阶段又会增加分析的复杂度。这一类的语义分析，通常是在语法树建立好之后，再来对语法树进行进一步的分析，将语法树上的语义信息补完。

在SASL里，我们将语法树的建立分成三个步骤。

第一步，在词法分析和语法分析的同时，进行简单的语义解析。包括字面值、操作符、关键字的提取等。这些一方面是语义，一方面也是为了语法分析服务的。

第二步，我们将语法分析得出来的分析树，转换成我们需要的语法树的形式。我们的语法树上，拥有一些属性。通过这些属性可以给语法树节点上附加产生代码所必须的语义。

第三步，遍历语法树，填充语义，执行一些准备工作。

这样，我们就建立了一颗可以被代码生成工具所识别的语法树。

接下来，我们将运用Spirit.Lex和Spirit.Qi来完成我们前两步的工作。

第三部分，我们暂时还不需要，等需要的时候，咱们再来扩充。

Exodus：语法分析（一）

在一个魔法世界里，你是一个会魔法的法师。我的意思是，作为一个法师，你什么都会了，也什么都有了，施法材料，法袍，魔杖，法术书。甚至你连成功后的庆祝动作都想好了。你以为你会“魔法”了。只可惜，这里还缺少了一样东西，那就是，魔法的口诀。

而在这里，我们什么都有了。用来分析的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

起源：词法分析

不管你学什么样的外语，大约都是从词汇开始。词，是一个语言里最小的语义单元。编译器阅读你的语言，也是如此。所以第一件事情，就是要把整个文法打散成一个一个的单词。在这里，我们把这些单词叫token。

怎么进行词法分析，此处就不再赘述，这是一个上下文无关文法的匹配问题。如果需要理解词法分析的原理，或者手工编写词法分析工具，可以参考陈梓翰提供的两篇极好的教程。在SASL里，我们不再发明轮子，而选用已有的词法分析工具。

可选的词法分析工具很多，例如出名的Lex及其改进Flex，ANTLR等。对于C++而言，这些方法多属于产生式的方法，就是用一段不太靠谱的代码去生成另外一些更不靠谱的代码。更重要的是，这些代码的编译、调试都不方便。所以最终我们还是选择了一个在用C++实现、并且可以直接在C++里书写词法和语法的分析器产生工具，它就是Spirit。

Spirit V1.8和V2.1都是Boost库里的一个部分。需要注意的是，Spirit的V1和V2是完全不兼容的两个库。在这里，我们选择了V2作为我们的词法和语法分析工具。Spirit V2总共分为3个部分，负责语法分析的Qi，格式化打印的Karma，和词法分析器Lex。此外，Spirit还有一个类似于boost.mpl和boost.lambda的库phoenix，这个库也常被用于词法和语法分析中。详细的使用指南和参考，可以参见Spirit的文档。

由于Spirit.Lex大量运用了Template Meta-Programming和编译器推导，因此编译时很容易出错，而且错误信息难于定位；同时Spirit.Lex的指南也写得非常简单，它所演示的特性，不足以用来实现一个完整的编译器。因此，这里我们也将给出另外一个快速指南，以展示那些我们在撰写编译器时所用到的技术和特性。

这里我们仍然以A+B这样一个简单的表达式为例，其中A和B都是一个字面值的整数，A+B之间没有其他空格填充。这样我们就可以把这个“句子”拆分成A，+，B三个token。例如“33+65”就可以被拆分成“33”，“+”，“65”三个token。对于这样一个表达式，我们只需要下面两个正则就可以完成词法分析：

literal_int = “[0-9]+”; literal_add=”\+”;

由于C++里面“\”是转义符，因此实际上literal_add实际上应该写成“\\+”。然后我们需要用Spirit来实现。

Spirit中，首先定义一个tokens列表：

template <typename BaseLexerT>

struct sasl_tokens : public boost::spirit::lex::lexer< BaseLexerT > {

    sasl_tokens(){

        littok_int = "[0-9]+";

        optok_add = "[\\+]";

 

        this->self =

            littok_int

            | optok_add;

    }

    boost::spirit::lex::token_def<> littok_int, optok_add;

};

 

然后，我们利用这个token列表生成一个词法分析器sasl_tokenizer：

 

typedef boost::spirit::lex::lexertl::lexer<> sasl_lexer_base; typedef sasl_tokens<sasl_lexer_base> sasl_tokenizer;

 

最后来执行一下我们的tokenizer。在执行之前，我们写一个callback函数，这个函数在每分析出一个词之后，都会被调用一下，我们用它来判断我们分出的词正确与否：

struct token_printer{

    template <typename TokenT> bool operator()( const TokenT& tok ){

        cout << "token: " << tok.value() << endl;

        return true;

    }

};

最后执行一下词法分析：

boost::spirit::lex::tokenize(first, last, sasl_tok, token_printer());

first，last是输入字符串的迭代器。如果输入为“55+65”，那么屏幕上就会依次打印出“55”，“+”，“65”的三行。

不过，如果你在“55+65”之间敲入一个空格，例如“55+_65”(‘_’代表空格)这样的，那么词法分析就会失败。因为“_”这个字符，没有合适的词可以匹配。即便是匹配了，空白这个Token也没办法用在语法树之中，最终也会导致语法分析失败。而在程序语言里，支持空白符号的过滤掉是必不可少的。所以，下一次，我们就要将语法，顺便过滤掉空白符，让我们可以自由写出美观的语句。

知道咱们的虚拟机能够执行OP CODE之后，下一步就要考虑，怎么从语法树里面生成咱们需要的OP CODE了。简单来讲，语法树就是将程序的逻辑按照树状组织并保存在内存中的一种形式。有关于更详细的信息，搜“Syntax Tree”，到处都是解释。

一时不明白也没关系，我们来看一个直观的例子。考虑a+b这样一个基本形式的表达式。这个表达式既可以按照我们所写的这样，分为a，+，b三个部分串行表示，也可以表示成下图的样子


可能一个表达式你还看不出来树形的优势。要是表达式级联起来，就显示出这种表示的威力了：

 
这样一个语法树，可以不借助任何别的手段，保存了表达式的优先级关系。这里的语法树表示的就是(A+B)*C的表达式。同时，在语法树上求值也很方便，后根遍历语法树就可以了。即先算出左右节点的值，再根据当前节点符号求出当前节点值。

王阳明说，知行合一。知道了语法树是什么东西，我们就要开始考虑怎么用了。“怎么用”这个问题可以分成两个部分，第一，语法树怎么实现。第二，语法树怎么生成op code。啊，先不要把语法树想象的这么复杂。在这里，我们的运算符只有加号，一个加号也只能带两个int的值节点，而不能递归的带上一个符号节点。也就是说，这棵树只可能有一种形式而已。

首先来解决语法树怎么实现的问题。在这个问题上，我们只需要把握一点，语法树是一个天然的composite模式。我们用一个UML来看看这个只有加法算符的语法树定义：
唔，很简洁，不是么。Node_type是一个syntax_node_types类型的枚举，这个枚举告诉以后的代码生成器这个抽象的node究竟是个什么类型，然后代码生成器再还原它原本的类型并生成适当的代码。op是一个operators类型的枚举，表示一个二元运算的操作符。对于本例，只有operators::add可用。
在有了基本实现之后，再考虑一下其它需求，例如语法树节点类型之间的可能存在的循环依赖问题，语法树的深浅拷贝问题，等等，最终SASL的语法树节点接口是这样的：


道理复杂，不过实际上，并没有那么复杂吧？
下面来解决第二个问题：怎么用表达式树产生代码？我不多解释，直接上代码，相信你一定会看明白的：



然后我们将生成语法树，生成code，运行code的代码补上，运行，OK~
你一定会说，啊，硬性绑定寄存器！太可怕了！如果表达式复杂了该怎么办呢？呵呵。这些都是以后的问题了。以后的问题，就由以后的我们去解决好了。今日事，今日毕，时间不早，咱们还是洗洗睡了。

     摘要: 本文重点在于利用现有各式各样的编译器前端或后端技术和库，以可控制和渐增的方式，将我们的编译器从无到有，从小到大，从简单到复杂，从低效到高效的实现出来。本文的写作目标是，我们将编写编译器的任务，分解成多个迭代的阶段，其中的大部分阶段，你都能够在理解它之后，在一个小时到一天不等的时间内达到预计的目标。  阅读全文

今天群里面正好有朋友问起这个问题，就简单的解答下，如果有问题的话，欢迎大家留言批评指正。

常用的源代码授权协议主要分为以 下两类，商业协议和开源协议。今天主要讨论一下开源协议。首先需要明确的是，既然是许可，就一定会具备法律效力。如果你的GNU作品被人侵权了的话，去找 GSF（GNU Software Foundation）吧，让他们把你打官司，就像Skype被告了那样的，哈。唔，当然你自己打也是可以的，就是搜集证据方面可能有点难度。

开源协议，都有一个共同的特性，就是开放了源代码（这句话貌似很废话yeah）。他们的区别在于三点：
1.对源代码的修改限制。一些开源协议会告诉你，只能使用已有源代码而不能进行修改。
2.对原有协议许可的修改限制。通常的开源协议都会让使用者在发布的二进制软件或者源代码中，保有被使用的软件的版权信息和协议许可。
3. 对二进制和源代码产品的发布限制。对于GPL协议而言，使用了GPL协议的产品的软件，是不允许单独发行二进制产品的，而必须要将源代码以GPL的协议发 布出来。这就是所谓的“传染性”。这也就意味着，只要你的产品的使用链上有GPL的玩意儿，对不起，你就只能GPL了。
而LGPL协议就要宽松的多。如果你使用了别人LGPL协议的二进制，只需要保有许可并不加修改，就不影响你的产品授权。但是如果你使用、修改了别人LGPL协议的源代码，那么，修改后的源代码就必须要公开，并且一样遵守LGPL协议。

GPL这样的协议，相对是严格的。开源协议里面，还有很宽松的BSD,MIT和BOOST协议。这些协议的被授权方，可以自由修改、散播源代码或者源代码衍生的产品，只需要你产品的授权协议里，将BSD,MIT,BOOST协议一并附上就可以了。
http://www.awflasher.com/blog/archives/939
这里有GPL,LGPL,APACHE,BSD,MIT五种常见开源协议的简单介绍。其他的可以参见baidu/wiki，或者如果你有足够的法律知识，可以去直接看协议条款吧，嘎嘎。

今天朋友的问题是，如果一个东西全部都是他做的，想以GPL的形式公开，同时还想卖钱，可以吗？
答案当然是肯定的。Qt 就是个最好的例子。Qt兼具GPL/LGPL协议和Qt Commercial的商业协议。你完全可以以GPL的的协议将你的产品公开，然后如果有人想用你的东西做商业用途，你就再签一份商业许可就可以了。以上 的几个开源协议，都是经由OSI批准的，强烈建议大家在发布新程序的时候，另可采用多份协议，也不要轻易修改标准协议。
但是注意，如果你的产品里，直接或间接使用了第三方产品（这个太常见了，比方说Image Library啦，boost啦等等），一定要看清楚它的协议。如果你不小心用了GPL协议的组件，那么对不起，你的商业授权就算是废了，因为你的产品只能是GPL协议的了。
所以说，如果制作商业产品，stl，gdi+这样的商业授权是首选（注意一下你有没有发布产品的权利，不是所有的商业授权你都有发布的权利的）。
其次是BSD,MIT一类的自由度非常高的协议，再其次是LGPL这样的二进制可发布的协议。
GPL是一定不能选的。相对的，如果你仅仅制作GPL协议的产品，也要看清楚，你是否具有发布第三方源代码的权利。当然如果仅仅发布你撰写的程序，是不会有问题的。

没啥好说的，没什么技术含量，就是有点用，功能类似于VA X的#ifndef guard.
生成的格式按照 PROJECTNAME_FILENAME_FILEEXTNAME_GUID 来的。
比方说我的就是

SPIRIT_SASL_AST_NODE_STATEMENT_H_B530FB44_F5C8_431F_A250_E426F791B7CF

如果有需要可以自己改一下代码就好了。

语言是VB.NET.

工程+源代码文件下载地址

     摘要: 详细讨论了在设计静态强类型语言语法时如何处理类型别名(typedef)和变量定义的类型声明的问题。  阅读全文

最近用了一段时间的wxWidgets。
基本上主流的界面库也就算用的差不多了。
这里拿一个表格对这些界面库做一个比较直观的比较。

界面库名称	接口设计	界面编辑器	高级布局功能	平面绘制	平台兼容性	语言支持	IDE兼容性	视图-模型分离机制	运行时	其它
Windows Forms	接口优秀。C++下使用CLI扩展，其它语言为原生支持。	界面编辑器完整，包括布局、属性、消息关联的完整设置。不可预览。	Table Layout，Splitter Layout，Flow Layout等，Anchor和Dock机制。多分辨率界面下表现良好。	GDI+，面向对象的2D绘制接口，使用简便。	需要.Net平台支持。WIndows或Linux（Mono，非官方支持），支持Windows CE	C++/CLI, 支持.net的语言。	仅VS。	布局和视图方案建立在代码中。部分组件支持Model-View架构。	需要部署对应的.net	商业协议
MFC	基于宏和虚函数，使用特殊格式注释，使用自定义的RTTI系统。类接口设计优良。通过回调函数和虚继承重载调用客户代码。	基于资源编辑器，仅能对空间基本布局和少量属性进行调整。不可预览。	缺乏高级布局功能，多分辨率需要是手工或程序中调整。	GDI及GDI封装，可选GDI+	Windows，Windows CE	C++ Only， 支持COM时可以实现Binary级别复用。	仅Visual Studio	使用资源保存控件的基本控件布局，提供Doc-View机制和控件数据交换支持视图分离。	需要部署MFC运行时库。	商业协议
WTL	基于模板和虚函数。类接口类似于MFC。需要使用多重继承。通过模板特化和回调函数与客户代码交互。	同MFC	同MFC	同MFC	同MFC	同MFC，对COM的支持比MFC完善很多。	Visual Studio，Windows下支持标准的C++编译器。	使用资源文件保存空间布局。	无	自由协议
wxWidget	宏，自定义RTTI。使用回调函数与用户代码交互。	无官方界面编辑器。可使用第三方界面编辑器。部分编辑器具有完整的所见即所得功能，且具有预览能力。	使用Sizer实现多分辨率的布局。功能偏弱。	wxDC等。	Windows，Linux，Unix，MacOS等	C++, .NET, Python, Lua, Ruby等	良好的编译器兼容性，缺乏IDE继承。	可以将界面属性生成到代码中，也可以使用XML格式保存。	wx的动态链接库或静态链接。	自由协议
Qt	使用宏和自定义的RTTI。使用Singal-Slot机制实现用户代码交互。可通过继承实现扩展。	Qt Designer，具备完整的所见即所得编辑功能。可预览界面。	具备完整的布局功能。多分辨率/多平台下表现良好。	QCanvas等。	Windows，Linux，Unix，MacOS等。	C++，Python等	可集成到Eclipse和VS	使用资源文件保存界面信息。部分组件具备Model-View-Delegate架构	qt的动态链接库。	开源协议+商业协议
GTK+	使用signal-slot机制完成用户代码交互。	GLADE，具备所见即所得的界面编辑功能	Layout Containers，具备较完整的布局能力。	GTK Graphics Context	Windows，Linux，Unix，MacOS等。	C，C++，Python，.NET等。	（暂时未知）	使用代码完成界面设置。部分组件具备Model-View架构。	GTK Runtime	开源协议

此外，除了WTL外，其余各界面库均有完整及时的文档和手册，因此比较项中不再指明。
回帖中有人指出国际化问题的比较，事实上MS的产品和开源对于国际化的解决方法是不同的。但是都可以比较方便的解决国际化问题。