编译技术的发展和应用.docx
- 文档编号:6170449
- 上传时间:2023-05-09
- 格式:DOCX
- 页数:17
- 大小:62.10KB
编译技术的发展和应用.docx
《编译技术的发展和应用.docx》由会员分享,可在线阅读,更多相关《编译技术的发展和应用.docx(17页珍藏版)》请在冰点文库上搜索。
编译技术的发展和应用
编译技术的发展和应用
据说第一个编译程序的出现是在20世纪50年代早期,很难讲出确切的时间,因为当初大量的实验和实现工作是由不同的小组独立完成的,多数早期的编译工作是将算术公式翻译成机器代码。
用现在的标准来衡量,当时的编译程序能完成的工作十分初步,如只允许简单的单目运算,数据元素的命名方式有很多限制。
然而它们奠定了对高级语言编译系统的研究和开发的基础。
20世纪50年代中期出现了FORTRAN等一批高级语言,相应的一批编译系统开发成功。
随着编译技术的发展和社会对编译程序需求的不断增长,20世纪50年代末有人开始研究编译程序的自动生成工具,提出并研制编译程序的编译程序。
它的功能是以任一语言的词法规则、语法规则和语义解释出发,自动产生该语言的编译程序。
目前很多自动生成工具已广泛使用,如词法分析程序的生成系统LEX,语法分析程序的生成系统YACC等。
20世纪60年代起,
不断有人使用自展技术来构造编译程序。
自展的主要特征是用被编译的语言来书写该语言自身的编译程序。
1971年,PASCAL的编译程序用自展技术生成后,其影响就越来越大。
随着并行技术和并行语言的发展,处理并行语言的并行编译技术,将串行程序转换成并行程序的自动并行编译技术也正在深入研究之中。
另外嵌入式应用迅速增长的需求,推动了交叉编译技术的发展.还有
系统芯片设计方法和关键EDA技术的研究,也带动了专用语言VHDL等及其编译技术的不断深化。
编译实现方式的发展
-手工
机器语言
汇编
系统程序设计语言
-自动构造工具lexyaccgcc
推动编译技术发展的因素
语言范型(计算模式)
计算机体系结构
语言范型
-命令式(imperativelanguage)
-应用式(applicative)
-基于规则的(rule-based)
-面向对象的(object-oriented)
-并行计算(parallelcomputing)
体系结构
-万诺曼机体系结构
-并行体系结构
-嵌入系统
编译程序执行环境
-批处理
-交互环境
—嵌入系统环境
为了提高软件开发的效率和保证质量,人们除了要在软件工程中对软件开发过程所要遵循的规范化或
标准化外,还尽量使用先进的软件开发技术和相应的软件工具,而大部分软件工具的开发,常常要用到编译技术和方法。
实际上编译程序本身也是一种软件开发工具。
为了提高编程效率,缩短调试时间,软件工作人员研制了不少对源程序处理的工具。
这些工具的开发不同程度地用到编译技术和方法。
下面仅是一些
例子。
1、语言的结构化编辑器结构化编辑器是引导用户在语言的语法制导下编制程序,能自动地提供关键
字和与其匹配的关键字,如if后必须有then,begin和end的配对,左右括号的配对等,这样可以减少语
法上的错误,可加快对源程序的调试,提高效率和质量。
2、语言程序的调试工具调试是软件开发过程中一个重要环节,结构化编辑器只能解决语法错误的问题,而对一个已通过编译的程序来说,需进一步了解的是程序执行的结果与编程人员的意图是否一致,程
序的执行是否实现预计的算法和功能。
这种对算法的错误或程序没能反应算法的功能等错误就需用调试器
来协助解决。
调试器的功能愈强,实现愈复杂,但它必须与语法分析、语义处理有紧密联系。
3、语言程序测试工具语言程序的测试工具有两种:
静态分析器和动态测试器
静态分析器是对源程序进行静态地分析。
它对源程序进行语法分析并制定相应表格,检查变量定值与引用的关系。
如某变量未被赋值就被引用,或定值后未被引用,或多余的源代码等一些编译程序的语法分
(显示语句或函
析发现不了的错误。
动态测试工具是在源程序的适当位置插入某些信息,并用测试用例记录数)程序运行时的实际路径。
将运行结果与期望的结果进行比较分析,帮助编程人员查找问题。
这种测试工
具在国内已有开发,如FORTRAN语言和C语言的测试工具。
4、高级语言之间的转换工具由于计算机硬件的不断更新换代,更新更好的程序设计语言的推出为提高计算机的使用效率提供了良好条件,然而一些已有的非常成熟的软件如何在新机器新语言情况下使用呢?
为了减少重新编制程序所耗费的人力和时间,就要解决如何把一种高级语言转换成另一种高级语言,乃至汇编语言转换成高级语言的问题。
这种转换工作要对被转换的语言进行词法和语法分析,只不过生成的目标语言是另一种高级语言而已。
这与实现一个完整的编译程序相比工作量要少些。
在国内已研制出C,
PASCAL,FORTRAN到Ada的翻译器和IBM4700汇编到C的转换器,其效果很好。
近年来,由于JAVA语言的发展,国内外也已研制出不少其他语言到JAVA的转换系统,如c到JAVA的转换系统,cobol到JAVA的转换系统等等。
编译实现方式的发展主要分一下五类:
手工、机器语言、汇编、系统程序设计语言、自动构造工具lexyaccgcc。
推动编译技术发展的因素主要包括:
语言范型(计算模式)、计算机体系结构语言范型主要包括:
命令
式(imperativelanguage)、应用式(applicative)、基于规则的(rule-based)、面向对象的(object-oriented)、并行计算(parallelcomputing)。
体系结构主要包括:
万诺曼机体系结构、并行体系结构、嵌入系统。
编译程序执行环境主要包括:
批处理、交
互环境、嵌入系统环境、并行编译技术、交叉编译。
编译程序在一个机器(宿主机)上运行,产生另一个机器(目标机)的汇编语言。
嵌入式系统中的应用程序正是借助这样的编译程序生成。
目标处理器MIPSX是MIPS系列芯片的种,属于RISC体系结构,来源于斯坦福大学的MIPS计划。
由于该系列CPU不是采用加州大学伯克利分校的RISC窗口技术而是采用消除流水线各级互锁的微处理器MIPS(MicroprocessorWithoutInterlockingPipelineStage)技术,因此而得名。
MIPS是将IBM公司对优化
编译程序的研究和加州大学伯克利分校的大规模集成电路的思想结合起来的产品。
由于RISC指令集的简单和整齐,为了达到更好地利用计算机的性能,MIPS系列芯片中很好地应用了流水线策略。
流水线是现代各类微处理器都采用的指令执行技巧,即将若干条指令的取指、译码和执行过程部分重叠在流水线中同时执行。
以前在CISC计算机中,由于指令多而复杂,处理每条指令的所需时间不固定,当后面指令需要前条指令的结果时,往往造成指令互锁,因此无法实现流水线。
而斯坦福大学的MIPS计划就是在编译的过程中,利用编译程序优化处理器的流水线以求提高处理器流水线的效率。
由于采用了硬件连线控制来执行数目不多的简单指令,而且还能重组软件流水线,这样就减少了硬件复杂性。
但是由于存在数据和指令转移的相关性,这会引起流水线的停顿,降低流水线整体的执行速率。
为了调整
这些相关性,又开发出了代码重组技术,其中一种是延迟转移(delayedbranch),另一种叫延迟装入,提升
了性能。
MIPS公司的R系列就是在此基础上开发的RISC工业产品的微处理器。
这些系列产品被很多计算机公司
采用生产各种工作站和计算机系统。
R系列遵循按比例提高性能设计技术,按不同工艺技术实现基本相同
的体系结构,其适用范围从低端的嵌入式控制器、个人计算机到高端的超级小型机、服务器甚至大型机和
巨型机,而且系统软件和应用程序都是兼容的。
MIPS公司在1986年推出82000处理器,1988年推出83000
处理器,1991年推出第一款64位商用微处理器84000。
之后,又陆续推出88000(于1994年卜810000(于1996年)和812000(于1997年)等型号。
1999年,MIPS公司发布MIPS32和MIPS64架构标准。
2000年,MIPS公司发布了针对MIPS324Kc的新版本以及未来64位MIPS6420Kc处理器内核。
在整个R系列中82000/82010是最基础的原型;83000/83010是82000/82010的增强型产品;由于84000采用高精度的CMOS工艺,因此其性能很高,用途很广;而86000/86010是ECL电路化的高速品种,但
是由于86000/86010的功耗大,成本高,所以其应用受到很大限制。
但是MIPSX并不属于以上提到的
CPU中的任何一种,它是由20世纪80年代后期由美国国防部高级研究项目署(DARPA)资助的一个项目
的成果。
因此,基于MIPSX的交叉编译工具链研究虽然现有的GNU交叉编译工具链对MIPS公司R系列
芯片的支持很好,但还是缺乏对MIPSX的有效支持,所以还是需要进行移植。
进行移植工作前,必须首
先了解MIPSX的体系结构。
经过实验室前几届师兄的分析,我们得知MIPSX的体系结构与MIPS公司R
系列芯片中的82000最为接近,当然它们在很多地方还是存在着差别,比如具体指令集的不同,比如MIPSX
没有浮点操作;MIPSX指令的基本操作码只占5位;MIPSX在跳转指令中的延时槽有两条等。
简单讲,编译器就是将"一种语言(通常为高级语言)”翻译为"另一种语言(通常
为低级语言)”的程序。
一个现代编译器的主要工作流程:
源代码(sourcecode)宀预处
理器(preprocessor)宀编译器(compiler)宀目标代码(objectcode)宀链接器(Linker)宀可执行程序(executables)
高级计算机语言便于人编写,阅读交流,维护。
机器语言是计算机能直接解读、运行
的。
编译器将汇编或高级计算机语言源程序(Sourceprogram)作为输入,翻译成目标语言
(TargetIanguage)机器代码的等价程序。
源代码一般为高级语言(High-levellanguage),如Pascal、C、C++、Java、汉语编程等或汇编语言,而目标则是机器语言的目标代码(Objectcode),有时也称作机器代码(Machinecode)。
对于C#、VB等高级语言而言,此时编译器完成的功能是把源码(SourceCode)编译成通用中间语言(MSIL/CIL)的字节码(ByteCode)。
最后运行的时候通过通用语言运行库的转换,编程最终可以被CPU直接计算的机器码(NativeCode)。
在20世纪40年代,由于冯诺伊曼在存储-程序
计算机方面的先锋作用,编写一串代码或程序已成必要,这样计算机就可以执行所需
的计算。
开始时,这些程序都是用机器语言(machineIanguage)编写的。
机器语言就是
表示机器实际操作的数字代码,例如:
C70600000002表示在IBMPC上使用的Intel8x86处理器将数字2移至地址0000(16进制)的指令。
但编写这样的代码是十分费时和乏味的,这种代码形式很快就被汇编语言(assembly
Ianguage)代替了。
在汇编语言中,都是以符号形式给出指令和存储地址的。
例如,汇编语言指令MOVX,2就与前面的机器指令等价(假设符号存储地址X是0000)。
汇编程
序(assembler)将汇编语言的符号代码和存储地址翻译成与机器语言相对应的数字代码。
汇编语言大大提高了编程的速度和准确度,人们至今仍在使用着它,在编码需要极快
的速度和极高的简洁程度时尤为如此。
但是,汇编语言也有许多缺点:
编写起来也不容易,阅读和理解很难;而且汇编语言的编写严格依赖于特定的机器,所以为一台计算机编写的代
码在应用于另一台计算机时必须完全重写。
发展编程技术的下一个重要步骤就是以一个更类似于数学定义或自然语言的简洁形式
来编写程序的操作,它应与任何机器都无关,而且也可由一个程序翻译为可执行的代码。
例
如,前面的汇编语言代码可以写成一个简洁的与机器无关的形式x=2。
在1954年至1957年期间,IBM的JohnBackus带领的一个研究小组对FORTRAN语言及其编译器的开发,使得上面的担忧不必要了。
但是,由于当时处理中所涉及到的大多
数程序设计语言的翻译并不为人所掌握,所以这个项目的成功也伴随着巨大的辛劳。
几乎与
此同时,人们也在开发着第一个编译器,NoamChomsky开始了他的自然语言结构的研究。
他的发现最终使得编译器结构异常简单,甚至还带有了一些自动化。
Chomsky的研究导致
了根据语言文法(grammar,指定其结构的规则)的难易程度以及识别它们所需的算法来
为语言分类。
正如现在所称的-与乔姆斯基分类结构(Chomskyhierarchy)一样-包括了文
法的4个层次:
0型、1型、2型和3型文法,且其中的每一个都是其前者的专门化。
2型
(或上下文无关文法(context-freegrammar))被证明是程序设计语言中最有用的,而
且今天它已代表着程序设计语言结构的标准方式。
分析问题(parsingproblem,用于限定上下文无关语言的识别的有效算法)的研究是在20世纪60年代和70年代,它相当完善地解决了这一问题,现在它已是编译理论的
一个标准部分。
它们与乔姆斯基的3型文法相对应。
对它们的研究与乔姆斯基的研究几乎
同时开始,并且引出了表示程序设计语言的单词(或称为记号)的符号方式。
人们接着又深化了生成有效的目标代码的方法,这就是最初的编译器,它们被一直使用至今。
人们通常将其误称为优化技术(optimizationtechnique),但因其从未真正地得
到过被优化了的目标代码而仅仅改进了它的有效性,因此实际上应称作代码改进技术(code
improvementtechnique)。
这些程序最初被称为编译程序-编译器,但更确切地应称为分析程序生成器(parsergenerator),这是因为它们仅仅能够自动处理编译的一部分。
这些程序中最著名的
是Yacc(yetanothercompiler-compiler),它是由SteveJohnson在1975年为Unix系统编写的。
类似地,有穷自动机的研究也发展了另一种称为扫描程序生成器(scannergenerator)
的工具,Lex(与Yacc同时,由MikeLesk为Unix系统开发的)是这其中的佼佼者。
在20世纪70年代后期和80年代早期,大量的项目都关注于编译器其他部分的生成自动化,这其中就包括代码生成。
这些尝试并未取得多少成功,这大概是因为操作太复杂而人们又对
其不甚了解。
编译器设计最近的发展包括:
首先,编译器包括了更为复杂的算法的应用程序,它用
于推断或简化程序中的信息;这又与更为复杂的程序设计语言(可允许此类分析)的发展结合在一起。
其中典型的有用于函数语言编译的Hindley-Milner类型检查的统一算法。
其次,编译器已越来越成为基于窗口的交互开发环境(interactivedevelopment
environment,IDE)的一部分,它包括了编辑器、链接程序、调试程序以及项目管理程序。
这样的IDE的标准并没有多少,但是已沿着这一方向对标准的窗口环境进行开发了。
编辑器(editor):
编译器通常接受由任何生成标准文件(例如ASCII文件)的编辑器编写的源程序。
现在,编译器已与另一个编辑器和其他程序捆绑进一个交互的开发环境-IDE中。
此时,尽管编辑器仍然生成标准文件,但会转向正被讨论的程序设计语言的格式或结构。
这
样的编辑器称为基于结构的(structurebased),且它早已包括了编译器的某些操作;因此,
程序员就会在程序的编写时而不是在编译时就得知错误了。
从编辑器中也可调用编译器以及
与它共用的程序,这样程序员无需离开编辑器就可执行程序。
编译原理是计算机专业的一门重要专业课,旨在介绍编译程序构造的一般原理和基本方法。
内容包括语言和文法、词法分析、语法分析、语法制导翻译、中间代码生成、存储管理、代
码优化和目标代码生成。
编译原理是计算机专业设置的一门重要的专业课程。
虽然只有少
大学课程为什么要开设编译原理呢?
这门课程关注的是编译器方面的产生原理和技术问题,似乎和计算机的基础领域不沾边,可是编译原理却一直作为大学本科的必修课程,同时也成为了研究生入学考试的必考内容。
编译原理及技术从本
质上来讲就是一个算法问题而已,当然由于这个问题十分复杂,其解决算法也相对复杂。
我们学的数据结构与算法分析也是讲算法的,不过讲的基础算法,换句
话说讲的是算法导论,而编译原理这门课程讲的就是比较专注解决一种的算法了。
在20世纪50年代,编译器的编写一直被认为是十分困难的事情,第一Fortran
的编译器据说花了18年的时间才完成。
在人们尝试编写编译器的同时,诞生了许多跟编译相关的理论和技术,而这些理论和技术比一个实际的编译器本身价值更大。
就犹如数学家们在解决著名的哥德巴赫猜想一样,虽然没有最终解决问题,但是其间诞生不少名著的相关数论。
推荐参考书
虽然编译理论发展到今天,已经有了比较成熟的部分,但是作为一个大学生来说,要自己写出一个像TurbocCJava那样的编译器来说还是太难了。
不仅写编译器困难,学习编译原理这门课程也比较困难。
第一本书的原名叫《CompilersPrinciples,Techniques,andTools》,另外一
个响亮的名字就是龙书。
原因是这本书的封面上有条红色的龙,也因为獗臼樵诒嘁朐?
砘?
嘴域确实?
忻?
所以很多国外的学者都直接取名为龙书。
最近机械工业出
版社已经出版了此书的中文版,名字就叫《编译原理》。
该书出的比较早,大概是在85或86年编写完成的,作者之一还是著名的贝尔实验室的科学家。
里面讲解的核心编译原理至今都没有变过,所以一直到今天,它的价值都非凡。
这本
书最大的特点就是一开始就通过一个实际的小例子,把编译原理的大致内容罗列
出来,让很多编译原理的初学者很快心里有了个底,也知道为什么会有这些理论,怎么运用这些理论。
而这一点是我感觉国内的教材缺乏的东西,所以国内的教材都不是写给愿意自学的读者,总之让人看了半天,却不知道里面的东西有什么用。
第二本书的原名叫《ModernCompilerDesign》,中文名字叫做《现代编译
程序设计》。
该书由人民邮电出版社所出。
此书比较关注的是编译原理的实践,书中给出了不少的实际程序代码,还有很多实际的编译技术问题等等。
此书另外一个特点就是其现代而字。
在传统的编译原理教材中,你是不可能看到如同Java中的垃圾回收等算法的。
因为Java这样的解释执行语言是在近几年才流行起来的东西。
如果你想深入学习编译原理的理论知识,那么你肯定得看前面那本龙书,如果你想自己动手做一个先进的编译器,那么你得看这本《现代编译程序设计》。
第三本书就是很多国内的编译原理学者都推荐的那本《编译原理及实践》。
或许是这本书引入国内比较早吧,我记得我是在高中就买了这本书,不过也是在前段时间才把整本书看完。
此书作为入门教程也的确是个不错的选择。
书中给出的编译原理讲解也相当细致,虽然不如前面的龙书那么深入,但是很多地方都是点到为止,作为大学本科教学已经是十分深入了。
该书的特点就是注重实践,不过感觉还不如前面那本《现代编译程序设计》的实践味道更重。
此书的重点还是在原理上的实践,而非前面那本那样的技术实践。
《编译原理及实践》在讲解编
译原理的各个部分的同时,也在逐步实践一个现代的编译器TinyC.等你把整本
书看完,差不多自己也可以写一个TinyC了。
作者还对Lex和Yacc这两个常用的编译相关的工具进行了很详细的说明,这一点也是很难在国内的教材中看到的。
推荐了这三本教材,都有英文版和中文版的。
很多英文好的同学只喜欢看原版的书,不我的感觉是这三本书的翻译都很不错,没有必要特别去买英文版的。
理解理论的实质比理解表面的文字更为重要。
编译原理的实质
几乎每本编译原理的教材都是分成词法分析,语法分析(LL算法,递归下
降算法,LR算法),语义分析,运行时环境,中间代码,代码生成,代码优化这些部分。
其实现在很多编译原理的教材都是按照85,86出版的那本龙书来安排教学内容的,所以那本龙书的内容格式几乎成了现在编译原理教材的定式,包括
国内的教材也是如此。
一般来说,大学里面的本科教学是不可能把上面的所有部分都认真讲完的,而是比较偏重于前面几个部分。
像代码优化那部分东西,就像个无底洞一样,如果要认真讲,就是单独开一个学期的课也不可能讲得清楚。
所
以,一般对于本科生,对词法分析和语法分析掌握要求就相对要高一点了。
词法分析相对来说比较简单。
可能是词法分析程序本身实现起来很简单吧,
很多没有学过编译原理的人也同样可以写出各种各样的词法分析程序。
不过编译
原理在讲解词法分析的时候,重点把正则表达式和自动机原理加了进来,然后以
一种十分标准的方式来讲解词法分析程序的产生。
这样的做法道理很明显,就是
要让词法分析从程序上升到理论的地步。
语法分析部分就比较麻烦一点了。
现在一般有两种语法分析算法,LL自顶
向下算法和LR自底向上算法。
LL算法还好说,到了LR算法的时候,困难就来了。
很多自学编译原理的都是遇到LR算法的理解成问题后就放弃了自学。
其实这些东西都是只要大家理解就可以了,又不是像词法分析那样非得自己写出来才算真正的会。
像LR算法的语法分析器,一般都是用工具Yacc来生成,实践中
完全没有比较自己来实现。
对于LL算法中特殊的递归下降算法,因为其实践十
分简单,那么就应该要求每个学生都能自己写。
当然,现在也有不少好的LL算
法的语法分析器,不过要是换在非C平台,比如JavaQelphi,你不能运用YACC工具了,那么你就只有自己来写语法分析器。
等学到词法分析和语法分析时候,你可能会出现这样的疑问:
词法分析和语法分析到底有什么?
就从编译器的角度来讲,编译器需要把程序员写的源程序转换成一种方便处理的数据结构(抽象语法树或语法树),那么这个转换的过程就
是通过词法分析和语法分析的。
其实词法分析并非一开始就被列入编译器的必备部分,只是我们为了简化语法分析的过程,就把词法分析这种繁琐的工作单独提取出来,就成了现在的词法分析部分。
除了编译器部分,在其它地方,词法分析和语法分析也是有用的。
比如我们在DOS,Unix,Linux下输入命令的时候,程序如何分析你输入的命令形式,这也是简单的应用。
总之,这两部分的工作就是把不规则的文本信息转换成一种比较好分析好处理的数据结构。
那么为什么编译原
理的教程都最终把要分析的源分析转换成树这种数据结构呢?
数据结构中有Stack,Line,List这么多数据结构,各自都有各自的特点。
但是Tree这种结构有
很强的递归性,也就是说我们可以把Tree的任何结点Node提取出来后,它依旧是一颗完整的Tree。
这一点符合我们现在编译原理分析的形式语言,比如我们在函数里面使用函树,循环中使用循环,条件中使用条件等等,那么就可以很
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 编译 技术 发展 应用