基于LLVM的编译器的设计与实现

学士学位论文目：基于LLVM的编译器的设计与实现设计人：梁关林指导教师：刘爱琴所属系部：计算机科学与技术学院专业班级：计算机082001班2012年6月4日太原科技大学毕业设计（论文）任务书学院:计算机科学与技术学院 学生姓名 梁关林 学号 200820010114 专业班级 计算机082001 同组人 无 任务下发时间 2012年3月 任务完成时间 2012年6月 设计（论文）题目 基于LLVM的编译器的设计与实现 设计目的要求 高质量应用软件的开发，需要高效的编程语言和编译器的支持。为了加深学生对编程语言和编译器的理解，要求学生设计一个类似C的小源语言，然后利用LLVM实现该语言的编译器。 设计主要内容 在深刻理解编译原理，掌握文法设计和编译器构造方法，并且熟悉LLVM的基础上，完成编程语言和编译器的设计。主要内容包括：(1)设计源语言，要求包括变量声明，基本赋值语句，数组访问，条件分支语句，循环语句，函数定义，和函数调用等。(2)学习LLVM，完成词法分析，语法分析，和语法制导（翻译成LLVMIR）工作，最后利用LLVM实现代码优化和代码生成功能。 设计提交资料 毕业论文外文资料翻译编译器软件 学生签名 指导教师签名 系主任签名 主管院长签名 中文摘要开发高性能的应用软件，除了一个良好的软件架构外，还需要高效的编程语言和高质量的编译器的支持。现有语言的改动和新语言的创造，都会带来编译器的开发需求。本文设计了一门新的编程语言leechee，定义了此种语言的文法结构、词法规则，并在linux环境下实现了leechee编程语言的编译器。具体实现方式为首先利用Flex完成词法分析，而后使用Bison完成文法设计、语法分析和语法制导翻译，把源代码翻译成LLVMIR，最后利用LLVM实现代码优化和代码生成功能。关键字：编程语言；编译器；语法制导翻译；LLVMIR；代码优化TheDesignandImplementationofLLVMbasedCompilerAuthor:LiangGuanlinTutor:LiuAiqinABSTRACTInadditiontoagoodsoftware-architecture,thedevelopmentofhigh-performanceapplicationsalsoneedsthesupportofanefficientprogramminglanguageandahigh-qualitycompiler.Changestoexistinglanguagesandcreationofnewlanguages,willbringthedevelopmentneedsofthecompilers.Thispaperdesignsanewprogramminglanguageleechee,definesitsgrammaticalstructures,lexicalrules,andimplementsitscompilerunderLinuxenvironment.Thespecificapproachis,first,finishesthescannerwithFlex,andthencompletesthegrammardesign,parser,syntaxdirectedtranslationwithBison,implementsthetranslationtoLLVMIR,andfinallyusetheLLVMtodothecodeoptimizationandcodegeneration.Keywords:programminglanguage;compiler;syntaxdirectedtranslation;LLVMIR;codeoptimization目录1第一章绪论11.1什么是编译器11.2总会有编译器的开发需求21.3为什么做这个项目4第二章设计什么样的编译器和语言42.1做一个什么样的编译器42.1.1利用LLVM实现一门新语言52.1.2利用flex和bison完成词法分析和语法分析62.2设计一个什么样的语言62.2.1计算机可以做什么72.2.2本设计的语言——leechee8第三章相关技术的介绍83.1Flex83.1.1Flex输入文件的格式93.2Bison93.2.1Bison的语法文件103.2.2文法规则的语法113.2.3文法设计需要注意的问题123.3LLVM123.3.1LLVMIR133.3.2LLVM对三段式设计的实现153.3.3利用LLVM完成代码优化17第四章语言和编译器的设计174.1语言设计174.1.1leechee的数据组成184.1.2leechee的文法规则244.1.3leechee的词法规则274.1.4leechee的输入输出284.2抽象语法树284.2.1抽象语法树的用处284.2.2leechee语法树的设计314.3语法制导翻译324.3.1利用Bison实现语法制导翻译324.3.2均分代码生成工作33第五章编译器的实现335.1抽象语法树的实现335.1.1NodeAST345.1.2类型365.1.3表达式425.1.4语句465.1.5声明505.2符号表515.3分析栈525.4中间代码生成的上下文535.5输入输出555.6代码优化56第六章用例说明566.1用例程序586.2使用步骤59结束语60致谢61参考文献62附录62附录Ⅰ英文资料翻译73附录Ⅱ程序代码第一章绪论1.1什么是编译器编译器（compiler）也是一个计算机程序，它把用某种编程语言（源语言）编写的代码转变成另一种计算机语言（目标语言，通常是二进制形式的目标代码）。转变源码最普遍的原因是为了生成执行的程序。编译器，这个名字主要是指把高级编程语言翻译成低级语言（比如，汇编语言或者机器码）的程序。如果翻译出来的程序能够在有着不同于编译器自身运行的CPU或者操作系统的计算机上运行，这种编译器就是交叉编译器（cross-compiler）。能够把低级语言翻译成高级语言的程序则叫做逆编译器（decompiler）。把高级语言翻译成其他高级语言的程序，通常被称为语言翻译器（languagetranslator）。语言重写器（rewriter）通常是指能够转变表达式而不改变所属语言的程序。一个编译器通常执行的操作有：词法分析，预处理，语法分析，语义分析（语法制导翻译），代码生成，和代码优化[1]。编译器软件的正确性非常重要，因为不正确的编译器行为产生的程序错误，通常很难被发现，也很难解决；为此，编译器的实现者付出了大量的努力来保证他们的软件的正确性。1.2总会有编译器的开发需求现在常用的语言都已经有很多优秀的编译器，比如C语言有GCC和ICC；C++有G++和I++；Java有JAVAC和GCJ。然而这些常用语言本身就一直在改变，不断地完善。因而，实现这些语言的编译器也必须做出相应的改动。语言自身的改变，有的是为了弥补自身的缺陷，例如java语言从设计至今，其体积已经增大了几倍；有的是为了适应新的软件开发需求，比如为了更容易地开发大型软件。除了那些成熟语言的改动会带来编译器软件编程的需要外，新语言的诞生也需要编译器程序员来完成新语言的实现工作。比如现在不断涌现的各种脚本语言，都需要编译器程序员来编写这些语言的编译器。新语言的设计（创造），有的是为了适应特殊领域的编程需要，比如SQL（StructuredQueryLanguage），是为关系数据库管理系统专门设计的专用语言。有的是为了更好地利用各种系统资源（尤其是硬件资源），比如OpenCL（OpenComputingLanguage），是为了更好地开发异构平台的计算能力而设计的。可以看到作为编程语言的实现软件（或者不同语言间的翻译软件）的编译器，对它的编程需求一直都存在。我们总有需要实现新的编译器，或者改动现有编译器的时候。图1.1一个典型编译器执行的操作1.3为什么做这个项目开发高性能的应用软件，除了一个良好的软件架构外，还需要一门符合要求的高效的编程语言来实现软件的设计，和一个高质量的编译器来把高级语言写的程序翻译成计算机硬件能够执行的机器代码。编程语言和编译器扮演着辅助软件设计和实现，以及开发计算机计算能力的角色。它们都会深刻影响软件的实际性能；编程语言还会影响软件开发的效率。虽然，现在已经有很多优秀的编程语言和优秀的编译器。但是，一切都在不断地改变。人们一直都会有编译器的开发需求，需要一门更符合要求的编程语言，一个更适合的编译器。我对编译器的开发工作很感兴趣，希望能够参与其中，因此，我借毕业设计这个机会，设计并实现一门小语言，以学习更多编译器方面的知识，加深对编译器和编程语言的理解。这就是我为什么做这个项目的原因。第二章设计什么样的编译器和语言这一章说明应该做一个什么样的编译器，设计一个什么样的语言，以及如何实现这个编译器的问题。2.1做一个什么样的编译器应该做一个什么样的编译器呢？实现一门现有的语言，比如C或者java？或者从语言设计，到代码生成，所有的工作都做一遍？实现一门现有的语言，比如C语言，我显然没有这样的能力；就算能实现，时间也不够。而且这么做不如直接去研究一个该语言的编译器来得更有意义。当然这也是需要大量的时间的（而且，这个工作无法成为设计）。从头到尾，把所有工作都做一遍。或许能够这样做。然而在有限的时间内，只能实现一个非常简单的语言，这么做又有什么意义呢。对一个编译器的入门者来说，需要加深对整个编译器实现流程的理解，也需要了解一些编译器的新技术，或者说这个领域的走向。2.1.1利用LLVM实现一门新语言LLVM（LowLevelVirtualMachine）是一个包含一系列模块化可重用编译器和工具链技术的项目。LLVM主要的子项目有：LLVMCorelibraries，Clang，dragonegg，LLDB等。其中LLVMCorelibraries（LLVM核心库）提供了一个现代源码的（modernsource）、目标独立的（target-independent）优化器；同时还为许多流行CPU提供了代码生成的支持。这些库是围绕着一个有详细说明的代码表示形式（LLVMIR）建立起来的。也就是说，只要我们能够把自己的语言翻译成LLVMIR，就可以利用LLVM完成代码优化和代码生成的工作。当然，你的目标语言（或者说目标CPU架构）必须是LLVM已经支持的。不然，还是得自己实现代码生成的功能。Clang是一个LLVM自身的C/C++/Objective-C编译器，目标是提供快速的编译。据说编译Objective-C代码时能够比GCC快3倍。dragonegg把LLVM的优化器、代码生成器和GCC4.5的分析器结合在一起。这样就使得LLVM能够编译Ada、Fortran等其他GCC编译器前端支持的语言，能够拥有一些Clang不支持的C特性（例如OpenMP）。LLDB是建立在LLVM库和Clang之上的一个非常好的本地调试器。2.1.2利用flex和bison完成词法分析和语法分析又利用其他工具完成编译工作？那到底还有多少情是自己做的呢？之所以要使用工具来完成语法分析工作，是因为本设计实现一个文法结构比较丰富的语言，一个类似C的小语言，能够实现控制流操作和过程调用这些功能。文法（或者说语言构造）多了，文法设计的难度就会增大。LR文法可以比较容易地描述复杂的语言文法。但是LR文法的语法分析表非常庞大，很难手动建立。因此，本设计选择使用bison（一个与yacc兼容的编译器构造工具）完成语法分析工作。使用flex（一个与lex兼容的词法分析构造工具）完成词法分析，则完全是为了节省时间。这样，需要做的工作就剩下设计文法和语法制导翻译了。然而这样做，是有缺陷的。因为这样将导致编译器的主体部分中出现大量不是自己写的代码和想控制又难以控制的模块，使得编译器看起来非常笨拙。所以现在很多流行的编译器（例如GCC和Clang）都使用LL文法，而不是LR文法。然而设计一个语言的LL文法并非易事，所以只好暂且这么做了。图2.1本设计编译器的实现方法2.2设计一个什么样的语言2.2.1计算机可以做什么设计一个计算机语言，需要清楚计算机能够做什么样的事情，打算利用它做什么事情。而后才能设计自己的语言。一台计算机的5个经典部件是输入，输出，内存，数据通路，和控制器，最后两个有时组合在一起称为处理器。同时，任何计算机的底层硬件都执行相同的基本功能：输入数据，输出数据，处理数据，和存储数据[2]。这大概就是计算机的模型了。我们用计算机来写文档，画图，看视频，玩游戏，等等各种各样的事情。然而计算机是怎么替我们做这些事情的呢？其实，计算机的核心部分——处理器（CPU）能够做的就是不断重复地执行各种指令，例如顺序执行的加、减、乘、除、移位指令，和二进制的与、或、非指令。除了顺序执行的指令外，处理器还可以执行选择指令，也就是条件跳转和无条件跳转指令。当然，一个功能完备的处理器，还必须能够执行数据的加载和存储指令。以上是在底层硬件上看到的操作，在高级语言中我们看到的则是算术逻辑运算，布尔运算，和控制流操作这些更符合我们人类思考方式的操作。不过，无论是从底层看，还是从高层看，计算机执行的操作都可以分为顺序操作和选择跳转操作。所以，在练习语言设计时，一定要覆盖计算机的这两项功能。此外，为了描述清楚计算机处理和存储的数据，我们需要一个类型系统，说明数据的大小和存储格式。而且，往往不同类型的数据，执行这些数据的操作的硬件也是不同的，例如，执行整型和浮点型运算的硬件就是独立分开的。2.2.2本设计的语言——leechee弄清楚计算机能够做什么之后，就可以讨论设计一个什么样的语言了。因为计算机最基本的功能是计算，所以本设计决定设计一个计算性的语言。利用它可以完成基本的算术逻辑运算。不过，为了减轻工作量，只支持加减乘除运算。在布尔运算上，则比较完整，包括与或非和各种关系运算。所有的计算任务都通过函数来描述。使用者（语言的使用者）编写程序时，从一个主函数开始描述他所需的计算任务。在一个函数中可以调用其他函数，来完成一些子任务（当然，不能调用主函数main）。总之，这是一个类似C的小语言。每个语言都有自己的名字，我也给自己的语言取个名字——leechee。第三章相关技术的介绍如上一章所提到的，这个设计中需要使用一些工具或者说技术，这里对其进行比较完整的介绍。3.1FlexFlex(fastlexicalanalysergenerator)是Lex的一个替代品。它经常和GNUBison语法分析器生成器一起使用。Flex最初由VernPaxson于1987年用C语言写成。Flex是一个生成扫描器的工具，能够识别文本中的词法模式。flex读入给定的输入文件，如果没有给定文件名的话，则从输入读取，从而获得一个关于需要生成的扫描器的描述。此描述叫做规则，由扩展的正则表达式和C代码对组成。flex的输出是一个C代码文件——lex.yy.c——其中定义了yylex()函数。编译输出文件并且和-lfl库链接生成一个可执行文件。当运行可执行文件的时候，它分析输入文件，为每一个正则表达式寻找匹配。当发现一个匹配时，它执行与此正则表达式相关的C代码。3.1.1Flex输入文件的格式flex的输入文件有三部分组成，用包含’%%’的独立一行分隔开。definitions%%rules%%usercodedefinition部分包含简单名字的定义，这些定义是为了简化扫描器的说明。definition部分还包含了开始状态的声明。rules部分包含了一系列的如下形式的规则：patternactionpattern（词法模式）必须是无缩进的扩展的正则表达式，action（pattern被识别后执行的语句）必须在pattern的同一行开始。usercode部分只是简单逐字地复制到lex.yy.c中。这一部分使用在调用扫描器或者被扫描器调用的同伴例程上。这一部分是可选的，如果省略的话，输入文件中第二个’%%’符号也可省略。Flex支持C风格的注释，也即是，任何在’/*’和’*/’之间的字符串都被看作是注释。具体请参考Flex的手册http://flex.sourceforge.net/manual/。3.2BisonBison是一个通用的分析器生成器，最初由RovertCorbett编写。RichardStallman使得它与Yacc兼容。CarnegieMellon大学的WilfredHansen为Bison添加了多字符字符串字面值(multi-characterstringliterals)和其它一些特性。Bison能够把带注释的上下文无关文法转换成采用LALR(1)分析表的，确定的LR或者推广的LR（generalized）分析器。作为一个实验特性，Bison还可以生成IELR(1)或者canonicalLR(1)分析表。一旦你精通Bison，你可以用它生成从简单的桌面计算器到复杂的程序设计语言等等许多语言的分析器。3.2.1Bison的语法文件Bison使用一个描述上下文无关文法的文件作为输入，并产生一个识别该文法的正确实例的C语言函数。按照惯例，Bison的文法文件一般以’.y’结尾。一个Bison语法文件有四个主要的部分，如下所示，由恰当的分隔符分隔。%{Prologue%}Bisondeclarations%%Grammarrules%%EpiloguePrologue部分包括宏定义和在语法规则动作中使用的函数和变量的声明。这些将复制到分析器文件的开头以便先于yyparse的定义。你可以使用`#include'来从头文件获取声明。如果你不需要任何的C声明，你可以省略这个部分的括号分隔符`%{'和`%}'。Bisondeclatations部分包含了定义终结符和非终结符的声明，优先级等等。在一些简单的语法中，可以不需要任何声明。GrammarRules部分包含了一个或多个Bison语法规则。就像Prologue部分被复制到开头一样，Epilogue部分被逐字地复制到分析器文件的结尾。如果你想放一些代码却没必要放在yyparse的定义之前，这里是最方便的地方。例如，yylex和yyerror的定义就经常放在这里。因为C语言要求函数在使用之前必须声明。你经常需要Prologue部分声明类似yylex和yyerror的函数，即使你在Epilogue部分已经定义了它们。3.2.2文法规则的语法一个Bison语法规则通常有如下的下形式：result:components...;reault是这个规则描述的非终结符，而components是被这个规则组合在一起的各种终结符和非终结符。例如：exp:exp'+'exp;表明两组exp类型和一个在中间的`+'记号，可以结合成一个更大的exp类型组。规则中的空白只用来分隔符号，你可以在你想要的地方添加额外的空白。决定规则的语义的动作可以分散在部件（components）中。一个动作看起来是这样的：{Cstatements}用花括号括起来的一个C语句序列，非常像C的一个复合语句。通常部件的后面只跟有一个语义动作。同一个result的多个规则可以分别书写，也可以用垂直条`|'按如下的方法连接起来：result:rule1-components...|rule2-components......如果一个规则的components为空，意味着result可以匹配空字符串。例如，这是如何定义一个由逗号分隔的由0个或多个exp组成的序列：expseq:/*empty*/|expseq1;expseq1:exp|expseq1’,’exp;我们通常对每个没有部件的规则加上一个`/*empty*/'的注释。具体请参考Bison的手册http://www.gnu.org/software/bison/manual/bison.html。3.2.3文法设计需要注意的问题对于符号串识别来说，它看到的只有符号，没有任何语义层面的东西。所以设计文法时，应该尽量从符号串模式设计的角度去设计，用不同的各种符号串模式去描述清楚语言里面的各种程序构造。还有，我们应该遵从已有的通用语言的惯例，避免自创一套文法。遵从通用语言的惯例，使得新设计的语言更易于被理解和接受，程序员在学习使用新语言时也可以减轻不少负担。3.3LLVMLLVM（LowLevelVirtualMachine）是一套编译器的基础设施（infrastructure），可以把它看作一个大项目，包括一套从前端，各种代码分析/优化工具，到代码生成器的编译器工具链，而且可兼容Unix系统上的现有工具。LLVM现在被用作实现各种静态和运行时编译语言的公共基础设施，例如，GCC支持的语言族，Java，.NET，Python，Ruby，Scheme，Haskell，D，以及许多不那么知名的语言。它也取代了多种特殊用途的编译器，比如Apple的OpenGL软件栈（stack）中的专用引擎，和Adobe的AfterEffects产品中的图像处理库。最后，LLVM还被用于创建许多新产品，也许其中最为人熟知的就是OpenCLGPU编程语言和它的runtime。3.3.1LLVMIRLLVMIR（LLVM中间表示形式）是LLVM设计最重要的一个方面，是LLVM编译器用来表示代码的形式。LLVMIR被设计来主持编译器中间级别的分析和变形。它的设计考虑了许多特定的目标，包括支持轻量的运行时优化，跨函数（过程间）优化，程序全局分析，和大胆的（aggressive）重组变形等等。不过，它最重要的方面是，它自身就被定义为一个一流的有着定义明确的语义的语言。眼见为实，下面就是LLVMIR的一个例子（一个.ll文件）：definei32@add1(i32%a,i32%b){entry:%tmp1=addi32%a,%breti32%tmp1}definei32@add2(i32%a,i32%b){entry:%tmp1=icmpeqi32%a,0bri1%tmp1,label%done,label%recurserecurse:%tmp2=subi32%a,1%tmp3=addi32%b,1%tmp4=calli32@add2(i32%tmp2,i32%tmp3)reti32%tmp4done:reti32%b}这段LLVMIR对应如下的C代码，提供了两种不同的整型相加方式。unsignedadd1(unsigneda,unsignedb){returna+b;}//Perhapsnotthemostefficientwaytoaddtwonumbers.unsignedadd2(unsigneda,unsignedb){if(a==0)returnb;returnadd2(a-1,b+1);}除了实现为一个自我完备的语言外，LLVMIR实际上被定义为三种同构异形的形式：上面的文本格式（.ll文件），一个被优化检查或者修改的在内存的数据结构，和一个在高效的、密集的在磁盘的二进制“bitcode”格式。LLVMIR是一种中间层次的程序表示方式，它独立于高级语言，没有描述高级语言里的特有的概念（比如，它没有表示或者说实现高级语言里面的访问控制），同时又能表示一些汇编（非常贴近于机器的表示方式）无法描述的概念（语义）。LLVM，LowLevelVirtualMachine，之所以取这个名称，我想是因为LLVM能够在一个贴近于机器，但又独立目标平台的层次上，对程序进行各种分析或者优化。也即是说围绕这LLVMIR可以形成一个程序优化/分析/存储/传送的生态系统。这或许就是LLVM的优势所在。3.3.2LLVM对三段式设计的实现传统静态编译器（比如大多C编译器）中普遍使用的设计方案是三段式设计，这种设计方案把编译器分成三个主要的模块，前端，优化器，和后端。前端对进行分析，检查其中的错误，并生成表示输入代码的具体语言的抽象语法树（AST）。AST通常被转换成一种新的表示方式，以方便优化的进行，优化器和后端都在这种表示方式的代码上进行。图3.1一个三段式编译器的主要模块这种经典设计之所以成功的最重要的原因是，它使得一个编译器可以支持多个前端和后端。只要一个编译器在它的优化器中使用一个共同的代码表示方式，任何语言的前端都可以翻译成这种表示形式，任何目标平台的后端都可以把它翻译成目标语言，如下图所示。图3.2可重定目标能力三段式设计的另一个优势是（直接来自可重定目标能力，retargetability），使用这种编译器的程序员要比支持一种语言和一种目标平台的编译器多很多。这就自然使得这种类型的编译器可以获得更多的增强和改进。虽然三段式设计的好处非常引人注目，在编译器教科书也都描写详细，但是它几乎从来都没有被完整地实现过。纵观开源编程语言的实现（LLVM出现之前）,你会发现实现Perl、Python、Ruby和Java编译器没有共享任何代码。比较成功的GCC也没有完整实现三段式设计，因为GCC的GIMPLE中级表示方式不是一个自我完备的表示方式，它的前端、优化器、和后端无法完全独立[4]。然而，因为LLVMIR是一个完整的自我完备的代码表示方式，它可以完整地实现三段式设计方案。在一个基于LLVM的编译器中，它的前端只需要负责源代码的语法分析，验证和错误诊断，然后把完成分析的代码翻译成LLVMIR。接着，这种IR就可以使用一系列的代码分析和优化程序来改善代码。最后，经过优化的IR被送到一个代码生成器，生成本地机器码。图3.2LLVM对三段式设计的实现此外，LLVM是作为一套库来实现的，这可以极大地方便编译器实现者来使用它。3.3.3利用LLVM完成代码优化低层次的表示方式因为很难主持（host）高层次的分析和变形而声名狼藉。例如，SGIPro64编译器的中间表示形式（WHIRL）包含不少于5种这种表示方式的不同级别，以使得能够在最高级别进行优化成为可能。在这个高质量的编译器中，所有的过程间优化都是在一个非常高层次的表示方式上完成的，这个表示方式其实就是一个语言中立的抽象语法树[5]。LLVM致力于链接和后链接时间的高层次变形。然而，因为许多原因，在低层次上表示代码也是有益的。LLVM也是一种低层次的表示方式，与众不同的是，它有一个较高层次的类型系统，这使得它能够支持许多高层次的优化（转换），而无需花费额外的代价（程序分析）。LLVM优化是通过各种趟（pass）实现的，这些趟遍历了一个程序的某些部分，或者搜集信息，或者进行变形操作。趟分为分析趟（analysispass）、变形趟（transformpass）和实用趟（utilitypass）。分析趟计算其他趟用到的、或者调试需要的、或者程序形象化需要的信息。变形趟可以使用分析趟，变形趟都会以某种方式改变程序。实用趟是提供了一些实用工具的趟，这些趟不适合进行归类。例如把函数提取成bitcode（LLVMIR一种存在形式），和把一个模块（表示一个程序的顶级结构）提取成bitcode，都是实用趟，它们既不是分析趟，也不是变形趟。LLVM提供了许多优化pass，能够做各种不同的事情，并且有着不同的利弊权衡。不像其它系统，LLVM没有坚持那种错误的概念，一套优化适合所有的语言和所有的情况。LLVM允许编译器实现者做完整的关于选用哪一个优化，以哪种顺序去执行这些优化，以及在那种情况下执行这些优化的选择。根据pass所做的工作不同，可以分为ModulePass、CallGraphSCCPass、FunctionPass、LoopPass、RegionPass、BasicBlockPass。ModulePass把整个程序看做一个单元，以无法预测的顺序访问函数体，或者添加和删除函数。CallGraphSCCPass以自底向上的方式遍历调用关系图。FunctionPass只在单个独立的函数上执行。LoopPass在一个函数的单个独立的循环上执行。RegionPass类似于LoopPass，不过，它在一个函数的单入口单出口的区域上执行。有点像FunctionPass，只是它的作用域被限制在一个基本块中，检查或者修改一个基本块中的指令。第四章语言和编译器的设计这一章对leechee语言及其编译器进行总体上的设计，包括语言的数据组成、文法规则、词法规则、输入输出，以及抽象语法树和语法制导翻译的设计。4.1语言设计4.1.1leechee的数据组成leechee的数据包括局部变量、局部常量和全局常量。之所以没有全局变量，是因为本设计认为实现计算任务的被调用函数（callee）的运行应该在主调函数（caller）的控制之下进行。而且，一个计算本身就是接收输入数据，然后完成计算任务，最终返回计算结果，并不需要产生其它的副作用。leechee数据类型包括整型和浮点型。其中整型有：bool，byte，short，int，long。浮点型有：float，double。此外，还有一个复合类型——数组，由一组指定数量（在声明是指定）的基本类型元素组成。表4.1基本数据类型 类型名称 数据类别 数据大小(bit) void 空类型 0 bool 整型 1 byte 整型 8 short 整型 16 int 整型 32 long 整型 64 float 浮点 32 double 浮点 644.1.2leechee的文法规则文法规定了什么样的程序是合法的。leechee的语言构造包括：函数、语句、表达式、声明等。具体如下：注意，为了方便，这里采用Bsion文法规则的书写方式，详见第二章第二节。小写的单词（包括缩略语和带下划线短语）表示非终结符，大写的单词表示终结符。文法规中的终结符将在词法规则中给出。translation_unit:global_declaration|translation_unitglobal_declaration;一个编译单元有一系列的全局声明组成，全局声明可以是函数定义、函数声明、或者常量声明。global_declaration:function_definition|function_declaration|constant_declaration;function_type:typeIDENTIFIER'('parameter_list')'|typeIDENTIFIER'('')';函数类型也是一种类型，由一个返回类型、一个标识符、和一个形参列表构成，形参可以为空。function_definition:function_typecompound_statement;function_declaration:function_type';';constant_declaration:CONSTtypeinit_declarator_list';';variable_declaration:typeinit_declarator_list';';declaration:variable_declaration|constant_declaration|function_declaration;局部声明可以是变量声明、常量声明、或者函数声明。basic_type:VOID|BOOLEAN|BYTE|SHORT|INT|LONG|FLOAT|DOUBLE;type:basic_type|array_type;array_type:basic_type'['constant_expression']'|basic_type'['']'|array_type'['constant_expression']'|array_type'['']';数组类型由一个基本类型和一个指明元素数量的常量表达式构成。init_declarator_list:init_declarator|init_declarator_list','init_declarator;init_declarator:IDENTIFIER|IDENTIFIER'='initializer;initializer:assignment_expression|'{'initializer_list'}'|'{'initializer_list',''}';初始化器由表达式或者表达式列表构成（用于数组初始化）。initializer_list:initializer|initializer_list','initializer;parameter_list:parameter|parameter_list','parameter;parameter:typeIDENTIFIER|unnamed_value;unnamed_value:type;形参可以用一个带类型的标识符表示，也可以只用一个类型表示。compound_statement:'{'statement_list'}'|'{''}';复合语句由一个花括号括起来的语句列表构成。statement_list:statement|statement_liststatement;statement:declaration|expression_statement|selection_statement|iteration_statement|jump_statement|compound_statement|empty_statement;语句包括声明语句、表达式语句、选择语句、循环语句、跳转语句、复合语句、和空语句。空语句就是一个独立分号‘;’。这些语句文法都类似于C语言中相应的语句。empty_statement:';';expression_statement:expression_list';';selection_statement:IF'('assignment_expression')'statement|IF'('assignment_expression')'statementELSEstatement;iteration_statement:WHILE'('assignment_expression')'statement|DOstatementWHILE'('assignment_expression')'';'|FOR'('for_init_statementassignment_expression';'expression_list')'statement|FOR'('for_init_statementassignment_expression';'')'statement;for语句由一个初始化的语句，一个代表条件的表达式，一个步进循环时执行的表达式序列，和一个代表循环体的语句构成。for_init_statement[3]:declaration|expression_statement|empty_statement;for语句的初始化语句可以是声明语句、表达式语句、和空语句。jump_statement:BREAK';'|RETURNassignment_expression';'|CONTINUE';';expression_list:assignment_expression|expression_list','assignment_expression;assignment_expression:logical_or_expression|unary_expressionassign_opassignment_expression;赋值表达式由一个单元表达式（目的表达式）、一个赋值运算符、和另一个赋值表达式构成。constant_expression:logical_or_expression;常量表达式在文法结构上和普通的二元表达式（双目运算表达式）完全相同，只不过它的操作数只能是常量。在语义分析过程中会检查它的操作数是否是常量。logical_or_expression:logical_and_expression|logical_or_expressionORL_OPlogical_and_expression;logical_and_expression:equality_expression|logical_and_expressionANDL_OPequality_expression;equality_expression:relational_expression|equality_expressionEQ_OPrelational_expression|equality_expressionNE_OPrelational_expression;relational_expression:additive_expression|relational_expression'<'additive_expression|relational_expression'>'additive_expression|relational_expressionLE_OPadditive_expression|relational_expressionGE_OPadditive_expression;表达式从底层的基本表达式（primaryexpression）开始，不断构成附加表达式、后缀表达式、单元表达式、造型表达式、倍增表达式、递增表达式、关系表达式、相等性表达式、逻辑与表达式、逻辑或表达式。additive_expression:multiplicative_expression|additive_expression'+'multiplicative_expression|additive_expression'-'multiplicative_expression;multiplicative_expression:cast_expression|multiplicative_expression'*'cast_expression|multiplicative_expression'/'cast_expression|multiplicative_expression'%'cast_expression;cast_expression:unary_expression|'('type')'cast_expression;unary_expression:postfix_expression|'+'unary_expression|'-'unary_expression|'!'unary_expression|INC_OPunary_expression|DEC_OPunary_expression;postfix_expression:attach_expression|postfix_expressionINC_OP|postfix_expressionDEC_OP;attach_expression:primary_expression|primary_expressionarray_offset|primary_expression'('argument_list')'|primary_expression'('')';附加表达式包括数组元素访问和函数调用。primary_expression:IDENTIFIER|literal|'('assignment_expression')';基本表达式包括标识符、字面值、圆括号括起来的赋值表达式。literal:OCT_INTEGER|DEC_INTEGER|HEX_INTEGER|FLOATING|BOOL_TRUE|BOOL_FALSE;字面值包括八进制、十进制、十六进制整数，浮点数，和布尔真、假。array_offset:'['assignment_expression']'|array_offset'['assignment_expression']';argument_list:assignment_expression|argument_list','assignment_expression;实参由一个赋值表达式列表构成。assign_op:'='|MUL_ASSIGN|DIV_ASSIGN|MOD_ASSIGN|ADD_ASSIGN|SUB_ASSIGN|SHLL_ASSIGN|SHRL_ASSIGN|SHRA_ASSIGN|ANDB_ASSIGN|ORB_ASSIGN|XORB_ASSIGN;4.1.3leechee的词法规则同样为了方便，这里使用Flex的词法规则书写方式，详见第二章第一节。space[]tab\tnewline\ndigit[0-9]hex_digit[a-fA-F0-9]letter[a-zA-Z_]expo[Ee][+-]?{digit}+Fsuffix(f|F|l|L)Isuffix(l|L)id{letter}({letter}|{digit})*oct_integer0{digit}+{Isuffix}?dec_integer{digit}+{Isuffix}?hex_integer0[xX]{hex_digit}+{Isuffix}?real_dot{digit}+\.{digit}*{expo}?{Fsuffix}?dot_real{digit}*\.{digit}+{expo}?{Fsuffix}?real_expo{digit}+{expo}{Fsuffix}?include"#include"whitespace[\t]*\"filename[^\t\n\"]+\"%%{space}/*noactionandnoreturn*/{tab}/*noactionandnoreturn*/{newline}/*noactionandnoreturn*/"if"{returnSAVE_TOKEN(IF);}"else"{returnSAVE_TOKEN(ELSE);}"while"{returnSAVE_TOKEN(WHILE);}"do"{returnSAVE_TOKEN(DO);}"for"{returnSAVE_TOKEN(FOR);}"break"{returnSAVE_TOKEN(BREAK);}"continue"{returnSAVE_TOKEN(CONTINUE);}"return"{returnSAVE_TOKEN(RETURN);}"void"{returnSAVE_TOKEN(VOID);}"bool"{returnSAVE_TOKEN(BOOLEAN);}"byte"{returnSAVE_TOKEN(BYTE);}"short"{returnSAVE_TOKEN(SHORT);}"int"{returnSAVE_TOKEN(INT);}"long"{returnSAVE_TOKEN(LONG);}"float"{returnSAVE_TOKEN(FLOAT);}"double"{returnSAVE_TOKEN(DOUBLE);}"true"{returnSAVE_TOKEN(BOOL_TRUE);}"false"{returnSAVE_TOKEN(BOOL_FALSE);}{id}{SAVE_STR;returnIDENTIFIER;}{oct_integer}{SAVE_STR;returnOCT_INTEGER;}{dec_integer}{SAVE_STR;returnDEC_INTEGER;}{hex_integer}{SAVE_STR;returnHEX_INTEGER;}{real_dot}{SAVE_STR;returnFLOATING;}{dot_real}{SAVE_STR;returnFLOATING;}{real_expo}{SAVE_STR;returnFLOATING;}"="{returnSAVE_TOKEN('=');}"*="{returnSAVE_TOKEN(MUL_ASSIGN);}"/="{returnSAVE_TOKEN(DIV_ASSIGN);}"%="{returnSAVE_TOKEN(MOD_ASSIGN);}"+="{returnSAVE_TOKEN(ADD_ASSIGN);}"-="{returnSAVE_TOKEN(SUB_ASSIGN);}"<<="{returnSAVE_TOKEN(SHLL_ASSIGN);}">>="{returnSAVE_TOKEN(SHRL_ASSIGN);}">>>="{returnSAVE_TOKEN(SHRA_ASSIGN);}"&="{returnSAVE_TOKEN(ANDB_ASSIGN);}"|="{returnSAVE_TOKEN(ORB_ASSIGN);}"^="{returnSAVE_TOKEN(XORB_ASSIGN);}"&&"{returnSAVE_TOKEN(ANDL_OP);}"||"{returnSAVE_TOKEN(ORL_OP);}"|"{returnSAVE_TOKEN('|');}"^"{returnSAVE_TOKEN('^');}"&"{returnSAVE