一个编译器的实现0

前一阵做了个编译器（仅词法分析、语法分析、部分语义分析，所以说是前端），拿来分享一下，如有错误，欢迎批评指教！

整个代码库具有如下功能：

提供编译器所需基础数据结构、计算流程框架类，可供继承使用；
提供基础数据结构的可视化控件；
提供类似YACC的词法分析器、语法分析器自动生成功能；
提供Winform程序，集成和扩展上述功能，方便研究和应用。

本文及其后续系列将逐步给出所有工程源代码（visual studio 2010版本）。

上图展示一下先。

图1 词法、语法分析和结点匹配

图2 自动生成词法分析器、语法分析器

图3 自动生成词法分析器、语法分析器

图4 自动打印语法树

为了说清楚编译器这种东西，我想最好还是举例。

比如我们要为数学计算的表达式（Expression）设计一个编译器。（当然有很多方法可以实现读取数学表达式并计算结果的算法，未必使用编译原理）

来看一些数学表达式的例子：

37

19 * 19 - 18 * 18

(19 + 18) * (19 - 18)

18 +19 / (18 / 18)

a  + (a + 1) + (a + 2) + (a + 3)

好了够了，大家能够了解本文所讨论的Expression的范围了。那么我们引入“文法”（Grammar）的概念。Expression的文法就是这样的：

<Expression> ::= <Multiply> <PlusOpt>;
<PlusOpt> ::= "+" <Multiply> | "-" <Multiply> | null;
<Multiply> ::= <Unit> <MultiplyOpt>;
<MultiplyOpt> ::= "*" <Unit> | "/" <Unit> | null;
<Unit> ::= identifier | "(" <Expression> ")" | number;

我们分别展示出上述几个例子用文法展开的过程。

37: <Expression>

=> <Multiply> <PlusOpt>

=> <Unit> <MultiplyOpt>

=> number

19 * 19 - 18 * 18: <Expression>

=> <Multiply> <PlusOpt>

=> <Unit> <MultiplyOPt> "-" <Multiply>

=> number "*" <Unit> "-" <Unit> <MultiplyOpt>

=> number "*" number "-" number "*" <Unit>

=> number "*" number "-" number "*" number

(19 + 18) * (19 - 18): <Expression>

=> <Multiply> <PlusOpt>

=> <Unit> <MultiplyOpt>

=> "(" <Expression> ")" "*" <Unit>

=> "(" <Multiply> <PlusOpt> ")" "*" "(" <Expression> ")"

=> "(" <Unit> <MultiplyOpt> "+" <Multiply> ")" "*" "(" <Multiply> <PlusOpt> ")"

=> "(" number "+" <Unit> <MultiplyOpt> ")" "*" "(" <Unit> <MultiplyOpt> "-" <Multiply> ")"

=> "(" number "+" number ")" "*" "(" number "-" number <MultiplyOpt> ")"

=> "(" number "+" number ")" "*" "(" number "-" number ")"

写到这里就，其余例子大家自己试试~如果写不出来，后面的部分可能就不太容易看了。（试试写写，很快就写的比较熟练了）

 

总结一下“文法”（Grammar）。文法就是描述Expression的构成的，和英语的语法类似吧。 有了文法，我们就可以写编译器了。

Expression的文法有5个式子，这5个式子就叫做“产生式”（Production），因为他们能从左边的结构产生（推导）出右边的结构来。一个文法至少有一个产生式，第一个产生式的左边的结点是初始结点，所有的推导都必须从初始结点（即第一个产生式）开始。

产生式（Production）左边叫做左部（左部只有始终一个结点），右边叫做右部（废话），中间用【::=】这个符号隔开。

右部由符号【|】分为若干部分，每一部分都是产生式可能推导出的一个结果，且每次只能选择其中一个进行推导。【null】表示什么也不推导出来。（这是个霸气的符号，不要觉得什么都不推导出来就不重要，恰恰相反，这个符号很重要）

为简化后文的说明，继续举例：<PlusOpt> ::= "+" <Multiply> | "-" <Multiply> | null;

对于这个产生式，其实是由三部分<PlusOpt> ::= "+" <Multiply>;和<PlusOpt> ::= "-" <Multiply>和<PlusOpt> ::= null;组成的，每一部分都称为一个“推导式”（Derivation）。

像【(19 + 18) * (19 - 18)】这样一个具体的“东西”，我们称之为一个“句子”（Sentence）。

明了了上述关于文法的东西，就可以进行编译器的设计了。

 

我们先搞搞清楚，编译器能做什么？以Expression的【19 * 19 - 18 * 18】为例，Expression的编译器首先要读取字符串格式的源代码，即：

1 var sentence = “19 * 19 - 18 * 18”;2 var expLexicalAnalyzer = new LexicalAnalyzerExpression();3 expLexicalAnalyzer.SetSourceCode(sentence);

 

然后，编译器进行词法分析，得到单词流（TokenList）。“流”这个东西，其实就是数组。

1 var tokens = expLexicalAnalyzer.Analyze();

在此例中，得到的单词流是这样的：

[19][Number]