Mini C编译器的设计与实现 (讲义) 电子科技大学计算机学院 《编译.docx
- 文档编号:567960
- 上传时间:2023-04-29
- 格式:DOCX
- 页数:45
- 大小:146.52KB
Mini C编译器的设计与实现 (讲义) 电子科技大学计算机学院 《编译.docx
《Mini C编译器的设计与实现 (讲义) 电子科技大学计算机学院 《编译.docx》由会员分享,可在线阅读,更多相关《Mini C编译器的设计与实现 (讲义) 电子科技大学计算机学院 《编译.docx(45页珍藏版)》请在冰点文库上搜索。
Mini C编译器的设计与实现
(讲义)
电子科技大学计算机学院
《编译原理》课程组
2008年
20
目录
第一章MiniC语言编译器简介 4
第二章理论基础 7
2.1编译系统概述 7
2.1.1什么是编译器 7
2.1.2编译器的产生 7
2.2编译器的结构 8
2.3编译器的组织 10
2.3.1编译的分遍 10
2.3.2分遍的设计 11
2.4编译器中的主要数据结构 11
2.5编译程序的开发 12
2.5.1历史与发展 12
2.5.2开发注意事项 12
2.5.3编译技术和软件工具 12
第三章MINIC语言和MINIC编译器 14
3.1MINIC编译器的开发背景和意义 14
3.2MINIC语言的基本描述 14
3.3MINIC编译器的功能 15
3.4MINIC编译器的程序结构 16
3.4.1MINIC编译器的核心模块 16
3.4.2MINIC编译器的文件组成 16
3.4.3MINIC编译器的分遍 17
3.5MINIC编译器中的主要数据结构 17
第四章MINIC编译器的实现 19
4.1词法分析阶段 19
4.1.1概述 19
4.1.2MINIC词法分析程序的实现 20
4.1.3关键字与标识符的识别 21
4.1.4为标识符分配空间 21
4.2语法分析阶段 22
4.2.1概述 22
4.2.2MINIC语言的语法 22
4.2.3MINIC语法分析程序的实现 23
4.3语义分析阶段 24
4.3.1概述 24
4.3.2MINIC语言的语义 24
4.3.3MINIC的符号表 25
4.3.4MINIC语义分析程序的实现 25
4.4MINIC运行时环境 26
4.4.1概述 26
4.4.2MINIC的运行时环境 26
4.5代码生成阶段 28
4.5.1概述 28
4.5.2目标机器——MiniMachine 29
4.5.3MINIC代码生成器的实现 31
4.5.3.1MINIC代码生成器的MM接口 31
4.5.3.2MINIC代码生成器 33
4.6.1将临时变量放入寄存器 35
4.6.2在寄存器中保存变量 36
4.6.3优化测试表达式 36
4.7MINIC编译器的使用方法 37
第一章MiniC语言编译器简介
随着计算机科学技术的飞速发展,计算机技术被应用在了越来越广泛的领域,实现各种各样功能的计算机程序被大量地开发出来,应用在我们的生活、学习和工作当中。
相应地,也产生了许多用以编写这些计算机程序的高级程序设计语言。
程序编制者通过特定语言的编译器将自己编写的源程序翻译为特定机器上的目标程序,从而能够最终达到程序执行的目的。
从20世纪60年代以来,编译器设计就一直是计算机研究发展和开发领域中的一个活跃主题。
虽然编译器设计已有很长的历史,并且也是一门相对成熟的计算机技术,但编译器毕竟是一种实现由高级语言源程序至机器或汇编指令的高效映射工具,随着计算机软、硬件水平的飞速发展,使得计算机应用日新月异,程序语言的设计在不断地变化,目标机体系结构也在不断地改进,软件越来越复杂,其规模也越来越大。
尽管编译器设计问题在高级层次上没有变化(或变化很小),但当我们深入其内部研究时就会发现,编译器的内部构造其实也一直在变化。
此外,由于我们能够提供给编译器本身使用的计算资源也在不断增加。
因此,现代编译器可以采用比以前更耗费时间和空间的算法。
当然,编译技术研究人员也在继续努力开发新的、更好的技术来解决传统编译器的一些设计性问题[1]。
编译器是一种相当复杂的系统程序,其代码的长度可从几千行到几百万行不等,所以编写甚至读懂这样的一个程序都不是一件容易的事。
绝大多数的计算机专业人员从来没有编写过一个完整的编译器,但是,几乎所有形式的计算均要用到编译器,而且任何一个与计算机打交道的专业人员都应该掌握编译器的基本结构和操作。
除此之外,计算机应用程序中经常遇到的一个任务就是有关命令解释程序和界面程序的开发,这比编译器的开发规模要小,但使用的却是很类似的技术。
因此,掌握编译器的开发技术具有非常重大的实际意义。
编译器的设计从本质上来说是一种工程活动,它所使用的方法必须很好地解决现实中出现的各种翻译问题(即用真实的语言编制且在真实的机器上能够执行的真实的程序)。
大多数情况下,开发编译器的人必须接受他们面对的语言和机
器,很少能够去影响或改善这两者的设计。
在开发过程中做什么样的分析和转换,以及什么时候去做,这些都是工程上的选择,但正是这些选择决定了一个编译器的性能高低。
本实验就建立在一个自主开发的名为MINI C的微型编译器基础之上,该编译器虽然功能弱于像TurboC或BorlandPascal这样的经典编译器,但也
已经完全具备了一个编译器应有的所有特征。
在编译器技术的发展过程中,如何提高编译的效率一直是核心研究目标之一,编译效率主要是根据该编译器所生成的目标代码在执行过程中的时间指标和空间指标来衡量的,所以编译优化也必定围绕时间和空间这两个方面来实施。
在编译过程中针对代码优化的技术有很多,它们通常是通过搜集源代码或中间代码的特定信息,然后利用这些信息对代码中的数据结构或算法操作实施等价的改进变换,从而力求在时间效率和空间效率上达到一个最佳平衡点。
编译器的开发者们总是希望能够将各种代码优化技术充分地运用在自己的编译器设计中,但往往事与愿违,毕竟优化操作本身也是需要付出开销的。
在MINI C编译器的开发过程中,虽然没有运用到太复杂的代码优化技术,但通过本实验的研究,在现有开发的MINI C编译器基础之上,能够在后续相关项目的开发中有效地提高程序代码的编译质量,对于自己以后的研究和发展方向将起到非常大的推动作用。
这正是本实验的研究意义所在。
本实验是以MINIC微型编译器的项目开发为基础,该项目的开发目标是自定义一种MINIC高级语言,然后编码实现出MINIC语言的编译器(称为MINIC编译器),完成将MINIC语言源程序翻译为基于MM机(MiniMachine)的目标代码的任务,这是本实验的实际应用背景。
编译器的开发具有极高的实用价值和意义,高级语言编译器的性能决定了基于该语言平台所开发出的软件的质量。
所以国内外很多大学的科研和技术人员也在积极地开展这方面的技术探索和项目实践。
他们大多是以特定的软件项目为背景来进行一些与编译器开发相关或类似的研究分析,他们的研究目标大多是基于某种实验型高级语言的编译器开发和优化改进,然后把有价值的研究成果移植或运用到产品级的编译器开发中(比如.NET平台编译器)。
最近十年以来,国外关于编译器设计的发展动态主要体现在:
首先,编译器采用了大量的更加复杂的算法,主要用于推断或简化程序中的信息,这又与更为复杂的程序设计语言的发展结合在一起,其中典型的有用于函数语言编译的Hindley-Milner类型检查的统一算法[2]。
其次,编译器已越来越成为基于窗口的可视化交互开发环境(InteractiveDevelopmentEnvironment,IDE)的一部分,该环境还包括了智能编辑器、连接程序、调试程序以及项目管理程序等,已经成为了事实上的编译器行业标准。
另一方面,尽管国内外的专家学者们近年来在编译原理领域进行了大量的研究,但是基本的编译器设计原理在近20年中都没有多大的改变,它现在正迅速地成为计算机科学课程中的中心环节之一。
在九十年代,作为GNU项目或其它开放源代码项目的一部分,许多免费的编译器或编译器构造工具被开发出来。
这些工具可用来编译数种程序设计语言的源程序(典型的就是GCC)。
它们中的一些项目被认为是高质量的,而且对现代编译理论感兴趣的人都可以较容易地得到它们的免费源代码。
典型的是在1999年,SGI公布了他们的一个工业化的并行优化编译器Pro64的源代码,随后被全世界多个编译器研究小组用做研究平台,并命名为Open64。
Open64的设计结构好,分析优化全面,是编译器高级研究的理想平台。
反观国内,现阶段对于编译技术的相关研究,基本上都是着眼于特定编译器的特定部分来展开的,而本实验将研究和分析的重点主要集中于一个完整的微型编译器的构造的讨论。
第二章理论基础
2.1编译系统概述
2.1.1什么是编译器
编译器,是将便于人类编写、阅读、维护的计算机高级语言程序翻译为机器能够识别、运行的计算机低级语言程序的一种系统软件。
编译器将源程序
(SourceProgram)作为输入,翻译产生使用目标语言的等价目标程序((TargetProgram)。
其中,源程序一般为高级语言(High-levellanguage),如Pascal,C++等,而目标语言则是汇编语言或目标机器的机器语言[3]。
编译器的这一作用如图2-1所示:
图2-1编译器的作用
2.1.2编译器的产生
本世纪四十年代,由于冯·诺依曼在存储程序计算机方面的先锋作用,使得编写一串代码或程序已成为可能和必要,这样计算机就可以执行所需的计算。
在初期,这些程序都是用机器语言编写,编写或维护这样的代码是非常枯燥乏味且效率低下的,所以机器语言很快就被汇编语言代替了。
汇编语言大大提高了程序编写速度和准确度,但它也有许多缺点。
于是发展编程技术的下一个重要革新就是以一个更加类似于数学定义或自然语言的简洁形式来编写程序的功能操作,它应与任何机器都无关,而且也可由一个程序翻译为可执行的代码。
随着对形式语言和自动机理论的研究,人们对高级程序设计语言的认识越来越深,对编译器结构的设计也越来越清晰。
人们通过对形式语言文法规则的研究,相当完善地解决了分析问题。
当分析问题变得相对成熟时,设计者们又花费了很多的精力来研究这一部分的编译器的自动构造,这就是分析程序生成器(parsergenerator)最初的雏形。
类似地,对有穷自动机的研究也促进了一种称为扫描程序生成器(scannergenerator)工具的发展。
接着,人们又深化了生成有效目标代
码的方法,这些就构成了传统的编译器,在这个过程中运用到的技术被一直使用至今。
2.2编译器的结构
严格地说,编译器是一个将高级语言源程序转换成能在一台计算机上执行的等价目标代码或机器语言程序的软件系统。
这个定义可扩展到包含将一个高级语言程序转换成汇编语言程序的系统,将一个高级语言程序转换成另一种高级语言程序的系统,从一个机器语言程序转换成另一种机器语言程序的系统,从一种高级语言程序转换成一种中间语言程序的系统,等等。
在通常情况下,一个编译器应由一系列的阶段组成,这些阶段从要编译的源程序的字符序列开始,依次对一个给定形式的程序进行分析,并得到一种新的表示形式,在大多数情况下最终产生一个可以与其他目标代码链接,并装入一台机器的存储器中执行的可重定位目标模块。
这一编译过程一般由如下6个阶段构成,它们执行不同的逻辑操作如图2-2所示[4]:
图2-2编译器的阶段示意图
(1)扫描程序(scanner)
在这个阶段,编译器阅读源程序(通常以字符流的形式表示,比如本实验设计的MINIC语言的源程序.c),由扫描程序执行词法分析(lexicalanalysis):
它将字符序列收集到称为记号(token)的单元中,也就是说,将其识别为一个个符合编程语言词法规范的单词符号。
实际上,一个扫描程序所做的工作与自然语言中对英文单词的拼写是十分类似的。
扫描程序还可完成与识别记号一起执行的其他操作,例如,可将相应的记号输入到对应的符号表中。
(2)语法分析程序(parser)
语法分析程序从扫描程序中获取记号形式的代码,并完成定义程序结构的语法分析(syntax analysis),根据语言的语法规则将上阶段产生的单词串分解成各类语法单位(如表达式、语句、子过程等),这与自然语言中关于某篇文章的句子的语法分析类似。
语法分析定义了程序的结构元素及其关系。
通常将语法分析的结果表示为分析树或语法树。
(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指出了它们之间的相互关系,但需要注意的是,这些关系仅代表它们之间的逻辑关系,并不一定就是执行时间上的先后顺序。
事实上,可按不同的执行流程来组织上述各阶段的工作,这在很大程度上依赖于编译过程中对源程序扫描的遍数,以及如何划分各遍扫描所进行的工作。
这里所说的“遍”,是指对源程序或其内部表示从头到尾扫视一次,并进行有关的加工处理工作,每一遍的工作都是从获取上一遍的工作结果开始,经过本遍的加工后,将结果保存起来以便交给下一遍[5]。
例如,对于要求经一遍扫描就能完成从源代码到目标代码翻译的编译程序,我们可以语法分析程序为中心来组织它
的工作流程,这样就不必产生中间代码,显然,这种做法所得到的目标代码的质量是不能保证的,总体来说弊大于利。
对于绝大部分语言(例如Pascal或C),实现一遍扫描的编译程序是非常困难的,所以宜于采用多遍扫描的编译程序结构。
具体的做法是将整个编译程序划分为若干个相继执行的模块,每一模块都对它前一模块的输出扫描一遍,并在扫描过程中完成前述6个阶段中的一个或几个,然后将工作结果保存下来供下一模块加工。
显然,第一个模块所扫描的是字符序列形式的源程序,最后一个模块所输出的是目标代码,而每一个中间模块输出的是与源程序等价的内部表示或中间代码。
2.3.2分遍的设计
在设计一个编译程序时,如何确定扫描遍数,如何组织各遍中的工作,主要取决于源语言的具体情况及编译程序运行的具体环境,如语言的结构、计算机软硬件的配置,以及对编译程序本身运行效率的要求等等。
一般而言,多遍扫描源程序具有如下优点:
(1)由于采用了模块结构,各遍扫描的功能相对独立,整个编译程序的结构比较清晰。
(2)由于对源程序及其内部表示进行多次扫视和加工,有利于进行比较细致和充分的代码优化处理。
(3)由于可将编译程序按模块依次调入内存,有利于采用覆盖技术,以减少执行编译程序时所占的内存空间。
由于分遍问题对具体语言及编译程序的运行环境有很强的依赖性,经过权衡,本实验设计的MINI编译器采用了4遍的扫描策略。
2.4编译器中的主要数据结构
当然,编译器的各个阶段使用的算法与支持这些阶段的数据结构之间的交互是非常密切的。
编译器的编写者在实施这些算法的同时应尽可能地保证它们不过于复杂,最理想的情况是:
该编译器在编译时所耗费的时间与程序大小成线形比例,即时间复杂度为O(n)。
能否达到这样的理想情况,很大程度上取决于所采用的数据结构,它们是各个阶段都需要使用到的,并用来在各阶段之间交流信息。
通常编译器中的主要数据结构包括:
记号、语法树、符号表、常数表、中间代码、
临时文件等。
2.5编译程序的开发
2.5.1历史与发展
在编译器开发的原始阶段,人们主要用机器语言或汇编语言来构造编译程序,难度极大且效率很低。
现在的大部分编译器是用某种高级语言开发的,这样更节约时间,而且易读、易改、易移植,同时也便于进行编译器的优化设计。
相信在不久的将来,编译器的开发将主要借助于成熟的自动化生成编译程序技术。
2.5.2开发注意事项
(1)源语言:
对被编译的源语言,要深刻理解其结构和含义。
在定义MINIC语言的过程中,是通过严格制定其词法规则、语法规则和语义规则来达到的。
(2)目标语言:
了解硬件的系统结构和操作系统的接口。
MINIC编译器的目标语言选择为面向MM机的汇编代码。
(3)编译技术:
词法分析、语法分析、语义分析、代码优化及代码生成的相关技术有很多,必须根据所开发的编译器的需求和特点来选择最合适的编译技术和方法。
关于MINIC编译器中使用到的编译技术可详细参考论文第四章。
(4)各种具体因素:
例如系统功能要求、硬件开发环境、软件开发工具等。
2.5.3编译技术和软件工具
为了提高软件开发的效率和保证开发质量,人们除了要遵循软件工程中对软件开发过程的规范化或标准化之外,还应尽量使用先进的软件开发技术和相应的软件工具,而大部分软件工具的开发,常常要用到编译技术和方法。
实际上编译程序本身也是一种软件开发工具。
为了提高编程效率,缩短调试时间,软件工作人员研制了不少对源程序处理的工具,这些工具的开发不同程度地用到编译程序各个部分的技术和方法,典型的有下面几种[7]:
(1)语言的结构化编辑器:
结构化编辑器是引导用户在语言的语法制导下编制程序,能自动地提供关键字和与其匹配的关键字,这样可以减少语法上的错
误,加快对源程序的输入和调试,提高效率和质量。
现在的可视化开发工具基本都具备了这个功能。
(2)语言程序的调试工具:
调试是软件开发过程中一个重要环节,凡是对算法的实现错误或程序没能反映算法的功能等错误就需用调试器来协助解决。
调试器的功能越强则实现越复杂,它必须与语法分析、语义处理有紧密联系。
(3)语言程序测试工具:
对源程序进行语法分析并制定相应表格,检查变量定值与引用的关系;也可在源程序的适当位置插入某些信息,并用测试用例记录程序运行时的实际路径,将运行结果与期望的结果进行比较分析,帮助编程人员快速查找问题所在。
(4)高级语言之间的转换工具:
为了减少重新编制程序所耗费的人力和时间,就要解决如何把一种高级语言转换成另一种高级语言,乃至汇编语言转换成高级语言的问题,这种异种程序设计语言之间的翻译转换工作要对被转换的语言进行词法和语法分析,只不过生成的目标语言是另一种高级语言而已,这与实现一个完整的编译程序相比工作量要少些。
(5)并行编译技术:
随着并行机及多处理机的发展,对软件的并行处理提出了新的要求,特别是并行编译技术发展很快。
运用重构技术把已有的串行语言编写的程序经过分析分解成可并行的成分,然后分配到多处理机上运行。
如果编程人员能按程序设计情况写出并行语言程序,那么两者结合将产生更高的效率。
第三章MINIC语言和MINIC编译器
3.1MINIC编译器的开发背景和意义
编译器是一种相当复杂的程序,其代码的长度可从几千行到几百万行不等。
编写甚至读懂这样的一个程序都非易事,大多数的计算机专业人员从来没有编写过一个完整的编译器。
但是,几乎所有形式的计算均要用到编译器,而且任何一个与计算机打交道的专业人员都应该掌握编译器的基本结构和操作。
除此之外,计算机应用程序中经常遇到的一个任务就是命令解释程序和界面程序的开发,这比编译器要小,但使用的却是很类似的技术。
因此,掌握这一技术具有非常重大的实际意义。
虽然MINI C只是一个规模很小的微型编译器的开发,但所谓“麻雀虽小,五脏俱全”,作为一次较为完整的编译开发实践,它已经足够让我透彻地了解一个编译器开发过程了,同时能更深刻地理解和运用编译开发过程中的众多技术和方法,并能在此基础上针对编译器的优化展开深入的讨论,这些对于自己以后的研究和发展方向将起到非常大的推动作用。
MINIC编译器以C语言作为开发语言,以TurboC2.0作为开发工具,MINIC编译器的各个阶段以模块的形式完成,最后以项目文件为单位来编译生成MINIC编译器的可执行文件。
3.2MINIC语言的基本描述
MINI C语言是本实验设计要实现的一种微型语言的名称,该语言的源程序为文本形式的ASCII字符序列。
考虑到针对现有的处理器来说,如果使用真正的机器代码作为MINIC编译器的目标语言会太过于复杂,所以MINIC语言将目标程序简化为一个假定的简单处理器的汇编语言,这个假定的处理器称为MM机(MiniMachine)。
可在任意一种文本编辑器中编辑MINIC语言的源程序并保存为扩展名为.min的文件,然后用命令行的形式调用MINIC编译器(MINIC.EXE)对该源程序进行编译,经过词法分析、语法分析并在此基础上展开语义处理,如果源程序中没有错误,则最终生成目标代码即基于MM机的指令文件(扩展名为.mm)。
这种目标代码文件可以使用MM机的模拟程序(MM
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- Mini C编译器的设计与实现 讲义 电子科技大学计算机学院 编译 编译器 设计 实现 讲义 电子科技 大学计算机 学院 编译