《基于LLVM的编译器的设计与实现.doc》由会员分享，可在线阅读，更多相关《基于LLVM的编译器的设计与实现.doc（101页珍藏版）》请在金锄头文库上搜索。
1、学士学位论文题目：基于LLVM的编译器的设计与实现设计人： 梁关林指导教师：刘爱琴所属系部：计算机科学与技术学院专业班级：计算机082001班2012年 6月 4日太原科技大学毕业设计（论文）任务书学院: 计算机科学与技术学院学 生 姓 名梁关林学号200820010114专业班级计算机082001同组人无任务下发时间2012年3月任务完成时间2012年6月设计（论文）题目基于LLVM的编译器的设计与实现设计目的要求高质量应用软件的开发，需要高效的编程语言和编译器的支持。为了加深学生对编程语言和编译器的理解，要求学生设计一个类似C的小源语言，然后利用LLVM实现该语言的编译器。设计主要内容在深
2、刻理解编译原理，掌握文法设计和编译器构造方法，并且熟悉LLVM的基础上，完成编程语言和编译器的设计。主要内容包括：(1) 设计源语言，要求包括变量声明，基本赋值语句，数组访问，条件分支语句，循环语句，函数定义，和函数调用等。(2) 学习LLVM，完成词法分析，语法分析，和语法制导翻译（翻译成LLVM IR）工作，最后利用LLVM实现代码优化和代码生成功能。设计提交资料毕业论文外文资料翻译编译器软件学生签名指导教师签名系主任签名主管院长签名太原科技大学学士学位论文中文摘要开发高性能的应用软件，除了一个良好的软件架构外，还需要高效的编程语言和高质量的编译器的支持。现有语言的改动和新语言的创造，都会
3、带来编译器的开发需求。本文设计了一门新的编程语言leechee，定义了此种语言的文法结构、词法规则，并在linux环境下实现了leechee编程语言的编译器。具体实现方式为首先利用Flex完成词法分析，而后使用Bison完成文法设计、语法分析和语法制导翻译，把源代码翻译成LLVM IR，最后利用LLVM实现代码优化和代码生成功能。关键字：编程语言；编译器；语法制导翻译；LLVM IR；代码优化The Design and Implementation of LLVM based CompilerAuthor: Liang Guanlin Tutor: Liu Aiqin ABSTRACTIn
4、addition to a good software-architecture, the development of high-performance applications also needs the support of an efficient programming language and a high-quality compiler. Changes to existing languages and creation of new languages, will bring the development needs of the compilers.This pape
5、r designs a new programming language leechee, defines its grammatical structures, lexical rules, and implements its compiler under Linux environment. The specific approach is, first, finishes the scanner with Flex, and then completes the grammar design, parser, syntax directed translation with Bison
6、, implements the translation to LLVM IR, and finally use the LLVM to do the code optimization and code generation.Keywords: programming language; compiler; syntax directed translation; LLVM IR; code optimization目录第一章 绪论11.1 什么是编译器11.2 总会有编译器的开发需求11.3 为什么做这个项目2第二章 设计什么样的编译器和语言42.1 做一个什么样的编译器42.1.1 利用
7、LLVM实现一门新语言42.1.2 利用flex和bison完成词法分析和语法分析52.2 设计一个什么样的语言62.2.1 计算机可以做什么62.2.2 本设计的语言leechee7第三章 相关技术的介绍83.1 Flex83.1.1 Flex输入文件的格式83.2 Bison93.2.1 Bison的语法文件93.2.2 文法规则的语法103.2.3 文法设计需要注意的问题113.3 LLVM123.3.1 LLVM IR123.3.2 LLVM对三段式设计的实现133.3.3 利用LLVM完成代码优化15第四章 语言和编译器的设计174.1 语言设计174.1.1 leechee的数据组
8、成174.1.2 leechee的文法规则184.1.3 leechee的词法规则244.1.4 leechee的输入输出274.2 抽象语法树284.2.1 抽象语法树的用处284.2.2 leechee语法树的设计284.3 语法制导翻译314.3.1 利用Bison实现语法制导翻译方案324.3.2 均分代码生成工作32第五章 编译器的实现335.1 抽象语法树的实现335.1.1 NodeAST335.1.2 类型345.1.3 表达式365.1.4 语句425.1.5 声明465.2 符号表505.3 分析栈515.4 中间代码生成的上下文525.5 输入输出535.6 代码优化55
9、第六章 用例说明566.1 用例程序566.2 使用步骤58结束语59致谢60参考文献61附录62附录 英文资料翻译62附录 程序代码73V第一章 绪论1.1 什么是编译器编译器（compiler）也是一个计算机程序，它把用某种编程语言（源语言）编写的代码转变成另一种计算机语言（目标语言，通常是二进制形式的目标代码）。转变源码最普遍的原因是为了生成执行的程序。编译器，这个名字主要是指把高级编程语言翻译成低级语言（比如，汇编语言或者机器码）的程序。如果翻译出来的程序能够在有着不同于编译器自身运行的CPU或者操作系统的计算机上运行，这种编译器就是交叉编译器（cross-compiler）。能够把低
10、级语言翻译成高级语言的程序则叫做逆编译器（decompiler）。把高级语言翻译成其他高级语言的程序，通常被称为语言翻译器（language translator）。语言重写器（rewriter）通常是指能够转变表达式而不改变所属语言的程序。一个编译器通常执行的操作有：词法分析，预处理，语法分析，语义分析（语法制导翻译），代码生成，和代码优化1。编译器软件的正确性非常重要，因为不正确的编译器行为产生的程序错误，通常很难被发现，也很难解决；为此，编译器的实现者付出了大量的努力来保证他们的软件的正确性。1.2 总会有编译器的开发需求现在常用的语言都已经有很多优秀的编译器，比如C语言有GCC和ICC
11、；C+有G+和I+；Java有JAVAC和GCJ。然而这些常用语言本身就一直在改变，不断地完善。因而，实现这些语言的编译器也必须做出相应的改动。语言自身的改变，有的是为了弥补自身的缺陷，例如java语言从设计至今，其体积已经增大了几倍；有的是为了适应新的软件开发需求，比如为了更容易地开发大型软件。除了那些成熟语言的改动会带来编译器软件编程的需要外，新语言的诞生也需要编译器程序员来完成新语言的实现工作。比如现在不断涌现的各种脚本语言，都需要编译器程序员来编写这些语言的编译器。新语言的设计（创造），有的是为了适应特殊领域的编程需要，比如SQL（Structured Query Language），
12、是为关系数据库管理系统专门设计的专用语言。有的是为了更好地利用各种系统资源（尤其是硬件资源），比如OpenCL（Open Computing Language），是为了更好地开发异构平台的计算能力而设计的。可以看到作为编程语言的实现软件（或者不同语言间的翻译软件）的编译器，对它的编程需求一直都存在。我们总有需要实现新的编译器，或者改动现有编译器的时候。图1.1 一个典型编译器执行的操作1.3 为什么做这个项目开发高性能的应用软件，除了一个良好的软件架构外，还需要一门符合要求的高效的编程语言来实现软件的设计，和一个高质量的编译器来把高级语言写的程序翻译成计算机硬件能够执行的机器代码。编程语言和编
13、译器扮演着辅助软件设计和实现，以及开发计算机计算能力的角色。它们都会深刻影响软件的实际性能；编程语言还会影响软件开发的效率。虽然，现在已经有很多优秀的编程语言和优秀的编译器。但是，一切都在不断地改变。人们一直都会有编译器的开发需求，需要一门更符合要求的编程语言，一个更适合的编译器。我对编译器的开发工作很感兴趣，希望能够参与其中，因此，我借毕业设计这个机会，设计并实现一门小语言，以学习更多编译器方面的知识，加深对编译器和编程语言的理解。这就是我为什么做这个项目的原因。第二章 设计什么样的编译器和语言这一章说明应该做一个什么样的编译器，设计一个什么样的语言，以及如何实现这个编译器的问题。2.1 做
14、一个什么样的编译器应该做一个什么样的编译器呢？实现一门现有的语言，比如C或者java？或者从语言设计，到代码生成，所有的工作都做一遍？实现一门现有的语言，比如C语言，我显然没有这样的能力；就算能实现，时间也不够。而且这么做不如直接去研究一个该语言的编译器来得更有意义。当然这也是需要大量的时间的（而且，这个工作无法成为设计）。从头到尾，把所有工作都做一遍。或许能够这样做。然而在有限的时间内，只能实现一个非常简单的语言，这么做又有什么意义呢。对一个编译器的入门者来说，需要加深对整个编译器实现流程的理解，也需要了解一些编译器的新技术，或者说这个领域的走向。2.1.1 利用LLVM实现一门新语言LLV
15、M（Low Level Virtual Machine）是一个包含一系列模块化可重用编译器和工具链技术的项目。LLVM主要的子项目有：LLVM Core libraries，Clang，dragonegg，LLDB等。其中LLVM Core libraries（LLVM核心库）提供了一个现代源码的（modern source）、目标独立的（target-independent）优化器；同时还为许多流行CPU提供了代码生成的支持。这些库是围绕着一个有详细说明的代码表示形式（LLVM IR）建立起来的。也就是说，只要我们能够把自己的语言翻译成LLVM IR，就可以利用LLVM完成代码优化和代码生成的工作。当然，你的目标语言（或者说目标CPU架构）必须是LLVM已经支持的。不然，还是得自己实现代码生成的功能。Clang是一个LLVM自身的C
