C语言编译器设计与实现.docx

C语言编译器设计与实现毕业论文目录摘要错误!未定义书签。Abstract错误!未定义书签。第一章绪论11.1 开发背景11.2 开发目标和意义21.3 当前编译器国外的发展情况3第二章理论基础62.1 编译系统概述62.1.1 什么是编译器62.1.2 编译器的产生62.2 编译器的结构72.3 编译器的组织102.3.1 编译的分遍102.3.2 分遍的设计112.4 编译器中的主要数据结构112.5 编译程序的开发122.5.1 历史与发展122.5.2 开发注意事项122.5.3 编译技术和软件工具12第三章C编译器可行性分析及总体设计153.1 可行性分析153.1.1 经济可行性153.1.2 技术可行性153.1.3 运行可行性163.1.4 时间可行性163.1.5 法律可行性163.2 C语言的基本描述173.3 C编译器的功能183.4 C编译器的程序结构183.4.1 C编译器的设计模式183.4.2 C编译器的文件组成203.5 C编译器中的主要数据结构20第四章C编译器的实现244.1 词法分析阶段244.1.1 概述244.1.2 C词法分析程序的实现254.1.3 关键字与标识符的识别274.1.4 词法识别具体实现274.2 语法分析阶段314.2.1 概述314.2.2 C语言抽象出来的文法规则324.2.3 C语法分析程序的实现384.3 语义分析阶段474.3.1 概述474.3.2 C语言的语义484.3.3 C的符号表484.3.4 C语义分析程序的实现494.4 中间代码生成阶段554.4.1 概述554.5 C编译器的使用方法及测试564.5.1 使用方法564.5.2 测试源文件564.5.3 测试词法分析574.5.4 测试语义分析及中间代码生成584.5.5 测试分析表文件的构造59参考文献62致谢63WORD版本第一章绪论1.1 开发背景随着计算机科学技术的飞速发展，计算机技术被应用在了越来越广泛的领域，实现各种各样功能的计算机程序被大量地开发出来，应用在我们的生活、学习和工作当中。相应地，也产生了许多用以编写这些计算机程序的高级程序设计语言。程序编制者通过特定语言的编译器将自己编写的源程序翻译为特定机器上的目标程序，从而能够最终达到程序执行的目的。从20世纪60年代以来，编译器设计就一直是计算机研究发展和开发领域中的一个活跃主题。虽然编译器设计已有很长的历史，并且也是一门相对成熟的计算机技术，但编译器毕竟是一种实现由高级语言源程序至机器或汇编指令的高效映射工具，随着计算机软、硬件水平的飞速发展，使得计算机应用日新月异，程序语言的设计在不断地变化，目标机体系结构也在不断地改进，软件越来越复杂，其规模也越来越大。尽管编译器设计问题在高级层次上没有变化（或变化很小），但当我们深入其部研究时就会发现，编译器的部构造其实也一直在变化。此外，由于我们能够提供给编译器本身使用的计算资源也在不断增加。因此，现代编译器可以采用比以前更耗费时间和空间的算法。当然，编译技术研究人员也在继续努力开发新的、更好的技术来解决传统编译器的一些设计性问题1。另一方面，很多编译“前端”技术，如文法、正则表达式、语法分析器以及语法制导翻译器等，仍然被广泛使用。1.2 开发目标和意义编译器是一种相当复杂的系统程序，其代码的长度可从几千行到几百万行不等，所以编写甚至读懂这样的一个程序都不是一件容易的事。绝大多数的计算机专业人员从来没有编写过一个完整的编译器，但是，几乎所有形式的计算均要用到编译器，而且任何一个与计算机打交道的专业人员都应该掌握编译器的基本结构和操作。除此之外，计算机应用程序中经常遇到的一个任务就是有关命令解释程序和界面程序的开发，这比编译器的开发规模要小，但使用的却是很类似的技术。因此，掌握编译器的开发技术具有非常重大的实际意义。编译器的设计的原理和技术还可以用于编译器设计之外的众多领域。因此，这些原理和技术通常会在一个计算机科学家的职业生涯中多次被用到。研究编译器的编写讲设计程序设计语言、计算机体系结构、形式语言理论、算法和软件工程。编译器的设计从本质上来说是一种工程活动，它所使用的方法必须很好地解决现实中出现的各种翻译问题（即用真实的语言编制且在真实的机器上能够执行的真实的程序）。大多数情况下，开发编译器的人必须接受他们面对的语言和机器，很少能够去影响或改善这两者的设计。在开发过程中做什么样的分析和转换，以及什么时候去做，这些都是工程上的选择，但正是这些选择决定了一个编译器的性能高低。本实验就建立在一个自主开发的名为C的微型编译器基础之上，该编译器虽然功能弱于像TurboC或BorlandPascal这样的经典编译器，但也已经完全具备了一个编译器应有的所有特征。虽然本实验只是一个规模很小的微型编译器的开发，但所谓“麻雀虽小，五脏俱全”，作为一次较为完整的编译开发实践，它已经足够让我透彻地了解一个编译器开发过程了，同时能更深刻地理解和运用编译开发过程中的众多技术和方法，并能在此基础上针对编译器的优化展开深入的讨论，这些对于自己以后的研究和发展方向将起到非常大的推动作用。C编译器以C+语言作为开发语言，以MicrosoftVisualStudio2012作为开发工具，C编译器的各个阶段以类的形式表示，最后以项目文件为单位来编译生成C编译器的可执行文件。本实验以MicrosoftVisualStudio2012作为开发工具，用标准C+进行开发，因此可以很好的的移植到其他平台（比如：linux，用g+编译生成可执行文件）。1.3 当前编译器国外的发展情况在编译器技术的发展过程中，如何提高编译的效率一直是核心研究目标之一，编译效率主要是根据该编译器所生成的目标代码在执行过程中的时间指标和空间指标来衡量的，所以编译优化也必定围绕时间和空间这两个方面来实施。在编译过程中针对代码优化的技术有很多，它们通常是通过搜集源代码或中间代码的特定信息，然后利用这些信息对代码中的数据结构或算法操作实施等价的改进变换，从而力求在时间效率和空间效率上达到一个最佳平衡点。编译器的开发者们总是希望能够将各种代码优化技术充分地运用在自己的编译器设计中，但往往事与愿违，毕竟优化操作本身也是需要付出开销的。在C编译器的开发过程中，虽然没有运用到太复杂的代码优化技术，但通过本实验的研究，在现有开发的C编译器基础之上，能够在后续相关项目的开发中有效地提高程序代码的编译质量，对于自己以后的研究和发展方向将起到非常大的推动作用。这正是本实验的研究意义所在。本实验是以C微型编译器的项目开发为基础，该项目的开发目标是自定义一种CWORD版本.高级语言，然后编码实现出C语言的编译器（称为C编译器），完成将C语言源程序翻译为基于MM机（MiniMachine）的目标代码的任务，这是本实验的实际应用背景。编译器的开发具有极高的实用价值和意义，高级语言编译器的性能决定了基于该语言平台所开发出的软件的质量。所以国外很多大学的科研和技术人员也在积极地开展这方面的技术探索和项目实践。他们大多是以特定的软件项目为背景来进行一些与编译器开发相关或类似的研究分析，他们的研究目标大多是基于某种实验型高级语言的编译器开发和优化改进，然后把有价值的研究成果移植或运用到产品级的编译器开发中（比如.NET平台编译器）。最近十年以来，国外关于编译器设计的发展动态主要体现在：首先，编译器采用了大量的更加复杂的算法，主要用于推断或简化程序中的信息，这又与更为复杂的程序设计语言的发展结合在一起，其中典型的有用于函数语言编译的Hindley-Milner类型检查的统一算法2。其次，编译器已越来越成为基于窗口的可视化交互开发环境（InteractivDeevelopmenEtnvironme，ntIDE）的一部分，该环境还包括了智能编辑器、连接程序、调试程序以及项目管理程序等，已经成为了事实上的编译器行业标准。另一方面，尽管国外的专家学者们近年来在编译原理领域进行了大量的但研是究基，本的编译器设计原理在近20年中都没有多大的改变，它现在正迅速地成为计算机科学课程中的中心环节之一。在九十年代，作为GNU项目或其它开放源代码项目的一部分许，多免费的编译器或编译器构造工具被开发出来这。些工具可用来编译数种程序设计语言的源（程典序型的就是GCC）。它们中的一些项目被认为是高质量的，而且对现代编译理论感兴趣的人都可以较容易地得到它们的免费源代码。典型的是在1999年，SGI公布了他们的一个工业化的并行优化编译器Pro64的源代码，随后被全世界多个编译器研究小组用做研究平台，并命名为Open64。Open64的设计结构好，分析优化全面，是编译器高级研究的理想平台。反观国，现阶段对于编译技术的相关研究，基本上都是着眼于特定编译器的特定部分来展开的，而本实验将研究和分析的重点主要集中于一个完整的微型编译器的构造的讨论。WORD版本第二章理论基础2.1 编译系统概述2.1.1 什么是编译器编译器，是将便于人类编写、阅读、维护的计算机高级语言程序翻译为机器能够识别、运行的计算机低级语言程序的一种系统软件。编译器将源程序(SourceProgram)作为输入，翻译产生使用目标语言的等价目标程序(TargetProgram)。其中，源程序一般为高级语言(High-levellanguage)，如Pascal，C+等，而目标语言则是汇编语言或目标机器的机器语言3。编译器的这一作用如图2-1所示：源程序A编译器A目标程序图2-1编译器的作用2.1.2 编译器的产生本世纪四十年代，由于冯·诺依曼在存储程序计算机方面的先锋作用，使得编写一串代码或程序已成为可能和必要，这样计算机就可以执行所需的计算。在初期，这些程序都是用机器语言编写，编写或维护这样的代码是非常枯燥乏味且效率低下的，所以机器语言很快就被汇编语言代替了。汇编语言大大提高了程序编写速度和准确度，但它也有许多缺点。于是发展编程技术的下一个重要革新就是以一个更加类似于数学定义或自然语言的简洁形式来编写程序的功能操作，它应与任何机器都无关，而且也可由一个程序翻译为可执行的代码。随着对形式语言和自动机理论的研究，人们对高级程序设计语言的认识越来越深，对编译器结构的设计也越来越清晰。人们通过对形式语言文法规则的研究，相当完善地解决了分析问题。当分析问题变得相对成熟时，设计者们又花费了很多的精力来研究这一部分的编译器的自动构造，这就是分析程序生成器（parsergenerator）最初的雏形。类似地，对有穷自动机的研究也促进了一种称为扫描程序生成器（scannergenerator）工具的发展。接着，人们又深化了生成有效目标代码的方法，这些就构成了传统的编译器，在这个过程中运用到的技术被一直使用至今。2.2 编译器的结构严格地说，编译器是一个将高级语言源程序转换成能在一台计算机上执行的等价目标代码或机器语言程序的软件系统。这个定义可扩展到包含将一个高级语言程序转换成汇编语言程序的系统，将一个高级语言程序转换成另一种高级语言程序的系统，从一个机器语言程序转换成另一种机器语言程序的系统，从一种高级语言程序转换成一种中间语言程序的系统，等等。在通常情况下，一个编译器应由一系列的阶段组成，这些阶段从要编译的源程序的字符序列开始，依次对一个给定形式的程序进行分析，并得到一种新的表示形式，在大多数情况下最终产生一个可以与其他目标代码，并装入一台机器的存储器中执行的可重定位目标模块。这一编译过程一般由如下6个阶段构成，它们执行不同的逻辑操作如图2-2所示4：（1） 扫描程序（scanner）在这个阶段，编译器阅读源程序（通常以字符流的形式表示，比如本实验设计的C语言的源程序.c），由扫描程序执行词法分析（lexicalanalysis）：它将字符序列收集到称为记号（token）的单元中，也就是说，将其识别为一个个符合编程语言词法规的单词符号。实际上，一个扫描程序所做的工作与自然语言中对英文单词的拼写是十分类似的。扫描程序还可完成与识别记号一起执行的其他操作，例如，可将相应的记号输入到对应的符号表中。（2） 语法分析程序（parser）语法分析程序从扫描程序中获取记号形式的代码，并完成定义程序结构的语法分析（syntaxanalysis），根据语言的语法规则将上阶段产生的单词串分解成各类语法单位（如表达式、语句、子过程等），这与自然语言中关于某篇文章的句子的语法分析类似。语法分析定义了程序的结构元素及其关系。通常将语法分析的结果表示为分析树或语法树。（3） 语义分析程序（semanticanalyzer）程序的语义就是它的“意思”，程序如何运行以及运行结果都由它的语义来决定。大多数程序设计语言具有在执行之前被确定语义的特征，这些特征不容易用语法结构表示，更无法用词法分析程序进行分析，这些特征被称为静态语义。语义分析程序的职责就是分析这样的语义，为代码生成阶段搜集相关的语义信息。一般程序设计语言的典型静态语义有声明和类型检查。而在程序执行阶段才能确定的程序特性称为动态语义，语义分析程序无法对这类特性做出分析。语义分析程序还要计算被称为属性（attribute）的程序固有信息，如数据类型、值等。语义分析程序通常将计算后的属性值添加到语法树中（也可将属性添加到符号表中）。（4） 源代码优化程序（sourcecodeoptimizer）完善的编译器通常包括许多代码改进和优化步骤。这些优化和改进一般是在语义分WORD版本.析之后完成的。在语法分析和语义分析的基础之上，将源程序变换为等价的中间代码。所谓中间代码，是指一种结构简单、含义明确、形式多样化的记号系统，它比较容易能转换为目标代码。优化程序将源代码以中间代码（intermediatecode）的形式输出，进而完成对源代码的相应优化处理，目的是使将来生成的目标代码更为高效（即省时间、省空间）。（5） 代码生成器（codegenerator）这是编译的最后必备阶段，它将中间代码（或经优化后的中间代码）转换成特定机器上的绝对指令代码或可重新定位的指令代码或汇编指令代码。由于该阶段的工作与硬件系统结构和机器指令含义有关，涉及到硬件系统功能部件的运用、机器指令的选择、各种数据的存储空间分配以及寄存器调度等，也就是说目标机器的特性成为了主要因素，所以这个阶段的工作相当复杂。正是出于这点考虑，本实验设计选择了与机器指令无关的三地址码的四元式表示形式。（6） 目标代码优化程序（targetcodeoptimizer）在这个阶段中，编译器尝试着改进由代码生成器生成的目标代码。这种改进包括对编址模式的选择、提高性能、将速度慢的指令更换成速度快的以及删除多余的操作等。除了这6个阶段，编译器通常还包含一符号表和访问该表的若干例程，以及针对编译过程中发现的各种错误进行检查和处理的错误处理程序，它们在编译过程的所有阶段都会使用到。上述编译过程的阶段划分只是一个典型模式，事实上并非所有的编译程序都分成这6个阶段，有些编译程序并不生成中间代码，有些编译程序并不进行优化，有些最简单的编译程序甚至在语法分析的同时产生目标代码。编译器生成的目标代码可以是可重定位目标代码或汇编代码，如果是汇编代码则需要再用汇编器来生成可重定位目标代码，WORD版本.本实验设计的C编译器生成的目标代码是三地址码的四元式表示形式。2.3 编译器的组织2.3.1 编译的分遍在2.2节中我们讨论了一个编译器的典型结构，简要介绍了编译器的6个阶段各自应完成的基本工作，并通过图2-2指出了它们之间的相互关系，但需要注意的是，这些关系仅代表它们之间的逻辑关系，并不一定就是执行时间上的先后顺序。事实上，可按不同的执行流程来组织上述各阶段的工作，这在很大程度上依赖于编译过程中对源程序扫描的遍数，以及如何划分各遍扫描所进行的工作。这里所说的“遍”，是指对源程序或其部表示从头到尾扫视一次，并进行有关的加工处理工作，每一遍的工作都是从获取上一遍的工作结果开始，经过本遍的加工后，将结果保存起来以便交给下一遍5。例如，对于要求经一遍扫描就能完成从源代码到目标代码翻译的编译程序，我们可以语法分析程序为中心来组织它的工作流程，这样就不必产生中间代码，显然，这种做法所得到的目标代码的质量是不能保证的，总体来说弊大于利。对于绝大部分语言（例如Pascal或C），实现一遍扫描的编译程序是非常困难的，所以宜于采用多遍扫描的编译程序结构。具体的做法是将整个编译程序划分为若干个相继执行的模块，每一模块都对它前一模块的输出扫描一遍，并在扫描过程中完成前述6个阶段中的一个或几个，然后将工作结果保存下来供下一模块加工。显然，第一个模块所扫描的是字符序列形式的源程序，最后一个模块所输出的是目标代码，而每一个中间模块输出的是与源程序等价的部表示或中间代码。2.3.2 分遍的设计在设计一个编译程序时，如何确定扫描遍数，如何组织各遍中的工作，主要取决于源语言的具体情况及编译程序运行的具体环境，如语言的结构、计算机软硬件的配置，以及对编译程序本身运行效率的要求等等。一般而言，多遍扫描源程序具有如下优点：（1） 由于采用了模块结构，各遍扫描的功能相对独立，整个编译程序的结构比较清晰。（2） 由于对源程序及其部表示进行多次扫视和加工，有利于进行比较细致和充分的代码优化处理。（3） 由于可将编译程序按模块依次调入存，有利于采用覆盖技术，以减少执行编译程序时所占的存空间。由于分遍问题对具体语言及编译程序的运行环境有很强的依赖性，经过权衡，本实验设计的编译器采用了简单的1遍扫描策略。2.4 编译器中的主要数据结构当然，编译器的各个阶段使用的算法与支持这些阶段的数据结构之间的交互是非常密切的。编译器的编写者在实施这些算法的同时应尽可能地保证它们不过于复杂，最理想的情况是：该编译器在编译时所耗费的时间与程序大小成线形比例，即时间复杂度为O（n）。能否达到这样的理想情况，很大程度上取决于所采用的数据结构，它们是各个阶段都需要使用到的，并用来在各阶段之间交流信息。通常编译器中的主要数据结构包括：记号、语法树、符号表、常数表、中间代码、临时文件等。2.5 编译程序的开发2.5.1 历史与发展在编译器开发的原始阶段，人们主要用机器语言或汇编语言来构造编译程序，难度极大且效率很低。现在的大部分编译器是用某种高级语言开发的，这样更节约时间，而且易读、易改、易移植，同时也便于进行编译器的优化设计。相信在不久的将来，编译器的开发将主要借助于成熟的自动化生成编译程序技术。2.5.2 开发注意事项（1） 源语言：对被编译的源语言，要深刻理解其结构和含义。在定义C语言的过程中，是通过严格制定其词法规则、语法规则和语义规则来达到的。（2） 目标语言：C编译器的目标语言选择为三地址的四元表达式。（3） 编译技术：词法分析、语法分析、语义分析、代码优化及代码生成的相关技术有很多，必须根据所开发的编译器的需求和特点来选择最合适的编译技术和方法。关于C编译器中使用到的编译技术可详细参考论文第四章。（4） 各种具体因素：例如系统功能要求、硬件开发环境、软件开发工具等。2.5.3 编译技术和软件工具为了提高软件开发的效率和保证开发质量，人们除了要遵循软件工程中对软件开发过程的规化或标准化之外，还应尽量使用先进的软件开发技术和相应的软件工具，而大部分软件工具的开发，常常要用到编译技术和方法。实际上编译程序本身也是一种软件开发工具。为了提高编程效率，缩短调试时间，软件工作人员研制了不少对源程序处理的工具，这些工具的开发不同程度地用到编译程序各个部分的技术和方法，典型的有下面几种7：（1） 语言的结构化编辑器：结构化编辑器是引导用户在语言的语法制导下编制程序，能自动地提供关键字和与其匹配的关键字，这样可以减少语法上的错误，加快对源程序的输入和调试，提高效率和质量。现在的可视化开发工具基本都具备了这个功能。（2） 语言程序的调试工具：调试是软件开发过程中一个重要环节，凡是对算法的实现错误或程序没能反映算法的功能等错误就需用调试器来协助解决。调试器的功能越强则实现越复杂，它必须与语法分析、语义处理有紧密联系。（3） 语言程序测试工具：对源程序进行语法分析并制定相应表格，检查变量定值与引用的关系；也可在源程序的适当位置插入某些信息，并用测试用例记录程序运行时的实际路径，将运行结果与期望的结果进行比较分析，帮助编程人员快速查找问题所在。（4） 高级语言之间的转换工具：为了减少重新编制程序所耗费的人力和时间，就要解决如何把一种高级语言转换成另一种高级语言，乃至汇编语言转换成高级语言的问题，这种异种程序设计语言之间的翻译转换工作要对被转换的语言进行词法和语法分析，只不过生成的目标语言是另一种高级语言而已，这与实现一个完整的编译程序相比工作量要少些。（5） 并行编译技术：随着并行机及多处理机的发展，对软件的并行处理提出了新的要求，特别是并行编译技术发展很快。运用重构技术把已有的串行语言编写的程序经过分析分解成可并行的成分，然后分配到多处理机上运行。如果编程人员能按程序设计情况写出并行语言程序，那么两者结合将产生更高的效率。WORD版本WORD版本第三章C编译器可行性分析及总体设计3.1 可行性分析3.1.1 经济可行性经济可行性研究是对组织的经济现状和投资能力进行分析，对系统建设运行和维护费用进行估算，对系统建成后可能取得的社会和经济效益进行估计。由于本系统是作为毕业设计由我们自己开发的，在经济上的投入甚微，系统建成之后将为今后C源程序的编译提供很大的方便，估算新系统的开发费用和今后的运行、维护费用，估计新系统将获得的效益，并将费用与效益进行比较，看是否有利。开发、运行和维护费用主要包括：购买和安装设备的费用：无。软件开发费用：若由实习单位的技术人员开发，则该项费用可以计入下面的人员费用一项；人员费用：系统开发人员、操作人员和维护人员的工资、培训费用等；消耗品费用：系统开发所用材料、系统正常运行所用消耗品，例如水、电费，打印纸、软盘、色带等开支。所有开支都不大，所以经济上是可行的。3.1.2 技术可行性技术可行性要考虑现有的技术条件是否能够顺利完成开发工作，软硬件配置是否满足开发的需求等。C编译系统用的是标准C+开发语言，调试相对简单，当前的计算机硬件配置也完全能满足开发的需求，因此在技术上是绝对可行的。软件方面：由于目前BS模式软件相对发展成熟，故软件的开发平台成熟可行,它们速度快、容量大、可靠性能高、价格低，完全能满足系统的需求。3.1.3 运行可行性对新系统运行后给现行系统带来的影响（包括组织机构、管理方式、工作环境等）和后果进行估计和评价。同时还应考虑现有管理人员的培训、补充，分析在给定时间里能否完成预定的系统开发任务等。运行可行性是对组织结构的影响，现有人员和机构和环境对系统的适应性及人员培训补充计划的可行性。当前我国信息化技术已经相当普及，各类操作人员水平都有相当的高度，所以在运行上是可行性的。本系统的开发，是用典型的VS2012或者其他c+编译工具开发，主要是对算法的处理，包括词法分析和分析表的构造，及目标代码的输出。已无技术上的问题。3.1.4 时间可行性从时间上看，在两个月的时间里学习相关知识，并开发C编译器系统，时间上是有点紧，但是不是不可能实现，通过两个多月的努力功能应该基本实现。3.1.5 法律可行性 所有技术资料都为合法。 开发过程中不存在知识产权问题。 未抄袭任何已存在的会员信息管理系统，不存在侵犯问题。 开发过程中未涉及任何法律责任。综上所述，本系统的开发从技术上、从经济上、从法律上都是完全可靠的。3.2 C语言的基本描述C语言是本实验设计要实现的一种微型语言的名称，该语言的源程序为文本形式的ASCII字符序列。考虑到针对现有的处理器来说，如果使用真正的机器代码作为C编译器的目标语言会太过于复杂，所以C语言将目标程序简化为三地址码的四元式表示形式。可在任意一种文本编辑器中编辑C语言的源程序并保存为扩展名为.c的文件，然后用命令行的形式调用C编译器（C.EXE）对该源程序进行编译，经过词法分析、语法分析并在此基础上展开语义处理，如果源程序中没有错误，则最终生成目标代码即三地址码的四元式表示形式。这种四元式表达式更接近于中间语言形式，由于这种形式的中间语言便于优化处理，因此是一种比较普遍采用的中间代码形式。C语言的程序结构很简单，它的语法与C相似但规模小于C语言。C源程序是一个由分号分隔开的语句序列。C只有两个控制语句：if语句和while语句，这两个控制语句本身也可包含语句序列。if语句有一个可选的else部分。除此之外，还有数据的输入和输出（输入语句一次只读入一个变量，而输出语句一次只输出一个表达式）。C的表达式也局限于布尔表达式和整型算术表达式。布尔表达式由对两个算术表达式的比较组成，所有比较使用和=比较运算符。算术表达式可以包括整型常数、变量、参数以及4个整型算符+、-、*、/，它们具备和通用语言相似的数学属性。布尔表达式通常只作为测试条件出现在控制语句中。虽然缺少实用程序设计语言（如C、Pascal）所需要的许多特征比如数组和指针等，但作为一次完整的编译开发实践，它已经足够体现出一个编译器的开发过程了。3.3 C编译器的功能C编译器的主要任务是分析基于C语言规的字符组成的C源程序，把它们识别为一个个具有独立意义的单词符号（Token），并识别其有关属性再转换成长度统一的属性字，以供后续语义部分分析使用。简单的说，C编译器的功能就是扫描C源程序，识别单词，转换成属性字，再经过语义处理和代码生成，最终得到目标代码文件即三地址四元表达式。一般的说，C编译器实现了下列几项功能：（1）从C源程序中逐一取出单词。（2）生成LR（1）分析表。（3）识别单词的属性并填入构造好的符号表中。（4）将单词转换成属性字，并输出二元组属性字流。（5）将符号表提供给语义分析程序加工处理。（6）生成目标代码。（7）提供基本出错处理。3.4 C编译器的程序结构3.4.1 C编译器的设计模式C编译器用C+实现，下面是主要类的类图：ReadCfgScannerGrammerLr图3-1C+实现C语言编译器的类图（1） 主控模块main.cpp：C编译器的主程序。（2） 文法类ReadCfg：文法规则类，定义C语言文法的规则。（3）词法扫描类Scanner：关键字、算符与界符将直接形成Token字；标识符将插入符号表后形成Token字，数字将插入常数表后形成Token字。（4） 词法扫描类Scanner：将源程序的字符序列收集到称作记号（token）的有意义单元中，即完成与语言单词拼写相类似的任务。（5） LR（1）分析表的构造类Grammer：根据C语言文法的特点，够造出相应的分析表（包括ACTION表和GOTO表）。（6） 语法分析类Lr：将语言结构的语义以属性（attribute）的形式赋予代表此结构的文法符号，而属性的计算以语义规则（semanticrules）的形式赋予由文法符号组成的产生式；在语法分析推导或归约的每一步骤中，通过语义规则实现对属性的计算，以达到对语义的处理。WORD版本3.4.2 C编译器的文件组成.h头文件.cpp源文件模块功能说明Cfg.hCfg.cpp文法的定义Token.hToken.cppToken字Scanner.hScanner.cpp词法分析Grammer.hGrammer.cpp语法分析表的构造Lr.hLr.cpp语法和语义分析表3-1C编译器的文件组成基类Token，它包括了编译器中各种数据类型的定义和整个编译器均可能使用到的全局变量的定义。ReadCfg类从文件读取C语言文法，并保存在文法结点Cfg_node中。C语言文法总结出有57个产生式，终结符（termina）l31和存放在set<int>terminal中，非终结符26个，存放在set<int>nontermina中l。Scanner类是词法分析的类，成员函数scan（）每次返回一个Token字。Grammer类主要负责大量数据结构的保存和LR（1）分析表的构造，最终分析表存放在action_goto_table.txt中。Lr类的包含语法分析的总控程序，用成员函数analyse（）实现对语法的分析，在语法分析推导或归约的每一步骤中，通过语义规则实现对属性的计算，以达到对语义的处理。main.c文件是C编译器的主程序，它负责整个程序的掌控。3.5 C编译器中的主要数据结构下面列举出在C编译器中使用到的主要数据结构，它们通常在编译的多个阶段都需要使用到，并用来在各阶段中共享一些特定数据8。（1） 记号（token）当扫描程序将若干个字符收集到一个记号中时，它通常是以符号表示这个记号的，也就是说，用一个枚举数据类型的值来表示源程序的记号集。有时还必须保留字符串本身或由此派生出的其他信息（例如：与标识符记号相关的名字或数字记号值）。在C编译器中，扫描程序一次只需要生成一个记号（这称为单符号先行），考虑到这种情况，可以用全程变来量放置记号信息。（2） 符号表（symboltable）符号表中的信息与标识符（函数、变量、常量以及数据类型等）有关。它几乎与编译器的所有阶段交互：扫描程序、分析程序或将标识符输入到表格中的语义分析程序；语义分析程序将增加数据类型和其它语义信息；优化阶段和代码生成阶段也将利用由符号表提供的信息生成正确而恰当的代码。因为在编译的全程中对符号表的访问非常频繁，所以插入、删除和访问等符号表操作都必须比常规操作更有效。尽管可以使用各种树的结构，但杂凑表却是能达到这一要求的最理想的数据结构。（3） 项目（item）在文法G中，某个产生式的右部标上“点号”的产生式，再放置一个向前所搜符号a，成为LR（1）项目。每个LR（1）项目集簇由若干状态组成，每个状态由若干项目组成。因此，对于构建项目集簇，项目的操作相当频繁，如何表示和处理项目成为构造分析表的重点。（4） 中间代码（intermediatecode）根据中间代码的类型（例如三元式代码和P-代码）和优化的类型，该代码可以是字符串数组（指针数组）、临时文本文件或是结构的连接列表。对于进行复杂优化的编译器，应特别注意选择允许简单重组的中间代码表示。WORD版本WORD版本WORD版本第四章C编译器的实现C编译器从整体上被划分为4个阶段：词法分析、语法分析、语义分析、代码生成，这4个阶段分别用不同的程序模块来实现(如表3-1)。一个C源程序经过C编译器的编译之后，生成三地址的四元表达式目标代码，在整个编译过程中，这4个阶段分别承担了相应的翻译任务。4.1 词法分析阶段4.1.1 概述编译器的词法分析阶段可将源程序读作有序字符文件并将其扫描分解为若干个记号(token)。记号与自然语言中的单词类似：每一个记号都是表示源程序中信息单元的字符序列。典型的有：关键字(keyword)，例如if和while，它们是字母的固定串，在该语言中具有特定的含义；标识符(identifier)是由用户定义的串，它们通常由字母和数字组成并由一个字母开头，例如变量名函数名等；算符符(operationsymbol)在语言中是作为语法上的运算符号使用的。例如，+，-，*，/，(，)，和+，-，<=；界符在语言中作为语法上的分界；数字，广义上就是源程序中的字面值。如前所述，词法分析程序的输入是源程序字符串，输出是与源程序等价的符号序列。作为词法分析程序的符号可以有各种不同的部表现形式，原则是不同的符号能彼此区别开且有唯一的表示。为了便于编译程序的进一步加工（语法分析），部表示的符号都按属性字形式，因此，词法分析程序的输出即是属性字序列，采用二元式来表示一个单词符号的部形式。符号类别符号值表4-1词法Token字这五类单词将用不同的方法处理。关键字、算符与界符将直接形成Token字；标识符将插入符号表后形成Token字，数字将插入常数表后形成Token字。在实际做词法分析时，考虑了所有的C语言现象，使得每一个C语言程序都可以被此法分析切割为单词并且赋值上属性。一般情况下，可以通过两种途径来设计词法分析程序。一种是用手工方式构造，另一种是所谓词法分析程序的自动生成。为了实现简单，本实验采取手工构造方式。4.1.2 C词法分析程序的实现C语言的记号分为5种类型：标示符，关键字，数字，算符和界限符。关键字一共有8个，它们的含义类似于标准C语言中的相应关键字。特殊符号共有12种：分别是4种基本的整数运算符号，5种比较符号（等号、小于号、小于等于、大于、大于等于），以及左括号、右括号、分号、赋值符号。其中，除了比较等号、小于等于符号和大于等于是两个字符的长度之外，其余均为单个字符。“其他”记号就是数和标识符了，数是一个或多个数字的序列，而标识符又是一个或多个字母的序列。所有这些记号归纳如下表4-2：关键字（8个）Int、if、while、double、return、void、continue、break界限符（12个）+、-、*、/、=、=、=、=、（、）、;其它数（1个或更多的数字序列）标识符（1个或更多的字母序列）表4-2C语言的记号除了上表的记号之外，C语言的源程序还要遵循以下的词法规则：代码应是自由书写格式；空白符由空格、制表位和新行组成。根据对语言中各类单词某种描述的定义，用手工方式构造词法分析程序。词法分析程序的主要任务就是扫描程序、识别单词、转换并输出属性字。下面给出单独成趟词法分析控制流程图。图4-1单独成趟的词法分析控制流程图词法分析主要包含在Scanner.h和Scanner.cpp文件中，其核心函数是scan（），它每次从第一个非空格或换行符开始识别，直到遇到空格或者换行符，遇到单行注释就跳过本行从“/”开始的以后字符识别，遇到多行注释就跳过直到遇到“*/”为止（不支持注释嵌套）。每次返回一个识别的单词，遇到不识别的单词就报错，输出不识别的单词和该单词的行数。扫描程序在识别出每个记号的同时，还会计算出该记号的特性（比如串值）这五类单词将用不同的方法处理。关键字、算符与界符将直接形成Token字；标识符将插入符号表后形成Token字，数字将插入常数表后形成Token字。Token是本实验的所有类的基类，有2个成员变量：Tag，Value。Value是文法中非终结符，而Tag是Value对应的唯一标记。4.1.3 关键字与标识符的识别C对于关键字的识别，是通过先将它们看作是标识符，然后再调用Token类的get_int（）方法，根据返回值Tag是否22（标示符的标志）为来判断是标示符还是关键字。4.1.4 词法识别具体实现/分析一个单词，并返回单词的Token字WO