编译原理讨论课报告编译技术的过去现在未来.docx
《编译原理讨论课报告编译技术的过去现在未来.docx》由会员分享，可在线阅读，更多相关《编译原理讨论课报告编译技术的过去现在未来.docx（15页珍藏版）》请在冰点文库上搜索。
编译原理讨论课报告编译技术的过去现在未来
编译原理课程讨论课报告
题目：
编译技术的过去现在未来
我们的讨论课的题目是编译技术的过去、现在和将来。
其中又有3个小题目分别是
（1）早期的编译技术
（2）目前流行的编译技术（3）未来的编译技术。
接下来我们的报告也将分为这三方面进行。
一丶编译技术的过去
编译技术的过去主要分成三部分，首先是编译技术出现的必要性，几种当时的编译原理和编译器的发展。
我们将编译器的发展作为了主要部分。
并且附加上国内的编译器发展。
1.编译技术出现的必要性
在20世纪40年代，由于冯·诺伊曼在存储-程序计算机方面的先锋作用，编写一串代码或程序已成必要，这样计算机就可以执行所需的计算。
开始时，这些程序都是用机器语言（machinelanguage）编写的。
机器语言就是表示机器实际操作的数字代码，例如：
C70600000002表示在IBMPC上使用的Intel8x86处理器将数字2移至地址0000（16进制）的指令。
但编写这样的代码是十分费时和乏味的，这种代码形式很快就被汇编语言（assemblylanguage）代替了。
在汇编语言中，都是以符号形式给出指令和存储地址的。
例如，汇编语言指令MOVX,2就与前面的机器指令等价（假设符号存储地址X是0000）。
汇编程序（assembler）将汇编语言的符号代码和存储地址翻译成与机器语言相对应的数字代码。
汇编语言大大提高了编程的速度和准确度，人们至今仍在使用着它，在编码需要极快的速度和极高的简洁程度时尤为如此。
但是，汇编语言也有许多缺点：
编写起来也不容易，阅读和理解很难；而且汇编语言的编写严格依赖于特定的机器，所以为一台计算机编写的代码在应用于另一台计算机时必须完全重写。
发展编程技术的下一个重要步骤就是以一个更类似于数学定义或自然语言的简洁形式来编写程序的操作，它应与任何机器都无关，而且也可由一个程序翻译为可执行的代码。
例如，前面的汇编语言代码可以写成一个简洁的与机器无关的形式x=2。
第一个编译程序的出现是在20世纪50年代早期，很难讲出确切的时间，因为当初大量的实验和实现工作是由不同的小组独立完成的，多数早期的编译工作是将算术公式翻译成机器代码。
用现在的标准来衡量，当时的编译程序能完成的工作十分初步，如只允许简单的单目运算，数据元素的命名方式有很多限制。
然而它们奠定了对高级语言编译系统的研究和开发的基础。
20世纪50年代中期出现了FORTRAN等一批高级语言，相应的一批编译系统开发成功。
随着编译技术的发展和社会对编译程序需求的不断增长，20世纪50年代末有人开始研究编译程序的自动生成工具，提出并研制编译程序的编译程序。
它的功能是以任一语言的词法规则、语法规则和语义解释出发，自动产生该语言的编译程序。
20世纪60年代起，不断有人使用自展技术来构造编译程序。
自展的主要特征是用被编译的语言来书写该语言自身的编译程序。
1971年，PASCAL的编译程序用自展技术生成后，其影响就越来越大。
在70年代后期和80年代早期，大量的项目都贯注于编译器其它部分的生成自动化，这其中就包括了代码生成。
这些尝试并未取得多少成功，这大概是因为操作太复杂而人们又对其不甚了解。
2.几种当时流行的编译语言
1）Fortran语言
Fortran源自于“公式翻译”（英语：
FormulaTranslation）的缩写，是一种编程语言。
它是世界上最早出现的计算机高级程序设计语言，广泛应用于科学和工程计算领域。
FORTRAN语言以其特有的功能在数值、科学和工程计算领域发挥着重要作用。
Fortran90之前的版本是人们所知晓的FORTRAN（全部字母大写），从Fortran90以及以后的版本都写成Fortran（仅有第一个字母大写）。
Fortran语言的最大特性是接近数学公式的自然描述，在计算机里具有很高的执行效率。
易学，语法严谨。
可以直接对矩阵和复数进行运算，这一点类似MATLAB。
自诞生以来广泛地应用于数值计算领域，积累了大量高效而可靠的源程序。
很多专用的大型数值运算计算机针对Fortran做了优化。
广泛地应用于并行计算和高性能计算领域。
Fortran90，Fortran95，Fortran2003的相继推出使Fortran语言具备了现代高级编程语言的一些特性。
2）Pascal语言
Pascal是一种计算机通用的高级程序设计语言。
它由瑞士Niklaus Wirth教授于六十年代末设计并创立。
以法国数学家命名的Pascal语言现已成为使用最广泛的基于DOS的语言之一，其主要特点有：
严格的结构化形式；丰富完备的数据类型；运行效率高；查错能力强。
正因为上述特点，Pascal语言可以被方便地用于描述各种算法与数据结构。
尤其是对于程序设计的初学者，Pascal语言有益于培养良好的程序设计风格和习惯。
IOI（国际奥林匹克信息学竞赛）把Pascal语言作为三种程序设计语言之一， NOI（全国奥林匹克信息学竞赛）把Pascal语言定为唯一提倡的程序设计语言，在大学中Pascal语言也常常被用作学习数据结构与算法的教学语言。
在Pascal问世以来的三十余年间，先后产生了适合于不同机型的各种各样版本。
其中影响最大的莫过于Turbo Pascal系列软件。
它是由美国Borland公司设计、研制的一种适用于微机的Pascal编译系统。
该编译系统由1983年推出1.0版本发展到1992年推出的7.0版本，其版本不断更新，而功能更趋完善。
3.编译器的发展
1.编译器的发展
编译器就是将“高级语言”翻译为“机器语言（低级语言）”的程序。
一个现代编译器的主要工作流程：
源代码（source code）→预处理（preprocessor）→编译器（compiler）→汇编程序（assembler）→目标代码（objectcode）→链接器 （Linker）→可执行程序（executables）。
编译器将源程序（Source program）作为输入，翻译产生使用目标语言（Targetlanguage）的等价程序。
源代码一般为高级语言 （High-level language）， 如 Pascal、C、C++、C#、Java等，而目标语言则是汇编语言或目标机器的目标代码（Object code），有时也称作机器代码（Machine code）。
Chomsky的研究导致了根据语言文法的难易程度以及识别它们所需要的算法来对语言分类。
正如现在所称的Chomsky架构（Chomsky Hierarchy），它包括了文法的四个层次：
0型文法、1型文法、2型文法和3型文法，且其中的每一个都是其前者的特殊情况。
2型文法（或上下文无关文法）被证明是程序设计语言中最有用的，而且今天它已代表着程序设计语言结构的标准方式。
分析问题（parsing problem，用于上下文无关文法识别的有效算法）的研究是在60年代和70年代，它相当完善的解决了这个问题。
现在它已是编译原理中的一个标准部分
有限状态自动机（Finite Automaton）和正则表达式（Regular Expression）同上下文无关文法紧密相关，它们与Chomsky的3型文法相对应。
对它们的研究与Chomsky的研究几乎同时开始，并且引出了表示程序设计语言的单词的符号方式。
人们接着又深化了生成有效目标代码的方法，这就是最初的编译器，它们被一直使用至今。
人们通常将其称为优化技术（Optimization Technique），但因其从未真正地得到过被优化了的目标代码而仅仅改进了它的有效性，因此实际上应称作代码改进技术（Code Improvement Technique）。
当分析问题变得好懂起来时，人们就在开发程序上花费了很大的功夫来研究这一部分的编译器自动构造。
这些程序最初被称为编译器的编译器（Compiler-compiler），但更确切地应称为分析程序生成器（Parser Generator），这是因为它们仅仅能够自动处理编译的一部分。
这些程序中最著名的是Yacc（Yet Another Compiler-compiler），它是由Steve Johnson在1975年为Unix系统编写的。
类似的，有限状态自动机的研究也发展了一种称为扫描程序生成器（Scanner Generator）的工具，Lex（与Yacc同时，由Mike Lesk为Unix系统开发）是这其中的佼佼者。
在70年代后期和80年代早期，大量的项目都贯注于编译器其它部分的生成自动化，这其中就包括了代码生成。
这些尝试并未取得多少成功，这大概是因为操作太复杂而人们又对其不甚了解。
编译器设计最近的发展包括：
首先，编译器包括了更加复杂算法的应用程序它用于推断或简化程序中的信息；这又与更为复杂的程序设计语言的发展结合在一起。
其中典型的有用于函数语言编译的Hindley-Milner类型检查的统一算法。
其次，编译器已越来越成为基于窗口的交互开发环境（InteractiveDevelopmentEnvironment，IDE）的一部分，它包括了编辑器、连接程序、调试程序以及项目管理程序。
这样的IDE标准并没有多少，但是对标准的窗口环境进行开发已成为方向。
另一方面，尽管近年来在编译原理领域进行了大量的研究，但是基本的编译器设计原理在近20年中都没有多大的改变，它现在正迅速地成为计算机科学课程中的中心环节。
在九十年代，作为GNU项目或其它开放源代码项目标一部分，许多免费编译器和编译器开发工具被开发出来。
这些工具可用来编译所有的计算机程序语言。
它们中的一些项目被认为是高质量的，而且对现代编译理论感兴趣的人可以很容易的得到它们的免费源代码。
大约在1999年，SGI公布了他们的一个工业化的并行化优化编译器Pro64的源代码，后被全世界多个编译器研究小组用来做研究平台，并命名为Open64。
Open64的设计结构好，分析优化全面，是编译器高级研究的理想平台。
2.国内编译器的研发历史
早在60年代初期，董韫美院士和杨芙清院士就分别在中科院和北大领导研究组开发编译器，那时面向的高级语言是ALGOL和FORTRAN，目标机是国产机。
在改革开放前，由于国家需要，中科院、国防科大、江南计算所、北大等单位一直在研制国产计算机，包括大型机和高性能计算机（如向量机、并行机），相应的也在研制高级语言编译器。
中科院计算所以董韫美院士领导的研究组先后开发了119机、109机的类 ALGOL语言编译器BCY。
国防科大开发了向量编译器和向量识别器。
70年代中科院计算所张兆庆教授研究组（以后称ACTGroup）开始在国产机上研制FORTRAN语言编译器，先后参与了众多的院级和国家级科研攻关项目，主持开发了013，757，KJ8920等国产大型机系统中的FORTRAN语言编译器，所研制的编译器支持了数百万行应用软件的运行。
90年代以来ACTGroup承担科学院重大项目，国家攻关项目，863项目，以及国际合作项目，先后开发了共享内存多处理机的并行识别器，分布式内存多处理机的并行识别器， SIMD芯片和VLIW芯片的并行优化C编译器。
将编译技术与图形学结合，ACTGroup还推出了集成化、可视化的并行编程环境。
ACTGroup在先进编译技术和并行编程环境方面的研究工作获国内外专家高度评价，国际著名学者评价此研究组居编译领域的世界先进行列。
（2）目前流行的编译技术
当今的编译技术飞速发展，出现越来越多的编译技术，并且在实际应用越来越广泛。
接下来这样介绍几种流行的编译技术。
1）并行编译技术
为了提高计算机体系结构的性能满足超大规模计算的日益增长的需求近几年并行机及多处理机的发展极其迅速而用户在这类计算机上能获得的实际运行速度在相当程度上还取决于并行程序设计和并行编译技术的水平。
因此并行编译系统已成为现代高性能计算机系统中一个重要的部分。
目前处理并行编译技术有以下两种方法。
1利用重构技术将串行程序并行化。
将已有的串行语言编写的程序经过相关分析分解成可并行的成分分配到多CPU或多处理机上运行这种技术在国内已有FORTRAN语言和C语言的并行重构处理系统。
2直接编写并行程序。
编写并行程序要比编写串行程序的要求高编程者自己必须知道程序各模块之间的逻辑结构关系及调用关系以确定哪些模块可以并行执行。
这种直接编写的并行程序要比利用重构技术改写的并行程序效率高。
并行编译技术是针对并行机和并行程序的，是一种实现多个处理机同时执行一个程序的技术。
不同的并行程序设计技术要用不同的并行编译技术来支持。
可以把并行编译技术分成串行程序并行化技术，并行语言处理技术，并行程序组织技术三个方面。
并行编译系统的功能
并行编译系统的功能是将并行源程序转换为并行目标代码。
可分为以下两类
1.不具有自动并行功能的系统
2.具有自动并行化功能的系统
并行编译系统的结构
向量编译系统包括向量化工具和向量编译器。
并行编译系统包括并行化工具，并行编译系统和并行运行库等，其结构如下图所示。
国内的并行编译技术
90年代以来，国内主要以研制并行机为主，相应的并行编译器研制也在国内开展起来。
代表性的成果有：
上海复旦大学朱传琪教授研究组研制的面向共享存储并行机的并行优化编译器AFT达到世界领先水平。
清华大学汤志忠教授研究组在软流水优化技术上做了很优秀的研究工作。
清华大学郑纬民教授研究组开发了交互式并行化系统 TIPSExplorer，北京大学许卓群教授、李晓明教授研究组在HPF（HighPerformanceFortran）编译器方面做了多年工作，取得很好的研究成果。
此外，国防科大、江南计算所等单位也都有从事并行编译技术研究。
随着芯片研制，国内还有若干单位也在开展基于GCC生成面向特定芯片的编译器工作。
自动并行编译为并行化现有的串行程序及编写新的并行程序提供了重要的支持，因此20多年来一直受到重视。
近几年来，自动并行编译技术的研究进展，包括在依赖关系分析，程序变换，数据分布和重分布及调度等方面的进展，将自动并行编译进一步推向了实用化。
该文介绍了自动并行编译技术的最新进展，并提出了进一步的研究所要解决的问题。
自动并行编译为充分发挥并行计算环境不断增强的计算能力提供了一条重要的途径I它有以下优点:
1.在缺乏被普遍接受的并行程序设计语言的情况下，自动并行化工具能有效地解决代码的可重用和可移植问题；
2.解决了用一种语言难以显式地表达从指令层到任务层各个层次的并行性，并进行基于体系结构的优化问题。
3.自动并行化工具为大量存在于应用领域的，并经过长时间的设计，使用和测试的成熟大型串行应用程序的并行化提供了唯一可行的选择。
自90年代以来，对自动并行编译技术的研究有了很大的进展，产生了一批有代表性的自动并行化系统，国外的有SUIF，polaris;国内的有JAPS,FAT.通过对这些系统的开发,人们提出了很多实用技术,涵盖了数据依赖关系分析,程序变换L数据分布及调度等方面的内容,下面依次对这些技术作简要的介绍.
依赖关系分析
循环体中的依赖关系分析和过程间依赖关系分析的质量决定了数据并行性和任务并行性的开发程度,多年来,它们一直是研究的热点,近几年的研究成果更是进一步地推动了自动并行的实用化.指针分析是对c,c++程序并行化不可缺少的工作
循环体中的依赖关系分析
循环占用了串行程序的绝大部分执行时间,因此,对循环体的依赖关系分析一直是最受关注的.早期的工作主要集中于数组是线性下标的精确方法和运行速度足够快的近似方法,分析也都是静态的.因此,在大多数情况下只能得到保守的结果.omegatest使用整数规划,综合得到了速度快且精确的结果.rangetest突破了线性下标的限制.RPT和LROT依赖于输入.静态所不能确定依赖关系的循环进行了动态并行化.
另外需要进一步研究的问题
开发通用的编译器研究平台，编译技术如果脱离了编译器是没有意义的，为了使新的编译技术能容易地集成于编译器上，以便测试和评价其性能，从而提高编译器技术的研究质量及加快研究的进展，需要可靠的模块B独立的编译器平台。
1.收集大量的与实际应用有关的测试程序，测试编译技术离不开测试程序，能够很好地刻画实际程序性质的测试程序对推进编译器技术的发展具有不可取代的作用。
2.开发高效的编译算法，为了将编译器的运行时间限制在可接受的范围内，包括依赖关系分析问题，多种循环重构技术的选择使用和组合问题，数据分布的选择，通信的优化，任务粒度的动态控制等问题，都需要更高效的算法处理。
可以考虑采用并行算法
3.开发自适应代码的产生算法，由于运行系统的变化性和程序对输入的依赖，为了提高加速比，需要开发产生自动适应系统变化和程序输入的代码的算法，包括运行时刻的依赖关系分析问题，运行时的数据分布和动态调度的算法。
2）动态编译技术
动态编译即运行时编译运行时的程序变换。
由于下述原因①面向对象语言和技术在当代软件开发中的使用已导致较大程度的延迟绑定限制了可供静态编译器分析的范围②分别编译和共享库编译器不一定能够看见所有的代码③有些信息如运行时常量值信息在编译时是不能确定的运行环境是不断变化的。
动态编译优化利用在运行时提供的信息对程序提供更完全的优化。
因此利用动态编译技术可大大扩大优化范围从而能够产生更有效的代码。
目前对动态编译的研究主要集中在3个方面①运行时特定化根据运行时常量将程序代码特定化然后在其中做各种优化工作。
如常量传播、循环展开②Justintime编译主要针对Java程序进行的运行时编译并根据profiling收集到的profile信息进行自适应的优化③动态的二进制代码转换和优化将针对一种体系结构产生的目标码直接移植到与之不同的另一类体系结构上运行。
当前编译器技术的限制是已有的技术都已经达到相当成熟的阶段在此基础上有重大突破比较难。
现在的发展只是各种技术的综合或者是针对十分具体的现象进行专门的优化达到加速某种算法模式的目的
3）交叉编译技术
一个高级语言往往需要在不同的目标机上实现这就提出了如何把已在某机器上实现的一个高级语言的编译程序移植到另一个目标机上的问题。
通常把某个机器称为宿主机上已有的软件移植到另一台器称为目标机上的过程称为移植在移植过程中也常会用到交叉编译的技术。
由于目标机的指令系统与宿主机的指令系统不同编译程序在宿主机A上运行将应用程序的源程序生成目标机B的代码这种编译技术称为交叉编译技术。
嵌入式系统中的应用程序正是借助这样的编译程序生成的近年来嵌入式应用的迅速增长推动了交叉编译技术的发展。
编译技术的应用
1）编译技术在反病毒方面的应用
被病毒感染的网页类文件经过词法分析和语法分析就可得到一有限自动机软件即虚拟机此种方式的查病毒虚拟机不同于以前虚拟机查毒方式以前查杀病毒时的环境就像一个高级机械手打开、定位、查杀而此种方式则是类似一个智能探测器打开、分析、查杀。
2）基于编译技术的可信赖计算方法
从源数据流区分部分项逐一调入表达式的字符串形式进行语法检查、拼成单词、生成逆波兰式和逆波兰式的翻译4个阶段进行处理为BS体系结构下的工程招投标双方的标底和标书搭建了清单审验的平台
3）基于编译技术的协议解析方法
基于编译技术的协议解析方法用形式化描述的方法对协议进行描述实现了与协议无关的协议解析和处理从而避免了针对不同通信协议均要编写相应的解析和处理程序使协议的解析和处理具有更好的灵活性和普适性。
（3）未来的编译技术
未来的编译技术向多核和多线程架构演变，并且软件系统正在日益复杂化，使解决程序缺陷和安全攻击问题变得更为迫切。
1.多核处理器将迅速发展，异构多核处理器也会大量出现并应用于越来越多的领域。
从消费类电子产品到超级计算机，都可能成为异构多核处理器大显身手的用武之地
但是异构多核处理器是开发芯片内并行的微处理器，这类处理器的出现并不会引起编译技术中重大的技术变革，只是给已有的编译优化技术提出了一些新的约束条件。
面向这些新的约束条件，需要对已有的编译优化技术在原有的基础上进行进一步的研究。
对于异构多核体系结构，编译系统面临的挑战仍然围绕着并行这一主题，从核内的指令级和向量级并行到核之间的线程级和任务级并行，需要解决的基本问题仍然相同。
但是，在高度集成的过程中，它同时还允许更紧密的协同工作、更大和更灵活的交互操作。
在开发其性能潜力的过程中，需要多种编译优化技术相互配合。
2.编译器将在提升程序的安全性和可靠性方面越来越重要。
最近几年，产品级的编译器都没有理由不提供这些安全保证，至少也应该为那些对安全敏感的软件提供特殊的安全选项支持。
此外，这些支持支持也可以利用一个相比机器码生成更强大的安全和可靠性技术保证的强类型虚拟机来实现。
1）多核处理器编程--Costofprogrammingmulticoreprocessors
异构多核处理器的结构特点
异构多核处理器正是针对特定领域问题的特殊性进行了处理器核心的异构设计，即将典型工作负载中不同类型的操作进行区分，分别用不同的处理器核来处理，以期获得整体上的高性能。
因此，异构多核处理器的结构特征是：
片内的多个处理器核按适用性分成多类（通常是2类）：
一类执行控制密集的操作；另一类执行计算密集的操作。
当然，每个处理器核并不是仅能执行计算或控制操作，而只是对其中一类操作更适合而已。
例如，面向控制密集操作的处理器核肯定也需要一定的数值计算能力，而处理数据密集操作的处理器核也需要能够完成简单的控制操作。
面向异构多核处理器的编译技术
目前，微处理器性能的充分发挥，越来越依赖于编译器，异构多核处理器更是如此。
对于异构多核处理器而言，由于不同结构的处理器核的指令集不同，需要生成在不同处理器核上执行的不同的执行码，因此编译过程更加复杂，同时，为了获得高性能，对编译优化技术的要求也更高。
编译的一般流程
面向异构多核处理器的编译过程，一般要经过如下若干步骤。
1．代码划分
要把用高级语言编写的程序编译成可在异构多核处理器上运行的执行代码，首先要区分哪些代码在哪类处理器上运行。
如果这部分工作由编译器自动完成，往往困难较大，并且性能低。
解决的办法通常是在源代码中添加指导语句，以便区分哪些源代码所描述的操作在哪类处理器上运行。
编译过程中的代码划分工作就是要识别这些指导语句，将在不同目标处理器核上执行的代码分离开，分别进行编译。
2．分别编译
这一步工作就是针对需要在不同类型的处理器核上执行的代码，分别调用面向目标处理器核的编译器，将其编译成执行代码。
因此，在这一步可能要调用多个编译器。
3．执行代码的组织
这一步需要解决的问题是，采用什么方式将要在不同处理器核上执行的目标代码组织成一个操作系统环境下的运行实体（可执行程序）。
通常的做法是：
运行实体在通用的标量处理器上加载执行，而将要在从处理器上执行的目标码作为该执行实体（可执行程序）的数据段中的一部分或者作为该执行实体运行时读取的数据文件。
经过以上3步，就完成了用户代码到执行程序的编译过程。
在运行过程中多个处理器核之间的协同常常还需要运行时系统提供支持。
向异构多核处理器的关键编译技术有以下几个方面。
1．面向SIMD结构的编译
SIMD结构是能充分利用处理器上大量的功能部件进行大规模数据并行计算的典型结构。
面向这种结构，通常采用自动向量化编译技术。
自动向量化是自动并行化的一种，尽管自动并行化相当困难，但仅仅面向程序中进行数据密集计算的循环来进行自动向量化是可行的。
早在向量并行计算机为主流并行计算系统的时代，就已经开始了对自动向量化技术的研究，如今已经有了相当多的积累。
采用SIMD结构的异构多核处理器的出现，又进一步推动了自动向量化编译技术研究的发展。
2．通信调度
异构多核处理器芯片内的通信包含多个层次：
单个从处理器内多个ALU15之间的数据传递、多个从处理器核之间的数据传递以及整个
升级会员 