Mini C编译器的设计与实现 电子科技大学计算机学院 《编译

MiniC编译器的设计与实现（讲义）电子科技大学计算机学院编译MiniC编译器的设计与实现（讲义）电子科技大学计算机学院编译原理课程组2008年1目录第一章MiniC语言编译器简介4第二章理论基础72.1编译系统概述72.1.1什么是编译器7生72.2编译器的结构82.3编译器的组织102.3.1编译的分遍102.3.2分遍的设计112.4编译器中的主要数据结构112.5编译程序的开发122.5.1历史与发展2.5.2开发注意事项122.5.3编译技术和软件工具12第三章MINIC语言和MINIC编译器143.1MINIC编译器的开发背景和意义143.2MINIC语言的基本描述143.3MINIC编译器的功台匕能153.4MINIC编译器的程序结构16MINIC编译器的核心模块16MINIC编译器的文件组成MINIC编译器的分遍173.5MINIC编译器中的主要数据结构17第四章MINIC编译器的实现194.1词法分析阶段19概述19MINIC词法分析程序的实现204.1.3关键字与标识符的识别214.1.4为标识符分配空间214.2语法分析阶段概述222MINIC语言的语法22MINIC语法分析程序的实现234.3语义分析阶段24概述24MINIC语言的语义24MINIC的符号表25MINIC语义分析程序的实现254.4MINIC运行时环境26概述26MINIC的运行时环境264.5代码生成阶段28概述284.5.2目标机器MiniMachine29MINIC代码生成器的实现31MINIC代码生成器的MM接口31MINIC代码生成器4.6.1将临时变量放入寄存器354.6.2在寄存器中保存变量364.6.3优化测试表达式364.7MINIC编译器的使用方法373第一章MiniC语言编译器简介随着计算机科学技术的飞速发展，计算机技术被应用在了越来越广泛的领域，实现各种各样功能的计算机程序被大量地开发出来，应用在我们的生活、学习和工作当中。相应地，也产生了许多用以编写这些计算机程序的高级程序设计语言。程序编制者通过特定语言的编译器将自己编写的源程序翻译为特定机器上的目标程序，从而能够最终达到程序执行的目的。从20世纪60年代以来，编译器设计就一直是计算机研究发展和开发领域中的一个活跃主题。虽然编译器设计已有很长的历史，并且也是一门相对成熟的算机技术，但编译器毕竟是一种实现由高级语言源程序至机器或汇编指令的高映射工具，随着计算机软、硬件水平的飞速发展，使得计算机应用日新月异，程序语言的设计在不断地变化，目标机体系结构也在不断地改进，软件越来越复杂，其规模也越来越大。尽管编译器设计问题在高级层次上没有变化（或变化很小），但当我们深入其内部研究时就会发现，编译器的内部构造其实也一直在变化。此夕卜，由于我们能够提供给编译器本身使用的计算资源也在不断增加。因此，现代编译器可以采用比以前更耗费时间和空间的算法。当然，编译技术研究人员也在1 继续努力开发新的、更好的技术来解决传统编译器的一些设计性问题。编译器是一种相当复杂的系统程序，其代码的长度可从几千行到几百万行不等，所以编写甚至读懂这样的一个程序都不是一件容易的事。绝大多数的计算机专业人员从来没有编写过一个完整的编译器，但是，几乎所有形式的计算均要用到编译器，而且任何一个与计算机打交道的专业人员都应该掌握编译器的基本结构和操作。除此之外，计算机应用程序中经常遇到的一个任务就是有关命令解程序和界面程序的开发，这比编译器的开发规模要小，但使用的却是很类似的技术。因此，掌握编译器的开发技术具有非常重大的实际意义。编译器的设计从本质上来说是一种工程活动，它所使用的方法必须很好地解决现实中出现的各种翻译问题（即用真实的语言编制且在真实的机器上能够执行的真实的程序）。大多数情况下，开发编译器的人必须接受他们面对的语言和机器，很少能够去影响或改善这两者的设计。在开发过程中做什么样的分析和转换，以及什么时候去做，这些都是工程上的选择，但正是这些选择决定了一个编译器的性能高低。本实验就建立在一个自主开发的名为MINIC的微型编译器基础之上，该编译器虽然功能弱于像TurboC或BorlandPascal这样的经典编译器，但也已经4完全具备了一个编译器应有的所有特征。在编译器技术的发展过程中，如何提高编译的效率一直是核心研究目标之一，编译效率主要是根据该编译器所生成的目标代码在执行过程中的时间指标和空间指标来衡量的，所以编译优化也必定围绕时间和空间这两个方面来实施。在编译过程中针对代码优化的技术有很多，它们通常是通过搜集源代码或中间代码的定信息，然后利用这些信息对代码中的数据结构或算法操作实施等价的改进变换，从而力求在时间效率和空间效率上达到一个最佳平衡点。编译器的开发者们总是希望能够将各种代码优化技术充分地运用在自己的编译器设计中，但往往事与愿违，毕竟优化操作本身也是需要付出开销的。在MINIC编译器的开发过程中，虽然没有运用到太复杂的代码优化技术，但通过本实验的研究，在现有开发的MINIC编译器基础之上，能够在后续相关项目的开发中有效地提高程序代码的编译质量，对于自己以后的研究和发展方向将起到非常大的推动作用。这正是本实验的研究意义所在。本实验是以MINIC微型编译器的项目开发为基础，该项目的开发目标是自定义一种MINIC高级语言，然后编码实现出MINIC语言的编译器(称为MINIC编译器)，完成将MINIC语言源程序翻译为基于MM机(MiniMachine)的目标代码的任务，这是本实验的实际应用背景。编译器的开发具有极高的实用价值和意义，高级语言编译器的性能决定了基于该语言平台所开发出的软件的质量。所以国内外很多大学的科研和技术人员也在积极地开展这方面的技术探索和项目实践。他们大多是以特定的软件项目为景来进行一些与编译器开发相关或类似的研究分析，他们的研究目标大多是基于某种实验型高级语言的编译器开发和优化改进，然后把有价值的研究成果移植或运用到产品级的编译器开发中（比如.NET平台编译器）。最近十年以来，国外关于编译器设计的发展动态主要体现在：首先，编译器采用了大量的更加复杂的算法，主要用于推断或简化程序中的信息，这又与更为复杂的程序设计语言的发展结合在一起，其中典型的有用于函数语言编译的2 Hindley-Milner类型检查的统一算法。其次，编译器已越来越成为基于窗口的可视化交互开发环境（InteractiveDevelopmentEnvironment，IDE）的一部分，该环境还包括了智能编辑器、连接程序、调试程序以及项目管理程序等，已经成为了事实上的编译器行业标准。另一方面，尽管国内外的专家学者们近年来在编译原理领域进行了大量的研究，但是基本的编译器设计原理在近20年中都没有多大的改变，它现在正迅速地成为计算机科学课程中的中心环节之一。5在九十年代，作为GNU项目或其它开放源代码项目的一部分，许多免费的编译器或编译器构造工具被开发出来。这些工具可用来编译数种程序设计语言的源程序（典型的就是GCC）。它们中的一些项目被认为是高质量的，而且对现代编译理论感兴趣的人都可以较容易地得到它们的免费源代码。典型的是在1999年，SGI公布了他们的一个工业化的并行优化编译器Pro64的源代码，随后被全世界多个编译器研究小组用做研究平台，并命名为Open64。Open64的设计结构好，分析优化全面，是编译器高级研究的理想平台。反观国内，现阶段对于编译技术的相关研究，基本上都是着眼于特定编译器的特定部分来展开的，而本实验将研究和分析的重点主要集中于一个完整的微型编译器的构造的讨论。6第二章理论基础2.1编译系统概述2.1.1什么是编译器编译器，是将便于人类编写、阅读、维护的计算机高级语言程序翻译为机器能够识别、运行的计算机低级语言程序的一种系统软件。编译器将源程序(SourceProgram)作为输入，翻译产生使用目标语言的等价目标程序(TargetProgram)。其中，源程序一般为高级语言(High-levellanguage)，如Pascal，C+等，而目标语言则是汇编语言或目标机器的机器语言。编译器的这一作用如图2-1所示：源我序k编译揣I标程序图2-1编译器的作用2.1.2编译器的产生本世纪四十年代，由于冯?诺依曼在存储程序计算机方面的先锋作用，使得编写一串代码或程序已成为可能和必要，这样计算机就可以执行所需的计算。在初期，这些程序都是用机器语言编写，编写或维护这样的代码是非常枯燥乏味且效率低下的，所以机器语言很快就被汇编语言代替了。汇编语言大大提高了程序编写速度和准确度，但它也有许多缺点。于是发展编程技术的下一个重要革新就是以一个更加类似于数学定义或自然语言的简洁形式来编写程序的功能操作，它应与任何机器都无关，而且也可由一个程序翻译为可执行的代码。随着对形式语言和自动机理论的研究，人们对高级程序设计语言的认识越来越深，对编译器结构的设计也越来越清晰。人们通过对形式语言文法规则的研究，相当完善地解决了分析问题。当分析问题变得相对成熟时，设计者们又花费了很多的精力来研究这一部分的编译器的自动构造，这就是分析程序生成器(parsergenerator)最初的雏形。类似地，对有穷自动机的研究也促进了一种称为扫描程序生成器(scannergenerator)工具的发展。接着，人们又深化了生成有效目标代码的方法，这些就构成了传统的编译器，在这个过程中运用到的技术被一直使用今。2.2编译器的结构严格地说，编译器是一个将高级语言源程序转换成能在一台计算机上执行的等价目标代码或机器语言程序的软件系统。这个定义可扩展到包含将一个高级语言程序转换成汇编语言程序的系统，将一个高级语言程序转换成另一种高级语言程序的系统，从一个机器语言程序转换成另一种机器语言程序的系统，从一种高级语言程序转换成一种中间语言程序的系统，等等。在通常情况下，一个编译器应由一系列的阶段组成，这些阶段从要编译的源程序的字符序列开始，依次对一个给定形式的程序进行分析，并得到一种新的表示形式，在大多数情况下最终产生一个可以与其他目标代码链接，并装入一台机器的存储器中执行的可重定位目标模块。这一编译过程一般由如下6个阶段构成，3 它们执行不同的逻辑操作如图2-2所示：记号中间代码源程序H苏代阈图2-2编译器的阶段示意图文字表ir语法例注释树语义分析程序语法分祈程序源代码忧化程序目标代码优化程序代码生成器投描程序错误处理器符号表（1）扫描程序（scanner）在这个阶段，编译器阅读源程序（通常以字符流的形式表示，比如本实验设计的MINIC语言的源程序.c），由扫描程序执行词法分析（lexicalanalysis):它将字符序列收集到称为记号（token）的单元中，也就是说，将其识别为一个个符合编程语言词法规范的单词符号。实际上，一个扫描程序所做的工作与自然语言对英文单词的拼写是十分类似的。扫描程序还可完成与识别记号一起执行的其他操作，例如，可将相应的记号输入到对应的符号表中。（2）语法分析程序（parser）语法分析程序从扫描程序中获取记号形式的代码，并完成定义程序结构的语法分析（syntaxanalysis），根据语言的语法规则将上阶段产生的单词串分解成各类语法单位（如表达式、语句、子过程等），这与自然语言中关于某篇文章的句子的语法分析类似。语法分析定义了程序的结构元素及其关系。通常将语法分析的结果表示为分析树或语法树。（3）语义分析程序（semanticanalyzer）程序的语义就是它的“意思”，程序如何运行以及运行结果都由它的语义来决定。大多数程序设计语言具有在执行之前被确定语义的特征，这些特征不容易用语法结构表示，更无法用词法分析程序进行分析，这些特征被称为静态语义。语义分析程序的职责就是分析这样的语义，为代码生成阶段搜集相关的语义信息。一般程序设计语言的典型静态语义有声明和类型检查。而在程序执行阶段才能定的程序特性称为动态语义，语义分析程序无法对这类特性做出分析。语义分析程序还要计算被称为属性（attribute）的程序固有信息，如数据类型、值等。语义分析程序通常将计算后的属性值添加到语法树中（也可将属性添加到符号表中）。（4）源代码优化程序（sourcecodeoptimizer）完善的编译器通常包括许多代码改进和优化步骤。这些优化和改进一般是在语义分析之后完成的。在语法分析和语义分析的基础之上，将源程序变换为等价的中间代码。所谓中间代码，是指一种结构简单、含义明确、形式多样化的记号系统，它比较容易能转换为目标代码。优化程序将源代码以中间代码（intermediatecode）的形式输出，进而完成对源代码的相应优化处理，目的是使将来生成的目标代码更为高效（即省时间、省空间）。（5）代码生成器（codegenerator）这是编译的最后必备阶段，它将中间代码（或经优化后的中间代码）转换成特定机器上的绝对指令代码或可重新定位的指令代码或汇编指令代码。由于该阶段的工作与硬件系统结构和机器指令含义有关，涉及到硬件系统功能部件的运用、机器指令的选择、各种数据的存储空间分配以及寄存器调度等，也就是说目标机器的特性成为了主要因素，所以这个阶段的工作相当复杂。正是出于这点考虑，本实验设计选择了面向MM(MiniMachine)机的汇编指令代码作为MINIC编译器的目标代码。(6) 目标代码优化程序(targetcodeoptimizer)在这个阶段中，编译器尝试着改进由代码生成器生成的目标代码。这种改进包括对编址模式的选择、提高性能、将速度慢的指令更换成速度快的以及删除多余的操作等。除了这6个阶段，编译器通常还包含一张符号表和访问该表的若干例程，以及针对编译过程中发现的各种错误进行检查和处理的错误处理程序，它们在编译过程的所有阶段都会使用到。上述编译过程的阶段划分只是一个典型模式，事实上并非所有的编译程序都分成这6个阶段，有些编译程序并不生成中间代码，有些编译程序并不进行优化，有些最简单的编译程序甚至在语法分析的同时产生目标代码。编译器生成的目标代码可以是可重定位目标代码或汇编代码，如果是汇编代码则需要再用汇编器生成可重定位目标代码，本实验设计的MINI编译器生成的目标代码可以是汇编代码。2.3编译器的组织2.3.1编译的分遍在2.2节中我们讨论了一个编译器的典型结构，简要介绍了编译器的6个阶段各自应完成的基本工作，并通过图2-2指出了它们之间的相互关系，但需要注意的是，这些关系仅代表它们之间的逻辑关系，并不一定就是执行时间上的先后顺序。事实上，可按不同的执行流程来组织上述各阶段的工作，这在很大程度上依赖于编译过程中对源程序扫描的遍数，以及如何划分各遍扫描所进行的工作。这里所说的“遍”，是指对源程序或其内部表示从头到尾扫视一次，并进行有关的加工处理工作，每一遍的工作都是从获取上一遍的工作结果开始，经过本遍的加工后，4 将结果保存起来以便交给下一遍。例如，对于要求经一遍扫描就能完成从源代码到目标代码翻译的编译程序，我们可以语法分析程序为中心来组织它的工作流程，这样就不必产生中间代码，显然，这种做法所得到的目标代码的质量是不能保证的，总体来说弊大于利。10对于绝大部分语言（例如Pascal或C），实现一遍扫描的编译程序是非常困难的，所以宜于采用多遍扫描的编译程序结构。具体的做法是将整个编译程序划分为若十个相继执行的模块，每一模块都对它前一模块的输出扫描一遍，并在扫描过程中完成前述6个阶段中的一个或几个，然后将工作结果保存下来供下一模块加工。显然，第一个模块所扫描的是字符序列形式的源程序，最后一个模块所输出的是目标代码，而每一个中间模块输出的是与源程序等价的内部表示或中间代码。2.3.2分遍的设计在设计一个编译程序时，如何确定扫描遍数，如何组织各遍中的工作，主要取决于源语言的具体情况及编译程序运行的具体环境，如语言的结构、计算机软硬件的配置，以及对编译程序本身运行效率的要求等等。一般而言，多遍扫描源程序具有如下优点：（1）由于采用了模块结构，各遍扫描的功能相对独立，整个编译程序的结构比较清晰。（2）由于对源程序及其内部表示进行多次扫视和加工，有利于进行比较细致和充分的代码优化处理。（3）由于可将编译程序按模块依次调入内存，有利于采用覆盖技术，以减少执行编译程序时所占的内存空间。由于分遍问题对具体语言及编译程序的运行环境有很强的依赖性，经过权衡，本实验设计的MINI编译器采用了4遍的扫描策略。2.4编译器中的主要数据结构当然，编译器的各个阶段使用的算法与支持这些阶段的数据结构之间的交互是非常密切的。编译器的编写者在实施这些算法的同时应尽可能地保证它们不过于复杂，最理想的情况是：该编译器在编译时所耗费的时间与程序大小成线形比例，即时间复杂度为O(n)。能否达到这样的理想情况，很大程度上取决于所采用的数据结构，它们是各个阶段都需要使用到的，并用来在各阶段之间交流信息。通常编译器中的主要数据结构包括：记号、语法树、符号表、常数表、中间代码、临时文件等。112.5编译程序的开发2.5.1历史与发展在编译器开发的原始阶段，人们主要用机器语言或汇编语言来构造编译程序，难度极大且效率很低。现在的大部分编译器是用某种高级语言开发的，这样更节约时间，而且易读、易改、易移植，同时也便于进行编译器的优化设计。相信在不久的将来，编译器的开发将主要借助于成熟的自动化生成编译程序技术。2.5.2开发注意事项（1）源语言：对被编译的源语言，要深刻理解其结构和含义。在定义MINIC语言的过程中，是通过严格制定其词法规则、语法规则和语义规则来达到的。（2）目标语言：了解硬件的系统结构和操作系统的接口MINIC编译器的目标语言选择为面向MM机的汇编代码。（3）编译技术：词法分析、语法分析、语义分析、代码优化及代码生成的相关技术有很多，必须根据所开发的编译器的需求和特点来选择最合适的编译技术和方法。关于MINIC编译器中使用到的编译技术可详细参考论文第四章。（4）各种具体因素：例如系统功能要求、硬件开发环境、软件开发工具等。2.5.3编译技术和软件工具为了提高软件开发的效率和保证开发质量，人们除了要遵循软件工程中对软件开发过程的规范化或标准化之外，还应尽量使用先进的软件开发技术和相应的软件工具，而大部分软件工具的开发，常常要用到编译技术和方法。实际上编译程序本身也是一种软件开发工具。为了提高编程效率，缩短调试时间，软件工作人员研制了不少对源程序处理的工具，这些工具的开发不同程度地用到编译程序7 各个部分的技术和方法，典型的有下面几种：（1）语言的结构化编辑器：结构化编辑器是引导用户在语言的语法制导下编制程序，能自动地提供关键字和与其匹配的关键字，这样可以减少语法上的误，加快对源程序的输入和调试，提高效率和质量。现在的可视化开发工具基本都具备了这个功能。（2）语言程序的调试工具：调试是软件开发过程中一个重要环节，凡是对算法的实现错误或程序没能反映算法的功能等错误就需用调试器来协助解决。调12试器的功能越强则实现越复杂，它必须与语法分析、语义处理有紧密联系。（3）语言程序测试工具：对源程序进行语法分析并制定相应表格，检查变量定值与引用的关系；也可在源程序的适当位置插入某些信息，并用测试用例记录程序运行时的实际路径，将运行结果与期望的结果进行比较分析，帮助编程人员快速查找问题所在。（4）高级语言之间的转换工具：为了减少重新编制程序所耗费的人力和时间，就要解决如何把一种高级语言转换成另一种高级语言，乃至汇编语言转换成高级语言的问题，这种异种程序设计语言之间的翻译转换工作要对被转换的语言进行词法和语法分析，只不过生成的目标语言是另一种高级语言而已，这与实现一个完整的编译程序相比工作量要少些。（5）并行编译技术：随着并行机及多处理机的发展，对软件的并行处理提出了新的要求，特别是并行编译技术发展很快。运用重构技术把已有的串行语言编写的程序经过分析分解成可并行的成分，然后分配到多处理机上运行。如果编程人员能按程序设计情况写出并行语言程序，那么两者结合将产生更高的效率。13第三章MINIC语言和MINIC编译器3.1MINIC编译器的开发背景和意义编译器是一种相当复杂的程序，其代码的长度可从几千行到几百万行不等。编写甚至读懂这样的一个程序都非易事，大多数的计算机专业人员从来没有编写过一个完整的编译器。但是，几乎所有形式的计算均要用到编译器，而且任何一个与计算机打交道的专业人员都应该掌握编译器的基本结构和操作。除此之外，计算机应用程序中经常遇到的一个任务就是命令解释程序和界面程序的开发，这比编译器要小，但使用的却是很类似的技术。因此，掌握这一技术具有非常重大的实际意义。虽然MINIC只是一个规模很小的微型编译器的开发，但所谓“麻雀虽小，五脏俱全”，作为一次较为完整的编译开发实践，它已经足够让我透彻地了解一个编译器开发过程了，同时能更深刻地理解和运用编译开发过程中的众多技术和方法，并能在此基础上针对编译器的优化展开深入的讨论，这些对于自己以后的研究和发展方向将起到非常大的推动作用。MINIC编译器以C语言作为开发语言，以TurboC2.0作为开发工具，MINIC编译器的各个阶段以模块的形式完成，最后以项目文件为单位来编译生成MINIC编译器的可执行文件。3.2 MINIC语言的基本描述MINIC语言是本实验设计要实现的一种微型语言的名称，该语言的源程序为文本形式的ASCII字符序列。考虑到针对现有的处理器来说，如果使用真正的机器代码作为MINIC编译器的目标语言会太过于复杂，所以MINIC语言将目标程序简化为一个假定的简单处理器的汇编语言，这个假定的处理器称为MM机(MiniMachine)。可在任意一种文本编辑器中编辑MINIC语言的源程序并保存为扩展名为.min的文件，然后用命令行的形式调用MINIC编译器(MINIC.EXE)对该源程序进行编译，经过词法分析、语法分析并在此基础上展开语义处理，如果源程序中没有错误，则最终生成目标代码即基于MM机的指令文件(扩展名为.mm)。这种目标代码文件可以使用MM机的模拟程序(MM.EXE)来读取并执行，从而14得到程序运行结果。MINIC语言的程序结构很简单，它的语法与C相似但规模小于C语言。MINIC源程序是一个由分号分隔开的语句序列。MINIC只有两个控制语句：if语句和while语句，这两个控制语句本身也可包含语句序列。if语句有一个可选的else部分。除此之外，还有数据的输入和输出（输入语句一次只读入一个变量，而输出语句一次只输出一个表达式）。MINIC的表达式也局限于布尔表达式和整型算术表达式。布尔表达式由对两个算术表达式的比较组成，所有比较使用和二比较运算符。算术表达式可以包括整型常数、变量、参数以及4个整型算符+、-、*、/，它们具备和通用语言相似的数学属性。布尔表达式通常只作为测试条件出现在控制语句中。虽然MINIC缺少实用程序设计语言（如C、Pascal）所需要的许多特征比如数组和指针等，但作为一次完整的编译开发实践，它已经足够体现出一个编译器的开发过程了。3.3 MINIC编译器的功能MINIC编译器的主要任务是分析基于MINIC语言规范的字符组成的MINIC源程序.min，把它们识别为一个个具有独立意义的单词符号（Token），并识别其有关属性再转换成长度统一的属性字，以供后续语义部分分析使用。简单的说，MINIC编译器的功能就是扫描MINIC源程序，识别单词，转换成属性字，再经过语义处理和代码生成，最终得到目标代码文件即基于MM的指令代码文件.mm。一般的说，MINIC编译器实现了下列几项功能：（1）从MINIC源程序中逐一取出单词。（2）构造语法树和静态符号表。（3）识别单词的属性并填入构造好的符号表中。（4）将单词转换成属性字，并输出二元组属性字流。（5）将符号表提供给语义分析程序加工处理。（6）生成目标代码并实施代码优化。（7）提供基本出错处理。153.4 MINIC编译器的程序结构MINIC编译器的核心模块（1）主控模块main.c：MINIC编译器的主程序，它还负责分配和初始化全程变量。（2）词法扫描程序cifa.c:将源程序的字符序列收集到称作记号（token）的有意义单元中，即完成与语言单词拼写相类似的任务。（3）语法分析程序yufa.c:从词法扫描程序中获取记号形式的源代码，并完成定义程序结构的的语法分析，生成语法树，记录符号表。（4）语义分析程序yuyi.c:分析程序的静态语义，包括声明和类型检查等，将语义信息添加到语法树结构中并进一步填写符号表。（5）代码生成器last.c:将MINIC语言的源程序翻译为目标程序即基于MM机的指令程序，并进行适当的代码优化。3.4.1 MINIC编译器的文件组成表3-1MINIC编译器的文件组成.h.call.h无数据类型的定义和编译器的全程变量无main.cMINIC编译器主程序func.hfunc.c实用程序函数cifa.hcifa.c词法分析程序yufa.hyufa.c语法分析程序hash.hhash.c符号表的杂凑表yuyi.hyuyi.c语义分析程序code.hcode.c用于依赖目标机器的代码生成实用程序last.hlast.c基于MM机的目标代码生成和优化程序所有代码文件都包含了all.h这个头文件，它包括了编译器中各种数据类型的定义和整个编译器均可能使用到的全局变量的定义。main.c文件是MINIC编译器的主程序，它还负责分配和初始化全程变量。其它的模块都以文件对即h头文件/c代码文件组成（如表3-1所示），在头文件中给出了外部可用的函数原型以及在相关代码文件中的实现（包括静态局部函数）。cifa、yufa、yuyi和last这4个文件分别与词法扫描程序、语法分析程序、语义分析程序和代码生成器这4个阶段16对应。func文件包括了一些实用程序函数，在生成源代码的内部表示（语法树）、显示列表与处理出错信息时均需要使用到这些函数。hash文件包括执行与MINIC应用相符的符号表的杂凑表。code文件包括用于依赖目标机器MM的代码生成实用程序。3.4.2 MINIC编译器的分遍虽然MINIC编译器规模较小，但仍由4遍构成：第1遍由构造语法树的扫描程序和分析程序组成；第2遍和第3遍执行语义分析，其中第2遍构造符号表而第3遍完成类型检查；第4遍是代码生成器。所有的4遍由主函数main.c来负责驱动。2.5 MINIC编译器中的主要数据结构下面列举出在MINIC编译器中使用到的主要数据结构，它们通常在编译的多8 个阶段都需要使用到，并用来在各阶段中共享一些特定数据。（1）记号（token）当扫描程序将若干个字符收集到一个记号中时，它通常是以符号表示这个记号的，也就是说，用一个枚举数据类型的值来表示源程序的记号集。有时还必须保留字符串本身或由此派生出的其他信息（例如：与标识符记号相关的名字或数字记号值）。在MINIC编译器中，扫描程序一次只需要生成一个记号（这称为单符号先行），考虑到这种情况，可以用全程变来量放置记号信息。（2）语法树（syntaxtree）如果语法分析程序确实生成了语法树，它的构造通常为基于指针的标准结构，在进行分析时动态分配该结构，则整棵树可通过一个指向根节点的单个指针变量来表示。结构中的每一个节点都是一个记录，它的域表示由分析程序和之后的语义分析程序收集的信息，例如，一个表达式的数据类型可作为表达式的语法树节点中的一个域。为了节省空间和保证信息完整性，这些域也可以动态分配或存放在诸如符号表的其他数据结构中，这样就可以有选择地进行分配和释放或只需存储指针值。（3）符号表（symboltable）符号表中的信息与标识符（函数、变量、常量以及数据类型等）有关。它几乎与编译器的所有阶段交互：扫描程序、分析程序或将标识符输入到表格中的语17义分析程序；语义分析程序将增加数据类型和其它语义信息；优化阶段和代码生成阶段也将利用由符号表提供的信息生成正确而恰当的代码。因为在编译的全程中对符号表的访问非常频繁，所以插入、删除和访问等符号表操作都必须比常规操作更有效。尽管可以使用各种树的结构，但杂凑表却是能达到这一要求的最理想的数据结构。（4）常数表（literaltable）常数表的功能是存放在该源程序中用到的所有常量和字符串，因此快速插入和查找在常数表中也十分重要。但是，在其中却无需删除操作，这是因为它的数据全程应用于程序而且同一常量或字符串在常数表中只会记录一次。通过允许重复使用常量和字符串，常数表对于缩小程序在存储器中的大小显得非常重要。（5）中间代码（intermediatecode）根据中间代码的类型（例如三元式代码和P-代码）和优化的类型，该代码可以是字符串数组（指针数组）、临时文本文件或是结构的连接列表。对于进行复杂优化的编译器，应特别注意选择允许简单重组的中间代码表示。(6) 临时文件(temporaryfile)由于内存空间紧张和地址模式的限制，计算机过去一直未能在编译器工作时将整个程序保留在存储器中。这一问题已经通过使用临时文件来保存翻译时中间步骤的结果或通过“匆忙地”编译(也就是只保留源程序早期部分的足够信息用以处理翻译)解决了。由于存储器的限制在当前看来已经基本不成问题了，所以现在可以将整个编译单元放在存储器之中，特别是在分遍编译的语言中能够极大地提高编译效率。但是偶尔还是会发现需要在某些编译步骤中生成中间文件。其中比较典型的是代码生成时需要反填(backpatch)地址。例如，当翻译如下的条件语句时：ifx=0.else.编译器在知道else部分代码的位置之前是无法生成该条件语句的真实代码的：CMPX,0JNENEXT/现在NEXT的位置还是未知NEXT:通常，必须为NEXT的值留出一个空格，一旦知道NEXT的值后就会将该空9 格填上，这称为反填，利用临时文件可以很容易地做到这一点。18第四章MINIC编译器的实现MINIC编译器从整体上被划分为5个阶段：词法分析、语法分析、语义分析、代码生成和代码优化，这5个阶段分别用不同的程序模块来实现(如表3-1)。一个MINIC源程序经过MINIC编译器的编译之后，生成面向MM机的指令目标代码，在整个编译过程中，这5个阶段分别承担了相应的翻译任务。4.1词法分析阶段4.1.1概述编译器的词法分析阶段可将源程序读作有序字符文件并将其扫描分解为若干个记号(token)。记号与自然语言中的单词类似：每一个记号都是表示源程序中信息单元的字符序列。典型的有：关键字(keyword)，例如if和while，它们是字母的固定串，在该语言中具有特定的含义；标识符(identifier)是由用户定义的串，它们通常由字母和数字组成并由一个字母开头，例如变量名函数名等；运算符(operationsymbol)是完成某种固定操作的符号，如+、-、*、/等，这些操作所施加的对象称为运算量；特殊符号(specialsymbol)，如分号、引号、花括弧等。由于扫描程序的任务是格式匹配的一种典型应用，所以需要研究在扫描过程中的格式说明和识别方法，其中最主要的工具就是正则表达式和有穷自动机。考虑到扫描程序是编译器中处理源代码输入的第一个阶段，而且由于这个输入经常需要耗费较多的额外时间，所以扫描程序的操作也就必须尽可能地高效了。因在构造过程中需要特别注意扫描程序结构的一些实际细节。扫描程序的构造问题的研究可分为以下几个部分：首先，给出扫描程序操作的一个概貌以及所涉及到的结构和概念。其次是掌握正则表达式，它是用于表示程序设计语言的词法构成结构的串格式的标准表示法，优点是非常简练和准确。接着是有穷自动机，它是对由正则表达式给出的串格式的识别算法，自动机比正则表达式更直观形象且利于程序实现。最后，一旦决定采用有穷自动机表示识别10 过程时，如何用代码实现该自动机即编写执行该识别过程的程序就成为了关键。194.1.2 MINIC词法分析程序的实现MINIC语言的记号分为3种典型的类型：关键字、特殊符号和“其它”记号。关键字一共有8个，它们的含义类似于C语言中的相应关键字。特殊符号共有10种：分别是4种基本的整数运算符号，2种比较符号（等号和小于号），以及左括号、右括号、分号和赋值符号。其中，除了赋值符号是两个字符的长度之外，其余均为单个字符。“其他”记号就是数和标识符了，数是一个或多个数字的序列，而标识符又是一个或多个字母的序列。所有这些记号归纳如下表4-1：表4-1MINIC语言的记号8if、else、while、goto、do、void、continue、break10+-*/=();:=数标识符(1个或更多的数字序列)(1个或更多的字母序列)除了上表的记号之外，MINIC语言的源程序还要遵循以下的词法规则：代码应是自由书写格式；空白符由空格、制表位和新行组成。所有的记号都可以用下图4-1的DFA来识别:图4-1MINIC扫描程序的完整DFA20需要注意的是，图4-1中的DFA并未包括关键字的识别，这是因为关键字和标识符的结构相同，在MINIC编译器的设计中，仅当识别出了一个标识符之后才考虑通过查找关键字表的方式来判断它是否为关键字。关于这个DFA的实现，主要包含在cifa.h和cifa.c文件中，其核心函数是getToken()，它消耗输入字符并按图4-1的DFA来返回下一个被识别的记号，使用的控制结构主要是一个双重嵌套switch多分支选择语句，使用的数据结构主一个有关“记号类型”的列表，该列表在all.h中被定义为枚举类型，该枚举类型中包含了表4-1中所有的记号以及文件结束记号EOF和错误记号ERROR。扫描程序在识别出每个记号的同时，还会计算出该记号的特性(比如串值)并放入变量tokenString中，这个tokenString变量和getToken()函数是提供给MINIC编译器其他部分的唯一两个服务。整个扫描程序使用到了3个全程变量：文件变量source、文件变量listing、行号变量lineno。扫描程序的字符输入是由getNextChar()函数提供的，该函数将一个256字节的字符缓冲区内的字符取到扫描程序中，当该缓冲区被耗尽时再从源程序文件即source文件中继续读取下一行。至于在图4-1中关于“INNUM”和“INID”到最终状态“DONE”的转换都应该是非消耗的，这种情况可通过提供ungetNextChar()函数往缓冲区中反填一个字符来保障。4.1.3关键字与标识符的识别MINIC对于关键字的识别，是通过先将它们看作是标识符，然后再在关键字表中查找它们来完成的。其实这种做法很普遍，不过由于在关键字表中查找过程的效率会影响到扫描程序的效率，所以通常需要更快速的查找算法(比如二分或哈希)。不过这个问题在MINIC看来没有必要，因为MINIC语言一共只有8个关键字，对于这种小型表格而言，MINIC扫描程序使用了一种最简便的方法一线性搜索，即按照关键字表的顺序从表头到表尾搜索每个关键字，具体的搜索过程是由函数reservedLookup()完成的。4.1.4为标识符分配空间由于tokenString变量的长度固定为40，即任何标识符的长度不能超过40个字符，因此如果为每一个标识符都分配一个固定的40字符长度的数组，那么就会浪费很多的内存空间(这是因为通常情况下绝大多数的标识符都很短)。出于这点考八、n虑，在MINIC编译器的func.c中提供了一个实用函数copyString()，用以复制记21号串的有效部分，该函数通过C的标准动态分配函数realloc()来为某标识符申请它所需的空间，即实现了按需分配，解决了空间浪费的问题。4.2语法分析阶段4.2.1概述分析的任务是确定源程序在语法上的正确性，因此，它又被称作语法分析。程序设计语言的语法通常是由上下文无关的文法规则来定义，其方式同扫描程序识别的由正则表达式提供的记号的词法结构相似，上下文无关文法的确利用了与正则表达式中极为类似的命名惯例和运算。但二者的主要区别在于上下文无关法的规则通常是递归的。例如，一般来说if语句中应允许嵌套其他的if语句，但在正则表达式中却不能这样做。这个区别带来的作用很明显：上下文无关文法能识别的结构相比正则表达式能识别的结构大大地增加了，用作识别这些结构的算法也与扫描算法差别很大，这是因为它们必须使用递归调用或显式管理的分析栈，相应地，用作表示语言语义结构的数据结构现在也必须是递归而不再是线性的了。11 在语法分析中经常使用的基本结构是树结构，可称作分析树或语法树。4.2.2 MINIC语言的语法表4-2MINIC的BNF文法program?stmt-sequencestmt-sequence?stmt-sequence;statement|statementstatement?if-stmt|while-stmt|assign-stmt|read-stmt|write-stmtif-stmt?ifexpstmt-sequenceend|ifexpstmt-sequenceelsestmt-sequenceendwhile-stmt?whileexpstmt-sequenceassign-stmt?identifier:=expread-stmt?readidentifierwrite-stmt?writeexpexp?simple-expcomparison-opsimple-exp|simple-expcomparison-op?|=simple-exp?simple-expaddopterm|termaddop?+|-term?termmulopfactor|factormulop?*|/factor?(exp)|number|identifier22我们可以从表4-2中阅读出MINIC的语法规则：MINIC程序只是一个语句序列，它共有5种语句：if语句、while语句、输入语句、输出语句和assignment语句。if语句可以包含else子句。另外还可以看出：MINIC的表达式有两类：布尔表达式和算术表达式。布尔表达式使用比较运算符“二”和“”，通常用在if语句和while语句中作为测试条件；算术表达式使用整型运算符“+”、-”、*”、/”，它们具有左结合和常规的优先关系。与此不同，比较运算是非结合的(每个没有括号的表达式只允许一种比较运算)。比较运算符的优先权都低于算术运算符。另外，我们也可以把MINIC的表达式看作三类：算符表达式、常量表达式和标识符表达式。这些在all.h文件中都进行了相关的定义。MINIC中的标识符指的是简单整型变量，它没有类似数组或记录等类型的变量。MINIC中也无需显式的变量声明：任何一个变量只是通过出现在赋值语句左边或者read关键字的右边来隐式地声明。另外，变量只有全局作用域。MINIC的语句序列是指用N个分号分隔开来的N条语句。4.2.3MINIC语法分析程序的实现在实现MINIC的语法分析器时，采用的核心算法是自顶向下分析方法中的递归下降分析法。递归下降分析法是一种比较简单直观、易于构造的自顶向下的语法分析方法，它要求被分析的文法满足LL(1)文法，而我们在表4-2中描述的MINIC语言的所有文法是符合这一要求的。递归下降分析法的实现思想是针对文法中的每个非终结符号编写一个递归过程，每个过程的功能是识别由该非终结符号推出的串，当某非终结符号的产生式有多个候选式时能够按LL(1)形式惟一地确定选择某个候选式进行推导。MINIC的语法分析程序包括两个代码文件：yufa.h和yufa.c。其中yufa.h非常简单，只由一个声明组成：TreeNode*parse(void);它定义了语法分析程序yufa.c的核心函数parse()，从声明中可以看出该函数将返回一个表示语法树的指针。yufa.c文件由11个相互递归的过程组成，这些过程与表4-2中的文法直接对应：1个对应于stmt-sequence，1个对应于statement，5个分别对应于5种不同的语句，剩下4个对应于表达式的不同优先层次。由于MINI23C程序就是由语句序列构成，所以核心函数parse（）只需要直接调用stmt_sequence（），然后由递归下降程序经过递归调用和回调自动完成语法分析并生成相应的语法树，再传递给后续的语义分析阶段。4.3语义分析阶段4.3.1概述语义分析是一个用于计算编译过程中所需的附加语义信息的阶段。由于它包括了计算上下文无关文法和标准语法分析算法以外的信息（即语义信息），因此，它不能被视为语法。语义信息的计算与被翻译程序的最终含义或语义密切相关，因为编译器完成的语义分析是静态定义（在程序执行之前予以明确的），所以语义分析也可称作静态语义分析。在一个典型的静态类型的语言（如C语言）中，语义分析的工作通常包括构造符号表、记录声明中建立的名字的含义、在表达式和语句中进行类型推断和类型检查、在程序的不同作用域范围内判断变量的合法性。12语义分析可以分为两类：（1）第一类分析是正确性分析，要求根据编程语言的语义规则判定程序的正确性，并保证它能正确执行。对于不同的语言来说，语义分析的差异很大。比如在LISP和Smalltalk这类动态制导的语言中，可能完全没有静态语义分析；而在Ada或C这类语言中就有很强的静态语义分析需求，程序必须提交执行。其他的语言介于这两种极端情况之间（例如Pascal语言，不像Ada和C对静态语义分析的要求那样严格，也不像LISP那样完全没有要求）。（2）第二类分析是优化性分析，是由编译程序执行的用于提高翻译程序执行效率的分析。这一类分析通常包括对“最优化”或代码改进技术的实现。4.3.2 MINIC语言的语义MINIC语言在静态语义方面的要求比较简单，分析是由程序yuyi.c负责的。在MINIC中没有明确的声明，也没有命名的常量、数据类型或过程；名字只引用变量，变量在第一次使用时隐含地声明，所有的变量都是整数数据类型；也没有嵌套作用域，因此一个变量名在整个程序中有恒定的含义，符号表也不需要保存任何作用域信息。在MINIC中的类型检查也比较简单。它只有两种类型：整型和布尔型。仅有24的布尔型值是两个整数值进行比较的结果。因为没有布尔型运算符或变量，所以布尔值只出现在if或while语句的条件测试表达式中，不作为运算符的操作数或赋值给变量的值，同时，布尔值也不能使用write语句输出。下面把对MINIC语义分析程序的代码实现的讨论分成两个部分：首先讨论符号表的结构及其相关操作，然后讨论语义分析程序自身的操作（包括符号表的造和类型检查）。4.3.3 MINIC的符号表在MINIC语义分析程序的符号表的设计中，首先要确定哪些信息需要在符号表中保存。一般情况下，符号表需要包括数据类型和作用域信息，但考虑到MINIC语言本身没有作用域信息，并且所有的变量都是整型，因此MINIC符号表也就不需要保存这些信息了。然而，在代码生成阶段，变量需要分配存储器地址，并且因为该地址信息在语法树中也没有说明，所以符号表就成为了存储这些地址的最佳数据结构。其实，在MINIC符号表中记录的变量地址可以仅仅看成是整数索引，每次遇到一个新的变量就自增。另外，为了使符号表的作用更明显和强大，还将源程序中被访问变量的行号也记录下来，并且可以在编译完成后显示出来，便于用户调试程序，这一点在使用MINIC编译程序的过程中可以看到。关于符号表的代码被包含在hash.h和hash.c文件中。符号表使用的结构是分离的链式杂凑表，关于MINIC符号表的操作有如下几种：（1）st_delete操作：因为无作用域信息，故MINIC符号表不需delete操作。（2）st_insert操作：插入新符号时，除标识符之外，还需行号和地址参数。（3）st_lookup操作：查找符号表，提取相关符号的语义信息。(4) printSymTab操作：用于在编译完成后向用户打印符号表汇总信息。4.3.4 MINIC语义分析程序的实现MINIC的静态语义具有标准编程语言的特性，符号表具有继承属性，表达式的数据类型具有合成属性。符号表可以通过对语法树的前序遍历来建立，类型检查可以通过后序遍历来完成。虽然这两个遍历能够较容易地合并成一个遍历，但为了使符号表建立和类型检查这两个处理步骤更加清晰，仍然把它们分成语法树上两个独立的遍。因此，语义分析程序与编译器其他部分的接口实际上就是两个25函数：buildSymtab()完成语法树的前序遍历(建立符号表)，当它遇到树中的变量标识符时，调用符号表的st_insert操作插入该变量，遍历完成后，再调用符号表的print操作来打印符号表信息到列表文件中typeCheck()完成语法树的后序遍历(执行类型检查)，在计算数据类型时把它们插入到对应的树节点，并把可能的类型检查错误记录到列表文件中。4.4 MINIC运行时环境4.4.1概述在前述内容中，已经讨论过了如何实现MINIC编译器静态分析的各阶段。主要包括词法扫描、语法分析和静态语义分析。这些分析仅仅取决于MINIC源语言的特性，而与目标语言（汇编语言或机器语言）