学习编写一个编译器

Question

首选语言:C/C++,Java和Ruby.

我正在寻找一些有用的书籍/教程,如何编写自己的编译器只是为了教育目的.我最熟悉C/C++,Java和Ruby,所以我更喜欢涉及这三者之一的资源,但任何好的资源都是可以接受的.

Answer 1

资源清单:

• 用于编译器教育的Nanopass框架
• 高级编译器设计和实现 $
• 编译器构造的增量方法
• ANTLR 3.x视频教程
• 编译器设计基础
• 构建一个鹦鹉编译器
• 编译器基础知识
• 编译器构造 $
• 编译器设计与构建 $
• 使用C $ 编写编译器
• 制作口译员
• C中的编译器设计
• 编译器:原理,技术和工具 $ - 又名"龙书" ; 被广泛认为是编写编写的"书".
• 设计编译器 $
• 编程语言要点
• Flipcode文章存档(查找"由Jan Niestadt实现脚本引擎")
• Game Scripting Mastery $
• 如何在C#中从头开始构建虚拟机
• 实现功能语言
• 实现编程语言(使用BNFC)
• 使用C#4.0实现编程语言
• 解释器模式(在Design Patterns $中描述)指定了一种评估语言中句子的方法
• 语言实现模式:创建自己的特定领域和通用编程语言
• 让我们构建一个编译器由杰克·克伦肖-该PDF 版本(例子是帕斯卡,但信息是普遍适用的)
• 链接器和装载器 $(Google图书)
• Lisp in Small Pieces(LiSP) $
• LLVM教程
• ML $中的现代编译器实现 - 还有一个Java $和C $版本 - 被广泛认为是一本非常好的书
• 面向对象的编译器构造 $
• 解析技术 - 实用指南
• Oberon项目 - 请看第13章
• 编程个人电脑 $
• 编程语言:应用和解释
• Rabbit:Scheme的编译器
• 关于信任信任的思考 - 快速指南
• 为.NET框架编写自己的编译器 - 来自MSDN的快速教程
• 计算机程序的结构与解释
• 类型和编程语言
• 想编写编译器？ - 快速指南
• 用Ruby编写编译器

传说:

• 链接到PDF文件
• $链接到印刷书籍

Answer 2

我认为这是一个非常模糊的问题; 仅仅因为涉及的主题的深度.但是,编译器可以分解为两个独立的部分; 上半部分和下部分.上半部分通常采用源语言并将其转换为中间表示,下半部分负责平台特定的代码生成.

尽管如此,一个简单的方法来处理这个主题(我们在编译器类中使用的那个,至少)的一个想法是在上面描述的两个部分中构建编译器.具体来说,只需构建上半部分,您就可以全面了解整个过程.

只需执行上半部分,您就可以获得编写词法分析器和解析器的经验,并生成一些"代码"(我提到的中间表示).因此,它将采用您的源程序并将其转换为另一种表示形式并进行一些优化(如果您需要),这是编译器的核心.然后,下半部分将采用该中间表示并生成在特定体系结构上运行程序所需的字节.例如,下半部分将采用您的中间表示并生成PE可执行文件.

关于这个主题的一些书籍,我发现特别有用的是编译原理和技术(或龙书,由于封面上可爱的龙).它有一些很棒的理论,绝对能够以一种非常容易理解的方式涵盖无上下文语法.此外,为了构建词法分析器和解析器,您可能会使用*nix工具lex和yacc.并且无趣​​的是,这本名为" lex and yacc "的书在"龙书"中留下了这一部分.

Answer 3

我认为ML中的Modern Compiler Implementation是编写文本的最佳编译器.还有Java版本和C版本,根据您的语言背景,其中任何一个都可能更容易访问.本书包含了许多有用的基本材料(扫描和解析,语义分析,激活记录,指令选择,RISC和x86本机代码生成)和各种"高级"主题(编译OO和函数语言,多态,垃圾收集,优化和单个静态分配形式)进入相对较小的空间(~500页).

我更喜欢现代编译器实现到龙书,因为现代编译器实现调查较少的领域 - 而是它真正覆盖了编写一个认真,体面的编译器所需的所有主题.完成本书后,如果需要,您将准备好直接处理研究论文.

我必须承认我对Niklaus Wirth的编译器构造有一个严重的情有独钟.它可以在线获得PDF格式.我发现Wirth的编程美学很简单,但有些人发现他的风格太小(例如Wirth喜欢递归下降解析器,但大多数CS课程专注于解析器生成器工具; Wirth的语言设计相当保守.)编译器构造是一个非常简洁的蒸馏Wirth的基本想法,所以无论你喜欢他的风格与否,我强烈建议你阅读这本书.

Answer 4

我同意龙书参考; IMO,它是编译器构建的权威指南.但是,为一些核心理论做好准备.

如果你想要一本理论上较轻的书,Game Scripting Mastery可能是一本更好的书.如果你是编译器理论的全新手,它提供了一个更温和的介绍.它没有涵盖更实用的解析方法(选择非预测递归下降而不讨论LL或LR解析),并且我记得,它甚至没有讨论任何类型的优化理论.此外,它不是编译为机器代码,而是编译为应该在您也编写的VM上运行的字节码.

它仍然是一个不错的阅读,特别是如果你可以在亚马逊上以便宜的价格买到它.如果您只想轻松介绍编译器,Game Scripting Mastery并不是一个糟糕的方法.如果你想要预先硬核,那么你应该满足于龙书.

Answer 5

"让我们构建一个编译器"很棒,但它有点过时了.(我不是说它使它甚至有点不那么有效.)

或者看看SLANG.这类似于"让我们构建一个编译器",但它是一个更好的资源,特别是对于初学者.这附带一个pdf教程,它教你编译器采用7步法.添加quora链接,因为它具有到SLANG的所有各种端口的链接,在C++,Java和JS中,也是python和java中的解释器,最初使用C#和.NET平台编写.

Answer 6

如果您希望使用功能强大的高级工具而不是自己构建所有工具,那么浏览本课程的项目和阅读材料是一个不错的选择.它是Java解析器引擎ANTLR的作者的语言课程.您可以从实用程序员那里获得该课程的PDF格式.

本课程将介绍您在其他地方看到的标准编译器编译器:解析,类型和类型检查,多态,符号表和代码生成.几乎没有涉及的唯一事情就是优化.最终项目是一个编译C子集的程序.因为你使用像ANTLR和LLVM这样的工具,所以在一天之内编写整个编译器是可行的(我有一个存在的证据,虽然我的意思是~24小时).它使用现代工具在实际工程上很重,理论上要轻一点.

顺便说一句,LLVM简直太棒了.在许多情况下,您通常可以编译成汇编程序,而不是编译到LLVM的中间表示形式会更好.它是更高级别的跨平台,LLVM非常擅长从中生成优化的程序集.

Answer 7

如果你没有时间,我推荐Niklaus Wirth的"编译器构造"(Addison-Wesley.1996),这是一本你可以在一天内阅读的小册子,但它解释了基础知识(包括如何实现词法分析器,递归下降解析器,和你自己的基于堆栈的虚拟机).在那之后,如果你想要深度潜水,就像其他评论者所说的那样,没有办法绕过龙书.

Answer 8

您可能想要查看Lex/Yacc(或Flex/Bison,无论您想要什么称呼它们).Flex是一个词法分析器,它将解析和识别您语言的语义组件("标记"),Bison将用于定义解析每个标记时会发生什么.这可能是,但绝对不限于,打印出C代码,编译为C的编译器,或动态运行指令.

这个FAQ应该对你有所帮助,本教程看起来非常有用.

Answer 9

一般来说,编译器没有五分钟的教程,因为这是一个复杂的主题,编写编译器可能需要几个月的时间.你必须自己搜索.

通常会解释Python和Ruby.也许你想从口译员开始.这通常更容易.

第一步是编写正式的语言描述,即编程语言的语法.然后,您必须根据语法将要编译或解释的源代码转换为抽象语法树,这是计算机理解并可以操作的源代码的内部形式.此步骤通常称为解析,解析源代码的软件称为解析器.解析器通常由解析器生成器生成,该生成器将形式语法转换为源或机器代码.对于解析的一个好的,非数学的解释我推荐解析技术 - 实用指南.维基百科对解析器生成器进行了比较,您可以从中选择适合您的解析器生成器.根据您选择的解析器生成器,您将在Internet上找到教程,对于非常流行的解析器生成器(如GNU bison),还有书籍.

为您的语言编写解析器可能非常困难,但这取决于您的语法.所以我建议保持你的语法简单(不像C++); 一个很好的例子就是LISP.

在第二步中,抽象语法树从树结构转换为线性中间表示.作为一个很好的例子,Lua的字节码经常被引用.但中间表示真的取决于你的语言.

如果要构建解释器,则只需解释中间表示.你也可以及时编译它.我建议使用LLVM和libjit进行即时编译.要使语言可用,您还必须包含一些输入和输出函数以及可能的小型标准库.

如果要编译语言,那将会更复杂.您必须为不同的计算机体系结构编写后端,并从这些后端的中间表示中生成机器代码.我建议LLVM执行此任务.

有一些关于这个主题的书籍,但我不建议将它们都用于一般用途.他们中的大多数都太学术或太实际.没有"在21天内自学编写编写器",因此,您将需要购买几本书才能更好地理解整个主题.如果您在互联网上搜索,您会看到一些在线书籍和讲义.也许附近有一所大学图书馆,您可以在那里借阅编辑器的书籍.

如果你打算让你的项目变得严肃,我还建议你在理论计算机科学和图论中有很好的背景知识.计算机科学学位也会有所帮助.

Answer 10

看看下面的书.作者是ANTLR的创建者.

语言实现模式:创建自己的特定领域和通用编程语言.

Answer 11

一本尚未提出但非常重要的书是John Levine的"Linkers and Loaders".如果您没有使用外部汇编程序,则需要一种方法来输出可以链接到最终程序的目标文件.即使您使用的是外部汇编程序,您也可能需要了解重定位以及整个程序加载过程如何工作以构建工作工具.本书针对各种系统(包括Win32和Linux)收集了大量关于此过程的随机知识.

Answer 12

Dragon Book绝对是"构建编译器"一书,但如果您的语言不像当前一代语言那么复杂,您可能需要查看Design Patterns中的Interpreter 模式.

书中的例子设计了一种类似正则表达式的语言,并且经过深思熟虑,但正如他们在书中所说,它有助于思考整个过程,但实际上只对小语言有效.但是,使用这种模式为小语言编写解释器要比了解所有不同类型的解析器,yacc和lex等等要快得多...

Answer 13

如果您愿意使用LLVM,请查看:http://llvm.org/docs/tutorial/.它教您如何使用LLVM的框架从头开始编写编译器,并且不假设您对该主题有任何了解.

教程建议你编写自己的解析器和词法分析器等,但我建议你在得到想法后研究野牛和flex.它们让生活变得更加轻松.

Answer 14

我记得大约七年前我问过这个问题,当时我还不熟悉编程.我问的时候非常小心,令人惊讶的是,我没有像你来到这里那样得到批评.然而,他们确实指出了" 龙书 " 的方向,在我看来,这是一本非常好的书,解释了编写编译器时你需要知道的一切(当然你必须掌握一两种语言.你知道的语言,更好.)

是的,许多人说读这本书很疯狂,你不会从中学到任何东西,但我完全不同意这一点.

许多人还说编写编译器是愚蠢而毫无意义的.好吧,编译器开发有用的原因有很多: - 因为它很有趣. - 它具有教育意义,在学习如何编写编译器时,您将学到很多关于计算机科学和其他在编写其他应用程序时有用的技术. - 如果没有人编写编译器,现有语言就不会更好.

我没有马上编写自己的编译器,但在询问后我知道从哪里开始.现在,在学习了许多不同的语言并阅读龙书之后,写作并不是一个问题.(我也在学习计算机工程,但我对编程知识的大部分都是自学成才.)

总结: - 龙书是一个伟大的"教程".但是在尝试编写编译器之前花一些时间掌握一两种语言.不要指望在未来十年左右成为一名编译大师.

如果你想学习如何编写解析器/解释器,这本书也很好.

Answer 15

我发现Dragon书太难以阅读而过于注重语言理论,而实际上编写编译器并不是真正需要的.

我将添加Oberon书,其中包含一个非常快速和简单的Oberon编译器Project Oberon的完整资源.

Answer 16

"......让我们构建一个编译器......"

我是@sasb的第二个http://compilers.iecc.com/crenshaw/.暂时忘记购买更多书籍.

为什么？工具和语言.

所需的语言是Pascal,如果我没记错的话是基于Turbo-Pascal.如果你去http://www.freepascal.org/并下载Pascal编译器就会发生这样的事情.所有的例子直接从页面开始工作~ http://www.freepascal.org/download.var关于Free的好东西Pascal几乎可以使用任何你可以关心的处理器或操作系统.

一旦你掌握了课程,那就试试更高级的" 龙书 " ~~ http://en.wikipedia.org/wiki/Dragon_book

Answer 17

我正在研究相同的概念,并找到了Joel Pobar的这篇有前途的文章,

为.NET Framework创建语言编译器 - 不确定它的去向

为.NET Framework创建语言编译器 - 原始文档的pdf副本

他讨论了编译器的高级概念,并继续为.Net框架创建自己的语言.虽然它的目标是.Net框架,但许多概念应该能够被复制.该条款包括:

1. Langauge的定义
2. 扫描器
3. 解析器(我主要感兴趣的位)
4. 针对.Net框架
5. 代码生成器

还有其他主题,但你得到了正义.

它针对人们开始,用C#编写(不完全是Java)

HTH

骨头

Answer 18

创建编译器的简单方法是使用bison和flex(或类似),构建树(AST)并在C中生成代码.生成C代码是最重要的一步.通过生成C代码,您的语言将自动适用于具有C编译器的所有平台.

生成C代码就像生成HTML一样简单(只使用print或等效),这反过来比编写C语法分析器或HTML解析器容易得多.

Answer 19

你应该查看Darius Bacon的" ichbins ",这是一个针对C语言的小型Lisp方言的编译器,只需6页以上的代码.它对大多数玩具编译器的优势在于语言足够完整,编译器就在其中编写.(tarball还包括一个解释器来引导这个东西.)

关于我在Ur-Scheme网页上学习编写编译器有用的东西还有很多东西.

Answer 20

从comp.compilers FAQ:

Per Brinch Hansen Prentice-Hall 1982编写的"个人计算机编程"ISBN 0-13-730283-5

这本不幸的标题书解释了使用类似Pascal的语言Edison的微用户单用户编程环境的设计和创建.作者提供了Edison编译器和简单支持操作系统的逐步实现的所有源代码和解释,所有这些都是用Edison本身编写的(除了用于PDP 11/23的符号汇编器编写的小型支持内核;也可以为IBM PC订购完整的源代码.

本书最有趣的内容是:1)它能够演示如何创建一个完整的,自包含的,自我维护的,有用的编译器和操作系统,以及2)对语言设计和规范问题以及交易的有趣讨论 - 第2章中的内容.

"Brinch Hansen on Pascal Compilers"作者:Per Brinch Hansen Prentice-Hall 1985 ISBN 0-13-083098-4

另一个理论上讲述了重要的实用主义 - 这是如何编写代码的.作者为Pascal-(Pascal"减号")提供了编译器和p代码解释器的设计,实现和完整源代码,Pascal子集是布尔和整数类型(但没有字符,实数,子范围或枚举类型) ,常量和变量定义以及数组和记录类型(但没有打包,变量,集合,指针,无名,重命名或文件类型),表达式,赋值语句,带有值和变量参数的嵌套过程定义,if语句,while语句,和开始 - 结束块(但没有函数定义,过程参数,goto语句和标签,case语句,repeat语句,for语句和with语句).

编译器和解释器是用Pascal*(Pascal"star")编写的,这是一个Pascal子集,扩展了一些Edison风格的功能,用于创建软件开发系统.作者出售了IBM PC的Pascal*编译器,但很容易将本书的Pascal编译器移植到任何方便的Pascal平台上.

本书使编译器的设计和实现看起来很简单.我特别喜欢作者关注质量,可靠性和测试的方式.编译器和解释器可以很容易地用作更复杂的语言或编译器项目的基础,特别是如果您需要快速启动并运行的话.

Answer 21

Python捆绑了一个用Python编写的python编译器.您可以看到源代码,它包括所有阶段,包括解析,抽象语法树,发出代码等.

Answer 22

Fraser和Hanson 的LCC编译器(维基百科)(项目主页)在他们的书"A Retargetable C Compiler:Design and Implementation"中有所描述.它非常易读,可以解释整个编译器,直到代码生成.

Answer 23

对不起,它是西班牙文,但这是阿根廷名为"CompiladoreseIntérpretes"(编译和口译)课程的参考书目.

课程从形式语言理论到编译器构建,这些是你需要构建的主题,至少是一个简单的编译器:

• 编辑器设计C.
  Allen I. Holub
  
  Prentice-Hall.1990年.

• Compiladores.TeoríayConstrucción.
  SanchísLlorca,FJ,GalánPascual,C.编辑Paraninfo.1988年.

• 编译器构造.
  Niklaus Wirth
  
  Addison-Wesley.1996年.

• Lenguajes,GramáticasyAutómatas.Unenfoquepráctico.
  PedroIsasiViñuela,PalomaMartínezFernández,DanielBorrajoMillán.Addison-Wesley Iberoamericana(España).1997年.

• 编译器设计的艺术.理论与实践.
  托马斯皮特曼,詹姆斯彼得斯.
  
  普伦蒂斯霍尔.1992年.

• 面向对象的编译器构造.
  吉姆福尔摩斯.
  Prentice Hall,Englewood Cliffs,NJ 1995

• Compiladores.Conceptos Fundamentales.
  B. Teufel,S.Schmidt,T.Teufel.
  
  Addison-Wesley Iberoamericana.1995年.

• 自动机理论,语言和计算简介.
  
  John E. Hopcroft.Jeffref D. Ullman.
  Addison-Wesley出版社.1979年.

• 正式语言简介.
  GyörgyE.Révész.
  
  Mc Graw Hill.1983年.

• 解析技术.实用指南.
  Dick Grune,Ceriel Jacobs.
  Impreso por los autores.1995年
  http://www.cs.vu.nl/~dick/PTAPG.html

• Yacc:又一个编译器编译器.
  Stephen C. Johnson
  计算科学技术报告N°32,1975.贝尔实验室.
  新泽西州默里山.

• Lex:一个词法分析器生成器.
  ME Lesk,E.Schmidt.计算科学技术报告No.39,1975.贝尔实验室.新泽西州默里山.

• lex&yacc.
  John R. Levine,Tony Mason,Doug Brown.
  O'Reilly&Associates.1995年.

• 计算理论的要素.
  Harry R. Lewis,Christos H. Papadimitriou.SegundaEdición.普伦蒂斯霍尔.1998年.

• Un Algoritmo Eficiente paralaConstruccióndelGrafo de Dependencia de Control.
  Salvador V. Cavadini.
  Trabajo Final de Grado para obtenerelTítulodeIngenieroenComputación.
  FacultaddeMatemáticaAplicada.UCSE 2001.

Answer 24

1. 这是一个广泛的主题.不要低估这一点.不要低估我不低估它的观点.
2. 我听说龙书是一个(？)的起点,还有搜索.:)更好地搜索,最终将是你的生活.
3. 构建自己的编程语言绝对是一个很好的练习!但要知道它最终永远不会用于任何实际目的.对此的例外很少,也很远.

Answer 25

如果你想了解更多关于编译器(和元编译器)的信息,那么这本书不是一本书,而是技术论文和非常有趣的学习经验...本网站将指导您构建一个完全独立的编译器系统,可以编译自己和其他语言:

教程:Metacompilers第1部分

这完全基于一篇惊人的10页小技术论文:

Val Schorre META II:面向语法的编译器编写语言

从1964年的诚实到上帝.我在1970年学会了如何构建编译器.当你最终了解编译器如何重新生成时,这是一个令人兴奋的时刻....

我从大学时代就知道网站作者,但我与网站无关.

Answer 26

我也喜欢Crenshaw教程，因为它非常清楚地表明编译器只是另一个程序，它读取一些输入并写入一些输出。

阅读。

如果需要的话，请尝试使用它，然后再看看另一篇有关如何真正编写更大，更完整的编译器的参考。

并阅读On Trusting Trust，以获取有关可以在此域中完成的显而易见的事情的线索。

Answer 27

这里有很多好的答案,所以我想我只需要在列表中添加一个:

十多年前,我得到了一本名为Project Oberon的书,它在编译器上有一些非常好的文字.这本书真正脱颖而出,因为源和解释是非常实用和可读的.完整的文本(2005年版)已经以pdf格式提供,因此您可以立即下载.编译器将在第12章中讨论:

http://www-old.oberon.ethz.ch/WirthPubl/ProjectOberon.pdf

Niklaus Wirth,JürgGutknecht

(这种处理方式并不像他关于编译器的书那么广泛)

我已经阅读了几本关于编译器的书籍,我可以在龙书上读到第二本书,花在这本书上的时间非常值得.

Answer 28

如果您有兴趣为函数式语言(而不是程序性语言)编​​写编译器,Simon Peyton-Jones和David Lester的" 实现函数式语言:教程 "是一本很好的指南.

功能评估如何工作的概念基础由一个简单但功能强大的功能语言"核心"的例子引导.此外,Core语言编译器的每个部分都用Miranda中的代码示例(一种与Haskell非常相似的纯函数语言)进行了解释.

描述了几种不同类型的编译器,但即使您只遵循所谓的Core模板编译器,您也会非常了解函数编程的内容.

Answer 29

您可以使用Apache Software Foundation的BCEL。使用此工具可以生成类似汇编程序的代码，但是它是带有BCEL API的Java。您可以学习如何生成中间语言代码（在这种情况下为字节码）。

简单的例子

1. 使用此函数创建一个Java类：

   public String maxAsString(int a, int b) {
       if (a > b) {
           return Integer.valueOf(a).toString();
       } else if (a < b) {
           return Integer.valueOf(b).toString();
       } else {
           return "equals";
       }
   }
   

现在使用此类运行BCELifier

BCELifier bcelifier = new BCELifier("MyClass", System.out);
bcelifier.start();

您可以在控制台上看到整个类的结果（如何构建字节码MyClass.java）。该函数的代码是这样的：

private void createMethod_1() {
  InstructionList il = new InstructionList();
  MethodGen method = new MethodGen(ACC_PUBLIC, Type.STRING, new Type[] { Type.INT, Type.INT }, new String[] { "arg0", "arg1" }, "maxAsString", "MyClass", il, _cp);

  il.append(InstructionFactory.createLoad(Type.INT, 1)); // Load first parameter to address 1
  il.append(InstructionFactory.createLoad(Type.INT, 2)); // Load second parameter to adress 2
    BranchInstruction if_icmple_2 = InstructionFactory.createBranchInstruction(Constants.IF_ICMPLE, null); // Do if condition (compare a > b)
  il.append(if_icmple_2);
  il.append(InstructionFactory.createLoad(Type.INT, 1)); // Load value from address 1 into the stack
  il.append(_factory.createInvoke("java.lang.Integer", "valueOf", new ObjectType("java.lang.Integer"), new Type[] { Type.INT }, Constants.INVOKESTATIC));
  il.append(_factory.createInvoke("java.lang.Integer", "toString", Type.STRING, Type.NO_ARGS, Constants.INVOKEVIRTUAL));
  il.append(InstructionFactory.createReturn(Type.OBJECT));
  InstructionHandle ih_13 = il.append(InstructionFactory.createLoad(Type.INT, 1));
  il.append(InstructionFactory.createLoad(Type.INT, 2));
    BranchInstruction if_icmpge_15 = InstructionFactory.createBranchInstruction(Constants.IF_ICMPGE, null); // Do if condition (compare a < b)
  il.append(if_icmpge_15);
  il.append(InstructionFactory.createLoad(Type.INT, 2));
  il.append(_factory.createInvoke("java.lang.Integer", "valueOf", new ObjectType("java.lang.Integer"), new Type[] { Type.INT }, Constants.INVOKESTATIC));
  il.append(_factory.createInvoke("java.lang.Integer", "toString", Type.STRING, Type.NO_ARGS, Constants.INVOKEVIRTUAL));
  il.append(InstructionFactory.createReturn(Type.OBJECT));
  InstructionHandle ih_26 = il.append(new PUSH(_cp, "equals")); // Return "equals" string
  il.append(InstructionFactory.createReturn(Type.OBJECT));
  if_icmple_2.setTarget(ih_13);
  if_icmpge_15.setTarget(ih_26);
  method.setMaxStack();
  method.setMaxLocals();
  _cg.addMethod(method.getMethod());
  il.dispose();
}