自己动手开发编译器

2011年8月2日

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

摘要: 前一阶段我们完成了编译器中的重要阶段——语义分析。现在，程序中的每一个变量和类型都有其正确的定义；每一个表达式和语句的类型都是合法的；每一处方法调用都选择了正确的方法定义。现在即将进入下一个阶段——代码生成。代码生成的最终目的，是生成能在目标机器上运行的机器码，或者可以和其他库链接在一起的可重定向对象。代码生成，和这一阶段的各个优化手段，统称为编译器的后端。目前大部分编译器，在代码生成时，都倾向于...阅读全文

posted @ 2011-08-02 14:57 装配脑袋 阅读(6334) 评论(38) 编辑

2011年7月22日

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

摘要: 上回我们已经用VBF的Parsers.Combinators库生成了miniSharp的语法分析器，并且能够将miniSharp的源代码翻译成抽象语法树（AST）。这一回我们要继续进行下一步——语义分析。就目前大家接触的编程语言，如C#、VB、C++来说，语义分析是编译器前端最复杂的部分。因为这些编程语言的语义都非常复杂。语义分析不像之前词法分析、语法分析那样，有一些特定的工具来帮助。这一部分通常...阅读全文

posted @ 2011-07-22 11:15 装配脑袋 阅读(7410) 评论(14) 编辑

2011年7月8日

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

摘要: 经过前面四篇的铺垫，我们终于拥有了编写语法分析器的强大工具，现在可以正式开发一门编程语言的语法分析器了。我们先来定义miniSharp的语法规则，然后根据LL文法的特点进行一些调整，最后借助解析器组合子生成完整的语法分析器。 miniSharp语言是C#的一个小子集，然而它仍然具有一门完整编程语言的所有要素，而且仍然是一种面向对象的语言。我们把miniSharp的语法分成三类——声明结构、语句和...阅读全文

posted @ 2011-07-08 01:19 装配脑袋 阅读(7308) 评论(21) 编辑

2011年7月3日

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

摘要: 上回我们用函数式编程的方法，结合Linq语法，建立了一套解析器组合子方案，并能成功解析自定义文法的输入字符串。但是，上次做成的解析器组合子有个重要的功能没有完成——错误报告。作为编程语言的语法分析器，不能在遇到语法错误的时候简单地返回null，那样程序员就很难修复代码中的语法错误。我们需要的是准确报告语法错误的位置，更进一步，是程序中所有的语法错误，而不仅仅是头一个。后者要求解析器具有错误恢复的能...阅读全文

posted @ 2011-07-03 22:16 装配脑袋 阅读(5396) 评论(13) 编辑

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

摘要: 上回我们说到手写递归下降语法分析器。手写递归下降的方式是目前很多编译器采用的方式，如果你想写一个商业质量的编译器，这是首选的方法。但是，一个完善的递归下降解析器需要的代码量也不少，如果要进行错误报告、错误恢复等等那代码量就更大了。作为懒人，我们有时想要一些小型语言的解析器，最好写起来像直接写文法的产生式一样，最好连错误报告和错误恢复也一并自动解决，可能吗？在过去很长一段时间，人们采用的方法是使用解...阅读全文

posted @ 2011-06-26 20:28 装配脑袋 阅读(6740) | 评论 (20) 编辑

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

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

posted @ 2011-06-21 00:22 装配脑袋 阅读(8532) | 评论 (22) 编辑

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

摘要: 上回我们已经学习了语法分析第一阶段——词法分析的原理和工具，介绍了正则表达式、正则语言和DFA等工具。今次我们要开始涉及编译器前端最重要的阶段——语法分析。简单而言，这一步就要完整地分析整个编程语言的语法结构。上回说到词法分析的结果是将输入的字符串分解成一个个的单词流，也就是诸如关键字、标识符这样有特定意义的单词。一种完整的编程语言，必须在此基础上定义出各种声明、语句和表达式的语法规则。观察我们所...阅读全文

posted @ 2011-06-18 20:27 装配脑袋 阅读(6793) | 评论 (16) 编辑

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

摘要: 这几天比较忙，让大家久等了。但是我语法分析篇还需要一些准备，所以今天带来一个特别娱乐项目。其实也正好想多举一些例子，介绍VBF.Compilers.Scanner库的使用方法。今天的问题来自于一道腾讯的PHP面试题，原题如下： 我们碰到了大麻烦，一个新来的传教士惹恼了上帝，上帝很愤怒，要求我们把圣经背熟，直至他说哪个单词，我们就要飞快的回答出这个单词在第几行第几个单词位置。听说你是个优秀的程序员，...阅读全文

posted @ 2011-06-16 21:30 装配脑袋 阅读(6287) | 评论 (16) 编辑

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

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

posted @ 2011-06-13 21:54 装配脑袋 阅读(7164) | 评论 (18) 编辑

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

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

posted @ 2011-06-12 01:36 装配脑袋 阅读(7636) | 评论 (20) 编辑

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

摘要: 上回我们说到用正则表达式来表示词法分析中的单词规则。正则表达式的规则很容易理解，但是正则表达式并不能直接用来解析字符串，我们还要引入一种适合转化为计算机程序的模型。今天我们引入的这种模型就叫做有穷自动机（finite automation，FA）,有时也叫有穷状态机（finite state machine）。有穷自动机首先包含一个有限状态的集合，还包含了从一个状态到另外一个状态的转换。有穷自动机...阅读全文

posted @ 2011-06-10 22:10 装配脑袋 阅读(10818) | 评论 (54) 编辑

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

摘要: 从今天这一篇起，我们就来正式揭开编译器的奥秘。首先我们接触到的模块是词法分析器，也叫词法扫描器，代码里我常常叫它Scanner。昨天我稍微解释了一下为什么需要将词法分析单独分离出来，今天来回顾一下这个问题。请看下面这段C#代码： 即使没有语法高亮，这段代码也可以很明显地分成好几部分。首先是关键字string，之后是变量名str，然后是等号=，接下来是一个字符串字面常量”Hello World”。现...阅读全文

posted @ 2011-06-08 21:12 装配脑袋 阅读(11206) | 评论 (50) 编辑

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

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

posted @ 2011-06-07 21:29 装配脑袋 阅读(12248) | 评论 (32) 编辑

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

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

posted @ 2011-06-06 22:05 装配脑袋 阅读(16393) | 评论 (90) 编辑