[转]装配脑袋：自己动手开发编译器

原文：http://www.cnblogs.com/Ninputer/archive/2011/06/06/2073908.html

自己动手开发编译器（零）序言

好久没写博客了，一来是自己懒，二来是最近一段时间都没有做什么自己认为可以分享的东西。这几天刚好重拾了一个一直打算做但没做的编译器类库，算是积累了一点小小的经验吧。本来我已经发到了Github上，也在微博上零星介绍了一些，但是我最终意识到，如果不写一个详细的文档，别人就不能容易地学习、了解和使用它。甚至于我自己也可能会把这次研究出来的小小成果给忘了。所以，必须下决心动一动笔头，也算是对老长时间不些博客的弥补吧。

[转]装配脑袋：自己动手开发编译器

本篇是系列的第零篇，我首先要介绍一下些这个系列的目的。从很久以来，编译器的技术就是计算机科学的基础。我想编程语言在大家软件开发生活中的重要性不言而喻。那么，为什么我们需要了解编译器内部的原理呢？有很多原因：首先，编译原理是一门经过长期实践完善的理论，它涵盖了很多算法，都是非常经典的算法。从前端到后端，编译器设计到的很多算法，都很强大、快速。比如我们经常要用到的正则表达式解析字符串的算法。通过学习编译原理，可以更加深刻地理解和应用这些算法。比如明白正则表达式能够表示何种语言，不能表示何种语言，何时性能最好，何时性能不好等，这样就能够在实践中更加科学地加以采用。其次，我们处在一个编程语言爆发的时代，我们所熟悉的语言每个版本都有新特性，更不要说各种新型语言、脚本、DSL和其他基于格式化文本的协议层出不穷。掌握一些编译原理的知识能让我们在这个时代更具有主动性。大家都知道，老赵最近开发的Jscex，它给javascript引入了优美的异步编程模型。相信大家不仅想崇拜老赵，更想知道为什么他能开发出这种创新的技术吧？其实很多知识就来自于编译原理。最后，我想说下我自己的学习目的。大家最近都知道C#5就快要出来了，在感叹变化之快的同时，是否也有一丝遗憾，那就是自己心目中的语言特性还是没有出现在C#5中呢？我相信各位有些人对编程语言的发展是感兴趣的，那么就不要停留在对各个语言特性品头论足的阶段了，动手来实现自己心中的想法吧！只有实践，才能知道自己的想法是不是对的，是不是有价值。实践是最好的学习方式。我想各位起码在大学期间都学过了编译原理这门课程，但是还有许多实际问题值得挑战，比如C#和VB等语言的源文件里支持中文，甚至变量和函数都可以用中文，那么怎么做才能在编程语言里支持中文？在大学学习的时候，也许没有处理过面向对象语言，那么面向对象语言有什么不同？有很多重载方法的时候，如何挑选一个最合适的？甚至再进阶一步可以考虑如何实现一个支持泛型的编程语言？Lambda表达式捕获变量是怎么做到的等等。至于编译器后端，那更是一个广阔的话题，涉及的技术可能帮助你深入操作系统和硬件的内部。

在一般人眼里，编译原理是个比较难掌握的理论体系。首先必须承认编译器涉及的技术非常广泛，每一种又可以非常深入，确实像个无底洞。所以这次我采用一个实际的例子，编写一个简单但具有基本功能的编程语言，在这个过程中逐个了解其中的技术。这样就可以边学习边实践。建议感兴趣的同学跟着动手实践，体会其中的乐趣。我并不会完全重复编译原理书本中的理论，而是会面向对现代编译器中的实际问题进行讨论。我想让我这个系列具有较高的实践价值。

本系列将会围绕我开发的一个编译器开发库——VBF.Compilers来进行。这个库涉及编译器前端各个阶段所需要的工具，如词法分析器、语法分析器的构造，以及读取源文件、记录编译错误的辅助设施等。完全由我来开发。有人可能要问我为何不用些现成的工具，比如ANTLR之类的呢？首先这些现成工具都有一些小毛病，不能令我完全满意；其次我的VBF与这些工具不同，它是一个纯粹的类库，只需要在VB或C#中引用，然后用VB或C#的语法来编写，就可以写出各种编译器模块来。比起依靠一堆工具框架的，我更喜欢类库这种形式。另外我的类库中也包含了我的一些小小创新，希望能给编译器开发带来一些方便。在这个系列里，我会兼顾VBF.Compilers的实现原理和其用法。大家如果想快一点实践呢，可以直接使用我的类库；如果不喜欢我的类库呢，也可以自己实现或者用别的代替，总之看大家的兴趣了。作为例子，我会在这个系列中实现一个C#语言的极小子集miniSharp，它的语法大家都再熟悉不过了，各位有兴趣可以对其随意扩展。

VBF.Compilers类库和例子的源代码已经全部上传至Github:https://github.com/Ninputer/VBF 请大家自行用git下载最新的代码。（注，请别担心，它虽然叫”VBF“但其实100%是C#开发的……）。另外欢迎大家关注我的微博：http://weibo.com/ninputer 我会经常在上面播报开发状态，另有许多其他丰富的信息~

好，那就请大家期待我这一系列的文章吧。

自己动手开发编译器（一）编译器的模块化工程

本系列的第一篇，我想概述一下编译器的构造，同时帮助大家了解编译器中各个组成部分的用途。想必大家看别的编译原理书籍，大都在第一章或者序言之类的地方，将编译器分成许多模块，然后每一个模块负责编译的特定阶段，最后串起来组成完整的编译器。比如下面这张图就是虎书（Modern Compiler by Andrew W. Appel）第一章中出现的编译器阶段示意图：

那么，为什么要将编译器拆成一个个阶段，一个个模块呢？答案是，为了更加容易设计和理解。一个完成编译器怎么也算是一项大工程，如果不将其分解，将是非常难以编写和维护的。而编译器的模块划分得越清晰，工作就越简单。比如在词法分析阶段将输入的字符流转化成单词（token）流，就大大减少了语法分析阶段需要判断的输入种类，在简化设计的同时还有助于提高性能。此外模块化还将编译器各个阶段的工作尽量独立开。比如编译器可以进行与具体CPU无关的优化，也可以针对某种CPU进行特定的优化，都可以分别独立进行而不用重新设计整个系统。

有个事实可能会令人感到惊讶，编译器的各个阶段和模块如何设计，甚至跟这种编程语言的语法有关。比如早期的编程语言Fortran，在设计当初人们还没有掌握现在这么多编译原理的理论，它的语法就不能像当今的语言一样清晰地分成词法分析和语法分析等阶段。因为Fortran的语法并不包含可以用自动机独立处理的词法结构。于是，Fortran语言的编译器在语法分析方面就比较繁杂。有一些历史背景的语言也可能会具有这种复杂化的语法，比如Visual Basic也属于不能用独立的、基于自动机的词法分析器来扫描的语言。因此VB的语法分析器就要比诸如C#等思路较新语言的难写很多。另外一个例子是早期的Pascal语言和某些C语言允许用一些特定的语法来指定某变量为寄存器变量（也许在近期的Delphi中仍然存在，求证）。这是因为当时还没有非常有效的寄存器分配算法，需要程序员凭自己的经验来决定。在今天如果一种语言还允许显式指定某个变量是寄存器变量，就会干扰寄存器分配模块的设计。综上所述我想给各位未来的编译器设计师们一个建议，好好设计你们的语法，就能大大简化编译器的设计！

除了简化设计之外，将编译器的各个阶段模块化还有更大的价值。原先我们认为编译器只要把源文件编译成最终的目标代码就好了。但是随着各种各样的开发工具出现——编辑器、自动完成、调试器、重构工具、测试覆盖率检测、性能剖析器…… 人们发现编译器编译过程中，各个阶段产生的结果都可能是非常有价值的。将编译器内部结构和中间结果暴露给用户是必然的趋势。比如Visual Studio下一代产品中将提供的Compiler as a Service特性，其做法就是将编译器的内部模块暴露给用户成为一种服务。我举几个例子可以让大家看到编译器模块的输出有哪些可能的用途：

编译器的阶段	产生的结果	用途
词法分析	单词流	语法高亮
语法分析	抽象语法树	语法高亮；代码格式化；代码折叠
语义分析	带类型信息和符号表的抽象语法树	重命名；重构；代码自动生成；代码自动改写
数据流分析	控制流图、冲突图	编辑后继续运行（Edit and Continue）

这里我只是举几个简单的例子，以上结果的用途当然不会仅限于此。我相信将编译器的内部模块暴露给用户还能产生无数有趣和有价值的应用。

上述编译器的各个阶段还可以根据其用途分成两个大阶段：词法分析、语法分析和语义分析重点在处理编程语言的符号系统上，统称为编译器的前端（front-end），而中间代码生成、规范化、指令选择、控制流分析、数据流分析、寄存器分配、指令流出、汇编、连结等着重处理代码计算逻辑的阶段统称为编译的后端（back-end）。应该说现代编译器研究的工作重点是编译器的后端，因为前端的技术已经相对非常成熟。但是前端的技术对我们日常开发来讲可能更有机会用到，而且通常更具趣味。所以我也会花较多时间在前端技术上。当大家完成一种编译器的前端后，有几种实现后端的选择：

使用CLR或Java虚拟机作为后端。因为这些大型虚拟机的抽象程度极高，这种方法是最容易的。非常适合动态语言和脚本。
采用可靠的开源或商业后端框架。比如著名的LLVM（http://llvm.org/）。这样可以直接利用LLVM的性能优化成果，以及跨平台等特性。
自己实现后端。要做的事情比较多，但更有助于理解翻译和优化代码的技术。
解释执行。不解释。。。

我将展示的例子miniSharp虽然是C#语法的子集，但是并没有限定必须运行在CLR之上。我会将它设定成一个可重定向的语言，即可以针对多种后端。这样就可以用一个例子演示尽可能多的技术。我也会视我自己的能力范围和工作进度动态调整本系列的内容。也希望大家继续关注VBF.Compilers项目（https://github.com/Ninputer/VBF）和我的微博（http://weibo.com/ninputer）！敬请期待下一篇。

自己动手开发编译器（二）正则语言和正则表达式

从今天这一篇起，我们就来正式揭开编译器的奥秘。首先我们接触到的模块是词法分析器，也叫词法扫描器，代码里我常常叫它Scanner。昨天我稍微解释了一下为什么需要将词法分析单独分离出来，今天来回顾一下这个问题。请看下面这段C#代码：

string str = "Hello World";

即使没有语法高亮，这段代码也可以很明显地分成好几部分。首先是关键字string，之后是变量名str，然后是等号=，接下来是一个字符串字面常量”Hello World”。现代语言如C#这样的，都能明显地将源代码分断成这样具有明确含义的片段，我们称之为词素（lexeme）。与描述整个C#语言的语法相比，我们用比较简单的规则就能描述不同类型的词素。比如上面这段代码中出现的词素用白话来描述的话就是：

类型	规则	例子
关键字string	正好是s-t-r-i-n-g这几个字母按顺序组成	string
标识符（变量名）	由字母开头，后面可以跟零个或多个字母或数字，但不能与关键字冲突	str
等号	一个=符号	=
字符串字面常量	由双引号开始，中间可以包含任意个不是双引号的字符，最后以双引号结尾	"hello world"
分号	一个;符号	;

我们看到，不同词素可以根据其特征划分到几个类型当中，而接下来的语法分析阶段，就可以直接以词素的类型——我们称之为单词（token）——作为输入。token有时候也翻译成令牌、记号、象征什么的，在本文中统一称为单词。如此可见，只要用相对简洁的规则，就能把原本字符串组成的源文件，分解为一串单词流，这样就能大大简化接下来的语法分析。这就是我们把词法分析单独分出来作为一个模块的根本原因。

不过，上面表格中所列的规则是用白话来描述的，我们希望能用一种形式化的语言来进行描述，以便计算机自动进行处理。正则表达式就是一个理想的选择。

大家日常编程中估计多多少少都接触过正则表达式，用它来匹配字符串等，也可能已经很熟悉其语法了。但我这次想从正则表达式的最基本概念来重新介绍一次，主要想让大家更深地理解它。首先我们要重新定义一下“语言”这个概念。“语言”就是指字符串的集合，其中的字符来自于一个有限的字符集合。也就是说，语言总要定义在一个有限的字符集上，但是语言本身可以既可以是有穷集合，也可以是无穷集合。比如“C#语言”就是指满足C#语法的全体字符串的集合，它显然是个无穷集合。当然也可以定义一些简单的语言，比如这个语言{ a }就只有一个成员，那就是一个字母a。后面我们都用大括号{}来表示字符串的集合。所谓正则表达式呢，就是描述一类语言的一种特殊表达式，正则表达式共有2种基本要素：

表达式ε表示一个语言，仅包含一个长度为零的字符串，可以理解为{ String.Empty }，我们通常把String.Empty记作ε，读作epsilon。
对字符集中任意字符a，表达式a表示仅有一个字符a的语言，即{ a }。

同时正则表达式定义了3种基本运算规则：

两个正则表达式的并，记作X|Y，表示的语言是正则表达式X所表示的语言与正则表达式Y所表示语言的并集。比如a|b所得的语言就是{a, b}。类似于加法
两个正则表达式的连接，记作XY，表示的语言是将X的语言中每个字符串后面连接上Y语言中的每一种字符串，再把所有这种连接的结果组成一种新的语言。比如令X = a|b，Y = c|d，那么XY所表示的语言就是{ac, bc, ad, bd}。因为X表示是{a, b}，而Y表示的是{ c, d}，连接运算取X语言的每一个字符串接上Y语言的每一个字符串，最后得到了4种连接结果。这类似于乘法
一个正则表达式的克林闭包，记作X*，表示分别将零个，一个，两个……无穷个X与自己连接，然后再把所有这些求并。也就是说X* = ε | X | XX | XXX | XXX | ……。比如a*这个正则表达式，就表示的是个无穷语言{ ε, a, aa, aaa, aaaa, …. }。这相当于任意次重复一个语言。

以上三种运算写在一起时克林闭包的优先级高于连接运算，而连接运算的优先级高于并运算。以上就是正则表达式的全部规则！并不是很难理解对吧？下面我们用正则表达式来描述一下刚才各个词素的规则。

首先是关键字string，刚才我们描述说它是“正好是s-t-r-i-n-g这几个字母按顺序组成”，用正则表达式来表示，那就是s-t-r-i-n-g这几个字母的连接运算，所以写成正则表达是就是string。大家一定会觉得这个例子很无聊。。那么我们来看下一个例子：标识符。用白话来描述是“由字母开头，后面可以跟零个或多个字母或数字”。先用正则表达式描述“由字母开头”，那就是指，可以是a-z中任意一个字母来开头。这是正则表达式中的并运算：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。如果每个正则表达式都这么写，那真是要疯掉了，所以我们引入方括号语法，写在方括号里就表示这些字符的并运算。比如[abc]就表示a|b|c。而a-z一共26个字母我们也简写成a-z，这样，“由字母开头”就可以翻译成正则表达式[a-z]了。接下来我们翻译第二句“后面可以跟零个或多个字母或数字”这句话中的“零个或多个”可以翻译成克林闭包运算，最后相信大家都可以写出来，就是[a-z0-9]*。最后，前后两句之间是一个连接运算，因此最后描述标识符“语言”的正则表达式就是[a-z][a-z0-9]*。其中的*运算也意味着“标识符”是一种无穷语言，有无数种可能的标识符。本来就是这样，很好理解对吧？

从上面例子可以看出，正则表达式都可以用两种要素和三种基本运算组合出来。但是如果我们要真的拿来描述词法单词的规则，需要一些便于使用的辅助语法，就像上边的方括号语法那样。我们定义一些正则表达式的扩展运算：

方括号表示括号内的字符并运算。[abc]就等于a|b|c
方括号中以^字符开头，表示字符集中，排除方括号中的所有字符之后，所剩字符的并运算。[^ab]就表示除了ab以外所有字符求并。
圆.点表示字符集内所有字符的并。因此 .* 这个表达式就能表示这种字符集所能组成的一切字符串。
X?表示 X|ε 。表示X与空字符串之间可选。
X+表示XX*。这等于限制了X至少要重复1次。

用过正则表达式的同学应该都熟悉以上运算了。其实.NET中的正则表达式还提供更多的扩展语法，但我们这次并不使用.NET的正则库，所以就不列出其余的语法了。

我们把所有能用正则表达式表示的语言称作正则语言。很遗憾，并非所有的语言都是正则语言。比如C#，或者所有编程语言、HTML、XML、JSON等等，都不是正则语言。所以不能用正则表达式定义上述语言的规则。但是，用正则表达式来定义词法分析的规则却是非常合适的。大部分编程语言的词素都可以用一个简单的正则表达式来表达。下面就是上述单词的正则表达式定义。

类型	正则表达式	例子
关键字string	string	string
标识符（变量名）	[a-z][a-z0-9]*	str
等号	=	=
字符串字面常量	"[^"]*"	"hello world"
分号	;	;

我们大家平时熟悉的正则表达式是写成上文这样的字符串形式。但这次我们要自己处理正则表达式，写成字符串显然增加了处理的难度（要解析正则表达式字符串）。所以在VBF.Compilers库的词法分析库中，我引入了一种用对象来表示正则表达式的手法。我定义了一个RegularExpression基类，然后为每一种正则表达式要素或运算编写了一个子类：

其中AlternationExpression就是“并”运算，ConcatenationExpression就是“连接”运算，EmptyExpression当然就表示ε空字符串，KleeneStarExpression表示“克林闭包”运算（你现在可以知道克林闭包也可以叫做克林星——本来就是一星号嘛）和表示单一字符的SymbolExpression。像SymbolExpression里面其实就储存了它所表示的一个字符，而AlternationExpression下面储存了两个RegularExpression实例，用来表示并运算的双方。所以，任何正则表达式都能用RegularExpression的对象树来表示。比如正则表达式[a|b]*就可以表示为：

RegularExpression re = new KleeneStarExpression(
             new AlternationExpression(
             new SymbolExpression(\'a\'), new SymbolExpression(\'b\')));

有点像Linq to XML有木有？虽然它写起来比字符串长了那么一点点（观众：是长好多吧……），但是我们不需要解析字符串就可以获得它的结构，这对下一步进行处理非常有帮助。好吧，我承认全都写这么长也受不了，所以我定义了一些辅助的静态方法和运算符重载。上面的正则表达式可以写成：

var re = (RE.Symbol(\'a\') | RE.Symbol(\'b\')).Many();

其中RE其实是要用using RE=VBF.Compilers.Scanners.RegularExpression;语句来声明的别名。虽然它还是比字符串的正则表达式长一些，但考虑到无需解析字符串带来的方便，就忍了吧。等到后面语法分析学习完了以后我会带大家自己开发正则表达式字符串的解析器。

接下来的问题是，怎么用正则表达式表示的规则来进行词法分析呢？正则表达式利于我们理解单词的规则，但并不能拿来直接解析字符串。为此我们要引入有穷自动机的概念来真正处理输入字符串。敬请期待下一篇。

同时大家别忘了关注VBF项目：https://github.com/Ninputer/VBF 和我的微博：http://weibo.com/ninputer 多谢大家支持！

自己动手开发编译器（三）有穷自动机

上回我们说到用正则表达式来表示词法分析中的单词规则。正则表达式的规则很容易理解，但是正则表达式并不能直接用来解析字符串，我们还要引入一种适合转化为计算机程序的模型。今天我们引入的这种模型就叫做有穷自动机（finite automation，FA）,有时也叫有穷状态机（finite state machine）。有穷自动机首先包含一个有限状态的集合，还包含了从一个状态到另外一个状态的转换。有穷自动机看上去就像是一个有向图，其中状态是图的节点，而状态转换则是图的边。此外这些状态中还必须有一个初始状态和至少一个接受状态。下面的图展示了一个有穷自动机，有根从外边来的箭头指向的状态表示初始状态，有个黑圈的状态是接受状态：

现在我们来看看有穷自动机怎么处理输入的字符串：

一开始，自动机处于初始状态
输入字符串的第一个字符，这时自动机会查询当前状态上与输入字符相匹配的边，并沿这条边转换到下一个状态。
继续输入下一个字符，重复第二步，查询当前状态上的边并进行状态转换
当字符串全部输入后，如果自动机正好处于接受状态上，就说该自动机接受了这一字符串。

刚才我们画的自动机，假如输入的字符串是"hello"（带引号）。一开始状态机处于状态1，输入引号以后就沿引号的边转换到了状态2；接下来输入hello都会沿着a-z这条边回到状态2，最后输入引号，转换到了状态3。由于状态3是接受状态，那么这个自动机就会接受这个字符串。而如果字符串是"abc（不带后面的引号），那么当字符串输入完毕之后自动机会处在状态2，而状态2不是接受状态，所以这个自动机就不接受"abc这个字符串。一个自动机接受的所有字符串组成的集合称作这个自动机的语言。这里语言的概念和上一回我们介绍正则表达式的语言概念是一样，都表示一个有限字符集上的字符串集合。

上面我们画的自动机是一个确定性有穷自动机（DFA），其特点是从每一个状态只能发出一条具有某个符号的边。也就是说不能出现同一个符号出现在同一状态发出的两条边上。但是，还有一种非确定性有穷自动机（NFA），它允许从一个状态发出多条具有相同符号的边，甚至允许发出标有ε（表示空）符号的边，也就是说，NFA可以不输入任何字符就自动沿ε边转换到下一个状态。下图展示了一个非确定性有穷自动机：

非确定性有穷自动机在遇到两条边上有相同的符号，会选择哪一边呢？遇到ε边到底会转移还是不会转移呢？答案是，NFA会自动猜测应该选择哪一条边，而且每次都能猜对。比如说，上面的NFA，假如输入字符串是aa，它就会选择右边这条路径，并且接受这个字符串；假如输入字符是aaa，它就会走左边这条路径，并接受字符串。它绝不会在输入字符是aaa的时候选择右边路径然后做出不接受这一判断。由于我们的计算机并没有这种“猜测”能力，大家可能会对NFA具有这种能力感到奇怪。有些人在刚刚接触这些概念的时候可能会觉得NFA因为具有自动猜测的能力，应该要比DFA更加强大。但事实上是，DFA、NFA和正则表达式是等价的，任何NFA都存在一个与之接受同样语言的DFA，和一个定义相同语言的正则表达式；同理任何正则表达式，也存在一个接受其所定义语言的NFA和一个DFA。这三种模型虽然定义迥然不同，但却表示同样的正则语言。幸运的是，只需要很简单的规则，就能把任何正则表达式转化成NFA，而任何一个NFA又都可以转化为DFA，这样我们就能把正则表达式转化为易于编程的DFA，来真正进行词法分析的工作。（注，也有正则表达式引擎直接模拟NFA的运行来解析字符串，有兴趣的读者可以自行寻找有关的资料。）

现在我们来看怎么把正则表达式转化为NFA。我们上次学到正则表达式有两种基本要素——字符表达式和ε表达式，以及三种基本运算——并、连接和闭包。首先我们来看最基础的ε表达式，它的NFA是这样的：

接下来是字符表达式a，它的NFA是这样：

所有正则表达式都可以转化为一个有一条输入边，以及一个接受状态的的正则表达式，我们先假设一个一般的正则表达式的NFA是这样：

然后我们定义两个正则表达试的并运算，X|Y的NFA为：（实际应用中，常常可以简化掉一部分ε转换边）

两个这正则表达式的连接运算，XY的NFA为：

一个正则表达式的克林闭包运算，Y*的NFA为：

递归运用以上规则，就可以把任何正则表达式转化为NFA。我们来试试看。上次研究了标识符的正则表达式[a-z][a-z0-9]*，运用以上规则，转换成的NFA是：

词法分析时，我们要把所有的单词的正则表达式分别转换成NFA，然后用“并”的关系将所有NFA连接到一起，就成了词法分析所需的最终NFA。

下面我们来看看上述逻辑在VBF.Compilers中是如何实现的。上次我们定义了一个RegularExpression基类和它的五个子类，分别对应于正则表达式的基本要素和基本运算。考虑到将正则表达式转换为NFA是一个相对独立的操作，所以我们采用Visitor模式，定义一个抽象类作为Visitor:

public abstract class RegularExpressionConverter<T>
{
    protected RegularExpressionConverter() { }

    public T Convert(RegularExpression expression)
    {
        if (expression == null)
        {
            return default(T);
        }

        return expression.Accept(this);
    }

    public abstract T ConvertAlternation(AlternationExpression exp);

    public abstract T ConvertSymbol(SymbolExpression exp);

    public abstract T ConvertEmpty(EmptyExpression exp);

    public abstract T ConvertConcatenation(ConcatenationExpression exp);

    public abstract T ConvertAlternationCharSet(AlternationCharSetExpression exp);

    public abstract T ConvertStringLiteral(StringLiteralExpression exp);

    public abstract T ConvertKleeneStar(KleeneStarExpression exp);
}

然后我们给RegularExpression类加上一个Accept抽象方法，让其子类分别实现。比如，KleeneStarExpression类的Accept就可以写成这样：

internal override T Accept<T>(RegularExpressionConverter<T> converter)
{
    return converter.ConvertKleeneStar(this);
}

最后我们实现一个NFAConverter，实现抽象类RegularExpressionConverter<NFAModel>。其中NFAModel是我们自己定义的NFA对象模型，其中定义了状态节点、边等概念。下面就是NFAConverter中翻译克林闭包的规则：

public override NFAModel ConvertKleeneStar(KleeneStarExpression exp)
{
    var innerNFA = Convert(exp.InnerExpression);

    var newTail = new NFAState();
    var entry = new NFAEdge(newTail);

    innerNFA.TailState.AddEmptyEdgeTo(newTail);
    newTail.AddEdge(innerNFA.EntryEdge);

    var kleenStarNFA = new NFAModel();

    kleenStarNFA.AddStates(innerNFA.States);
    kleenStarNFA.AddState(newTail);
    kleenStarNFA.EntryEdge = entry;
    kleenStarNFA.TailState = newTail;

    return kleenStarNFA;
}

代码应当是相当直观的，它就是重复上面画图的逻辑，先将克林闭包内部的表达式转换成NFA，再创建一些辅助的外围状态和相应的状态转换。

有了从正则表达式转换到NFA的算法之后，我们还需要NFA到DFA的转换。这个转换算法称作“子集构造”。我们前面说过NFA遇到同一状态发出带有同一符号的不同的边时，能自动猜测转移到哪一边。而子集构造的思想就是不猜测NFA会转移到哪个状态，而是假设NFA能同时处于所有可能的状态。比如，我们重新考虑前面最开始展示的NFA。一开始，这个NFA的初始状态就包含两个ε转换，我们假设NFA能同时处于所有这种ε转换的目标状态上，也就是说它的初始状态其实是三个状态的集合：

我们称这三个状态为初始状态的ε-闭包（ε-closure）。接下来，如果输入了字符a，那么NFA就可以从当前状态的ε-闭包内任何状态开始，通过字符a的边进行状态转换。这时，我们就得到NFA的下一个状态：

接下来再次输入字符a，我们也可以从当前状态集合出发，找到下一个状态集合：

如果字符串到此为止，这时NFA的状态集合中包含了一个接受状态，因此NFA决定接受字符串“aa”。也就是说，这次没有用到猜测能力，就成功地解析了aa这个字符串。这样我们就了解到，一定存在一个DFA，它的每个状态都是NFA状态的的一个子集。下面我简单转述一下虎书中有关子集构造算法。令edge(s, c)表示从状态s沿着标有字符c的边可以达到的所有NFA状态的集合。对状态集合S，closure(S)是从S中的状态出发，无需接受任何字符，只沿ε边就可以达到的状态组成的集合，可以用迭代法来求出：

接下来我们定义输入一个字符之后的动作规则，从NFA状态集合d中的状态出发，输入符号c，所能达到的NFA的新的状态集合记作DFAedge(d, c)，它定义为

最后，假设构成语言的字符集是Σ，构造出整个DFA的算法是：

以上代码在理解了子集构造的基本原理之后很容易就能够转换成代码。VBF.Compilers中的NFA->DFA转换代码比较长，我就不贴在这里了，有兴趣的可以到github上自行下载。

将正则表达式通过NFA最后转化为DFA之后，如何进行真正的字符串扫描工作就是水到渠成的工作了。我们下一篇将介绍具体的做法，以及针对Unicode字符集的处理方式。下一篇我还会介绍VBF.Compilers.Scanners类库的基本用法。如果大家不想自己实现整套算法，那么下回就可以参考我的文章，用VBF库制造出任意的词法分析器来。所以，敬请期待下一篇！

此外别忘了关注我的VBF项目：https://github.com/Ninputer/VBF 和我的微博：http://weibo.com/ninputer 多谢大家支持！

自己动手开发编译器（四）利用DFA转换表建立扫描器

上回我们介绍了两种有穷自动机模型——确定性有穷自动机DFA和非确定性有穷自动机，以及从正则表达式经过NFA最终转化为DFA的算法。有些同学表示还是难以理解NFA到底怎么转化为DFA。所以本篇开头时我想再多举一个例子，看看NFA转化为DFA之后到底是什么样。首先我们看下面的NFA，它是从一组词法分析所用的正则表达式转换而来的。这个NFA合并了IF、ID、NUM、error这四个单词的NFA。因此，它的四个接受状态分别代表遇到了四种不同的单词。

用上一篇学到的方法，我们需要求出一个DFA，它的每个状态都是NFA状态集合的一个子集。首先我们要定义任何状态的ε-闭包，之所以叫ε-闭包，是因为它对ε转换而言是封闭的，也就是说ε-闭包内任何状态，经过ε转换之后，都还是闭包内的一个状态。接下来，从初始状态ε-闭包开始，我们要计算输入任何一种字符后，NFA所能转换到的下一个状态集合。这一步的公式是：

其中那个U型的符号，表示：对NFA状态集合d中的任何状态s，求出s在遇到符号c之后所能达到的所有状态组成的集合，再把所有这种集合求并集。最后，再对这个集合求出ε-闭包。我很难找出一种更简单的描述方式，简而言之就是要计算出NFA状态集合d，在输入符号c之后，所能达到的一切状态的新集合。而这个集合，就会变成DFA的一个状态，这个状态是从d，沿着一条标有c的边达到的。我们首先求出初始状态的ε-闭包作为DFA的初始状态，然后，我们要反复从当前已知的NFA状态集合出发，计算输入任意字符后所能达到的新状态集合，直到不能再找出新的NFA状态集合为止。这一段算法的确是有一点考验思考能力的，所以建议大家画几个简单的NFA，照着上一篇中的公式比划一下，多思考思考，一定可以理解的。下面我贴出上边NFA转换而成的DFA，让大家对NFA转成的DFA有个感性的认识：

大家可以看出，转换而成的DFA每一个状态都是由若干个原NFA状态组成的集合。而任何状态集合，其中只要有一个是NFA的接受状态，我们就将它作为DFA的接受状态。注意，有些状态中可能包含不止一个NFA接受状态。比如上图接受IF的状态是NFA的状态集合{3,6,7,8}，其中3号是NFA中接受IF的状态，而8号则是NFA中接受ID的的状态。那么为什么我们选择让DFA状态接受IF而不是ID呢，因为IF是关键字，ID是标识符，我们必须让IF的优先级高于ID，不然就无法在词法分析的时候解析出if关键字。也就是说，在设计词法分析其的时候我们要让所有的保留关键字优先级高于ID，这一点就是在DFA接受状态的选取上体现出来的。

一旦完成了NFA->DFA的转换，DFA状态就没有必要保留原来NFA状态集合的信息了，我们完全可以把DFA进一步抽象为一个表，其中表的一行就是DFA的一个状态，而每一列就是一个字符。这是上一篇我们引入的第一个DFA：

将这个DFA写成状态转换表的形式，就成了这样：

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	"
1	2
2	2	2	2	2	2	2	2	2	2	2	2	2	2	2	2	2	2	2	2	2	2	2	2	2	2	2	3
3

这个表可能跟大家想象当中有一点点不一样，我们来观察一下：首先这个表比DFA状态图中多一个状态0，而且这个状态上，无论输入什么字符都转到状态0上。我们称这个状态为停机状态。在实践当中，我们一律使用状态0作为停机状态。停机状态的含义就是，一旦状态机到达这个状态就“死”了，它再也不能离开这个状态。等一下我们再看为什么需要这个停机状态，先来看看状态1。在这个状态上，当输入字符是"（引号）的时候，就会转换到状态2，这跟上面的DFA状态图一致；而如果输入字符是a-z之类的，全部都转到状态0，也就是停机状态。这意味着在状态1，接受这些（a-z）字符是未定义的，会导致DFA死掉。接下来是状态2，这个状态应该和大家的预期是一样的，a-z的字符输入，会回到状态2，而输入引号则会转到状态3。最后是状态3，因为状态3没有发出任何边，所以状态3上任何输入字符都会导致停机。最后我们回过头来考虑为什么需要停机状态，因为我们需要它来判断是否检测到了一个单词。用DFA状态转换表进行词法分析的步骤是：

一开始，让DFA处于状态1（而不是0，切记！）。
输入字符串的一个字符，并且检查表中对应于这个字符的下一个状态。
转换到下一个状态。同时，如果这个状态不是0，用另一个变量记住这个状态。
不断输入字符串进行状态转换，直到当前状态为0（停机状态）。
检查另外一个变量记住的上一个状态，如果上一个状态是接受状态，报报告成功扫描一个单词；如果不是接受状态，报告词法错误。
如果要继续解析，需要将DFA的状态恢复到1（而不是0），再重新开始。

也就是说，我们总要等到DFA运行到停机状态，也就是死了之后才判断是否成功扫锚到一个单词，这是因为我们想要词法分析器进行最长匹配。比如我们解析C#代码：string1 = null; 这句代码中的string1是一个标识符，代表一个变量。如果词法扫描器刚刚扫描到string，就报告发现了“关键字string”，那这里逻辑就不对了。而如果等到DFA状态抓换到停机状态时再判断，就能判断到最长可能的的单词。比如，当词法分析器分析到了string时，它仍然没有停机，于是就输入了下一个字符"1"，这时词法分析的状态就从接受“关键字string”的状态转换到接受“标识符”的状态；然后词法分析器发现下一个字符是空格，而空格接在string1后面并不是任何合法的单词，所以它就会转到停机状态。最后我们判断停机前最后一个状态是接受“标识符”的状态，于是报告成功扫描标识符string1。这样就实现了最长匹配的目的。

在VBF.Compilers.Scanners库中，我采用的是一个二维数组来存储的DFA状态转换表。其中有一个FiniteAutomationEngine.cs中包含了储存DFA转换表，以及进行状态转换操作的任务。最后Scanner类实现了真正的词法分析逻辑。大家如果对上述语言描述的算法有兴趣，可以直接去看这两个类的实现。

接下来我们要考虑一个非常实际的问题。如果词法分析器要支持Unicode字符集（UTF-16）上字符串的解析，那么DFA转换表会非常大。实际上，如果要支持中文的注释、字符串或者标识符，DFA转换表会有4万列以上，最多可以有65536列。这样只要一个状态就会占掉sizeof(int) x 65536= 256KB的内存。像C#这样的语言，DFA可能会多至几百个状态。即使是我们要做的C#超小子集miniSharp，也有140个状态。这样光DFA状态转换表就要占35MB内存。虽然现在计算机动辄就有8G内存，但是CPU的二级或三级缓存通常只有几MB，如果不能将DFA转换表全部放进二级缓存的话，效率必然大大受到影响。我们观察一下上面列出的DFA状态转换表，会发现从a-z这些字符的列都是完全一样的，它们全都在状态1转到状态0；在状态2转换到状态2；在状态3转到状态0。我们称这样转换表的列完全相同的字符称作同一个等价类。如果我们的DFA状态转换表不用字符作为列，而是使用等价类的话，就能大大缩小状态转换表的体积。然后，我们只要用一个字符->等价类的映射表，就能用O(1)的时间复杂度，将任意字符映射到它的等价类。比如，在应用等价类之后，上面展示的DFA可以变成：

等价类表：

转换表：

1
1	2
2	2	3
3

这样一来，只需要有一个一行的等价类表。而因为最多也就只有65536个等价类（每种字符一个等价类），所以这个等价类表可以声明成ushort[65536]，它只会占128K内存。经过压缩之后，miniSharp语言的等价类一共只有57个。所以140个状态只需要不到32KB的内存即可装下，现在它可以完全装载到CPU的二级缓存中了，完美达成目标！

在VBF.Compilers类库中，为了NFA-> DFA算法的高效，甚至在NFA时就计算了等价类表。当然在NFA阶段计算得没有DFA阶段这样精确，所以在转换成DFA之后会再次计算等价类表。这种所谓的双重压缩法，把处理大量Unicode字符集NFA转换所需要的数小时时间减小到了几百毫秒。

接下来，我们就来简单了解一下VBF.Compilers.Scanners库的用法。首先，要写自己的词法分析器，需要引用VBF.Compilers.Common.dll库和

VBF.Compilers.Scanners.dll。其中Common库包含一个储存编译错误的类，和一个重要的类：SourceReader。这个类可以将任何TextReader作为输入，而且还支持在读取的过程中统计当前源代码的行、列。因此词法分析器就依赖于这个类来进行源代码输入。要定义一个词法分析器，需要一个最基础的类——Lexicon类。这个类相当于一个字典，它会保存所有单词的定义，同时在内部进行正则表达式到DFA的转换等工作。下面的代码演示了Lexicon类的用法：

using RE = VBF.Compilers.Scanners.RegularExpression;

…

Lexicon lexicon = new Lexicon();
LexerState lexer = lexicon.DefaultLexer;

Token IF = lexer.DefineToken(RE.Literal("if"));
Token ELSE = lexer.DefineToken(RE.Literal("else"));
Token ID = lexer.DefineToken(RE.Range(\'a\', \'z\').Concat(
    (RE.Range(\'a\', \'z\') | RE.Range(\'0\', \'9\')).Many()));
Token NUM = lexer.DefineToken(RE.Range(\'0\', \'9\').Many1());
Token WHITESPACE = lexer.DefineToken(RE.Symbol(\' \').Many());

ScannerInfo info = lexicon.CreateScannerInfo();

我们来逐行解读一下这些代码。首先Lexicon类直接用new就可以创建出来，无需任何参数。接下来是这样代码：

LexerState lexer = lexicon.DefaultLexer;

这行代码调用了lexicon的DefaultLexer属性，返回了一个LexerState对象，它代表一个词法分析器的整体状态。后面我们就要用这个对象来定义单词的正则表达式。默认情况下，DefaultLexer是唯一的LexerState，而且不用创建新的LexerState对象。但是假如我们需要让某些词素在不同环境下展示为不同的类型，就可以定义新的LexerState。比如说“get”这个词素通常应该是一个标识符，而在定义属性的上下文环境下，它就变成了一个关键字。LexerState允许派生子状态来支持这种场景。但目前我们先暂考虑只有DefaultLexer的情况。

在拿到DefaultLexer之后即可使用DefineToken方法定义单词。DefineToken接受一个RegularExpression对象作为参数。RegularExpression类（在代码中简写为RE）的静态方法可以表示正则表达式的基本运算和几种常用的扩展运算。下面的表列出了RegularExpression常见用法：

RegularExpression类的用法	例子	表示的正则表达式
\| 运算符 Union方法	x \| y x.Union(y)	x\|y
>> 运算符 Concat方法	ｘ >> y ｘ.Concat(y)	xy
Many方法	x.Many()	x*
Many1方法	x.Many1()	x+
Optional方法	x.Optional()	x?
Range静态方法	RE.Range(\'0\', \'9\')	[0-9]
CharSet静态方法	RE.CharSet("abc")	[abc] （并运算）
Literal静态方法	RE.Literal("abc")	abc （连接运算）
Repeat方法	x.Repeat(5)	xxxxx
CharsOf静态方法	RE.CharsOf(c => c == \'a\')	[a] （根据lambda表达式创建一组字符的并运算集合）
Symbol静态方法	RE.Symbol(\'a\')	a

大家可以看上面的代码，结合这个表来学习RegularExpression的各种用法。注意，定义Token的先后顺序决定了各个单词的优先级，排在前面的更加优先。为了确保保留关键字的优先级，所有关键字必须在标识符ID之前定义。在所有的单词都定义完毕之后，我们调用Lexicon的CreateScannerInfo方法来得到一个ScannerInfo对象。这个对象就包含了已经转换好的DFA和各种词法分析器运转所需要的参数。下一步，我们就可以用ScannerInfo对象创建出Scanner对象，请看下面的代码：

Scanner scanner = new Scanner(info);

string source = "asdf04a 1107 else";
StringReader sr = new StringReader(source);

scanner.SetSource(new SourceReader(sr));
scanner.SetSkipTokens(WHITESPACE.Index);

Lexeme l1 = scanner.Read();
Console.WriteLine(l1.TokenIndex); //等于ID.Index
Console.WriteLine(l1.Value); //等于 asdf04a

Lexeme l2 = scanner.Read();
Console.WriteLine(l2.TokenIndex); //等于NUM.Index
Console.WriteLine(l2.Value); //等于 1107

Lexeme l3 = scanner.Read();
Console.WriteLine(l3.TokenIndex); //等于ELSE.Index
Console.WriteLine(l3.Value); //等于 else

Lexeme l4 = scanner.Read();
Console.WriteLine(l4.TokenIndex); //等于info.EndOfStreamTokenIndex
Console.WriteLine(l4.Value); //等于 null

创建Scanner对象时，需要传入上一步生成的ScannerInfo对象，接下来可以指定输入的源代码。这里我们用StringReader来读取一段字符串源代码。注意Scanner的SetSkipTokens方法，可以设定词法扫描器自动跳过的单词。比如我们不希望词法分析器返回空白字符的词素，就设定跳过WHITESPACE单词。在操作Scanner类的时候，所有与Token相关的操作都是通过Token.Index（一个整数）来完成的，因为Scanner内部仅仅保存了Token在Lexicon内部的索引值，这样可以减小内存使用并且提高效率。

一切准备就绪之后就可以调用scanner.Read()方法来进行词法分析了！每次调用scanner.Read()会返回下一个词素（Lexeme对象），从Lexeme的属性中我们可以拿到该词素对应的单词类型（仍然是以Token.Index整数形式），词素的字符串表示（Value属性）以及词素在源代码中位置等丰富的信息。当扫描到文件或字符串尾部时，scanner.Read()会返回一个特殊的词素表示End Of Stream。这个特殊词素的TokenIndex可以从ScannerInfo对象查询到（每个ScannerInfo的EndOfStreamTokenIndex会不一样）。大家可以试着运行一下上述代码，并且修改自己的词法定义或源代码，来观察Scanner类的各种行为。另外VBF.Compilers.Scanner库还提供了两种具有特殊能力的Scanner——分别是PeekableScanner和ForkableScanner，未来的篇章中我们会用到它们的特殊能力。

到本篇为止，我们已经完整地讨论了词法分析所需的各种技术和VBF的实现。下一篇我们将讨论miniSharp语言的词法定义，并真正实现miniSharp的词法分析器。届时大家可以学到怎么创建支持中文的标识符和注释的正则表达式。敬请期待！

此外别忘了关注我的VBF项目：https://github.com/Ninputer/VBF 和我的微博：http://weibo.com/ninputer 多谢大家支持！

自己动手开发编译器（五）miniSharp语言的词法分析器

多谢各位的一直以来的支持，我们今天总算走到了实践的一步。今天我们要用VBF.Compilers的词法分析库来开发一个小型语言——miniSharp的词法分析。miniSharp是C#语言的子集，miniSharp程序的语义就等于把它当做C#的语义。但是miniSharp只支持很少的语言特性，以降低制作编译器的难度。简单来说miniSharp有如下特征：

只有一个源文件，不能引用其他dll（甚至不能引用.NET的类库）。
没有命名空间。
第一个类必须是静态类，而且里面只能定义一个静态方法Main作为程序入口。
只能定义类，没有枚举、结构体、接口、委托等。
类的成员只有私有的字段和共有的非静态方法两种。不支持虚方法。
方法必须有返回值，除了Main方法之外。
支持的类型只有int、bool、int[]和自定义的类。不支持其他类型。
仅支持一个库函数System.Console.WriteLine，只支持参数是int的用法。
只支持if-else语句、while语句、赋值语句、变量声明语句和调用WriteLine语句。
只支持+、-、*、/、>、<、==、&&、||和!运算符
每个方法只能有一个return语句，必须是方法最后一条语句。
其他C#特性皆不支持。

大家肯定觉得这个语言“阉割”得实在太厉害了，我感兴趣的泛型、Lambda表达式、Linq啥的统统都不支持，还写个什么劲呀。但是我劝告各位不要一口吃个胖子。如果写大型语言，会耗费很大的经历在语法分析、语义分析这两步上，甚至可能会遇到困扰很久的问题，导致我们不能很快地体验编译器后端的技术。所以咱们先从简单的语言开始，一步一步来。基本原理都是一样的，等大家熟悉之后自然就可以自己往里面加入任何想加的特性。注：miniSharp设计参考了虎书Java版中的miniJava语言。

今天我们首先来看miniSharp的词法分析。miniSharp语言的单词根据优先级和不同种类可以分成以下五类：

关键字
标识符
整型数字常量
各种标点符号
空白符、换行符和注释

关键字大家都好理解。标识符是有必要仔细考虑的单词，因为我们希望miniSharp像C#一样支持用中文做变量名或函数名，所以肯定不能使用“下划线或字母开头，后面跟下划线、字母或数字”这样的定义。参考C#语言规范，我们要用Unicode字符分类来定义标识符。后面整型、标点符号什么的无需多说，最后我们要讨论一下空白符、换行符和注释的词法规则。

先从简单的开始，我们要为miniSharp中每一种关键字创建一个单词类型。这些关键字都不能用作标识符，所以都是保留字。所有关键字的正则表达式都是一串字符的连接运算，所以我们直接用RegularExpression的Literal方法来定义：

var lex = lexicon.DefaultLexer;

//keywords
K_CLASS = lex.DefineToken(RE.Literal("class"));
K_PUBLIC = lex.DefineToken(RE.Literal("public"));
K_STATIC = lex.DefineToken(RE.Literal("static"));
K_VOID = lex.DefineToken(RE.Literal("void"));
K_MAIN = lex.DefineToken(RE.Literal("Main"));
K_STRING = lex.DefineToken(RE.Literal("string"));
K_RETURN = lex.DefineToken(RE.Literal("return"));
K_INT = lex.DefineToken(RE.Literal("int"));
K_BOOL = lex.DefineToken(RE.Literal("bool"));
K_IF = lex.DefineToken(RE.Literal("if"));
K_ELSE = lex.DefineToken(RE.Literal("else"));
K_WHILE = lex.DefineToken(RE.Literal("while"));
K_SYSTEM = lex.DefineToken(RE.Literal("System"));
K_CONSOLE = lex.DefineToken(RE.Literal("Console"));
K_WRITELINE = lex.DefineToken(RE.Literal("WriteLine"));
K_LENGTH = lex.DefineToken(RE.Literal("Length"));
K_TRUE = lex.DefineToken(RE.Literal("true"));
K_FALSE = lex.DefineToken(RE.Literal("false"));
K_THIS = lex.DefineToken(RE.Literal("this"));
K_NEW = lex.DefineToken(RE.Literal("new"));

其中的lexicon是我们上一回介绍的Lexicon类创建的实例。

接下来我们重点来看标识符的词法。我们不支持C#中@开头的标识符，所以只考虑一种情况。C# Spec规定标识符开头字符必须是一个“字母类”字符或者下划线“_”字符。其中“字母类”并非只是大小写字符，而是Unicode分类中的Lu、Ll、Lt、Lm、Lo、Nl这些类别的字符。含义分别如下：

Lu表示大写字母，包含所有语言中的大写字母。
Ll表示小写字母，包含所有语言中的小写字母。
Lt表示所有词首大写字母（titlecase）。
Lm表示所有修饰字母（modifier）。
Lo表示其他字母，如中文、日文的字符。
Nl表示数字，但不是十进制数字，而是字母表示的。比如罗马数字。

标识符第二个字符开始，允许“字母类”字符和下划线以外，还允许以下类型的字符：

组合类字符，Unicode分类Mn和Mc
十进制数字，Unicode分类Nd
连接类字符，Unicode分类Pc
格式类字符，Unicode分类Cf

用VBF.Compilers.Scanners类库时，可以使用RegularExpression.CharsOf方法，借助Lambda表达式来生成Unicode字符的并集。目前我的设计处理这一块不是十分高效，所以miniSharp的词法就稍微简化一点，允许以字母类的字符或下划线开头，然后零个或多个字母类字符、下划线或数字，也即不支持上述定义中组合类、连接类和格式类字符。定义标识符的正则表达式写法如下：

var lettersCategories = new[] 
{ 
    UnicodeCategory.LetterNumber,
    UnicodeCategory.LowercaseLetter,
    UnicodeCategory.ModifierLetter,
    UnicodeCategory.OtherLetter,
    UnicodeCategory.TitlecaseLetter,
    UnicodeCategory.UppercaseLetter
};

var RE_IdChar = RE.CharsOf(c => lettersCategories.Contains(Char.GetUnicodeCategory(c))) | RE.Symbol(\'_\');

ID = lex.DefineToken(RE_IdChar >>
    (RE_IdChar | RE.Range(\'0\', \'9\')).Many(), "identifier");

大家可以看到我用了.NET类库中的Char.GetUnicodeCategory方法来判断Unicode分类。将来的VBF类库中可能会提供Unicode分类的直接支持。接下来是整型常量和标点符号，没有啥好说的，直接看代码：

INTEGER_LITERAL = lex.DefineToken(RE.Range(\'0\', \'9\').Many1(), "integer literal");

//symbols

LOGICAL_AND = lex.DefineToken(RE.Literal("&&"));
LOGICAL_OR = lex.DefineToken(RE.Literal("||"));
LOGICAL_NOT = lex.DefineToken(RE.Symbol(\'!\'));
LESS = lex.DefineToken(RE.Symbol(\'<\'));
GREATER = lex.DefineToken(RE.Symbol(\'>\'));
EQUAL = lex.DefineToken(RE.Literal("=="));
ASSIGN = lex.DefineToken(RE.Symbol(\'=\'));
PLUS = lex.DefineToken(RE.Symbol(\'+\'));
MINUS = lex.DefineToken(RE.Symbol(\'-\'));
ASTERISK = lex.DefineToken(RE.Symbol(\'*\'));
SLASH = lex.DefineToken(RE.Symbol(\'/\'));
LEFT_PH = lex.DefineToken(RE.Symbol(\'(\'));
RIGHT_PH = lex.DefineToken(RE.Symbol(\')\'));
LEFT_BK = lex.DefineToken(RE.Symbol(\'[\'));
RIGHT_BK = lex.DefineToken(RE.Symbol(\']\'));
LEFT_BR = lex.DefineToken(RE.Symbol(\'{\'));
RIGHT_BR = lex.DefineToken(RE.Symbol(\'}\'));
COMMA = lex.DefineToken(RE.Symbol(\',\'));
COLON = lex.DefineToken(RE.Symbol(\':\'));
SEMICOLON = lex.DefineToken(RE.Symbol(\';\'));
DOT = lex.DefineToken(RE.Symbol(\'.\'));

稍微说明一点，整型常量和上面的标识符的词法，在调用lex.DefineToken时都多传了一个参数。这个参数是可选的描述信息，如果不传会直接使用正则表达式的字符串形式。而标识符的正则表达式有4万多个字符那么长而且没有可读性，所以加一个额外字符串描述一下。它将来会被用于生成编译错误信息。

最后我们来写空白符、换行符和注释的正则表达式。这三个是完全按照C# spec的规范编写的。其中注释包含了两种：//开头直到换行的注释已经/*开头直到*/的多行注释。大家可以学习一下它们的正则表达式怎么写：

var RE_SpaceChar = RE.CharsOf(c => Char.GetUnicodeCategory(c) == UnicodeCategory.SpaceSeparator);

WHITESPACE = lex.DefineToken(RE_SpaceChar | RE.CharSet("\u0009\u000B\u000C"));

LINE_BREAKER = lex.DefineToken(
    RE.CharSet("\u000D\u000A\u0085\u2028\u2029") |
    RE.Literal("\r\n")
);

var RE_InputChar = RE.CharsOf(c => !"\u000D\u000A\u0085\u2028\u2029".Contains(c));
var RE_NotSlashOrAsterisk = RE.CharsOf(c => !"/*".Contains(c));
var RE_DelimitedCommentSection = RE.Symbol(\'/\') | (RE.Symbol(\'*\').Many() >> RE_NotSlashOrAsterisk);

COMMENT = lex.DefineToken(
    (RE.Literal("//") >> RE_InputChar.Many()) |
    (RE.Literal("/*") >> RE_DelimitedCommentSection.Many() >> RE.Symbol(\'*\').Many1() >> RE.Symbol(\'/\'))
);

最后还有一点后续的代码，从Lexicon对象生成ScannerInfo，再生成Scanner：

ScannerInfo info = lexicon.CreateScannerInfo();
Scanner scanner = new Scanner(info);

string source = "//任意miniSharp源代码";
StringReader sr = new StringReader(source);

scanner.SetSource(new SourceReader(sr));
scanner.SetSkipTokens(WHITESPACE.Index, LINE_BREAKER.Index, COMMENT.Index);

这样就完成了！我们创建了一个完整的miniSharp词法分析器。现在它就能分析所有miniSharp源代码了。注意我们设定了该词法分析器忽略所有空白符、换行以及注释，是为了后面语法分析简便而考虑的。各位读者可以自己试着任意扩展这个词法分析器，比如增加字符串常量的词法、更多关键字和运算符甚至前所未有的新词法。祝各位实践愉快！下一篇开始我们要进入另一个重要的环节——语法分析部分，敬请期待。

此外别忘了关注我的VBF项目：https://github.com/Ninputer/VBF 和我的微博：http://weibo.com/ninputer 多谢大家支持！

自己动手开发编译器特别篇——用词法分析器解决背诵圣经问题

这几天比较忙，让大家久等了。但是我语法分析篇还需要一些准备，所以今天带来一个特别娱乐项目。其实也正好想多举一些例子，介绍VBF.Compilers.Scanner库的使用方法。今天的问题来自于一道腾讯的PHP面试题，原题如下：

我们碰到了大麻烦，一个新来的传教士惹恼了上帝，上帝很愤怒，要求我们把圣经背熟，直至他说哪个单词，我们就要飞快的回答出这个单词在第几行第几个单词位置。听说你是个优秀的程序员，那么髟助我们完成这个不可能的任务吧。

要求如下：

1）/myworks/example/bbe.txt，98版本英文圣经一本

2）输入部分要求如下：php ./example.php [单词]

3）输出部分如下：[单词] 1,2 2,4 5,6表示：此单词在1行2列（第二个单词），2行4列...

说明：

1）此文本4MB之巨...

2）单词的含义：由英文字母（大小写），数字（0-9）组成的串

3）提供给你的机器OS为ubuntu 9.10，内存只有1G，而且，很不幸的，其中700M用来做了别的

4）上机考试不允许上网，但我装了man文档以及读取CHM以及PDF的阅读器，在电脑的桌面的CHM文件夹中，有相应的PHP参考手册

5）算法复杂度要求不能大于O（N^2）（就是N的平方）

6）什么？PHP低效且用起来不顺手，好的，你可以用别的语言来实现。但注意：提供给你的机器上只有python 2.4/perl 5.8/gcc[g++] 4.1

原题是要求使用PHP的，我们只是娱乐，不是真面试，当然就无视各种规定了。这道题不必使用词法分析的原理，可以写出很快的算法。但是用词法分析库来实现也是个不错的注意，因为DFA词法分析是O(N)的算法而且实际执行起来效率相当不错。下面我们就用VBF.Compilers.Scanner库来解决这道题：

Imports VBF.Compilers.Scanners
Imports VBF.Compilers.Scanners.RegularExpression
Imports System.IO

Module Program

    Sub Main(args As String())
        Dim findword = args(0)

        Dim bibleLexicon As New Lexicon()
        Dim lex = bibleLexicon.DefaultLexer

        \'定义要寻找单词的词法
         Dim TARGET = lex.DefineToken(Literal(findword))
        \'定义一般单词的词法
         Dim WORD = lex.DefineToken((Range("0"c, "9"c) Or
                                    Range("a"c, "z"c) Or
                                    Range("A"c, "Z"c)).Many1)
        \'定义换行
         Dim LF = lex.DefineToken(Symbol(vbLf) Or Literal(vbCrLf))
        \'定义其他所有符号均忽略
         Dim OTHER = lex.DefineToken(Range(ChrW(0), ChrW(255)))

        Dim bibleScanner As New PeekableScanner(bibleLexicon.CreateScannerInfo())
        bibleScanner.SetSkipTokens(OTHER.Index)

        Using sr As New StreamReader("bible.txt")
            Dim source As New SourceReader(sr)
            bibleScanner.SetSource(source)

            Dim scannerWatch As New Stopwatch

            Dim lines = 1, columns = 1, totalwords = 0, targetwords = 0
            scannerWatch.Start()
            Do While bibleScanner.Peek() <> bibleScanner.ScannerInfo.EndOfStreamTokenIndex
                Dim x As Lexeme = bibleScanner.Read()

                Select Case x.TokenIndex
                    Case TARGET.Index
                        Console.WriteLine("第{0}行,第{1}列", lines, columns, x.Value)
                        columns += 1
                        targetwords += 1
                        totalwords += 1
                    Case WORD.Index
                        columns += 1
                        totalwords += 1
                    Case LF.Index
                        lines += 1
                        columns = 1
                End Select
            Loop
            scannerWatch.Stop()

            Console.WriteLine("总单词数: " & totalwords)
            Console.WriteLine("目标单词出现次数: " & targetwords)
            Console.WriteLine("消耗时间: " & scannerWatch.ElapsedMilliseconds)
        End Using
    End Sub

End Module

这就是完整的代码。为了统计是第几个单词，我们按照题目的规定，定义了一般单词的词法，目标单词的词法，并且忽略所有其他字符（设定为SkipTokens）。分析过程就是不断读取下一个单词，直到文件的末尾。注意，这次我展示的是具有超前查看功能的PeekableScanner类，它可以超前查看任意多个单词，其实也可以用普通的Scanner而且性能更好。现在大家可以试试圣经中出现了什么单词，比如我们试一下apple：

第5769行,第29列
第14112行,第8列
第16578行,第14列
第17558行,第8列
第17646行,第25列
第20351行,第34列
第22304行,第23列
第22908行,第31列

可见我手里这本圣经出现了8次apple（我特意看了前面，亚当和夏娃吃的是fruit，不是apple……）。如果搜microsoft的话发现圣经中并没有出现，怪不得苹果最近这么风光……

源代码和圣经文件可以在这里下载：BibleFinder.7z

另外有不少同学问虎书是什么书，这里有龙书、虎书和鲸书的介绍：http://unistd.blog.51cto.com/1126453/260372。下一篇开始我们正式进入语法分析部分。希望大家继续关注我的VBF项目：https://github.com/Ninputer/VBF 和我的微博：http://weibo.com/ninputer 多谢大家支持！

自己动手开发编译器（六）上下文无关语言和文法

上回我们已经学习了语法分析第一阶段——词法分析的原理和工具，介绍了正则表达式、正则语言和DFA等工具。今次我们要开始涉及编译器前端最重要的阶段——语法分析。简单而言，这一步就要完整地分析整个编程语言的语法结构。上回说到词法分析的结果是将输入的字符串分解成一个个的单词流，也就是诸如关键字、标识符这样有特定意义的单词。一种完整的编程语言，必须在此基础上定义出各种声明、语句和表达式的语法规则。观察我们所熟悉的编程语言，其语法大都有某种递归的性质。例如四则运算与括号的表达式，其每个运算符的两边，都可以是任意的表达式。比如1+a是表达式，(1+a)*(2 – c)也是表达式，((a+b) + c) * (d – e)也是表达式。再比如if语句，其if的块和else的块中还可以再嵌套if语句。我们在词法分析中引入的正则表达式和正则语言无法描述这种结构，如果用DFA来解释，DFA只有有限个状态，它没有办法追溯这种无限递归。所以，编程语言的表达式，并不是正则语言。我们要引入一种表现能力更强的语言——上下文无关语言。

要介绍上下文无关语言，我们先来了解一下定义上下文无关文法的工具——产生式的写法。我们还是使用编程语言的表达式作为例子，但这次我们假设表达式只有三种——单个表示变量名标识符、括号括起来的表达式和两个表达式相加。比如a是一个变量表达式，a+b是两个变量表达式相加的表达式，(a+b)是一个括号表达式。我们用符号E来表示一个表达式，那么这三种表达式分别可以定义为：

E → id

E → E + E

E → ( E )

这种形式的定义就叫做产生式。出现在→左侧符号E称作非终结符（nonterminal symbol），代表可以继续产生新符号的“文法变量”。符号→表示非终结符可以“产生”的东西。而上述产生式中的蓝色id、+、（等符号，是具有固定意义的单词，它们不再会产生新的东西，称作终结符（terminal symbol）。注意，非终结符可以出现在产生式的右侧，这就是具有递归性质文法的来源。产生式经过一系列的推导，就能够生成各种完全由终结符组成的句子。比如，我们演示一下表达式(a + b) + c的推导过程：

E => E + E => (E) + E => (E + E) + E => (a + E) + E => (a + b) + E => (a + b) + c

推导过程中的=>代表将当前句型中的一个非终结符替换成产生式右侧的内容。以上推导过程中，我们每次都将句型中最左边一个非终结符展开，所以这种推导称为最左推导。当然也有最右推导，不同之处就算是每次将句型中最右边的非终结符展开：

E => E + E => E + c => (E) + c => (E + E) + c => (E + b) + c => (a + b) + c

可见，同一个结果可以具有多种不同的推导过程。使用最左推导时，句型的左侧逐渐变得只有终结符；而最右推导正好相反，推导过程中句型的右侧逐渐变得只有终结符，最终结果都是整个句子变为终结符。所有符合文法定义的句子，都可以用文法的产生式推导出来。

我们语法分析的目的是解析输入的单词流(a + b) + c，得到它的语法分析树。先来看看语法分析树是什么样的。还是以(a + b) + c为例，语法分析树是这样的：

语法分析树的每一个节点都是一个非终结符或者终结符，其中终结符都是树的叶子结点（没有子节点），而非终结符都是有子节点的。一旦我们得到了语法分析树，就可以很容易地进行后续的语义分析，比如这个表达式的语义是“先将a和b代表的变量相加，再把所得的结果与c代表的变量相加”。那么语法分析树是怎么得到的呢，其实刚才的产生式推导过程，就可以顺便建立语法分析树，只要在展开非终结符的同时，在语法分析树中相应的节点下加入非终结展开的结果即可生成。下面我们用动画演示上述产生式通过最左推导和最右推导产生(a + b) + c语法分析树的过程：

最左推导	最右推导
[转]装配脑袋：自己动手开发编译器	[转]装配脑袋：自己动手开发编译器

我们可以看到最左推导和最右推导的语法分析树是一样的，这证明用相同的文法解析同样的输入也至少存在两种不同的分析方法。后续篇章介绍的递归下降法就是一种最左推导的分析方法，而另一类非常流行的LR分析器则是基于最右推导的分析方法。目前流行的编译器开发方式是在语法分析阶段构造一棵真正的语法分析树，然后再通过遍历语法树的方法进行后续的分析，所以最左推导和最右推导的过程对我们来讲区别不大。

我们刚才举的例子中，表达式(a + b) + c只能有一种语法分析树。但另外一些语法分析的输入，可能存在多种语法分析树，这称为歧义。刚才的文法其实就是有歧义的（在哪里？请大家思考一下），但为了更清楚地表达歧义的危害，我们再举一个新的例子，它在前面例子中增加了乘法：

E → id

E → E + E

E → E * E

E → ( E )

如果用上述产生式推导出表达式a * b + c，就有两种可能的最左推导：

最左推导1：E => E + E => E * E + E => a * E + E => a * b + E => a * b + c

最左推导2：E => E * E => a * E => a * E + E => a * b + E => a * b + c

这两种推导的语法树是不一样的：

推导1	推导2
[转]装配脑袋：自己动手开发编译器	[转]装配脑袋：自己动手开发编译器

我们刚才讨论了，语法分析树将用于下一步的语义分析。而在语义分析中，上述两个语法树的不同主要体现在运算符的优先级上。如果按照推导1的语法树，应该先将a和b相乘，再加上c；而如果按照推导2的语法树，则应该先把b和c相加，再和a相乘。很明显，这两种语义的计算结果是可以不一样的。我们不想编程语言中的同一种表达式有两种语义，所以有歧义的文法是不适合用在语法分析的。实践中应该使用没有歧义的文法来确保同一段程序仅存在唯一一种语法分析树。比如我们可以修改一下上述文法的产生式，让运算符具有左结合的特性，并让乘法一开始就有高于加法的优先级：

F → id

F → ( E )

T → T * F

T → F

E → E + T

E → T

修改文法之后，*号的两侧，不允许直接出现带+号的表达式，而只能出现带括号的表达式和变量名；同时，连续的加法或乘法必须从左侧开始运算。这就限制了推导可能进行的方式。在新文法下表达式a * b + c就只存在一种语法分析树了：

我们最后用在miniSharp的文法就和这一个非常类似。在实践当中，我们通常需要仔细观察和思考所用的文法是否具有歧义。如果有一些文法拿不定主意，我建议大家去参考C# spec，里面对C#的文法进行极其详细的定义，我相信大家看过Spec之后会更加了解一门现代的编程语言的文法。我也将在后续篇章中介绍一些常见语法结构的设计方法。

在本篇的最后，我想再多介绍一点点上下文无关语言。有些同学可能从刚才开始就想问为何这种语言和文法叫做“上下文无关”呢？其实这里的“上下文无关”是指文法中的产生式都可以无条件展开为箭头右侧的内容。另外存在一种上下文相关文法，它的产生式都需要在一定条件下才能展开。上下文相关语言要比上下文无关文法复杂得多，而其没有一种通用的方法可以有效地解析上下文相关语言，因此它也不会用在编程语言的设计当中。同学们也许已经意识到，即使是上下文无关文法和语言，也要比正则表达式和正则语言复杂得多。在此我没有办法详细地描述上下文无关语言的性质，但是我可以给感兴趣的同学稍微科普一下。就像正则表达式存在一种等价的计算模型——有穷自动机——可以用来解析正则语言一样，上下文无关文法也存在一种等价的计算模型——下推自动机（Put-Down Automation, PDA）。下推自动机除了一组有限的状态和状态转换以外，还带有一个无限容量的栈。和有穷自动机不同，下推自动机的状态并不仅根据输入字符和当前状态来进行转移，还要根据栈顶的字符；而且下推自动机还必须决定何时向栈中压入或弹出字符。和有穷自动机类似，下推自动机也存在非确定性下推自动机（NPDA）和确定性下推自动机（DPDA）两种。这两种下推自动机是不等价的。其中非确定性下推自动机对应于整个上下文无关语言，而确定性下推自动机则对应于上下文无关语言的一个真子集。NPDA所具有的“猜测”能力要比NFA强大得多，以至于我们无法很容易地用计算机来模拟。我们只能够模拟DPDA来进行解析。所幸的是，几乎所有编程语言的文法，都是能用一个DPDA所接受的。我们在接下来的篇章中引入的语法分析机制，有些甚至还达不到DPDA的能力，也就是说我们只能处理上下文无关文法中的一小部分。但即使是这一小部分，也足够将C#这样的语法描述出来了。

下一篇中我们将介绍递归下降语法分析器的实现方法。希望大家继续关注我的VBF项目：https://github.com/Ninputer/VBF 和我的微博：http://weibo.com/ninputer 多谢大家支持！

自己动手开发编译器（七）递归下降的语法分析器

上回我们说到语法分析使用的上下文无关语言，以及描述上下文无关文法的产生式、产生式推导和语法分析树等概念。今天我们就来讨论实际编写语法分析器的方法。今天介绍的这种方法叫做递归下降（recursive descent）法，这是一种适合手写语法编译器的方法，且非常简单。递归下降法对语言所用的文法有一些限制，但递归下降是现阶段主流的语法分析方法，因为它可以由开发人员高度控制，在提供错误信息方面也很有优势。就连微软C#官方的编译器也是手写而成的递归下降语法分析器。

使用递归下降法编写语法分析器无需任何类库，编写简单的分析器时甚至连前面学习的词法分析库都无需使用。我们来看一个例子：现在有一种表示二叉树的字符串表达式，它的文法是：

N → a ( N, N )

N → ε

其中终结符a表示任意一个英文字母，ε表示空。这个文法的含义是，二叉树的节点要么是空，要么是一个字母开头，并带有一对括号，括号中逗号左边是这个节点的左儿子，逗号右边是这个节点的右儿子。例如字符串A(B(,C(,)),D(,))就表示这样一棵二叉树：

注意，文法规定节点即使没有儿子（儿子是空），括号和逗号也是不可省略的，所以只有一个节点的话也要写成A(,)。现在我们要写一个解析器，输入这种字符串，然后在内存中建立起这棵二叉树。其中内存中的二叉树是用下面这样的类来表示的：

class Node
{
    public Node LeftChild { get; private set; }
    public Node RightChild { get; private set; }
    public char Label { get; private set; }

    public Node(char label, Node left, Node right)
    {
        Label = label;
        LeftChild = left;
        RightChild = right;
    }
}

这是一道微软面试题，曾经难倒了不少参加面试的候选人。不知在座各位是否对写出这段程序有信心呢？不少参选者想到了要用栈，或者用递归，去寻找逗号的位置将字符串拆解开来等等方法。但是若是使用递归下降法，这个程序写起来非常容易。我们来看看编写递归下降语法分析器的一般步骤：

使用一个索引来记录当前扫描的位置。通常将它做成一个整数字段。
为每个非终结符编写一个方法。
如果一个非终结符有超过一个的产生式，则在这个方法中对采用哪个产生式进行分支预测。
处理单一产生式时，遇到正确终结符则将第一步创建的扫描索引位置向前移动；如遇到非终结符则调用第二步中创建的相应方法。
如果需要产生解析的结果（比如本例中的二叉树），在方法返回之前将它构造出来。

我们马上来试验一下。首先建立一个类，然后存放一个索引变量来保存当前扫描位置。然后要为每一个非终结符创建一个方法，我们的文法中只有一个非终结符N，所以只需创建一个方法：

class BinaryTreeParser
{
    private string m_inputString;
    private int m_index;

    //初始化输入字符串和索引的构造函数，略

    Node ParseNode()
    {
        
    }
}

回到刚才的产生式，我们看到非终结符N有两个产生式，所以在ParseNode方法的一开始我们必须做出分支预测。分支预测的方法是超前查看（look ahead）。就是说我们先“偷窥”当前位置前方的字符，然后判断应该用哪个产生式继续分析。非终结符N的两个产生式其中一个会产生a(N, N)这个的结构，而另一个则直接产生空字符串。那现在知道，起码有一种可能就是会遇到一个字母，这时候应该采用N → a(N, N)这个产生式继续分析。那么什么时候应该采用N → ε进行分析呢？我们观察产生式右侧所有出现N的地方，倘若N是空字符串，那么N后面的字符就会直接出现，也就是逗号和右括号。于是这就是我们的分支预测：

如果超前查看遇到英文字母，预测分支N → a(N, N)
如果超前查看遇到逗号、右括号预测分支N → ε

转化成代码就是这样：

Node ParseNode()
{
    int lookAheadIndex = m_index;

    char lookAheadChar = m_inputString[lookAheadIndex];

    if (Char.IsLetter(lookAheadChar))
    {
        //采用N → a(N, N)继续分析
    }
    else if (lookAheadChar == \',\' || lookAheadChar == \')\' )
    {
        //采用N → ε继续分析
    }
    else
    {
        throw new Exception("语法错误");
    }
}

接下来我们分别来看两个分支怎么处理。先来看N → ε，这种情况下非终结符是个空字符串，所以我们不需要移动当前索引，直接返回null表示空节点。再来看N → a(N, N) 分支，倘若输入的字符串没有任何语法错误，那就应该依次遇到字母、左括号、N、逗号、N右括号。根据上面的规则，凡是遇到终结符，就移动当前索引，直接向前扫描；而要是遇到非终结符，就递归调用相应节点的方法。所以（不考虑语法错误）的完整方法代码如下：

Node ParseNode()
{
    int lookAheadIndex = m_index;

    char lookAheadChar = m_inputString[lookAheadIndex];

    if (Char.IsLetter(lookAheadChar))
    {
        //采用N → a(N, N)继续分析
        char label = m_inputString[m_index++]; //解析字母
        m_index++; //解析左括号，因为不需要使用它的值，所以直接跳过

        Node left = ParseNode(); //非终结符N，递归调用

        m_index++; //解析逗号，跳过

        Node right = ParseNode(); //非终结符N，递归调用

        m_index++; //解析右括号，跳过

        return new Node(label, left, right);
    }
    else if (lookAheadChar == \',\' || lookAheadChar == \')\')
    {
        //采用N → ε继续分析
        //无需消耗输入字符，直接返回null
        return null;
    }
    else
    {
        throw new Exception("语法错误");
    }
}

因为存在语法约束，所以一旦我们完成了分支预测，就能清楚地知道下一个字符或非终结符一定是什么，无需再进行任何判断（除非要进行语法错误检查）。因此根本就不需要寻找逗号在什么位置，我们解析到逗号时，逗号一定就在那，这种感觉是不是很棒？只需要寥寥几行代码就已经写出了一个完整的Parser。大家感兴趣可以继续补全一些辅助代码，然后用真正的字符串输入试验一下，是否工作正常。前面假设输入字符串的语法是正确的，但真实世界的程序总会写错，所以编译器需要能够帮助检查语法错误。在上述程序中加入语法错误检查非常容易，只要验证每个位置的字符，是否真的等于产生式中规定的终结符就可以了。这就留给大家做个练习吧。

上面我们采用的分支预测法是“人肉观察法”，编译原理书里一般都有一些计算FIRST集合或FOLLOW集合的算法，可以算出一个产生式可能开头的字符，这样就可以用自动的方法写出分支预测，从而实现递归下降语法分析器的自动化生成。ANTLR就是用这种原理实现的一个著名工具。有兴趣的同学可以去看编译原理书。其实我觉得“人肉观察法”在实践中并不困难，因为编程语言的文法都特别有规律，而且我们天天用编程语言写代码，都很有经验了。

下面我们要研究一下递归下降法对文法有什么限制。首先，我们必须要通过超前查看进行分支预测。支持递归下降的文法，必须能通过从左往右超前查看k个字符决定采用哪一个产生式。我们把这样的文法称作LL(k)文法。这个名字中第一个L表示从左往右扫描字符串，这一点可以从我们的index变量从0开始递增的特性看出来；而第二个L表示最左推导，想必大家还记得上一篇介绍的最左推导的例子。大家可以用调试器跟踪一遍递归下降语法分析器的分析过程，就能很容易地感受到它的确是最左推导的（总是先展开当前句型最左边的非终结符）。最后括号中的k表示需要超前查看k个字符。如果在每个非终结符的解析方法开头超前查看k个字符不能决定采用哪个产生式，那这个文法就不能用递归下降的方法来解析。比如下面的文法：

F → id

F → ( E )

E → F * F

E → F / F

当我们编写非终结符E的解析方法时，需要在两个E产生式中进行分支预测。然而两个E产生式都以F开头，而且F本身又可能是任意长的表达式，无论超前查看多少字符，都无法判定到底应该用乘号的产生式还是除号的产生式。遇到这种情况，我们可以用提取左公因式的方法，将它转化为LL(k)的文法：

F → id

F → ( E )

G → * F

G → / F

E → FG

我们将一个左公因式F提取出来，然后将剩下的部分做成一个新的产生式G。在解析G的时候，很容易进行分支预测。而解析E的时候则无需再进行分支预测了。在实践中，提取左公因式不仅可以将文法转化为LL(k)型，还能有助于减少重复的解析，提高性能。

下面我们来看LL(k)文法的第二个重要的限制——不支持左递归。所谓左递归，就是产生式产生的第一个符号有可能是该产生式本身的非终结符。下面的文法是一个直截了当的左递归例子：

F → id

E → E + F

E → F

这个表达式类似于我们上篇末尾得到的无歧义二元运算符的文法。但这个文法存在左递归：E产生的第一个符号就是E本身。我们想像一下，如果在编写E的递归下降解析函数时，直接在函数的开头递归调用自己，输入字符串完全没有消耗，这种递归调用就会变成一种死循环。所以，左递归是必须要消除的文法结构。解决的方法通常是将左递归转化为等价的右递归形式：

F → id

E → FG

G → + FG

G → ε

大家应该牢牢记住这个例子，这不仅仅是个例子，更是解除大部分左递归的万能公式！我们将要在编写miniSharp语法分析器的时候一次又一次地用到这种变换。

由于LL(k)文法不能带有左递归和左公因式，很多常见的文法转化成LL(k)之后显得不是那么优雅。有许多程序员更喜欢使用LR(k)文法的语法分析器。LR代表从左到右扫描和最右推导。LR型的文法允许左递归和左公因式，但是并不能用于递归下降的语法分析器，而是要用移进-归约型的语法分析器，或者叫自底向上的语法分析器来分析。我个人认为LR型语法分析器的原理非常优雅和精妙，但是限于本篇的定位我不准备介绍它。我想任何一本编译原理书里都有详细介绍。当然如果未来我的VBF库支持了LR型语法分析器，我也许会追加一些特别篇，谁知道呢？

希望大家看了今天这篇文章之后，都能用递归下降法写出一些LL(k)文法的语法分析器来。下一篇我将介绍使用C#和VB中神奇的Linq语法来“组合”出语法分析器来，敬请期待！

希望大家继续关注我的VBF项目：https://github.com/Ninputer/VBF 和我的微博：http://weibo.com/ninputer 多谢大家支持！

自己动手开发编译器（八）用Linq编写解析器组合子

上回我们说到手写递归下降语法分析器。手写递归下降的方式是目前很多编译器采用的方式，如果你想写一个商业质量的编译器，这是首选的方法。但是，一个完善的递归下降解析器需要的代码量也不少，如果要进行错误报告、错误恢复等等那代码量就更大了。作为懒人，我们有时想要一些小型语言的解析器，最好写起来像直接写文法的产生式一样，最好连错误报告和错误恢复也一并自动解决，可能吗？在过去很长一段时间，人们采用的方法是使用解析器生成器（parser generator）。因为不管是LL递归下降解析还是LR的移进归约解析，都可以很容易地用计算机来生成所需的规则。这样的著名工具有yacc、ANTLR等。他们的特点是要用一种专门的语法格式来编写文法产生式，然后经过一个翻译程序生成解析器的代码。在函数式语言发展起来之后，有些人发现函数式语言的抽象能力非常强，甚至能够直接用函数式语言的代码来表达文法的产生式，并将解析器“组合”出来，这称作解析器组合子（parser combinator）。如今C#和VB语言也具有函数式语言相当的特征，特别是还有Linq助阵，以至于在C#和VB中也能享受组合子带来的方式。今天我们就来看看怎么做解析器的组合子。这一篇文字描述可能比较模糊，大家一定要认真地看代码，动手实验。

解析器组合子的基本思想是“组合”，首先我们要定义一些最基本的产生式作为基础组合子，然后通过组合的方式拼装出最终的解析器来。回想一下正则表达式的定义，它有两个基本表达式要素——空表达式和字符表达式，以及三个基本运算——并、连接和克林闭包。用基本运算连接基本表达式，就能组成任何正则表达式。解析器组合子也需要定义两个基本的产生式和两个基本运算。

首先是产生空字符的产生式：

G → ε

这个产生式不产生任何单词，换句话说在解析的时候，不解析任何单词就能成功解析出一个G。因此这个产生式的解析器永远都能解析成功。

接下来是产生一个单词t的产生式：

G → t

产生式产生一个特定单词t，表示在解析的时候，如果遇到单词t，则成功解析出一个G，而遇到其他单词则会解析失败。

再来定义两个基本运算。首先是连接运算：

G → X Y

产生式先产生X再产生Y，表示在解析的时候先成功解析X，再成功解析Y，就能成功解析出一个G。

接下来是并运算：

G → X

G → Y

这表示，G既可以产生X也可以产生Y。在解析时无论成功解析X还是Y，都能成功解析出一个G。以上四种基本产生式嵌套使用，就能表示任何上下文无关文法。

下面定义解析器函数的原型委托：

public delegate IResult<T> ParserFunc<out T>(ForkableScanner scanner);

public interface IResult<out T>
{
    T Value { get; }
    ForkableScanner ReturnedScanner { get; }
}

public class Result<T> : IResult<T>
{
    public T Value { get; private set; }
    public ForkableScanner ReturnedScanner { get; private set; }

    public Result(T value, ForkableScanner returnedScanner)
    {
        Value = value;
        ReturnedScanner = returnedScanner;
    }
}

这并不是VBF.Compilers.Parsers.Combinators库最后采用的Parser函数原型，但它非常适合第一次接触解析器组合子的同学们理解。先看第一行委托的结构，它接受一个ForkableScanner作为参数，然后返回一个IResult<T>类型。首先什么是ForkableScanner呢？我们在词法分析篇定义的Scanner类只能不断地向前Read，而在函数式编程风格中，我们需要一个无副作用的Scanner。简而言之，任何一个个ForkableScanner可以随时“Fork”成两个ForkableScanner，而这两个Scanner任何一个向前扫描，都不会影响另外一个，而且他们各自扫描都回得到同样的单词流。这都是为了处理上述“并”运算的解析器，并运算需要两个分支能够互不影响地单独进行。接下来是返回类型IResult<T>，定义成接口是为了能够加上.NET 4泛型协变的“out”关键字。实际类型Result<T>包含一个解析结果T和成功解析之后返回的Scanner，代表余下的输入流。如果返回的整个Result对象为null，则表示解析失败。后面所有解析器组合子最终都是为了生成这样一个委托的对象，一旦生成了这个对象，就可以马上拿来解析了。

有了解析器函数原型，下面就开始一样一样地定义基础组合子。所谓组合子其实都是一些静态方法（本例中这些静态方法都定义在Parsers静态类中）、返回类型就是上面的解析器委托。由于返回类型也是委托，所以这些组合子实际上都是一些高阶函数（返回函数的函数）。在我们的代码中常常是一个lambda表达式。较少使用lambda表达是的同学第一次看下面的代码可能会略微感到头晕，只需要稍微休息一下再重新看即可……

首先是空产生式G → ε，它的组合子是：

public static ParserFunc<T> Succeed<T>(T result)
{
    return scanner => new Result<T>(result, scanner);
}

这个组合子接受一个参数，表示其解析结果。正如前面所介绍，由Succeed组合子生成的解析器，永远都会成功解析，而且会将设定的结果返回。

第二种是接受一个单词的的产生式G → t，我们将它的组合子定义成一个扩展方法：

public static ParserFunc<Lexeme> AsParser(this Token token)
{
    return scanner =>
    {
        var lexeme = scanner.Read();
        if (lexeme.TokenIndex == token.Index)
        {
            return new Result<Lexeme>(lexeme, scanner);
        }
        else
        {
            return null;
        }
    };
}

注意这个组合子生成的解析器是Lexeme（词素）类型的，词素对象是我们在词法分析阶段定义的，里面包含了词素的类型和具体字符串。这个组合子接受一个Token作为参数，而返回的解析器从输入的Scanner中读取下一个词素，如果该词素的单词类型与传入的Token相匹配，就报告解析成功，否则解析失败。

第三种是两个文法的连接G → X Y。我们需要定义一个组合子，接受两个已经存在的ParserFunc函数，返回一个新的ParserFunc，先后调用两个传入的ParserFunc：

public static ParserFunc<Tuple<T1, T2>> Concat<T1, T2>(this ParserFunc<T1> parser1, ParserFunc<T2> parser2)
{

    return scanner =>
    {
        var result1 = parser1(scanner);

        if (result1 == null) return null;

        var result2 = parser2(result1.ReturnedScanner);

        if (result2 == null) return null;

        return new Result<Tuple<T1, T2>>(Tuple.Create(result1.Value, result2.Value), result2.ReturnedScanner);
    };
}

注意我们返回的ParserFunc结果类型是Tuple<T1, T2>，因为结果中需要同时包含T1和T2。

用这种方式定义的连接运算组合子，在实践中非常难用。因为我们的文法常常要包含不止两个符号连接的情形。假如我们的产生式是G → X Y Z，那么必须写成 X.Concat(Y.Concat(Z))，而它的返回类型是Tuple<T1, Tuple<T2, T3>>，如果要取得结果中的Z，只能写r.Item2.Item2。实际上miniSharp这样的语言，文法中出现7-8个符号连接也不是什么稀奇的事情，而如果都用这个组合子的话，Tuple嵌套会复杂到把人的眼睛都搞晕掉。所以这时我们想到了——Linq。Linq的“组合子”中，有一种叫SelectMany，他给我们带来了这种语法糖：

List<int> la = new List<int>() { 1, 2, 3 };
List<string> lb = new List<string>() { "a", "b", "c" };

var r = from a in la
        from b in lb
        select a + b;

它实际可以翻译成：

var r = la.SelectMany(a => lb.SelectMany(b => a + b));

也就是说，连续from语句，其实是SelectMany扩展方法的嵌套调用。这种调用方法有把lambda嵌套“打平”的功能，非常类似于单子风格中的Bind运算。实际上C#和VB允许在任何自定义类型上扩展SelectMany方法，然后就允许用Linq语法的from去调用。有些人非常鄙视语法糖，但这个语法糖却是无法替代的，这是C#版解析器组合子关键中的关键！由此就可以将连接运算定义成一个SelectMany组合子：

public static ParserFunc<TResult> SelectMany<T1, T2, TResult>(this ParserFunc<T1> parser,
    Func<T1, ParserFunc<T2>> parserSelector, Func<T1, T2, TResult> resultSelector)
{

    return scanner =>
    {
        var result1 = parser(scanner);

        if (result1 == null) return null;

        var parser2 = parserSelector(result1.Value);

        var result2 = parser2(result1.ReturnedScanner);

        if (result2 == null) return null;

        return new Result<TResult>(resultSelector(result1.Value, result2.Value), result2.ReturnedScanner);
    };
}

这个神奇的SelectMany组合子不但消除了嵌套Tuple带来的混乱，还允许我们用一个自定义的select语句生成连接运算的结果，这在生成语法树的时候尤为方便。我们一会再看例子，先继续看最后一种基本组合子。

最后一种基本组合子是并运算。并运算要求产生式产生两种可能的分支。对应到解析器组合子上，连接运算也要接受两个现成的解析器作为参数，但是选择哪一个呢？这里我们没有办法做分支预测，所以只好采取尝试的办法。有一种尝试的方法就是先试用第一个解析器，如果失败了，再试用第二个，这是一种类似深度优先搜索的办法：

public static ParserFunc<T> Union<T>(this ParserFunc<T> parser1, ParserFunc<T> parser2)
{
    return scanner =>
    {
        var scanner1 = scanner;
        var scanner2 = scanner.Fork();

        var result1 = parser1(scanner1);
        if (result1 != null)
        {

            return result1;
        }

        var result2 = parser2(scanner2);

        return result2;
    };
}

仅仅使用以上四个组合子函数，就可以来写Parser了！是否还半信半疑呢？我们就来写上一次写过的二叉树字符串表示的语法分析器。忘记的同学建议打开上一篇看看。我们把文法再抄一遍：

N → a ( N, N )

N → ε

这里面涉及的单词包括字母、左右括号和逗号，我们都用词法分析篇的方法将他们定义出来。然后再用解析器组合子组合出上述文法的解析器。完整的代码如下：

Lexicon binaryTreeSyntax = new Lexicon();
LexerState lex = binaryTreeSyntax.DefaultLexer;

//定义词法
Token LEFTPH = lex.DefineToken(RE.Symbol(\'(\'));
Token RIGHTPH = lex.DefineToken(RE.Symbol(\')\'));
Token COMMA = lex.DefineToken(RE.Symbol(\',\'));
Token LETTER = lex.DefineToken(RE.Range(\'a\',\'z\') | RE.Range(\'A\',\'Z\'));

//定义语法
ParserFunc<Node> NodeParser = null;
NodeParser = 
    (from a in LETTER.AsParser()
     from _1 in LEFTPH.AsParser()
     from left in NodeParser
     from _2 in COMMA.AsParser()
     from right in NodeParser
     from _3 in RIGHTPH.AsParser()
     select new Node(a.Value[0], left, right))
    .Union(Parsers.Succeed<Node>(null));


//运行部分
ForkableScannerBuilder builder = 
    new ForkableScannerBuilder(binaryTreeSyntax.CreateScannerInfo());

string source = "A(B(,),C(,))";
SourceReader sr = new SourceReader(
    new StringReader(source));

ForkableScanner scanner = builder.Create(sr);

var tree = NodeParser(scanner);

重点来看“定义语法”部分，我们来看看产生式都是如何转变为组合子调用的。首先，N → ε转化为了一句Parsers.Succeed调用，代表总能解析成功，而且不消耗输入单词的解析器。然后是N → a ( N, N )，连续的连接转化为一连串Linq的from子句。而其中出现了终结符的地方，则通过AsParser扩展方法将Token转化为Parser。最后再用一个Union组合子将两个N产生式组合到一起，中间我们还看到了用select子句方便地构造想要的解析结果能力。再一次，赞叹SelectMany的神奇力量！初看起来，Linq用来写文法感觉怪怪的，但是习惯了之后，可以非常快速地将各种产生式以Linq语句的方式表达出来。

解析器组合子最大的优点就是无论实现还是使用都非常简洁，高度体现了函数式编程的优势。但它最大的缺点是难以调试。倘若大家用解析器组合子组合出来的解析器有错误，无法获得想要的解析结果，那可就麻烦了。大家可以试试用Visual Studio的调试器跟踪一下解析器组合子，会发现它的跳转非常频繁，而且根本看不出当前在干什么（因为运行时已经生成了Lambda函数，无法获得组合子传入的参数），也无法看出下一步会运行什么。所以，采用解析器组合子唯一确保正确的做法，就是编写足够的测试用例。

还有一个重要的问题要解决——语法错误。大家可以试一试输入一个不符合语法的字符串，比如去掉一个括号，看看会是什么结果？答案是直接返回null——和一开始的设定一样。无法知道错误出在了哪里。作为编程语言的解析器，不仅应该能报告错误出现的位置，而且还应该能自动进行某种错误恢复，这样就可以继续完成解析，从而获得所有的语法错误，而不仅仅是头一个。这个功能非常重要，但我们今天设计的解析器组合子结构却非常不擅长进行错误报告和恢复。比如说Union组合子，干脆就是通过解析错误来判断要不要采用这个分支，如果每个分支都错了，它又如何决定报告哪条分支的错误呢？可以设定一些规则，但是我们想要更好、更智能的错误报告和恢复功能。这就留到下一篇，正式介绍VBF库中采用的CPS风格解析器组合子了。敬请期待！

希望大家继续关注我的VBF项目：https://github.com/Ninputer/VBF 和我的微博：http://weibo.com/ninputer 多谢大家支持！

自己动手开发编译器（九）CPS风格的解析器组合子

上回我们用函数式编程的方法，结合Linq语法，建立了一套解析器组合子方案，并能成功解析自定义文法的输入字符串。但是，上次做成的解析器组合子有个重要的功能没有完成——错误报告。作为编程语言的语法分析器，不能在遇到语法错误的时候简单地返回null，那样程序员就很难修复代码中的语法错误。我们需要的是准确报告语法错误的位置，更进一步，是程序中所有的语法错误，而不仅仅是头一个。后者要求解析器具有错误恢复的能力，即在遇到语法错误之后，还能恢复到正常状态继续解析。错误恢复不仅仅可以用在检测出所有的语法错误，还可以在存在语法错误的时候仍然提供有意义的解析结果，从而用于IDE的智能感知和重构等功能。手写的递归下降语法分析器可以很容易地加入错误恢复，但需要针对每一处错误手工编写代码来恢复。像C#官方编译器，给出的语法错误信息非常全面、精确、智能，全都是手工编写的功劳。又回到我们是懒人这个残酷的事实，能不能在让解析器组合子生成的解析器自动具有错误恢复能力呢？

首先来看上一个版本的四个基本组合子：空产生式的Succeed组合子，token产生式的AsParser组合子，连接运算产生式的SelectMany组合子和并运算产生式的Union组合子。首先Succeed是不会解析失败的，所以它没有必要进行错误恢复。现在来看AsParser组合子，它的逻辑是读取下一个词素，如果词素的单词类型和组合子的参数匹配则解析成功，否则解析失败。代码如下：

public static ParserFunc<Lexeme> AsParser(this Token token)
{
    return scanner =>
    {
        var lexeme = scanner.Read();
        if (lexeme.TokenIndex == token.Index)
        {
            return new Result<Lexeme>(lexeme, scanner);
        }
        else
        {
            return null;
        }
    };
}

如果要对失败的情形进行错误恢复，有两种可行的选择：1、假装要解析的Token存在，继续解析（这种做法相当于在原位置插入了一个单词）；2、跳过不匹配的单词，重新进行解析（这种做法相当于删除了一个单词）。如果漏写一个分号或者括号，插入型错误恢复就能有效地恢复错误，如果是多写了一个关键字或标识符造成的错误，删除型错误恢复就能有效地恢复。但问题是，我们怎么能在组合子的代码中判断出哪种错误恢复更有效呢？最优策略是让两种错误恢复的状态都继续解析到末尾，然后看哪种恢复状态整体语法错误最少。但是，只要有一个字符解析失败，就要分支成两个完整解析，那么错误一旦多起来，这个分支的庞大程度将使得错误恢复无法进行。更何况，错误并不仅仅出现在真正的语法错误上，我们还要用错误来判断“并”运算组合子的分支问题。请看上一版本Union组合子的代码：

public static ParserFunc<T> Union<T>(this ParserFunc<T> parser1, ParserFunc<T> parser2)
{
    return scanner =>
    {
        var scanner1 = scanner;
        var scanner2 = scanner.Fork();

        var result1 = parser1(scanner1);
        if (result1 != null)
        {

            return result1;
        }

        var result2 = parser2(scanner2);

        return result2;
    };
}

在Union中，我们先试验第一个parser1能否解析成功，如果失败才解析parser2。如果解析器有自动错误恢复的功能，那么我们就无法用这种方式判断了，因为两条分支遇到错误之后都会继续进行下去。我们可以让两条分支都解析到底，然后挑错误较少的分支作为正式解析结果。但同上所述，这种做法的分支多得难以置信，效率上决定我们不能采用。

为了避免效率问题，我们需要一种“广度优先”的处理方案。在遇到错误时产生的“插入”和“删除”两条分支，要同时进行，但要一步一步地进行。这里所谓的一“步”，就是指AsParser组合子读取一个词素。我们看到四种基本组合子中，只有AsParser组合子会用scanner来真正读取词素，其他组合子最终也是要调用到AsParser组合子来进行解析的。我们让两个可能的分支都向前解析一步，然后看是否其中一条分支的结果比另外一条更好。所谓更好，就是一条分支没有进一步遇到错误，而另外一条分支遇到了错误。如果两条分支都没有遇到错误，或者都遇到了错误，我们就再向前推进一步，直到某一步比另外一步更好为止。Union组合子也可以采用同样的策略处理。这是一种贪心算法的策略，我们所得到的结果未必是语法错误最少的解析结果，但它的效率是可以接受的。

那么怎么进行“广度优先”推进呢？我们上次引入的组合子，当前的组合子无法知道下一个要运行的组合子是什么，更无法控制下一个组合子只向前解析一步。为了达到目的，我们要引入一种新的组合子函数原型，称作CPS（Continuation Pass-in Style）风格的组合子。不知道大家有多少人听说过CPS，这在函数式编程界是一种广为应用的模式，在.NET世界里其实也有采用。.NET 4.0引入的Task Parallel Library库中的Task类，就是一个典型的CPS设计范例。我举一个简单的例子来介绍一下CPS。如果有两个函数A和B，需要按顺序调用，用传统方式编程很简单，就是直接调用：

void A()
{
    Console.WriteLine("A");
}

void B()
{
    Console.WriteLine("B");
}

void Run()
{
    A();
    B();
}

而如果采用CPS，则是把B传递给A，这时我们称B是A的continuation，或者future。

void A(Action future)
{
    Console.WriteLine("A");
    future();
}

void B()
{
    Console.WriteLine("B");
}

void Run()
{
    A(B);
}

乍一看这也不能实现什么特别的事情，但其实是很有用的。A获得了自己的future之后可以自行决定如何运行它。比如可以异步地运行。这样我们就在Run()方法中，用一种容易理解的方式，构建出了一条异步调用序列。.NET 4.0的Task Parallel Library正是这样的风格，每个Task类通过ContinueWith方法接受自己的future。而我们的函数式解析其组合子，也可以用这种方式，让每个Parser函数接受一个future，并自行决定如何调用future。这里最关键的思想是实现延迟调用future，从而实现“广度优先”的单步解析效果。首先来看看新的Parser类原型（警告，这一篇里采用的函数式技巧比上一篇还要难懂得多，如果看了之后发生头晕，嗜睡等症状，请休息之后重新看……）：

public delegate Result<T> ParserFunc<T>(ForkableScanner scanner, ParserContext context);
public delegate ParserFunc<TFuture> Future<T, TFuture>(T value);

public abstract class Parser<T>
{
    public abstract ParserFunc<TFuture> BuildParser<TFuture>(Future<T, TFuture> future);
}

ParserFunc方法和上一篇非常类似，但是多了一个ParserContext方法。我们会用这个对象来保存一些错误报告的信息。再来是Future函数的定义，Future返回的类型是一个ParserFunc委托对象；Future的参数T，则是用来让每一个组合子生成的Parser，将自己的解析结果T传给它自己的Future用的。注意这次多了一个Parser<T>抽象类，它代替ParserFunc成为组合子的生成对象。它之所以不能声明成一个委托，是因为它的BuildParser方法要接受一个额外的泛型类型参数TFuture。接下来每一个解析器组合子都需要继承自Parser<T>，并实现它的BuildParser方法。下面我们就来看一看新的CPS型解析器组合子怎么定义。

首先还是G → ε的组合子，它永远都能解析成功，所以，它的逻辑是生成一个ParserFunc，将预设的解析结果传递给自己的Future:

public class SucceedParser<T> : Parser<T>
{
    public T Value { get; private set; }

    public SucceedParser(T value)
    {
        Value = value;
    }
    public override ParserFunc<TFuture> BuildParser<TFuture>(Future<T, TFuture> future)
    {
        return (scanner, context) => future(Value)(scanner, context);
    }
}

这是第一次实践CPS风格，大家一定要注意观察它与上一次传统风格解析器组合子的不同。最关键的一点，就是返回的ParserFunc，必须要调用BuildParser传进来的future函数，传递自己的解析结果。

接下来就是重头戏G → t，我们要在这个单词解析器组合子中加入期待已久的错误报告和错误恢复功能，请看代码：

public class TokenParser : Parser<Lexeme>
{
    public Token ExpectedToken { get; private set; }
    public string MissingCorrection { get; private set; }

    public TokenParser(Token expected)
    {
        ExpectedToken = expected;
        MissingCorrection = expected.ToString();
    }


    public override ParserFunc<TFuture> BuildParser<TFuture>(Future<Lexeme, TFuture> future)
    {
        ParserFunc<TFuture> scan = null;
        scan = (scanner, context) =>
        {
            var s1 = scanner.Fork();

            var l = scanner.Read();

            int tokenIndex;
            tokenIndex = l.TokenIndex;

            if (tokenIndex == ExpectedToken.Index)
            {
                var r = context.StepResult(0, () => future(l)(scanner, context));
                return r;
            }
            else
            {
                Lexeme correctionLexeme = l.GetErrorCorrectionLexeme(ExpectedToken.Index, MissingCorrection);
                ErrorCorrection insertCorrection = new InsertedErrorCorrection(ExpectedToken.ToString(), correctionLexeme.Span);

                if (l.IsEndOfStream)
                {
                    scanner.Join(s1);
                    return context.StepResult(1, () => future(correctionLexeme)(scanner, context), insertCorrection); //插入
                }
                else
                {
                    ErrorCorrection deleteCorrection = new DeletedErrorCorrection(l);
                    return context.ChooseBest(context.StepResult(1, () => future(correctionLexeme)(s1, context), insertCorrection), //插入
                        context.StepResult(1, () => scan(scanner, context), deleteCorrection)); //删除
                }
            }
        };

        return scan;
    }
}

大致描述下来就是生成这样一个ParserFunc：首先通过Scanner读取下一个词素，并判断它是否是期待的单词。如果是，则调用context.StepResult(0, …)方法（稍后解释）；如果不是，则判断是否遇到的输入流的末尾，如果是末尾，则只尝试“插入”修复方案（因为无法删除“流末尾”单词），如果不是末尾则使用context.ChooseBest方法，尝试插入和删除两种修复方案。context.StepResult方法就是产生延迟执行future的关键。它的第一个参数表示该结果的“代价”，0表示这是一个成功解析的结果；1表示是经过错误恢复的结果。第二个参数则是一个延迟执行的委托，这个委托只会在我们需要将解析器“推进一步”的时候才会执行，我们将future函数的调用放在这里并做成延迟执行的方式，就是要等待广度优先一步一步地向前解析时才执行下一步的操作。那么这个context.ChooseBest函数到底是如何实现的呢？请看代码：

private Result<T> ChooseBest<T>(Result<T> result1, Result<T> result2, int correctionDepth)
{
    if (result1.Type == ResultType.Stop)
    {
        return result1;
    }
    if (result2.Type == ResultType.Stop)
    {
        return result2;
    }

    var step1 = (StepResult<T>)result1;
    var step2 = (StepResult<T>)result2;

    if (step1.Cost < step2.Cost)
    {
        return step1;
    }
    else if (step1.Cost > step2.Cost)
    {
        return step2;
    }
    else
    {
return new StepResult<T>(Math.Max(step1.Cost, step2.Cost), 
            () => ChooseBest(step1.NextResult, step2.NextResult, correctionDepth + 1), null);
    }
}

ChooseBest方法要比较两个Result的代价，并选取代价较小的分支。如果代价一样，则通过延迟计算的方法将比较推至下一轮。我们到处采用延迟计算的手段，以至于整个单词流都输入之后，解析可能仍然没有结束！所以Result类有一个集中取得每一步结果的功能，在单词流输入完毕后还要继续驱动这些延迟计算，直到拿到最终的解析结果。

接下来是表示连接运算G → X Y的SelectMany组合子。具体方法是将传入的future作为Y的future，再将Y的Parser作为X的future，以此将两者连接起来：

public class ConcatenationParser<T1, T2, TR> : Parser<TR>
{
    public Parser<T1> ParserLeft { get; private set; }
    public Func<T1, Parser<T2>> ParserRightSelector { get; private set; }
    public Func<T1, T2, TR> Selector { get; private set; }

    public ConcatenationParser(Parser<T1> parserLeft, Func<T1, Parser<T2>> parserRightSelector, Func<T1, T2, TR> selector)
    {
        CodeContract.RequiresArgumentNotNull(parserLeft, "parserLeft");
        CodeContract.RequiresArgumentNotNull(parserRightSelector, "parserRightSelector");
        CodeContract.RequiresArgumentNotNull(selector, "selector");

        ParserLeft = parserLeft;
        ParserRightSelector = parserRightSelector;
        Selector = selector;
    }

    public override ParserFunc<TFuture> BuildParser<TFuture>(Future<TR, TFuture> future)
    {
        return (scanner, context) => 
            ParserLeft.BuildParser(
                left => ParserRightSelector(left).BuildParser(
                    right => future(Selector(left, right))))(scanner, context);
    }
}

最后的并运算，则是广度优先同时实验两个传入的Parser，即直接用ChooseBest方法选取继续执行的Parser：

public class AlternationParser<T> : Parser<T>
{
    public Parser<T> Parser1 { get; private set; }
    public Parser<T> Parser2 { get; private set; }

    public AlternationParser(Parser<T> parser1, Parser<T> parser2)
    {
        CodeContract.RequiresArgumentNotNull(parser1, "parser1");
        CodeContract.RequiresArgumentNotNull(parser2, "parser2");

        Parser1 = parser1;
        Parser2 = parser2;
    }

    public override ParserFunc<TFuture> BuildParser<TFuture>(Future<T, TFuture> future)
    {
        return (scanner, context) =>
        {
            var s1 = scanner;
            var s2 = scanner.Fork();

            return context.ChooseBest(Parser1.BuildParser(future)(s1, context), Parser2.BuildParser(future)(s2, context));
        };
    }
}

如果大家还不能很清晰地理解上述CPS风格解析器组合子的原理，也不要担心。我也是花了整整两个星期时间反复看论文才理清所有细节的。而且我贴的也是简化的代码，并不完整。大家可以下载VBF库的源代码来仔细研究。当然，如果对Haskell不恐惧的话，看原始的论文也不错。从这里下载论文（点右上方Download下面的PDF图标）：http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.30.7601

最后，我们像上一篇传统解析器组合子那样，为每种组合子声明一个便于使用的静态函数或者扩展方法。注意，在上述四种基本组合子外，CPS组合子如要正常工作，需要一个特殊的组合子——EndOfStreamParser，它类似于TokenParser但错误恢复的时候从不尝试插入。这里略过它的实现，直接来看辅助函数的定义：

public static class Parsers
{
    public static Parser<Lexeme> AsParser(this Token token)
    {
        CodeContract.RequiresArgumentNotNull(token, "token");

        return new TokenParser(token);
    }

    public static Parser<Lexeme> Eos()
    {
        return new EndOfStreamParser();
    }

    public static Parser<T> Succeed<T>(T value)
    {
        return new SucceedParser<T>(value);
    }

    public static Parser<TResult> SelectMany<T1, T2, TResult>(this Parser<T1> parser, Func<T1, Parser<T2>> parserSelector, 
        Func<T1, T2, TResult> resultSelector）
    {
        CodeContract.RequiresArgumentNotNull(parser, "parser");
        CodeContract.RequiresArgumentNotNull(parserSelector, "parserSelector");
        CodeContract.RequiresArgumentNotNull(resultSelector, "resultSelector");

        return new ConcatenationParser<T1, T2, TResult>(parser, parserSelector, resultSelector);
    }

    public static Parser<T> Union<T>(this Parser<T> parser1, Parser<T> parser2)
    {
        CodeContract.RequiresArgumentNotNull(parser1, "parser1");
        CodeContract.RequiresArgumentNotNull(parser2, "parser2");

        return new AlternationParser<T>(parser1, parser2);
    }
}

这样，我们就能和上一篇一样用Linq的语法来组合Parser了。最后我们还需要一个驱动延迟计算的类：

public class ParserRunner<T>
{
    public ParserContext Context { get; private set; }
    private ParserFunc<T> m_runner;

    public ParserRunner(Parser<T> parser, ParserContext context)
    {
        CodeContract.RequiresArgumentNotNull(parser, "parser");
        CodeContract.RequiresArgumentNotNull(context, "context");

        m_runner = parser.BuildParser(FinalFuture);
        Debug.Assert(m_runner != null);
        Context = context;
    }

    public T Run(ForkableScanner scanner)
    {
        var result = m_runner(scanner, Context);
        return result.GetResult(Context);
    }

    private ParserFunc<T> FinalFuture(T value)
    {
        return (scanner, context) => context.StopResult(value);
    }
}

这个类里我们定义了整个解析器最终的一个future——它产生令所有分支判断停止的StopResult。这里最关键的是利用result.GetResult虚方法推进广度优先的分支选取，并且收集这条路线上所有的语法错误。我们所有的语法错误就只有两种：“丢失某单词”（采用了插入方式错误恢复）和“发现了未预期的某单词”（采用了删除方式错误恢复）。

下面的例子演示了真正的VBF.Compilers.Parsers.Combinators.dll库的用法。真正的VBF库除了定义基本组合子之外还定义了许许多多的重载和扩展函数，基本实现了EBNF的所有功能（而且还可以很容易地继续无限扩展）。用VBF库时Linq语句可以直接在Token上使用，而无需到处使用AsParser扩展方法。此外还有大量的代码，限于逻辑无法全部在博客中展现，大家如想了解最好的方法还是直接下载我的代码观看和试用。

class Node
{
    public Node LeftChild { get; private set; }
    public Node RightChild { get; private set; }
    public char Label { get; private set; }

    public Node(char label, Node left, Node right)
    {
        Label = label;
        LeftChild = left;
        RightChild = right;
    }
}

class Program
{
    static void Main(string[] args)
    {
        Lexicon binaryTreeSyntax = new Lexicon();
        LexerState lex = binaryTreeSyntax.DefaultLexer;

        //定义词法
        Token LEFTPH = lex.DefineToken(RE.Symbol(\'(\'));
        Token RIGHTPH = lex.DefineToken(RE.Symbol(\')\'));
        Token COMMA = lex.DefineToken(RE.Symbol(\',\'));
        Token LETTER = lex.DefineToken(RE.Range(\'a\', \'z\') | RE.Range(\'A\', \'Z\'));

        //定义语法
        ParserReference<Node> NodeParser = new ParserReference<Node>();
        NodeParser.Reference =
            (from a in LETTER
             from _1 in LEFTPH
             from left in NodeParser
             from _2 in COMMA
             from right in NodeParser
             from _3 in RIGHTPH
             select new Node(a.Value[0], left, right))
            | Parsers.Succeed<Node>(null);

        var builder = new ForkableScannerBuilder(binaryTreeSyntax.CreateScannerInfo());

        string source = "A(B(,),C(,))";
        SourceReader sr = new SourceReader(
            new StringReader(source));


        ForkableScanner scanner = builder.Create(sr);
        CompilationErrorManager errorManager = new CompilationErrorManager();

        ParserContext context = new ParserContext(errorManager, 0, 1);
        context.DefineDefaultCompilationErrorInfo(0);

        var runner = new ParserRunner<Node>(NodeParser.SuffixedBy(Parsers.Eos()), context);
        var result = runner.Run(scanner);

        foreach (var error in errorManager.Errors.OrderBy(e => e.ErrorPosition.StartLocation.CharIndex))
        {
            Console.WriteLine(error.ToString());
        }
    }
}

注意from语句已经可以直接使用Token类型，Union操作也可以用“|”运算符代替。由于广度优先分支判断的缘故，整个文法在用于解析之前，必须在后面连接一个EndOfStream，代表解析到文件末尾才算结束。最后的代码还演示了如何将解析错误打印出来。大家可以将输入字符串故意改错，看看是否能够检测出来。还可以试试错误太多太离谱时的性能下降现象。

在下一篇，我们将正式用这套解析器组合子实现miniSharp语言的语法分析器，并且还会接触到VBF库扩展组合子的各种用法。敬请期待！

希望大家继续关注我的VBF项目：https://github.com/Ninputer/VBF 和我的微博：http://weibo.com/ninputer 多谢大家支持！

自己动手开发编译器（十）miniSharp语法分析器

经过前面四篇的铺垫，我们终于拥有了编写语法分析器的强大工具，现在可以正式开发一门编程语言的语法分析器了。我们先来定义miniSharp的语法规则，然后根据LL文法的特点进行一些调整，最后借助解析器组合子生成完整的语法分析器。

miniSharp语言是C#的一个小子集，然而它仍然具有一门完整编程语言的所有要素，而且仍然是一种面向对象的语言。我们把miniSharp的语法分成三类——声明结构、语句和表达式。声明结构就是类、方法、字段的声明。语句就是诸如if-else、while这样特定含义的指令。而表达式则是表示一种有运算结果的结构，如二元运算符表达式、函数调用表达式等。C#中赋值也是一种表达式，但miniSharp为了简化后续代码生成，将赋值当成一种语句。

首先来定义声明结构的文法。为了简化语义分析，我们规定程序中第一个类必须是一个静态类，静态类中只能有一个静态方法Main——这是整个miniSharp唯一允许的静态方法。在静态类之后可以定义多个普通类，普通类之间可以继承。下面定义文法的产生式采用了扩展写法，支持类似克林闭包的*符号。G → X* 代表G → ε; G → H; H → XG。文法中的蓝色字代表终结符（词法分析获得的单词）

Program	→	MainClass ClassDecl*
MainClass	→	static class ID { public static void Main (string[] ID) { Statement+ } }
ClassDecl	→	class ID { FieldDecl* MethodDecl* }
→	class ID : ID { FieldDecl* MethodDecl* }
FieldDecl	→	Type ID;
MethodDecl	→	public Type ID (FormalList) { Statement* return Exp ; }
FormalList	→	Type ID FormalRest*
→	ε
FormalRest	→	, Type ID
Type	→	int[]
→	bool
→	int
→	ID

语句部分我们将要定义语句块和六种语句。其中if-else语句的else部分是不能省略的。while语句不支持break。剩下四种分别是调用Console.WriteLine的语句、赋值语句、数组元素赋值语句和变量声明语句。

Statement	→	{ Statement* }
→	if ( Exp ) Statement else Statement
→	while ( Exp ) Statement
→	System.Console.WriteLine( Exp )
→	ID = Exp ;
→	ID [ Exp ] = Exp ;
→	Type ID ;

表达式部分我们将要定义二元、一元、数组长度、数组访问、字面常量、变量、this引用、new运算、方法调用等多种表达式。

Exp	→	Exp op Exp
→	Exp[ Exp ]
→	Exp .Length
→	Exp .ID ( ExpList )
→	INTEGER_LITERAL
→	true
→	false
→	ID
→	this
→	new int [ Exp ]
→	new ID ()
→	! Exp
→	( Exp )
ExpList	→	Exp ExpRest*
→	ε
ExpRest	→	, Exp

其中二元运算表达式的op是+、-、*、/、>、<、==、&&和||之一。为了简单起见我们这里的二元运算表达式文法是有歧义而且没有正确定义优先级的。按照C#的语言规范，运算符的优先级关系如下（只提取了miniSharp支持的部分）：

1	(Exp) new this 变量常量方法调用属性访问数组访问
2	!
3	* /
4	+ -
5	< > ==
6	&&
7	\|\|

有些语法分析器就是使用有歧义的二元运算符文法，在遇到歧义时使用预定义的运算符优先级来解决冲突。现在的语法分析器倾向于直接使用无歧义的文法。下面的文法就是经过精心安排的运算符文法，消除了歧义并使得运算符具有左结合和优先级的区别：

BasicExp	→	括号、new、this、变量、常量、方法调用、属性访问、数组访问
Factor	→	BasicExp
→	! Factor
Term	→	Factor
→	Term op Factor 其中 op 是 * /
Comparand	→	Term
→	Comparand op Term 其中 op 是 + -
Comparison	→	Comparand
→	Comparison op Comparand 其中 op 是 < > ==
Logical	→	Comparison
→	Logical && Comparison
Exp	→	Logical
→	Exp \|\| Logical

这样我们就定义了miniSharp的完整文法。注意，上述文法仍然存在一些左公因式和左递归的现象。我们用的解析器组合子因为独特的广度优先分支判断方式，其支持的文法实际上已经超越了递归下降语法分析器的LL(k)文法，称作LL(∞)的文法，这种文法非常强大，可描述所有确定性下推自动机DPDA接受的语言。但是，它仍然不允许文法存在左递归，而左公因式也会大大降低解析器的效率。所以消除左递归和尽量避免左公因式仍然是真正实现语法分析器时需要着重考虑的任务。

现代语言的语法分析器通常都是将源代码翻译成一棵抽象语法树（Abstract Syntax Tree，AST）。后续的语义分析可以在抽象语法树上继续进行。我们在语法分析篇（六）介绍过“语法分析树”，它是一种在文法推导过程中建立起来的树状数据结构。那么什么是抽象语法树呢？其实就是经过简化和抽象的语法分析树。在完整的语法分析树中每个推导过程的终结符都包含在语法树内，而且每个非终结符都是不同的节点类型。实际上，如果仅仅是要做编译器的话，很多终结符（如关键字、各种标点符号）是无需出现在语法树里的；而前面表达式文法中的Factor、Term也实际上没有必要区分为两种不同的类型，可以将其抽象为BinaryExpression类型。这样简化、抽象之后的语法树，更加利于后续语义分析和代码生成。使用.NET里的面向对象语言来实现语法树，最常见的做法就是用组合模式，将语法树做成一颗对象树，每种抽象语法对应一个节点类。下图就是miniSharp的抽象语法树的所有类。

节选其中一个语法树节点展示一下，比如大家熟悉的IfElse语句的语法树节点类：

public class IfElse : Statement
{
    public Expression Condition { get; private set; }
    public Statement TruePart { get; private set; }
    public Statement FalsePart { get; private set; }
    public SourceSpan IfSpan { get; private set; }
    public SourceSpan ElseSpan { get; private set; }

    public IfElse(Expression cond, Statement truePart, Statement falsePart, SourceSpan ifSpan, SourceSpan elseSpan)
    {
        Condition = cond;
        TruePart = truePart;
        FalsePart = falsePart;
        IfSpan = ifSpan;
        ElseSpan = elseSpan;
    }

    public override T Accept<T>(IAstVisitor<T> visitor)
    {
        return visitor.VisitIfElse(this);
    }
}

它的结构非常简单，里面保存了所有作为子节点成分的字段，例如IfElse是由一个Condition表达式和TruePart、FalsePart两个语句组成。另外我们还多储存了两个SourceSpan，分别是if语句中“if”关键字和“else”关键字出现的源代码位置（多少行，多少列）。保存位置是为了后续语义分析中提供错误信息的位置。比如if的条件表达式必须是个bool类型的表达式，但语法分析阶段无法做出类型验证，而到了语义分析阶段分析出了语义错误，仍然需要向编译器用户提供错误的位置，这些SourceSpan就可以派上用场。

注意节点类最后还实现了一个Accept方法，用来支持语法树的Visitor模式。我们在语义分析阶段和代码生成阶段，需要一次又一次地遍历抽象语法树。为了简化语法树的访问，我们声明一个IAstVisitor<T>接口作为语法树的Visitor，后续过程需要遍历语法树时，就实现这一接口即可。实际上这个接口有一个默认实现——AstVisitor类，允许只重写一部分成员。

有了Ast，下面我们就开始编写miniSharp的语法分析器。在本系列的第五篇（miniSharp语言的词法分析器）中我们已经用VBF词法分析库定义了miniSharp的词法，生成了一些Token对象。那么接下来就只要使用Linq语法的解析器组合子，根据本篇开头定义的文法进行组合，并适时使用select语句生成语法树节点的对象即可。比如，文法最开始的Program和MainClass的写法如下：

PProgram.Reference = // MainClass ClassDecl*
    from main in PMainClass
    from classes in PClassDecl.Many()
    select new Program(main, classes);

PMainClass.Reference = // static class id { public static void Main(string[] id) { statement }}
    from _static1 in K_STATIC
    from _class in K_CLASS
    from className in ID
    from _1 in LEFT_BR
    from _public in K_PUBLIC
    from _static2 in K_STATIC
    from _void in K_VOID
    from _main in K_MAIN
    from _2 in LEFT_PH
    from _string in K_STRING
    from _3 in LEFT_BK
    from _4 in RIGHT_BK
    from arg in ID
    from _5 in RIGHT_PH
    from _6 in LEFT_BR
    from statements in PStatement.Many1()
    from _7 in RIGHT_BR
    from _8 in RIGHT_BR
    select new MainClass(className, arg, statements);

这代码是如此的直白以至于没什么可解释的。唯一要注意的是PProgram.Reference这个用法，这里PProgram是ParserReference<T>类的实例。这个类允许先直接new出来，然后再用.Reference = XXX的方式为其指定语法规则。这样就允许一个Parser组合子先使用，后定义（比如上面例子中的PMainClass就先在PProgram的语法定义中使用了，然后下面才定义其语法）。因为文法中的非终结符常常出现递归引用，用ParserReference这个类可以大大简化我们的工作，不用关心Parser的声明先后顺序问题。

我们重点来看一些需要特殊技巧的例子。首先是声明方法形式参数的文法，采用了FormalList → Type ID FormalRest*这样的定义方法，这是避免左递归的技巧。但是这样一来，方法的第一个参数就和其他的参数分别定义在两个语法当中。我们希望生成的抽象语法树不区分第一个参数和其余参数，所以可以在生成语法树时采用一点点小技巧来办到：

var paramFormal =
    from paramType in PType
    from paramName in ID
    select new Formal(paramType, paramName);

PFormalList.Reference = // Type id FormalRest* | <empty>
    (from first in paramFormal
     from rest in PFormalRest.Many()
     select new[] { first }.Concat(rest).ToArray()) |
    Parsers.Succeed(new Formal[0]);

PFormalRest.Reference = // , Type id
    paramFormal.PrefixedBy(COMMA.AsParser());

另外注意扩展的产生式“X*”在VBF解析器组合子库中可以直接使用X.Many()的方式实现。VBF中还定义了数个这种方便的扩展组合子。

最后要注意的是二元运算符的分析器。我们前面写出的无歧义符合优先级的二元运算符文法仍然是左递归的，用于解析器组合子时必须像上面的FormalList那样改成右递归的。但是这些运算符都是左结合的，我们不想让生成的抽象语法树也变成右递归的形态。因此，这里我们需要用（传统）Linq的Aggregate扩展方法来处理一下生成的语法树：

var termRest =
    from op in (ASTERISK.AsParser() | SLASH.AsParser())
    from factor in PFactor
    select new { Op = op, Right = factor };

PTerm.Reference = // term * factor | factor
    from factor in PFactor
    from rest in termRest.Many()
    select rest.Aggregate(factor, (f, r) => new Binary(r.Op, f, r.Right));

var comparandRest =
    from op in (PLUS.AsParser() | MINUS.AsParser())
    from term in PTerm
    select new { Op = op, Right = term };

PComparand.Reference = // comparand + term | term
    from term in PTerm
    from rest in comparandRest.Many()
    select rest.Aggregate(term, (t, r) => new Binary(r.Op, t, r.Right));


var comparisonRest =
    from op in (LESS.AsParser() | GREATER.AsParser() | EQUAL.AsParser())
    from comparand in PComparand
    select new { Op = op, Right = comparand };

PComparison.Reference = // comparison < comparand | comparand
    from comparand in PComparand
    from rest in comparisonRest.Many()
    select rest.Aggregate(comparand, (c, r) => new Binary(r.Op, c, r.Right));

除此之外，剩下的语法翻译成组合子基本上都是水到渠成的工作了。完整的代码全部都在MiniSharpParser.cs中，大家可以自行下载阅读。经过小小的努力，我们终于能将miniSharp的源代码转换为抽象语法树了，接下来我们就要进入下一个编译器重要的阶段——语义分析。敬请期待下一篇！

希望大家继续关注我的VBF项目：https://github.com/Ninputer/VBF 和我的微博：http://weibo.com/ninputer 多谢大家支持！

自己动手开发编译器（十一）语义分析

上回我们已经用VBF的Parsers.Combinators库生成了miniSharp的语法分析器，并且能够将miniSharp的源代码翻译成抽象语法树（AST）。这一回我们要继续进行下一步——语义分析。就目前大家接触的编程语言，如C#、VB、C++来说，语义分析是编译器前端最复杂的部分。因为这些编程语言的语义都非常复杂。语义分析不像之前词法分析、语法分析那样，有一些特定的工具来帮助。这一部分通常都是要纯手工写代码来完成。我们的miniSharp语义因为已经高度简化，它的语义分析可以说比C#要容易一个数量级。我们只会在选定方法重载的时候见识一下C#复杂语义的冰山一角。

所谓编程语言语义，就是这段代码实际的含义。编程语言的代码必须有绝对明确的含义，这样人们才能让程序做自己想做的事情。比如最简单的一行代码：a = 1; 它的语义是“将32位整型常量存储到变量a中”。首先我们对“1”有明确的定义，它是32位有符号整型字面量，这里“32位有符号整型”就是表达式“1”的类型。其次，这句话成为合法的编程语言，32位整型常量必须能够隐式转换为a的类型。假设a就是int型变量，那么这条语句就直接将1存储到a所在内存里。如果a是浮点数类型的，那么这句话就隐含着将整型常量1转换为浮点类型的步骤。在语义分析中，类型检查是贯穿始终的一个步骤。像miniSharp这样的静态类型语言，类型检查通常要做到：

判定每一个表达式的声明类型
判定每一个字段、形式参数、变量声明的类型
判断每一次赋值、传参数时，是否存在合法的隐式类型转换
判断一元和二元运算符左右两侧的类型是否合法（比如+不就不能在bool和int之间进行）
将所有要发生的隐式类型转换明确化

要进行以上操作，需要一个表存储所有已知的类型。如果引用了外部程序集，则也需要将外部程序集中的类型信息放到表中。类型信息包括类型的名字、父类（如果有的话）、成员以及相互隐式转换的规则。我们用如下的类来表示一个miniSharp自定义类型：

public class CodeClassType : TypeBase
{
    public bool IsStatic { get; set; }
    public CodeClassType BaseType { get; set; }
    public Collection<Method> Methods { get; private set; }
    public Collection<Method> StaticMethods { get; private set; }
    public VariableCollection<Field> Fields { get; private set; }

    public CodeClassType()
    {
        Methods = new Collection<Method>();
        StaticMethods = new Collection<Method>();
        Fields = new VariableCollection<Field>();
    }

    public override bool IsAssignableFrom(TypeBase type)
    {
        CodeClassType otherClassType = type as CodeClassType;

        if (otherClassType == null)
        {
            return false;
        }

        if (otherClassType == this)
        {
            return true;
        }
        else
        {
            return IsAssignableFrom(otherClassType.BaseType);
        }
    }

}

miniSharp不支持显式类型转换，而唯一支持的隐式类型转换是子类引用到父类引用的转换。

除了自定义类型之外，我们还需要表示数组类型和基元类型（int和bool），简陋地如下处理：

public class PrimaryType : TypeBase
{
    public static readonly PrimaryType Int = new PrimaryType() { Name = "int" };
    public static readonly PrimaryType Boolean = new PrimaryType() { Name = "bool" };
    public static readonly PrimaryType String = new PrimaryType() { Name = "string" };
    public static readonly PrimaryType Void = new PrimaryType() { Name = "void" };

    public static readonly PrimaryType Unknown = new PrimaryType() { Name = null };

    public override bool IsAssignableFrom(TypeBase type)
    {
        if (this == type)
        {
            return true;
        }
        else
        {
            return false;
        }

    }
}

public class ArrayType : TypeBase
{
    public TypeBase ElementType { get; set; }

    public static readonly ArrayType IntArray = new ArrayType() { Name = "int[]", ElementType = PrimaryType.Int };
    public static readonly ArrayType StrArray = new ArrayType() { Name = "string[]", ElementType = PrimaryType.String };

    public override bool IsAssignableFrom(TypeBase type)
    {
        CodeClassType elementClassType = ElementType as CodeClassType;
        ArrayType arrayType = type as ArrayType;

        if (elementClassType != null && arrayType != null)
        {
            return elementClassType.IsAssignableFrom(arrayType.ElementType);
        }

        return false;
    }
}

实际上C#会将int和bool直接映射到System.Int32以及System.Boolean结构体。我们的miniSharp不仅仅要翻译成托管代码，所以并没有采用这个规定，但在生成IL的时候仍然做这样的特殊处理。最后因为miniSharp并不支持引用外部程序集，所以我也没有将类型表独立出来，而是将类型信息存储在每个表示class的语法树节点上，以方便语义分析时访问。

语义分析的第二个主要任务是找到所有标识符的定义。标识符在miniSharp里主要有：类名、字段名、方法名、参数名和本地变量名。遇到每个名称，我们必须解析出标识符表示的类、方法或字段的定义。比如下面这段代码：

class MyClass
{
    int a;

    public int Foo()
    {
        int a;
        a = 1;
        if (this.a > 0)
        {
            return this.a;
        }
        else
        {
            return a;
        }
    }
}

有一个字段叫a，在过程Foo中又定义了一个同名局部变量a。那么过程内的局部变量a就会覆盖字段的a，这句话的意思是标识符“a”在Foo中将表示局部变量，而不是同名字段。在语义分析里，我们遇到每一个可能代表变量的标识符时，都要按照一套预先设定的规则来寻找其定义。比如按照如下顺序：

搜索当前的本地符号表，其中包括当前作用域中定义的本地变量和方法参数
搜索当前类的字段

如果类的字段不仅仅是private的话，如果类还允许定义属性的话，这里的规则还要多好几条。所幸miniSharp只用以上两条就够了。我们看看怎么表示本地符号表。

public class VariableCollection<T> : KeyedCollection<string, T> where T : VariableInfo
{
    private Stack<HashSet<string>> m_levelStack;
    public int m_Levels;

    public VariableCollection()
    {
        m_Levels = 0;
        m_levelStack = new Stack<HashSet<string>>();
    }

    protected override string GetKeyForItem(T item)
    {
        return item.Name;
    }

    public void PushLevel()
    {
        m_levelStack.Push(new HashSet<string>());
        m_Levels++;
    }

    public void PopLevel()
    {
        if (m_Levels == 0)
        {
            throw new InvalidOperationException();
        }

        var keysInLevel = m_levelStack.Pop();
        m_Levels--;

        foreach (var key in keysInLevel)
        {
            Remove(key);
        }
    }

    protected override void InsertItem(int index, T item)
    {
        base.InsertItem(index, item);

        if (m_Levels > 0)
        {
            var keysInLevel = m_levelStack.Peek();
            keysInLevel.Add(GetKeyForItem(item));
        }


    }
}

为了简便处理这里所用的数据结构都比较粗糙。但基本思想是使用一个Stack，在进入一个新的作用域（大括号包围的语句块）时压入一个新的HashSet，储存这一作用域内声明的变量。当作用域结束时弹出一个HashSet，这个作用域内的变量就从表里删除了。所以，miniSharp允许两个不互相嵌套的语句块内定义同名变量，但不允许在同一个方法内的语句块内覆盖语句块外定义的变量或形式参数。

接下来我们要讨论方法重载选取的问题。这是miniSharp中唯一一个稍微有些复杂性的语义。miniSharp允许同一个类多个方法具有相同的方法名，只要他们的形式参数表的类型不完全一样即可。而判断一个方法调用表达式到底调用的是哪个方法，一共分为以下几个步骤。

第一步，找到当前类中所有签名相符的方法。miniSharp和C#一样，当前类中的方法具有比父类更高的优先级。而VB则采取当前类和父类相同优先级（使用Overloads关键字时）。所以miniSharp也要先在当前类中搜索合适的候选。第二个条件是签名相符，它的定义是方法调用的表达式与候选方法的名称相同，参数列表长度一致，并且方法调用的表达式列表中的每一个表达式的类型，都能隐式转换成候选方法参数表中对应位置参数的类型。稍微形式化一下，就是方法F(T1, T2, T3,…,Tn)是调用表达式C(E1, E2, E3,… Em)的签名相符候选方法的条件是F.Name = C，m = n并且对所有i从1到n满足Ti.IsAssignableFrom(typeof(Ei))。
第二步，所有签名相符的候选方法中，找到一个最佳候选。如果有两个候选方法P(P1, P2,…,Pn)和Q(Q1, Q2,…,Qn)，那么我们说P比Q更佳当且仅当：P的每一个参数类型都比Q的相应参数类型更好或至少一样好，同时Q的每一个参数类型都不比P的相应参数类型更好。如果P和Q各自有一些参数类型比对方更好，那么就视为P和Q条件一致，无法做出判断（有歧义）。
调用表达式列表项E所对应的候选方法参数类型TP比TQ更好意味着：TP与typeof(E)相等但TQ与typeof(E)不相等；或者TQ.IsAssignableFrom(TP)，这意味着TP比TQ更“具体”一些。如果TP和TQ之间无法相互隐式转换，或者两者是相同的类型，则视为无法区分。
如果在当前类中没有符合条件的候选，则对父类重复以上步骤。

真正C#的方法重载判断大体上也是这个步骤，但还要更加复杂得多。因为C#还有param数组型参数，可选参数，命名参数，泛型方法等语法。这里C#的Spec整整写了好几页纸来描述完整的规则。初看起来这段规则转换成代码很难写，所以我采用了一种取巧的方法：定义一个比较两个候选参数好坏的Comparer类，然后用Order By的方式对候选参数进行排序。Comparer类如下：

public class MethodOverloadingComparer : IComparer<Method>
{
    private IList<Expression> m_expressionList;

    public MethodOverloadingComparer(IList<Expression> expressions)
    {
        Debug.Assert(expressions != null);
        m_expressionList = expressions;
    }

    public int Compare(Method x, Method y)
    {
        //step 1. find one with better conversion.
        int lastComparisonResult = 0;
        for (int i = 0; i < m_expressionList.Count; i++)
        {
            int result = CompareConversion(x.Parameters[i].Type, y.Parameters[i].Type, m_expressionList[i]);

            if (lastComparisonResult < 0 && result > 0 || lastComparisonResult > 0 && result < 0)
            {
                //none is better
                return 0;
            }
            else if (result != 0)
            {
                lastComparisonResult = result;
            }
        }

        return lastComparisonResult;
    }

    private int CompareConversion(TypeBase leftTarget, TypeBase rightTarget, Expression source)
    {
        if (leftTarget == rightTarget)
        {
            //same type, no better one
            return 0;
        }
        else if (leftTarget == source.ExpressionType && rightTarget != source.ExpressionType)
        {
            //left is better;
            return -1;
        }
        else if (leftTarget != source.ExpressionType && rightTarget == source.ExpressionType)
        {
            //right is better;
            return 1;
        }
        else
        {
            if (leftTarget.IsAssignableFrom(rightTarget))
            {
                //right is more specific
                return 1;
            }
            else if(rightTarget.IsAssignableFrom(leftTarget))
            {
                //left is more specific
                return -1;
            }
            else
            {
                //both are bad
                return 0;
            }
        }
    }
}

最后，我们要将这一系列步骤组合到一起。由于miniSharp的类可以以任何顺序定义，一个类中的方法也可以以任何顺序定义，调用时并不受任何限制。所以我们无法只用一次抽象语法树的遍历来完成语义分析。我采用的做法是分成三次遍历，前两次分别对类的生命和成员的声明进行解析并构建符号表（类型和成员），第三次再对方法体进行解析。这样就可以方便地处理不同顺序定义的问题。总的来说，三次遍历的任务是：

第一遍：扫描所有class定义，检查有无重名的情况。
第二遍：检查类的基类是否存在，检测是否循环继承；检查所有字段的类型以及是否重名；检查所有方法参数和返回值的类型以及是否重复定义（签名完全一致的情况）。
第三遍：检查所有方法体中语句和表达式的语义。

因为上一次抽象语法树的设计已经采用了Visitor模式，所以以上三个阶段的语义分析可以分别写成三个Visitor来进行处理。语义分析模块同时还要报告所有语义错误。下面我给出第一阶段的Visitor实现供大家参考：

public class TypeDeclResolver : AstVisitor
{
    private TypeCollection m_types;
    private CompilationErrorManager m_errorManager;

    private const int c_SE_TypeNameDuplicates = 301;
    
    public void DefineErrors()
    {
        m_errorManager.DefineError(c_SE_TypeNameDuplicates, 0, CompilationStage.SemanticAnalysis,
            "The program has already defined a type named \'{0}\'.");
    }

    public TypeDeclResolver(CompilationErrorManager errorManager)
    {
        m_errorManager = errorManager;
        m_types = new TypeCollection();
    }

    public override AstNode VisitProgram(Program ast)
    {
        Visit(ast.MainClass);

        foreach (var cd in ast.Classes)
        {
            Visit(cd);
        }

        return ast;
    }

    public override AstNode VisitMainClass(MainClass ast)
    {
        //main class must be the first class.
        Debug.Assert(m_types.Count == 0);
        var name = ast.Name.Value;

        var mainclassType = new CodeClassType() { Name = name, IsStatic = true };

        m_types.Add(mainclassType);
        ast.Type = mainclassType;

        return ast;
    }

    public override AstNode VisitClassDecl(ClassDecl ast)
    {
        var name = ast.Name.Value;

        if (m_types.Contains(name))
        {
            m_errorManager.AddError(c_SE_TypeNameDuplicates, ast.Name.Span, name);
            return ast;
        }

        var classType = new CodeClassType() { Name = name };

        m_types.Add(classType);
        ast.Type = classType;

        return ast;
    }

    public TypeCollection Types
    {
        get { return m_types; }
    }

}

其中的ErrorManager类是与词法、语法分析阶段共享的语法错误管理类，可以方便地随时定义和保存编译错误。为了减少语义分析的负担，我们规定只有语法分析阶段没有错误才进行语义分析，而且语义分析的三个阶段任何一步有语法错误都可以不再继续执行分析。

第二个阶段和第三个阶段的代码较长，我就不贴在这里了，大家可以下载我的代码自行观看。在此我只贴一个比较有代表性的Call表达式解析过程，方便大家理解上述方法重载的逻辑（但我还没有仔细进行过测试，所以不保证这段代码完全没有bug）

public override AstNode VisitCall(Call ast)
{
    // step 1. resolve each argument
    foreach (var argument in ast.Arguments)
    {
        Visit(argument);
    }

    //step 2. resolve object
    Visit(ast.Target);

    CodeClassType targetType = ast.Target.ExpressionType as CodeClassType;

    if (targetType == null)
    {
        m_errorManager.AddError(c_SE_MethodMissing, ast.Method.MethodName.Span, ast.Method.MethodName.Value);
        ast.ExpressionType = PrimaryType.Unknown;
        return ast;
    }

    //step 3. resolve method
    ResolveMethod(ast, targetType);

    //step 4. TODO: add type conversion node to arg implicit conversions

    return ast;
}

private void ResolveMethod(Call ast, CodeClassType targetType)
{
    if (targetType == null)
    {
        m_errorManager.AddError(c_SE_MethodMissing, ast.Method.MethodName.Span, ast.Method.MethodName.Value);
        ast.ExpressionType = PrimaryType.Unknown;

        return;
    }

    // step 1: collect candidates from current type
    var candidates = (from m in targetType.Methods
                      where String.Equals(m.Name, ast.Method.MethodName.Value, StringComparison.InvariantCulture) 
                      && m.Parameters.Count == ast.Arguments.Count
                      select m).ToArray();

    if (candidates.Length == 0)
    {
        ResolveMethod(ast, targetType.BaseType);
        return;
    }

    // step 2: remove unqualifed candidates
    List<Method> qualifiedCandidates = new List<Method>();
    foreach (var candidate in candidates)
    {
        bool isQualified = true;
        for (int i = 0; i < candidate.Parameters.Count; i++)
        {
            if (!candidate.Parameters[i].Type.IsAssignableFrom(ast.Arguments[i].ExpressionType))
            {
                isQualified = false;
                break;
            }
        }

        if (isQualified) qualifiedCandidates.Add(candidate);
    }

    if (qualifiedCandidates.Count == 0)
    {
        ResolveMethod(ast, targetType.BaseType);
        return;
    }

    // step 3: choose a "best" one
    if (qualifiedCandidates.Count > 1)
    {
        var comparer = new MethodOverloadingComparer(ast.Arguments);
        qualifiedCandidates.Sort(comparer);

        var firstCandidate = qualifiedCandidates[0];
        var secondCandidate = qualifiedCandidates[1];

        if (comparer.Compare(firstCandidate, secondCandidate) < 0)
        {
            //choose first as the best one
            ast.Method.MethodInfo = firstCandidate;
            ast.ExpressionType = firstCandidate.ReturnType;
        }
        else
        {
            //ambiguous between first & second
            m_errorManager.AddError(c_SE_MethodAmbiguous, ast.Method.MethodName.Span, 
                firstCandidate.GetSignatureString(), secondCandidate.GetSignatureString());
            ast.ExpressionType = PrimaryType.Unknown;
        }
    }
    else
    {
        ast.Method.MethodInfo = qualifiedCandidates[0];
        ast.ExpressionType = qualifiedCandidates[0].ReturnType;
    }
}

经过完善的语义分析，我们就得到了一个具有完整类型信息，并且没有语义错误的AST。下一阶段我们就可以开始为编程语言生成代码了。首先我们将从生成CIL开始，做一个和C#类似的托管语言。之后我们将深入代码生成的各项技术，亲自动手生成目标机器的代码。敬请期待下一篇！

希望大家继续关注我的VBF项目：https://github.com/Ninputer/VBF 和我的微博：http://weibo.com/ninputer 多谢大家支持！

自己动手开发编译器（十二）生成托管代码

前一阶段我们完成了编译器中的重要阶段——语义分析。现在，程序中的每一个变量和类型都有其正确的定义；每一个表达式和语句的类型都是合法的；每一处方法调用都选择了正确的方法定义。现在即将进入下一个阶段——代码生成。代码生成的最终目的，是生成能在目标机器上运行的机器码，或者可以和其他库链接在一起的可重定向对象。代码生成，和这一阶段的各个优化手段，统称为编译器的后端。目前大部分编译器，在代码生成时，都倾向于先将前段解析的结果转化成一种中间表示，再将中间表示翻译成最终的机器码。比如Java语言会翻译成JVM bytecode，C#语言会翻译成CIL，再经由各自的虚拟机执行；IE9的javascript也会先翻译成一种bytecode，再由解释器执行或者进行JIT翻译；即使静态编译的语言如C++，也存在先翻译成中间语言，再翻译成最终机器码的过程。中间表示也不一定非得是一种bytecode，我们在语法分析阶段生成的抽象语法树（AST）就是一种很常用的中间表示。.NET 3.5引入的Expression Tree正是采用AST作为中间表示的动态语言运行库。那为什么这种做法非常流行呢？因为翻译中中间语言有如下好处：

使用中间语言可以良好地将编译器的前端和后端拆分开，使得两部分可以相对独立地进行。
同一种中间语言可以由多种不同的源语言编译而来，而又可以针对多种不同的目标机器生成代码。CLR的CIL就是这一特点的典型代表。
有许多优化可以直接针对中间语言进行，这样优化的结果就可以应用到不同的目标平台。

我们这次动手编写编译器，自然也少不了中间语言这一步。为了达到亲手实践的目的，我们将会自己定义中间语言，但是那样的话想要把编译出的程序运行起来就还需要很多工作。为了提前体验运行目标代码的成就感，同时验证编译器前端的正确性，我们这次先将miniSharp编译成CLR的中间语言——CIL（Common IL，MSIL），并且就使用.NET自带的Reflection.Emit库来做。

首先来了解一下CIL的特点。CIL是一种bytecode，在.NET的程序集里他是二进制方式存在的。我们常常见到的是用ILDASM或者ILSpy反汇编而成的汇编形态。例如这一段：

.method public hidebysig newslot

instance int32 ComputeFac (

int32 num

) cil managed

{

// Method begins at RVA 0x2050

// Code size 30 (0x1e)

.maxstack 6

.locals init (

[0] int32

)

IL_0000: ldarg.1

IL_0001: ldc.i4.1

IL_0002: clt

IL_0004: brfalse IL_0010

IL_0009: ldc.i4.1

IL_000a: stloc.0

IL_000b: br IL_001c

IL_0010: ldarg.1

IL_0011: ldarg.0

IL_0012: ldarg.1

IL_0013: ldc.i4.1

IL_0014: sub

IL_0015: call instance int32 Fac::ComputeFac(int32)

IL_001a: mul

IL_001b: stloc.0

IL_001c: ldloc.0

IL_001d: ret

} // end of method Fac::ComputeFac

和机器语言相比，CIL是一种高度抽象的中间语言。程序集里有非常丰富的元数据，可以直接对应到源代码里的类和方法。而CIL仅仅用于描述方法体的逻辑。CIL较少反应出运行时真正发生在CPU上的事情，而更多地与源代码中的语句和表达式接近。所以我们说CIL是一种相当高级的中间语言。CIL是一种栈式机。要注意的是，这里的“栈”与运行时的内存堆和栈的“栈”没有任何关系。CIL的栈是一个运算栈（evaluation stack），它在运行时实际是不存在的，但我们必须要在理解CIL运行过程时想象它存在。运算栈在CIL中的作用是保存运算的中间结果，这与寄存器机的寄存器有些类型。CIL的每一条指令都只能对运算栈顶进行操作。

看上面的IL代码，第一行ldarg.1指令的作用是将1号实参加载到运算栈的栈顶上，第二条ldc.i4.1指令是将32位整型常量1压入运算栈。注意“ldc.i4.1”是一条指令，它是不带参数的。IL中有许多这种缩短格式的指令，以消除或减少指令参数，从而减少目标代码的体积。经过这两条指令后，运算栈中有两个值：栈顶是32位常量1，其下面是方法的1号参数值。这时遇到指令clt，这条指令会将运算栈先后弹出两个值，并比较它们的大小，如果后弹出的值小于先弹出的值，则将32位整数“1”压入运算栈，反之则将“0”压入运算栈。假设该方法第一个实参传的是“0”，以上过程如图所示：

执行指令

运算栈

空

ldarg.1

压入参数值0

ldc.i4.1

压入常数1

clt

弹出1

弹出0

比较0 < 1，所以压入1

接下来的brfalse指令又会弹出运算栈顶的值，并根据这个值决定是否要进行跳转。以此类推，即可理解每条指令的作用。任何一条IL指令总会将一些值压入栈；或者从栈中弹出一些值；或者先弹出一些值，再压入一些值。这些不同的动作称为这条指令的栈转换行为。每条指令都有固定的栈转换行为，只要理解了栈转换行为，就等于完全理解一条IL指令。

MSDN中OpCodes类的帮助中详细介绍了每一条指令的栈转换规则。当我们需要了解CIL指令的含义时，这个帮助就是最好的资料。简单了解了CIL与运算栈之后，大部分指令的行为都是很好理解的。我这里稍微解释一下某些特殊的规则。

在CIL指令表当中大家会看到许多指令有多个版本。比如ldloc指令用于将局部变量加载到运算栈顶。这个指令就有ldloc、ldloc.s、ldloc.0、ldloc.1等不同的版本。这其中的ldloc是该指令的长版本，其他指令则是短版本。因为CIL是bytecode，所以这些指令在程序集中都是一个或两个字节的代码。ldloc长版本指令自身编码为两个字节（FE 06），而且它需要一个uint16（两字节）的参数，所以它一共需要占四个字节的空间。我们知道一个方法很少有65536这么多个本地变量，很多也就是1-2个，有十几个的已经算是非常多了。所以都用这么长的指令非常浪费。短版本ldloc.s自身编码只有一个字节（11），而且它的参数是uint8（一个字节），该指令只占2个字节的空间。但是ldloc.s只能加载索引在0-255范围内的本地变量。最后，针对最常用的头4个本地变量，还有四个最短版本。比如ldloc.0，仅占一个字节的编码（06）没有参数。我们在生成代码的时候需要根据访问本地变量的索引来选取不同的指令：

private void EmitLoadLocal(int locIndex)
{
    switch (locIndex)
    {
        case 0:
            m_ilgen.Emit(OpCodes.Ldloc_0);
            break;
        case 1:
            m_ilgen.Emit(OpCodes.Ldloc_1);
            break;
        case 2:
            m_ilgen.Emit(OpCodes.Ldloc_2);
            break;
        case 3:
            m_ilgen.Emit(OpCodes.Ldloc_3);
            break;
        default:
            if (locIndex <= 255)
            {
                m_ilgen.Emit(OpCodes.Ldloc_S, (byte)locIndex);
            }
            else
            {
                m_ilgen.Emit(OpCodes.Ldloc, (short)locIndex);
            }
            break;
    }
}

下面我们就开始为miniSharp语言编写CIL代码生成器。和语义分析阶段类似，我们只需要编写一个AST的Visitor实现即可。要注意，我们不仅需要生成方法的IL代码，还需要生成程序集、模块、类、方法、构造函数、字段等定义。Reflection.Emit为这些结构提供了各类Builder类型，使用非常方便，但必须注意一些规则：

为了生成exe，程序集入口的PEFileKind应当是ConsoleApplication（默认是Dll）。
每个类对应一个TypeBuilder，生成一个类之后必须调用其CreateType方法真正生成类型。一个类CreateType之前，它的父类必须已经CreateType过才行。所以要按照继承顺序创建各个类。
TypeBuilder上也有Type类的所有方法，如GetConstructor、GetMethod之类，但只有当TypeBuilder调用过CreateType之后这些方法才能使用。所以我们必须自己保存未完成类型的成员信息。

下面的代码展示了按照类继承顺序生成各类的代码：

public override AstNode VisitProgram(Program ast)
{
    List<ClassDecl> classesInHierarchyOrder = new List<ClassDecl>();

    var topBaseClasses = from c in ast.Classes where c.BaseClass.Type == null select c;
    classesInHierarchyOrder.AddRange(topBaseClasses);

    while (classesInHierarchyOrder.Count < ast.Classes.Count)
    {
        foreach (var c in ast.Classes)
        {
            foreach (var b in classesInHierarchyOrder.ToArray())
            {
                if (c.BaseClass.Type == b.Type)
                {
                    classesInHierarchyOrder.Add(c);
                }
            }
        }
    }

    foreach (var c in classesInHierarchyOrder)
    {
        Visit(c);
    }

    Visit(ast.MainClass);

    return ast;
}

下面展示MainClass的生成方法。这里用了一个技巧，即static class = abstract + sealed。

public override AstNode VisitMainClass(MainClass ast)
{
    m_currentType = m_module.DefineType(
        ast.Type.Name, TypeAttributes.Class | TypeAttributes.Abstract | TypeAttributes.Sealed);
    m_currentMethod = m_currentType.DefineMethod(
        "Main", MethodAttributes.Public | MethodAttributes.Static, typeof(void), new[] { typeof(string[]) });

    m_ilgen = m_currentMethod.GetILGenerator();

    foreach (var s in ast.Statements)
    {
        Visit(s);
    }

    m_ilgen.Emit(OpCodes.Ret);

    m_currentType.CreateType();
    m_mainMethod = m_currentMethod;
    return ast;
}

搞定类和方法之后，就开始要生成方法体的代码了。这一部分最主要的翻译对象是语句和表达式，有一个要注意的规则：

表达式执行之后，该表达式的结果应当压入运算栈。
语句执行后，运算栈应当被清空。

如果不满足上述规则，生成的代码就很有可能是错的，要非常小心。下面展示两个最基本的语句——if else和while的生成方法。

public override AstNode VisitIfElse(IfElse ast)
{
    var ifBlock = m_ilgen.DefineLabel();
    var elseBlock = m_ilgen.DefineLabel();
    var endif = m_ilgen.DefineLabel();

    Visit(ast.Condition);
    //the e-stack should have a bool value
    m_ilgen.Emit(OpCodes.Brfalse, elseBlock);

    //if block
    m_ilgen.MarkLabel(ifBlock);
    Visit(ast.TruePart);
    m_ilgen.Emit(OpCodes.Br, endif);

    //elseblock
    m_ilgen.MarkLabel(elseBlock);
    Visit(ast.FalsePart);

    //after if
    m_ilgen.MarkLabel(endif);

    return ast;
}

public override AstNode VisitWhile(While ast)
{
    var beforeWhile = m_ilgen.DefineLabel();
    var afterWhile = m_ilgen.DefineLabel();

    m_ilgen.MarkLabel(beforeWhile);

    Visit(ast.Condition);
    //the e-stack should have a bool value
    m_ilgen.Emit(OpCodes.Brfalse, afterWhile);

    Visit(ast.LoopBody);

    m_ilgen.Emit(OpCodes.Br, beforeWhile);
    m_ilgen.MarkLabel(afterWhile);

    return ast;
}

这里if语句采用的是brfalse指令。实际上CIL中有许多条件分支语句，如blt、bge等等，可直接翻译if ( a > b )这样的结构，效率更高。此次我采用偷懒的做法，全都用clt, cgt这样的有返回值的指令来计算大于小于等比较运算，但后统一用brfalse来执行条件跳转。上面这段代码还展示了Label在Emit API中的使用方法。翻译赋值语句和数组赋值语句时要注意，为本地变量、本地参数或类的字段赋值时采用的指令和栈转换动作均有所不同，需要分别考虑。比如ldfld之前必须先将目标对象压栈，如果是this的话应该用ldarg.0指令（实例方法默认第0个参数是this引用）

再来演示两个基本表达式的翻译，二元运算符和方法调用：

public override AstNode VisitBinary(Binary ast)
{
    //push operands
    Visit(ast.Left);
    Visit(ast.Right);

    switch (ast.Operator)
    {
        case BinaryOperator.Add:
            m_ilgen.Emit(OpCodes.Add);
            break;
        case BinaryOperator.Substract:
            m_ilgen.Emit(OpCodes.Sub);
            break;
        case BinaryOperator.Multiply:
            m_ilgen.Emit(OpCodes.Mul);
            break;
        case BinaryOperator.Divide:
            m_ilgen.Emit(OpCodes.Div);
            break;
        case BinaryOperator.Less:
            m_ilgen.Emit(OpCodes.Clt);
            break;
        case BinaryOperator.Greater:
            m_ilgen.Emit(OpCodes.Cgt);
            break;
        case BinaryOperator.Equal:
            m_ilgen.Emit(OpCodes.Ceq);
            break;
        case BinaryOperator.LogicalAnd:
            m_ilgen.Emit(OpCodes.And);
            break;
        case BinaryOperator.LogicalOr:
            m_ilgen.Emit(OpCodes.Or);
            break;
        default:
            m_ilgen.Emit(OpCodes.Pop);
            m_ilgen.Emit(OpCodes.Pop);
            m_ilgen.Emit(OpCodes.Ldc_I4_0);
            break;
    }
    return ast;
}

public override AstNode VisitCall(Call ast)
{
    var methodRInfo = GetClrMethod(ast.Method.MethodInfo);

    //push target object
    Visit(ast.Target);

    //push arguments
    foreach (var arg in ast.Arguments)
    {
        Visit(arg);
    }

    m_ilgen.EmitCall(OpCodes.Call, methodRInfo, null);

    return ast;
}

注意这里翻译&&和||运算符时没有生成“短路”操作，因此与C#的语义稍有不同。如果要支持短路也非常容易，大家可以亲自实验一下。翻译二元运算符时，如果语义分析正确无误，不应该进入default分支。所以在此只进行一种错误处理的逻辑，它仍然要保持运算栈的平衡。翻译方法调用时，应当先将方法的目标对象压栈，然后从左到右依次压入每个实参，最后调用call指令完成调用。

所有的TypeBuilder都调用CreateType之后，最后调用AssemblyBuilder.Save方法，就可以将目标程序集写入磁盘了！

public void Create(Ast.AstNode ast, string url)
{
    Visit(ast);

    Debug.Assert(m_assembly != null);

    m_assembly.SetEntryPoint(m_mainMethod, PEFileKinds.ConsoleApplication);
    m_assembly.Save(url);
}

现在终于可以试试看了，我们来编译一段miniSharp代码试试：（阶乘计算）

static class 程序入口
{
    //中文注释
    public static void Main(string[] args)
    {
        Fac o;
        o = new Fac();
        System.Console.WriteLine(o.ComputeFac(8));
    }
}

class Fac
{
    public int ComputeFac(int num)
    {
        int num_aux;
        if (num < 1)
            num_aux = 1;
        else
            num_aux = num * (this.ComputeFac(num - 1));

        return num_aux;
    }
}

生成的程序集：

运行结果：

看到自己的编译器正确地编译源代码，是否觉得很有成就感呢？如果只想做一个托管编程语言，那么生成CIL就是最后一步了。但是CLR帮我们做的实在太多了，不能满足我们的求知欲。所以，下一阶段我们将亲手实现从中间语言到目标机器代码的编译器后端部分。从下一篇开始本系列的间隔时间会变得比较长而且不确定，因为我自己也需要一边学习一边实践。

希望大家继续关注我的VBF项目：https://github.com/Ninputer/VBF 和我的微博：http://weibo.com/ninputer 多谢大家支持！