高级程序设计语言原理课件

高级程序设计语言原理

第一章程序设计语言研究什么是语言：语言是信息交流工具。有如下几种定义：1、Webster字典定义Anartificiallyconstructedprimarilyformalsystemofsignsandsymbols(assymboliclogic)includingrulesfortheformationofadmissibleexpressionsandfortheirtransformation基于一组记号与符号由人工构造的（基本上是）形式化的系统（如符号逻辑），包括合法表达式的形成规则和转换规则。2、Longman字典定义Anysystemofsigns,movements,etc.,usedtoexpressmeaningsorfeelings任何表情达意的记号系统。3、英汉双解计算机辞典定义（清华大学出版社）Asetofcharacters,conventionsandrules,thatisusedforconveyinginformation.Thethreeaspectsoflanguagearepragmatics,semanticsandsyntax一种用于传递信息之字符、约定和规则的集合。语言的三个方面是语用、语义和语法。4、中国大百科全书，电子学与计算机卷语言的基础是一组记号和一组规则，根据规则由记号构成之记号串的总体就是语言。5、徐家福：软件语言及其实现语言是基于一组记号与一组规则、根据规则由记号构成之记号串的总体。任何语言均包括语法、语义和语用三个方面。语言的作用描述作用、交流作用和标志作用（软件语言可作为计算技术发展的里程碑标志）语言是人类生活的必要工具，不同的语言被使用于不同的领域和方面在计算领域，也存在不同层次的语言，本书所论及的是实现层次的语言，即程序设计语言。程序设计语言=字符集+规则集（用于组合字符）任何用于描述算法和数据结构的一套符号系统均可称为程序设计语言本课程研究的对象：主要考虑那些在计算机上实现的程序设计语言术语所界定的范围：术语“程序设计语言”并没有一个公认的范围定义通常这个术语是指高级语言计算机上语言的层次：纯二进制机器码或符号机器码符号汇编语言宏汇编语言高级语言甚高级语言Byte或word，指令、数据不分用一些符号来代表指令，如sub代表减，Add代表加等，机器地址用十进制。有时汇编语言等同于符号机器码。变量名用符号，地址也可用符号而非数字。编制的程序称为汇编程序。用户可以定义新指令及子程序源程序编译为目标程序，或解释执行高级程序语言的高层规约语言，提供比高级程序语言更高级的语言设施。又称为“可执行的规约语言”。有时也不区别于高级语言。程序设计语言的四个基本特征：1、用户不需要具有机器代码的知识，只需学习特定的程序设计语言，并独立于任何特定的机器代码而使用。这并不意味着用户可以完全忽略实际的计算机，如：需知道浮点数的表示或使用某些机器资源。2、程序设计语言必须有较大程度的机器独立性（完全的机器独立性）。这意味着必须有较大潜力，使得源程序可运行在具有不同机器代码的两台计算机上，不需要完全重写。

3、当源程序翻译成机器代码时，通常对每个执行单元有多个机器指令，如：A=A+B需多个机器指令来实现4、程序设计语言的记号比机器语言更接近于被求解的问题。如：A=A+B比其机器翻译更易于理解。1.1为什么研究程序设计语言两个基本观察：1、已有数百种语言被设计和实现。在1969年，Sammet就列出了当时120种相当广泛使用的语言，在此以后，又有很多语言被开发。在早期，为一个项目的进行而开发一种语言是常有的事。2、大多数程序员通常不会同时使用多种语言，一般限制到1~2种。事实上，都是直接使用计算机上已有的语言如C、Ada、Fortran等。既然如此，为什么要去研究各种不同的语言，有的语言甚至永远不可能再被使用？学习、研究程序设计语言的理由不仅仅是停留于肤浅的对语言特性的了解和考虑深入了解根本性的语言设计概念及它们对语言实现的影响1、提高开发有效算法的能力很多语言提供的特性如果被合适地使用，会给程序员带来益处，但如被不合适地使用，将可能导致大量计算机时间浪费或使程序员出现耗时的逻辑错误。有可能一个长期使用某一语言的程序员也并不理解该语言的所有特性。如递归特性：是一个非常便利的程序设计语言特性如正确、合适使用，可得到优美和高效算法的直接实现。如不正确使用，将可能导致执行时间的天文数字增长。如果程序员不知道递归蕴含的设计问题和实现困难，将难于使用这种结构；对递归原理和实现技术的了解可使程序员了解在特定语言中的递归的相对代价并通过其理解确定其使用是否合适。新的程序设计方法不断在文献中引入，如OO程序设计，逻辑程序设计和并发程序设计的使用均需要对实现这些概念的语言的详细了解和掌握。2、改善对现行程序设计语言的使用通过对语言特性的实现细节的了解，可大大增加书写高效的程序的能力。如：对数据结构，诸如数组、串、表、记录等，如何被创建和操作的了解对递归的实现细节的了解以及对对象类如何被创建的了解将对书写高效程序有很大帮助3、增加可使用的有用的程序设计结构的词汇量语言对思维既有帮助，也有限制人们使用语言去表达思想，但语言也控制人如何思维，用字句中没有直接表达的方式来思维是十分困难的。在解决一个问题时，要寻找合适的数据和程序结构，通常人们首先考虑他熟悉的语言中可直接表达的结构。研究各种语言提供的结构和这些结构被实现的方式，程序员可增加其编程词汇。对实现技术的了解非常重要。如要使用一个结构，该结构在语言中没有直接提供，程序员必须提供自己的实现（使用语言提供的基本结构）。如子程序控制结构、协同例程（coroutine）在很多程序中有用，但很少有语言直接提供协同例程特性。C或Fortran程序员可以设计程序来使用协同例程结构，然后将它们实现为C或Fortran程序（如果熟悉相关概念及实现）从而可以提供大型程序的正确控制结构。4、允许更好地选择语言对程序设计语言知识的掌握可以允许程序员针对特定的项目，恰当地选取合适的语言，从而减少编码工作量。如：C、Fortran、Ada可用于数值运算，Lisp、ML、Prolog可用于人工智能应用。对每种语言的特性的长处和弱点的了解和掌握有利于程序员做出广泛而正确的选择。5、更易于学习新语言对自然语言语法结构的学习和了解可使对新语言的学习更容易对程序设计语言各种结构和实现技术的了解，也可使程序员能够在需要时更容易地学习新语言6、更易于设计新语言很少有程序员把自己考虑为语言设计者，然而，任何程序都有一个用户界面，这事实上也是某种形式的程序设计语言，用户界面包括提供给用户用于和程序通讯的命令和数据格式。大型程序，如文本编辑器、操作系统、图形包的用户界面的设计者，必须考虑很多存在于通用程序设计语言设计中的相同问题。如果程序员熟悉一般程序设计语言中的结构和实现方法，则程序设计将可以大为简化。总之，程序设计语言的研究十分重要，包括语言特性和实现技术（特别是不同结构的运行时表示技术）等主要研究内容。程序设计语言的优点比机器或汇编语言更易于学习。这涉及很多方面的问题，如一个极端强大的程序设计语言可能比一个只有十几条指令的机器的汇编语言更难学。但给定基本相同的复杂度，程序设计语言更易学（记号更接近问题域；更少关心物理硬件）程序设计语言书写的程序更易于调试debug（程序更为短小；记号本身更自然，因此更多注意力可放在程序逻辑而非语法细节上）。程序更易于理解程序设计语言的记号自然起到了文档的作用上述原因导致解决问题的时间和代价减少。程序设计语言的缺点编译过程需要机器时间，它可能超过易于调试所节省的时间编译器可能产生低效的代码如果用户不知道机器代码或编译器未提供合适的调试工具，则程序调试可能非常困难。程序设计语言的分类这是一个非常困难的问题，并没有公认的定义。这里给出一些术语，有些是相互交迭的，一个语言可能归属于两个类别。面向过程的语言（procedure-oriented）用户刻划一个可执行操作集合，它将以某种顺序完成，从而刻划了一个过程。关键因素是这些明确可执行的操作，执行顺序由用户确定。非过程型语言（nonprocedural）这只是一个相对的术语，没有人定义过，也不可能定义。意指用户指定的顺序步骤的减少程度，越接近于用户只陈述问题而不指定求解步骤，语言就越是非过程的。更进一步，可以有一个有序的步骤序列，其中每一步是某种程度上非过程性的，或是一个可执行操作的集合，其顺序用户并没有指定。两种情形均导致更多的非过程性。在Fortran出现前，语句Y=A+B*C－D/E被认为是非过程性的。因为它不能写成一个可执行单元和被任何系统翻译。随着编译系统的发展，过去非过程的今天变成过程的，而今天非过程的，明天可能是过程的。当今非过程系统的例子如：RPG（报告生成器）或排序生成器，只需给定输入和希望的输出即可，过程将被自动完成。说明型语言（DeclarativeLanguage）——完全非过程的程序只定义做什么，不需指定如何做，如函数式（归约）、逻辑式（归结、合一）语言及其它甚高级语言。面向问题的语言（problem-oriented）该术语有不同解释和用法，最常见用法是强调一个语言易于对特定问题求解（相对汇编语言），很多人将其用于针对非常特殊的应用领域。面向应用的语言（Application-oriented）这是极易误解的、但广为使用的术语。实际上，所有语言均是面向应用的，只是领域大小不同罢了。如：Fortran适合数值科学计算，Cobol适合商业数据处理PL/1则二者均适合，领域更广，又称通用（generalpurpose）语言，实际上很少有真正通用的语言一般考虑：数值科学应用，非数值应用（如形式代数），商业数值处理，串、表处理等更特殊的领域：网形、仿真、数控、设备检查等专用语言（specialpurpose）用于满足单一的目标（指定领域；对特殊应用易用；提高效率等）问题定义或规约语言（problem-defining,specification）文字地定义问题，或特别定义输入、输出，但不定义变换方法问题求解语言（problem-solving）可以完整地刻划一个问题的求解，这也是一个相对的术语标注语言（reference）是一个确定的字符集，具有语言的格式。通常用唯一字符表示某概念或语言中的字符，不一定要适合计算机输入。通常包含英文单词（作为多单个字符），也可能提供固定符号集。不需要易读。出版语言（publication）标注语言的变种，如A↑2变成A2。硬件语言（hardware）又称hardwarerepresentation，是标注语言直接映射到合适的格式以利于计算机直接输入。硬件语言本身和标注语言必须有很好映射，如**作为↑的硬件表示，begin用‘BEGIN’表示等1.2程序设计语言简史程序设计的历史很复杂，至今已很难于拟出一条全面清晰的发展轨迹。已有各种不同的总结方式。1978年，ACMSpecialInterestGrouponProgrammingLanguage(SIGPLAN)召开了一个会议，HOPL（HistoryofProgrammingLanguage），专门研讨语言发展历史。程序语言的早期发展语言发展可追溯到1945年，德国的KonradZuse设计了“Plankalkul”，未实现。1954年，Laning和Zierler开发了一个用于数学计算的高级语言，运行于M.I.T的Whirlwind上，这大概是第一个运行的编译器。它可以书写数学表达式（具有上、下标）、赋值、分叉、输入/输出、子程序，并处理微分方程。第一个广泛使用的高级语言是Fortran。IBM的JohnBackus领头在50年代中期完成，初衷是解决科学及工程计算，但后也用于更多领域，甚至写编译器。该语言证明了高级语言的可行性，奠定了后来语言研究的基础。1958年，ACM和欧洲的GAMM联合开发用于算法处理的语言IAL（InternationalAlgebraicLanguage），最终修改变成了Algol60（早点的版本是Algol58），Algol58和Algol60导致了很多相关的程序设计语言研究和编译技术开发的发展。在实践方面Fortran有很大影响，但Algol带动了语言的理论研究热潮。50年代中期，RemingtonRandUnivac的GraceHopper及其同事设计了Flow-Matic，该语言面向商业数据处理，这是第一个面向英语的语言，并成为Cobol的主要源泉。1959年，在DoD赞助下，组织了一批计算机制造商和用户开发了Cobol（CommonBusinessOrientedLanguage），该语言在商业数据处理领域的影响甚至大于Fortran在科学计算领域的影响。1958、1959可能是语言历史上生产率最大的两年。M.I.T的VictorYngve开发了Comit，这是串处理语言，用于翻译自然语言。M.I.T的JohnMcCarthy和其学生开发了人工智能语言Lisp。Lisp至今仍在使用，Comit后来变成了Snobol（Bell电话实验室于60年代中期开发）科学计算和数据处理是计算机早期的主要应用，语言也是如此，向跨两个领域的通用性发展。1959-1960，SystemDevelopmentCorporation和JulesSchwartz在Algol58基础上开发了Jovial，这是第一次通用性尝试。1963-1964，IBM和SHARE的一个联系计划开发了第一个通用语言（跨两个领域）PL/I。Algol68是随后的一个大的语言计划，这是一个全新的开发，而不仅仅是升版，其主要特性是正交性，它定义了少量的基本特征和组合它们的系统规则，允许程序员定义新的数据类型及操作。下一个大的语言计划是，1975年开始的DOD项目，目标是开发适合于嵌入式计算机系统的语言，此即Ada。1979年开始发布，1980年定稿，成为后期开发、实现和标准化的基础，Ada不仅仅是适合嵌入系统，可有更广用途。随着交互计算系统的出版，适合交互环境的语言开始出现。1963年，RandCorporation的J.CliffShaw开发了Joss.。1964年，DartmouthCollege的JohnKemeny和ThomasKurtz开发了广为流传的Basic。针对非数值数学计算（如形式代数操作）的需要。IBM的JeanSammet于1962-1964开发了Formac。MIT的JoelMoses于1970年代早期开发了Macsyma。专用领域语言开发。1956年，MIT的DouglasRoss为机床控制开发了APT。其他有：civilengineeriy:Cogo computer-assistedinstruction:Coursewriter equipmentcheckout:Atlas。1967~1977，在美国，在给定年度内使用的语言数大概是170种，同时，每年或每两年有25—30的增减。1978年HOPL会议，讨论的语言满足如下标准：a.1967年时已出版并被使用。b.1977年仍在使用。c.在计算领域有很大影响。选出的语言有：Algol,Apl,APT,Basic,Cobol,Fortran,GPSS,Joss,Jovial,Lisp,PL/I,Simula,Snobol。80年代的两个重要语言PASCAL（NiklausWirth,1968）和Ada未列入。PASCAL在70年代后期成为非常重要的语言，特别是在计算机教学方面。E.Sammet在“ProgrammingLanguage：HistoryandFuture”，CommunicationsoftheACM中列出了若干代表性语言：APT（AutomaticallyProgrammedTools）1956，第一个专用领域语言。Fortran（FORmulaTRANslation）1956，第一个广泛使用的高级语言，为大量的科学和工程人员打开了使用计算机的大门。Flow-Matic1956，第一个商业数据处理语言，第一次强调“类英文”的语法。IPL-V(InformationProcessingLanguageV)1958，第一个表处理语言。Comit1957，第一个实用的串处理和模式匹配语言。Cobol（CommonBusiness-OrientedLanguage）1960，最广泛使用的数据处理语言。具有类英文的语法和机器独立性。Algol60（ALGOrithmicLanguage）1960，用于刻划算法。形式化语法定义，带动了语言的理论和实现技术研究。Lisp（LIStProcessing）1960，引入了函数程序设计概念，基于表处理。Jovial（JulesOwnVersionofIAL）1960，第一次包含了科学计算，I/O信息的逻辑操作、数据存贮和处理等能力。大多数Jovial编译器用Jovial书写。GPSS（General-PurposeSystemSimulator）1961，第一个仿真语言。Joss（JOHNNIACOpen-ShopSystem）1964，第一个交互式语言。Formac（FORmulaManipulationCompiler）1964，第一个广泛使用的形式代数操作语言。APL/360（AProgrammingLanguage）1967，引入了许多高级操作子，允许很短的算法，产生了看问题的新方式。Pascal1971，在一个小语言中引入了如赋类型的新概念，并以优美方式组合了各种著名结构。程序设计语言的角色早期，计算机非常昂贵，而程序员年薪不高，关键资源是计算机。因此，语言设计是为了更高效地执行程序，高级语言需和汇编语言竞争。Fortran的主要设计者Backus在Fortran面世十年后曾说：坦率地讲，我们当时未曾有过任何最模糊的关于FORTRAN及其编译器将如何工作的想法。我们只是简单地努力优化目标程序，运行时间，因为当时大多数人不相信你可以真正完成这样的事。他们认为机器编码的程序将是极端低效的，对很多应用都是不实用的。我们未曾想到的一个结果是：有这样一个系统，它被设计为完全独立于程序将最终运行于其上的机器。这后来证明是非常有价值的能力，但当时我们肯定未曾想到。我们的活动没有任何组织。程序的每个部分由一到二人完成，除了极少数例外，他们完全负责他们所做的事情。事情无序地发展，当FORTRAN发布时，我们面临这样一个事实：25000条指令将并不是全正确的，存在着大量将在大量使用后才会显示出来的问题。60年代中期，程序设计发生了变化，机器价格下降，程序设计价格上升。程序移植的需求越来越多，软件的维护占用了大量的计算资源。此时的目标不再是编译程序后使其高效地运行，高级语言的任务变成使其易于开发正确的程序以解决某给定应用领域中的问题。编译技术成熟于60、70年代，语言技术以解决特定领域问题为中心，如：Fortran用于科学计算，COBOL用于商业应用，JOVIAL用于军事应用，LISP用于人工智能应用，以及Ada用于嵌入式军事应用等。程序设计语言也会进化和消亡，如：Algol已不再使用，Cobol使用正在下降，Pascal的很多结构仍在Ada中存在，但其黄金时代已过去。仍在使用的旧语言也经历了不断的修订以反应来自其他计算领域的影响，Fortran和Cobol已有多个标准化标本。Ada有1995年新标准。Lisp修订后有Scheme和CommonLisp。C++和ML则反应了人们在设计和使用语言中获得的经验的混合。对语言的主要影响源自如下几个方面：1、计算机能力计算机经历了数代的巨大变化，操作系统成为语言基于的平台（不再仅依靠硬件）。这些因素影响了高级语言的结构和使用语言特性的代价。2、应用应用领域有了很大变化，计算机应用已渗透到几乎所有领域，新应用的需求影响了新语言的设计和旧语言的修订。特别是近几年，INTERNET的发展进一步拓广的应用范围。3、程序设计方法人们对书写大型复杂系统的方法的深入研究和程序设计环境的变化也影响语言的发展。4、实现方法更好的实现方法影响到新语言中特性的选择。5、理论研究使用形式化的数学方法，对语言设计和实现的概念基础的研究加深了我们对语言特性的优势和弱点的理解，从而影响语言中特性的选取，如“继承”，因语义复杂，而被有的语言放弃。6、标准化标准化语言需要易于在不同计算机上实现，使程序易于移植，这对语言的设计影响是保守的，即轻易不引入新特性。一些重要的语言和技术影响：1951－55：硬件：电子管计算机，水银延迟线内存方法：汇编语言，基础概念：子程序，数据结构语言：表达式编译器的实验性使用1956－60：硬件：磁带存储器，磁芯内存，晶体管电路方法：早期编译技术，BNF文法，代码优化，解释器，动态存储方法和表处理语言：FORTRAN，ALGOL58，ALGOL60，COBOL，LISP1961－65硬件：可兼容的体系结构家族，磁盘存储器方法：多道程序设计操作系统，语法制导的编译器语言：COBOL61，ALGOL60（修订），SNOBOL，JOVIAL，APL符号体系1966－1970硬件：增加尺寸和速度并降低成本，小型计算机，微程序设计，集成电路方法：分时和交互式系统，优化编译器，翻译器书写系统语言：APL，FORTRAN66，COBOL65，ALGOL68，SNOBOL4，BASIC，PL/1，SIMULA67，ALGOL－W1971－75硬件：微型计算机，小型计算机时代，小型大规模存储系统，磁性内存的衰落和半导体内存的兴起方法：程序验证，结构化程序设计，软件工程作为一门学科的早期发展语言：PASCAL，COBOL74，PL/1（标准），C，Scheme，Prolog1976-80硬件：商用质量的微机，大型大规模存储系统，分布式计算方法：数据抽象，形式化语义，并发、嵌入式、和实时程序设计技术语言：Smalltalk，Ada，FORTRAN77，ML1981－85硬件：个人计算机，第一代工作站，视频游戏，局域网，Arpanet方法：面向对象程序设计，交互式环境，语法制导编辑器语言：TurboPascal，Smalltalk80，Prolog的发展，Ada83，Postscript1986－90硬件：微机时代，工程工作站的上升，RISC体系结构，全域网，Internet方法：客户/服务器计算语言：FORTRAN90，C++，SML（标准ML）1991－95硬件：非常快的廉价工作站和微机，大规模并行体系结构，语音，视频，传真，多媒体方法：开放系统，环境框架，国家信息基础设施（信息高速公路）语言：Ada95，过程语言（TCL，PERL）1996－2000硬件：二代Internet，机群，网络计算机（NC）方法：软件构件技术，Agent，中间件，浏览器/服务器计算，Internet计算语言：JAVA，XML，IDL（后两种一个意义上不能算为程序设计语言）1.3程序设计语言的评价好语言的属性1、清晰、简单、一致（协调）程序设计语言既是思考算法的概念框架，又是表达算法的工具。语言对程序的帮助不仅在编码阶段，还会在此阶段前较长一段时间，均有帮助。语言应该是提供清晰、简单、一致的概念，用作算法开发的基本原语。因此，希望有最少数量的不同概念及其尽可能简单和规则的组合规则，称为概念完整性。语言的语法对程序的书写、测试、理解和修改有较大影响，因此，可读性是一个中心问题。特别精简或隐义的语言使程序易于书写（对有经验的程序员），但难于读（当要修改时），如APL，甚至程序员本人过一段间后也难读懂。有的语言几乎相同的语句实际上代表了完全不同的事。因此，一条基本原则是，语义不同应在语法中完全反映出来。2、正交性意味着可以以所有可能的方式来组合语言特性以得到有意义的组合结果，如条件语句和任意表达式的组合。正交性使语言易学，程序易写，因为不需记住太多的例外和特殊情况，缺点是：逻辑上不协调或极端低效的组合可能会被编译器忽略。正交性在语言设计中是一个有争议的属性。3、应用自然性语言的语法应使得正确的使用可以允许程序结构反映出算法的逻辑结构。理想地：直接将程序的设计翻译为合适的反映算法结构的程序语句。顺序算法、并发算法、逻辑算法等各有不同的自然结构。语言应提供合适的数据结构、操作、控制结构和面向问题的自然语法。语言流行的主要原因之一便是对自然性的需要。特别适合某类应用的语言将大大简化该领域程序的创建，如Prolog适合于推导，C++适合于OO设计。4、对抽象的支持即使对最自然的语言，在刻划问题求解的抽象数据结构和操作与语言固有的特别的基本数据结构和操作间总是存在着差距。如C可能是一个合适的用于构造大学课程调度应用的语言，但抽象的数据结构如“学生”、“课程”、“授课老师”、“教室”等以及抽象操作“分配某学生到某课程”，“安排某课在某教室”等并不在C语言中提供，而它们对应用本身是非常自然的。程序员的任务之一便是为问题求解设计合适的抽象，然后用实际语言提供的更基本的特性来实现这些抽象。理想地：语言应允许数据结构、数据类型和操作作为自包含的抽象而定义，程序员可以将它们用在程序的其他部分（只需了解其抽象性质，而无需知道实现细节）。5、程序易于验证程序的可靠性总是一个中心的问题，有很多技术验证一个程序是否正确地完成所需功能。程序可以用形式化方法证明是正确的，也可以用桌面检查方式非形式地证明正确性（读程序文本）也可以用测试的方法，用测试数据输入，检查输出结果是否满足规约，对大型程序，可能需要这些方法的组合语言应该对程序验证提供支持，其支持力度是选择语言的主要标准之一。语义和语法结构的简单性是简化程序验证的主要因素。6、编程环境语言的技术结构仅仅是影响其使用的一个方面，而合适的编程环境可以弥补语言技术上的弱点。编程环境包含很多因素：可靠的、有效的、有良好文档的语言实现自然是首要因素。特殊的编辑器和测试包可以加速程序的创建和测试。维护和修改程序的多个版本的机制有利于大型程序的开发。7、程序的易移植性程序的易移植性是很多项目的重要目标。广泛使用的和独立于机器特性而定义的语言是易移植性的有用的基础，如：Ada、Fortran、C、Pascal等有标准化定义的语言书写的程序易移植性较好。8、使用代价代价是评价语言的主要元素，但具有不同的代价度量。a.程序执行代价在早期，代价主要是程序执行代价。因此，优化编译器的实现、高效的寄存器的分配和高效的运行时支持机制的设计是非常重要的。程序执行代价对语言设计是重要的，但主要对将重复执行的大程序更为重要。目前，对很多应用、执行速度不再是主要考虑。对程序开发的更好诊断和更容易的用户控制以及程序的维护也需要考虑，在此情况下，执行时间增加10%—20%，也是可容忍的。b.程序翻译代价当Fortran或C等用于教学时，高效的翻译（编译）比高效执行更为重要。通常学生程序会多次编译，而执行次数不多，需要快速、高效的编译器。c.程序生成、测试和使用的代价对某类问题，求解应该在程序员最少投入的情形下被设计、编码、测试、修改和使用。如：Smalltalk是价格有效的，求解一个问题的时间和努力均较少。对使用语言的总代价的考虑在很多情况下变得和传统的代价同等重要。d.程序维护的代价研究表明，对较长时间运行的程序的代价不是初始设计、编码、测试的代价而是整过生命周期代价（涉及开发和维护）。维护包括发现错误的修改、平台的变化所需的修改、程序的扩展和加强。语言对维护的支持是非常重要的（长期运行的程序由多个人员维护，语言应有支持）语言的应用领域语言的使用依赖于所求解问题的应用领域，过去30年各种应用领域的语言已有很大变化。1、60年代的应用60年代的程序设计可分为四个基本类：商业处理、科学计算、系统程序设计、人工智能应用。商业处理这类应用大多是大的数据处理系统，运行在大型机上，其基本特征是：读大量在多个磁带设备上的历史数据，读少量的当前事务集，写出一个新的历史数据集。COBOL是这类应用的代表语言。商业应用还包括商业计划、风险分析和“Whatif”方案（60年代，这样一个应用通常需几个月）。科学计算主要用于各种数学方程的求解，包括数值分析、微积分求解、统计，这是计算机的第一个应用领域，Fortran是最流行语言，其语法接近数学。系统操作系统和编译器这类应用要求能够访问硬件的全部功能和资源，当时没有有效的语言存在。汇编语言是主要的选择。Jovial（Algol的变体）曾用于美国DoD的一些项目，60年代末，PL/I可用于此目的。一个相关的应用领域是过程控制，由于当时计算机的庞大和昂贵，大多数过程控制应用是非常大的，如电站控制和自动装配线控制。Forth语言专为此而设计，汇编语言也常被使用。人工智能其特征是对大的数据空间的搜索算法。LISP是主要语言。2、90年代的应用当前的情况远较过去复杂，有更多的应用领域，可选语言也更多。商业处理COBOL仍然是主要语言，C和PL/1也时常被使用然而“Whatif”方案已完全改变，spreadsheet已完全改革该领域过去对典型的商业计划程序需化一个程序员几个月，现在可在几小时内泡制出很多。第四代语言也开始进入此市场。4GL提供了基于窗口的程序员界面，易于访问数据库记录，易于产生填空式的输入表和优美的输出报告，有时4GL编译器产生COBOL程序作为输出。科学计算Fortran仍有较大市场，C开始进入该领域。Fortran90加入了许多Ada和其他语言的特征。系统软件60年代末的C和后来的C++占据了这个领域。C提供了非常高效的执行，允许程序员对操作系统和硬件的完全访问，其他语言如：Modula、Pascal、现代BASIC也可用于此。Ada以支持系统软件开发为目标，但从未达到其成为此领域主要语言的目标。汇编语言的使用已成为过去。实时语言的需求也在增加，C、Ada、Pascal常用于此。AILISP仍在使用，只是改为Scheme和CommonLisp。Prolog是此领域的新军。出版字处理系统有自己的输入命令和输出文件语法。TEX是常用的语言，它产生Postscript页面描述语言（直接使用已不多见）。Process（处理）60年代，程序员通过命令操作计算机，现在常用程序来控制其他程序，如：每天半夜备份文件，自动回答电子邮件等。这样的活动称为处理，这需要专用的处理语言，例如有：UNIX中的Shell，DOS中的BAT等。新范型新的应用模型仍在研究中，ML用于类型理论研究，其用户正在增长。Smalltalk是另一重要语言，它是OO语言的起源。JAVA的应用域也在逐步扩大。语言的标准化一个例子：inti；i=(1&&2)+3；这是一条C语言语句，该语句是否有效？i的值是什么？要回答这个问题，三个方法是常用的。1.通过阅读语言参考手册以决定语句的含义2.在自己的计算机上写一段程序查看其结果3.阅读语言标准中的定义选择2是常用的方法——简单易行，因为语言概念和其特殊实现相关。直接查用户参考手册也是常用的。但选择3较少用，因为很少有人看语言标准。选择1、2意味着一个语言的概念是和其特殊实现相关的。但实现是否正确？如：移植一个程序到另一计算机上，仍能正确编译吗？通常语言设计涉及一些复杂的细节，各个厂商有不同的解释，从而产生细微的执行行为上的差异。厂商也可能决定加入新的特性到语言中以增强其有用性，但新加入是否“合法”是一个问题，它有可能导致移植的困难。为解决这些问题，大多数语言有标准定义，所有实现应该符合标准，通常有两种标准：1.业主标准（Proprietary）。开发并拥有语言的公司所给定的定义。这类标准通常不适合已广泛使用的语言。实现上的变体会随着很多增强和不兼容而出现。2.合议标准（Consensus）。基于相关参与者的同意而由一个组织产生的标准。合议标准是保证语言实现一致性的主要方法。每个国家都有自己的标准化组织美国：AmericanNationalStandardInstitute,ANSI负责程序设计语言标准的是：ComputerBusinessEquipmentManufactureAssociation(CBEMA)的X3委员会。IEEE（InstituteofElectricalandElectronicEngineers）也开发相应标准。英国：BSI（BritishStandardsInstitute）国际：ISO（InternationalStandardsOrganization），在瑞士、日内瓦。标准开发遵循类似的过程在某一时间，一组人认为一个语言需要一个标准定义了，标准化组织将组织一批志愿者来开发标准，当工作组提出标准后，让更大范围的人进行投票，不能达成共识的部分去掉，然后产生语言标准。从理论上说，这是一个好过程，然而，实际上标准制订技术和政治因素参半，如：编译器的制造商在标准化过程中均有财力投入，都希望标准按自己的思路走，从而避免改变自己的实现以及失去用户群。标准的制定是一个合议的过程，不是每一个人按自己的方式办，而是希望最终的语言能为所有人所接受。在意见不同时，有时不得不将有的特性排除在标准外。为了更好地使用标准，有三个值得强调的问题：1.时限：什么时候开始标准化一个语言？Fortran于1966年开始标准化，当时已有很多不兼容版本，从而导致了很多问题。另一个极端，Ada于1983年在有任何实现前即开始标准化，因此，并不清楚标准产生时是否有语言可以使用。第一批的Ada编译器在87或88年才出现。人们应该尽早开始一个语言的标准化，只要有足够的语言使用经验即可，太晚则会导致很多不兼容的实现。2.相符性——什么意味着程序和编译器符合标准程序符合标准——如果该程序只使用标准定义的特性编译器符合标准——对一个给定的符合标准的程序，可以生成能够产生正确输出的可执行码。这里并未涉及对标准的扩充，如编译器加了附加特性，则使用这些特性的程序将不合标准。标准通常强调符合标准的程度，大多数编译器都加入了自己的特性。3.废弃新的计算机结构需要新的语言特性。一旦我们标准化一个语言，几年以后它可能会变得古怪。如：Fortran66标准就已过时，它没有类型、嵌套控制结构、封装、块结构和其他现代特征。一般每五年应复审标准，或者重新修订或者丢弃。所有标准的一个问题是：遵循旧标准书写的程序怎么办？重写程序代价非常大，因此大多数标准需要向后兼容。这样也存在一些问题：具有废弃结构的语言可能变得难以控制，更危险的是这些结构可能会对好的程序设计有害。目前，存在两个相关概念：废弃和反对（deprecate）废弃——一个特性被废弃是指：它是一个可能在下一个标准版本中丢弃的特性，这意味着，该特性仍然可用，但在5—10年内会被丢弃，这样提前可为重写作好准备。反对——反对特性将在下一个标准版本中变成废弃的，新编写的程序不应再使用此类特性。符合标准的编译器允许有扩展，只要能正确地编译符合标准的程序即可。大多数编译器均有扩展，厂商加入特性以力争扩大市场份额。这是导致语言发展的重要因素之一。学术界，人们并不关心这样的标准，总是根据自己的研究扩展和修改语言。这也是语言发展的重要源泉。1.4环境对语言的影响语言的发展不能在真空中进行，支持语言的硬件对语言有很大影响。支持程序执行的外部环境称为操作或目标环境。程序被设计、编码、测试和调试的环境称为宿主环境。通常可分为四类目标环境：批处理环境交互式环境嵌入式系统环境程序设计环境－－交互式环境的特例批处理环境最早和最简单的操作环境只含有外部数据文件数据文件→程序处理→数据文件称为批处理：因为输入数据聚集成批并成批处理。Fortran、C、和Pascal均是为批处理而设计的，当然也可用于交互式嵌入式环境。对语言设计的影响环境的影响可分为四个方面：I/O特性、错误和例外处理、时间设施和程序结构。批处理语言中，文件是大多数I/O特性的基础。虽然文件可用作到终端的交互式I/O，但对交互I/O的特殊需要并不涉及。文件通常存贮定长记录，而终端需要键盘上每输入一个字符就读入一次。嵌入系统需访问特殊的I/O设备，批处理器则不作此考虑。批处理中，终止程序执行的错误是可接受的，但代价昂贵，因为错误纠正后，必须重复全部运行。同时，来自用户的立即处理和纠正错误的帮助是不可能的。这样语言的错误或例外处理机制强调在程序中进行错误/例外处理，使得程序可从大多数错误恢复，无终止地继续执行码。批处理的第三特征是程序时间限制的缺乏。语言通常不提供监控或直接影响执行速度的设施。语言特性的实现也通常反映出时间限制的缺乏。程序结构通常包含一个主程序和一个子程序集合，如:C、Fortran、Pascal等。子程序完全由编译器处理，编译器在工作时间内很少和程序员交流。交互式环境当前的PC机和工作站大多如此使用，程序在执行过程中直接和用户交互，从键盘或mouse接收数据并送到显示器显示。如字处理、游戏、数据管理、CAI等。影响:交互式I/O完全不同于一般的文件操作.错误处理方式不同，一旦错误输入，程序可能显示错误消息并请求纠正，在程序中处理错误的设施并不重要，错误时终止程序通常是不可接受的。必须经常使用某种时间限制，至少必须有可以忍受的时间反应。有时，长时间不输入会导致其他操作的调用。主程序的概念通常不存在。程序由一系列子程序构成，用户在终端输入“主程序”作为命令序列。和用户的交互形式为：请求命令，按命令执行，请求另一命令。嵌入式系统环境一个用于控制一个大系统的部分的计算机系统称为嵌入式系统（成为大系统的有机集成部分，其失误将导致整个大系统的失败）。可靠性和正确性是这类系统程序的主要属性。影响：嵌入式系统的程序通常没有操作系统的支持，也没有通常的文件和I/O设备环境，程序必须和非标准的I/O设备直接交互，通常使用特殊的过程。因此，语言通常不考虑文件和面向文件的I/O操作。特殊设备的访问能力是必须提供的：通过访问特殊的硬件寄存器、存储位置中断处理器或以汇编或其他低级语言书写的子程序。错误处理是十分重要的。每个程序应准备好处理所有错误，采取适当的动作去恢复和继续。程序终止是不可接受的，除非灾难性的系统失误。通常也无用户提供交互帮助。错误处理还必须处理系统部件的失败（除了一般的错误外）。嵌入系统总是涉及实时操作，即能对输入作出及时反应并同时产生输出，语言必须具有时间设施。嵌入式计算机系统通常是分布系统，涉及多个计算机。这样，运行的程序通常是一个并发执行的任务集，每个任务控制或监控一个局部。如果有主程序，也仅仅是为了初始化任务的执行，一旦初始化后，任务通常并发运行，且无限地运行，除非整个系统失败或关闭。程序设计环境这是程序创建和测试的环境，和操作环境相比，它对程序设计影响稍小，然而，普遍的认识是：好的程序设计环境对程序生产有较大影响，程序设计环境通常包含一个支持工具的集合和调用它们的命令集（编辑器、调试器、验证器、测试数据生成器、美化打印器等）。对语言的影响主要体现在两个方面：分开编译和部件装配，程序测试和调试分开编译——这对大型程序的实现非常重要分开编译的困难在于：编译一个子程序时，编译器可能需要其他子程序或共享数据对象的信息。所需指导的信息包括：1、被调用子程序的参数的数量、类型、顺序等的规约，允许编译器检查外部子程序的调用是否有效。其他子程序的书写语言也是需要知道的，编译器可以据此设置适当调用顺序，以传送数据和控制信息。2、被引用变量的类型声明是需要的，允许编译器确定外部变量的存储表示，使得引用可以用适合的访问格式来编译。3、外部定义而在内部声明使用的数据类型的定义是需要的，允许编译器分配存储和计算局部数据格式。为了提供关于分开编译的子程序、共享数据对象和类型定义的信息，通常有三个方法：1、语言可能需要信息在子程序中重新申明（如Fortran）。2、指定特殊的编译顺序，先编译所需的外部信息（如Ada、Pascal）3、需要在编译过程中包含相关规约的库的存在，使得编译器可随时查询（Ada、C++）方法一又可称为独立编译每个子程序可不需外部信息而独立编译，子程序是完全自包含的。缺点是：没有办法检查内外信息的一致性。这种不一致错误只能在装配阶段才可能知道。方法二、三需要工具将子程序、类型定义和公共环境的规约放到库中。通常子程序的体（body，含局部变量和语句）可以略去，只需规约。体部分可在以后分开编译。如Ada中，每个子程序、任务或包分成两个部分（可以分开编译）：规约和体。一个对尚未编译的子程序的调用称为Stub，包含Stub的子程序可以执行。但当到达Stub点时，该调用产生一个系统诊断信息而不进行实际调用，从而可达到单独测试目的。分开编译影响语言设计的另一面是共享名（不同开发者可能对子程序类型定义、公共变量使用相同的名）的使用。通常解决共享名的方法有三：1、每个共享名必须是唯一的（由程序员来保证），如C中extern中的变量名。命名约定用于每个小组使用不同的子程序名（如固定的名字前缀），如C中的_缀。2、语言常使用作用域（Scope）（在嵌套情况下，只有最外层子程序中的名对外可知）规则来隐藏名字。3、通过显式地加入来自外部的定义而使名字可用，OOPL的继承即为这种机制，通过包含外部定义的类在一个子程序中，该类定义的其他对象也就自然可知。Ada中，名字可以重载，n个对象可有相同名字，需编译器来指定实际的引用。测试和调试大多数语言会有辅助程序测试和调试的特性。1、执行追踪。Prolog、LISP和很多其它交互语言提供了允许特殊语句和变量被标志为执行时“追踪”。当标记的语句被执行或标记的变量被赋新值时，程序的执行中断，指定的追踪子程序被调用。2、断点（Breakpoint）。在交互式编程环境中，语言常提供断点设施，当达到断点，执行中止，控制权交给程序员，他可检查或修改变量值并且开始程序执行。3、断言（Assertion）。断言是一个条件表达式，插入在程序中。例：assert（x>0andA=1）or（x=0andA>B+10）断言陈述了在指定点变量值间应有的关系。当断言被“使能”，编译器插入相应的代码来测试被陈述的条件，条件不成立，则执行终止，调用例外处理。程序正确后，可将断言设置掉重编译，此时，它只作为注释用。早期的语言设计需使程序能高效地运行于昂贵的硬件上，因此，早期语言总以翻译成高效的机器码为目标，既使程序难以书写。现在，硬件价格下降、软件价格上升，更强调程序容易书写，即使慢点也可。例如，ML的类型特性、C++的类、Ada的Package均在执行速度上有代价，但对保证程序正确性有帮助。开发语言时，有三个影响语言设计的主要因素：计算机本身在计算机上支持语言的执行模型，即虚拟计算机语言所实现的计算模型2.1计算机的结构和操作一个计算机是能够存储和执行程序的数据结构和算法的集成集合。计算机可构造为实际的物理设备，用导线、集成电路、电路板等。此即实际计算机或称硬件计算机。计算机构造为软件，用运行于其他计算机上的程序。此即软件仿真计算机。程序设计语言的实现是通过一个翻译器，将以语言书写的程序翻译为机器语言程序（可为某计算机直接执行，可以是硬件计算机，也可以为软硬参杂的虚拟机）。一个计算机包含6个主要部件，它们紧密地对应于程序设计语言的主要方面。1、数据：计算机必须提供各种基本数据项和操作的数据结构。2、基本操作：必须提供对操作数据有用的基本操作集。3、顺序控制：必须提供控制基本操作执行顺序的机制。4、数据访问：必须提供控制向操作的执行供给数据的机制。5、存储管理：必须提供控制程序和数据存储分配的机制。6、操作环境：必须提供与包围程序和被处理数据的外部环境通讯的机制。计算机硬件一个典型的传统计算机组织如下：包括程序和被处理的数据操作主存和高速缓存中的数据在主存和外部环境间传递程序或数据完成处理工作取机器指令解码调用指定的基本操作，以指定的操作数作为输入数据有三个主要的存贮部件：主存，高速寄存和外部文件。主存：组织为线性位串，可分为定长的字（32或64）或8位字节。寄存器：字长度的位串，可能有特殊的子域可直接访问，可存数据或主存地址。外部文件：存在盘、带或CD-ROM上，按记录划分，记录是位或字节的序列。一个计算机有被硬件基本操作直接操作的固有数据类型。一般有：整数、单精度实数（浮点数）、定长字符串、定长位串等。除了明显的硬件数据元素外，程序（也有固有的内部表示，称为机器语言表示）也是一种数据形式。机器语言程序可构造为存储位置的序列，每个包含一或多条指令，每条包括操作码和若干操作数（指示）。操作计算机必须包含有一个固有的基本操作集，通常和机器语言指令中操作码一一对应。典型的操作集包括在固有数值类型上的基本算术操作。测试数据项各种性质的基本操作。访问和修改数据项的基本操作。控制I/O设备的基本操作。顺序控制的基本操作。传统的机器是CISC，complexinstructionsetcomputers.新近发展的是RISC，reducedinstructionsetcomputers.更少的基本指令，更简单的内部逻辑。顺序控制程序地址寄存器（位置计数器）的内容决定了下一条将执行的指令，即包含了下条指令的地址。某些基本操作允许修改程序寄存器，从而传递控制到程序的其他部分。解释器实际地使用程序地址寄存器并指导操作序列。解释器是计算机操作的中心，其周期动作如图所示：数据访问除了操作码外，每个机器指令必须指明所需的操作数（必须在主存或寄存器中）计算机必须结合指定操作数的手段和从给定操作数指示器检索操作数的机制。同时，操作的结果也必须存储在指定的位置。传统的存储控制机制是为存储位置设定整数地址，提供操作从给定地址的位置检索内容和存储新值。寄存器也赋以整数地址。存储管理机器设计的一个驱动原则是保持所有计算机资源尽可能多地被使用，中心冲突是：CPU中的操作是纳秒级（一个操作10—50ns）访问主存是是微秒级（0.1~0.2微秒，100—200ns）外部数据操作是毫秒级（15—30毫秒）这样在内外速度间相差1000,000倍。为了平衡速度差异，各种存储管理机制是必须的。1、在最简单的设计（如低价PC）中，只有简单的存储管理设施。程序和数据执行时驻留内存，在一个时刻只有一个程序准备执行。虽然CPU必须等待数据，它也是价格有效的，因为不需加入附加硬件。2、为加速外部数据访问和CPU间的平衡，操作系统常使用多道程序设计，当等待毫秒去读数据时，计算机将执行另一个程序。为了保证多个程序同时驻留主存，通常有硬件设施负责页面查找或动态程序重定位，页面查找通过预测进行，预测在最近将来最可能使用的页面，将其放入主存。如在主存，则程序执行，否则，出现页间错，操作系统将从外存中读取所需页，同时执行别的程序。3、为加速主存和CPU间的不平衡，常使用Cache存储器（小的高速数据存储）。Cache可允许计算机操作，好象主存具有和CPU相同速度，通常是1K到256K字节，32K的Cache，可达到95%的选中率。操作环境计算机的操作环境通常包括外围存储器和I/O设备，这些设备表示了计算机的外部世界，和计算机的任何通讯必须通过它们。操作环境中通常有硬件的不同，如：高速存储（扩展内存），中速存储（磁盘），低速存储（磁带）和I/O设备。各种计算机体系结构计算机硬件的组织有多种形式，上面的讨论是基于VonNeumann体系结构。VonNeumann体系结构：命名来源于数学家JohnvonNeumann，他在40年代开发这个初始设计，作为ENIAC计算机设计的一部分，现今计算机仍属此体系结构。多处理器：VonNeumann设计的最大问题是外部数据设备的慢速和CPU寄存器高速间的矛盾。解决方案之一是在指定系统中使用多个CPU，这样的多处理系统已使用了30多年，通过几个相对不昂贵的CPU的粘合，再加上单一的主存、磁盘、磁带等，得到一个高效系统。操作系统将不同程序运行于不同CPU上，从而整个性能得到改善。语言和系统设计正在演化，使得能够书写程序在多个计算机上执行并相互通讯。计算机状态对计算机静态组织的了解只是一个部分，全面了解则涉及计算机在程序执行时的动态操作，包括：执行开始时各存储部件的内容，操作执行顺序。执行进行时如何修改各种数据部件，程序执行的最后结果等。通常对计算机动态行为的观察是通过计算机状态（执行过程中某点主存、寄存器和外存的内容决定）的概念。程序的执行体现为一系列状态的变化初始状态通过一系列状态变迁（从当前状态通过存贮内容的修改进入新的状态），得到最终状态。如果我们可以预测状态变迁序列，则可以声称了解了计算机的动态行为。固件计算机如前定义，计算机=算法集+数据结构集 可执行程序表示为计算机的机器语言程序通常认为计算机操作在相当低级的机器语言之上，具有简单的指令格式。然而，机器语言并不一定限制到低级。可以选择任何程序设计语言，精确地刻划数据结构集和定义程序执行规则的算法，这样该计算机的“机器语言”就是该高级语言。每个程序定义了计算机的初态，程序执行的规则定义了程序执行过程中状态的变迁序列，程序执行结果由程序执行完成后计算机的终态决定。给定一个精确的计算机定义，总是可能将其用硬件实现，从而可使计算机的机器语言为C、Ada、或其他高级语言。如此考虑的一个重要的基本原则是：任何精确定义的算法或数据结构可以用硬件实现。计算机简单地是算法和数据结构的集合，我们可以假定其硬件实现是可能的，不管其复杂度和相应的机器语言。实际的计算机通常有相当低级的机器语言。高级语言作为机器语言会使机器非常复杂，具应用灵活性较差。一个具有低级通用指令集和简单的、无结构的主存和寄存器的计算机可以被编程为相当广范围的高效计算机。一个常用的选择（相对于计算机的严格硬件实现）是固件计算机，由运行在特殊的微可偏程硬件计算机上运行的微程序来仿真。这种计算机的机器语言是绝对低级的微指令集，用微指令集可编码得到微程序，微程序将仿真所希望的计算机的操作，并定义了解释周期和各种基本操作。通常微程序本身驻留在特殊的只读存储器中，由宿主机硬件高速执行，这种计算机在执行速度上和硬件直接实现计算机无太大差别。计算机的微程序仿真有时可称为emulation（仿真），该计算机称为虚拟机，因为机器本身并不存在。翻译器和软件仿真计算机理论上，有可能直接构造硬件或固件计算机，运行任何特殊的程序设计语言，但构造这样的计算机并不经济。现实的考虑是实际计算机采用低级机器语言（基于速度、灵活性和价格考虑），编程仍以高级语言进行。语言实现者面临的任务是如何使高级语言程序执行在实际计算机上，不管其机器语言。这个实现问题有两个基本方案。1、翻译（编译）高级语言程序→翻译器→等价的机器语言程序→硬件直接执行源语言→目标语言几种特殊类型的翻译器：A、汇编器目标语言：实际计算机的机器语言源语言：汇编语言，机器语言的符号表示大多数指令是一对一的翻译B、编译器目标语言：汇编和机器语言源语言：高级语言C、装配器或连接编辑器（loader/linkeditor）目标语言：实际的机器代码源语言：几乎相同于机器代码，通常包含可重定位的机器语言程序和数据表（刻划可重定位代码为变成真正可执行所必须修改的地方）D、预处理器或宏处理器源语言：某种高级语言的扩展形式目标语言：同样语言的标准形式。通常进行宏替换。高级源语言到可执行机器语言的翻译通常涉及多个翻译步骤，有时，编译本本身也涉及多遍（多步），如：先产生某种中间形式。2、软件仿真（软件解释）我们可以通过运行在另一台宿主机上的程序仿真一台计算机，其机器语言为高级语言。用宿主机的机器语言构造一个程序集（表达高级语言执行必需的算法和数据结构），即用软件构造运行于宿主机上的高级语言计算机，称为高级语言计算机在宿主机上的软件仿真（或软件解释）。仿真计算机接受高级语言程序作为输入，主仿真器程序完成解释算法（解码并执行语言），最后从程序产生输出。软件仿真和翻译的不同：均以高级语言程序为输入，但是，翻译为目标码后再运行于实际计算机上仿真计算机直接执行输入程序翻译器以物理输入顺序处理程序语句，每个语句只处理一次。仿真器以逻辑控制流处理程序，可能重复处理某些语句而完全忽略其他语句。纯粹的翻译和纯粹的仿真形成两个极端全翻译是很少的，除了输入语言和输出语言非常相似，如汇编语言。全仿真也非常少，除了操作系统控制语言或交互式语言情形。通常语言实现是二者的结合。如图所示。翻译和仿真各有不同优点有的程序结构最好翻译成更简单的形式，——如循环中语句多次执行，翻译可省去解码时间。有的方面最好保持原有形式，在执行时根据需要处理。翻译的主要缺点是失去了关于程序的一些信息。单个的高级语言语句比单条机器语言指令含有更多信息。仿真的优缺点基本正好相反。不需要太多的空间来存储代码序列的多份拷贝。但解码代价高。通常，如源语言结构在目标语言中有直接表示，则代码扩展不太严重，可采用翻译。其他情形，可采用仿真。是否程序执行时的基本表示为实际机器的机器语言，形成了语言划分的基础。1、编译型语言。如：C、C++、Fortran、Ada等源语言翻成机器码，仿真仅限于一些运行支持例程（用于仿真源语言中和机器语言没有紧密类似的基本操作）。通过硬件解释器，可实现更快的程序执行。当然，也可能有的部分仍采用软件仿真，如数据控制结构和存储管理。2、解释型语言。如：LISP、ML、Prolog、Smalltalk等翻译器不是产生机器代码，而是产生某种中间形式，比源语言更易执行。然后使用软件解释器对中间代码进行执行。通常执行慢，也需要对基本操作、存储管理和其他语言特性的仿真，这类语言翻译器很简单，更多的复杂性在软件仿真。2.2虚拟计算机和绑定时间计算机的构造方式1、通过硬件实现，直接使用物理设备2、固件实现，在合适的硬件计算机上使用微程序设计3、软件仿真，在宿主机上用某种语言实现4、上述技术的组合，各自选择合适的实现方式当一个程序设计语言被实现，程序执行时使用的运行时数据结构和算法定义了一个计算机。类似计算机的固件实现，我们称其为由语言实现定义的虚拟计算机。该虚拟机的机器语言是该语言的翻译器产生的可执行程序（形式：对编译是实际的机器码形式；对解释是某种任意结构）；其数据结构是程序运行时使用的运行时数据结构；基本操作是那些运行时实际可执行的；顺序控制、数据控制和存贮管理结构也是那些运行时使用的，不管其是用软件、硬件或微程序表示。语法和语义语法：程序看起来象什么。语法规则规定了如何书写语句、声明和其他语言结构。语义：对各种语法结构赋予的含义。在语言手册和其他语言描述中，通常围绕语言中的各种语法结构组织语言描述。典型地，给出语法（对一个语言结构，如语句、声明），然后给出语义，BNF是主要的语法记号体系。本书的组织方式略有不同，围绕和虚拟机相关联的结构来组织，这种风格用用在虚拟机中的数据结构和操作来描述语言的语义。有时，这些数据结构和操作是直接和语言语法中的特殊结构相关联的，而通常，这种联系并不是太直接。如：Pascal虚拟机中可能在程序执行中使用向量，而向量结构是在声明中直接给出的；然而，虚拟机也可能有其它不能在程序中直接可见数据结构，如子程序“活跃记录”的中心栈。这些“隐藏”的虚拟机结构和那些直接对应程序员写在程序中的某些东西的“可见”结构一样，对更好地了解语言同等重要。因此，这里的讨论是围绕在虚拟机中看到的结构，而不仅仅是语法元素来进行的。一个特殊的虚拟机元素可能在程序中没有语法表示；可被单个语法元素直接表示；可被几个分开的语法元素表示（由翻译器合起来产生一个虚拟机元素）。虚拟机和语言实现如果语言用它们的虚拟机来定义，使得每个语言和一个共同理解的虚拟机相关联，则使用虚拟机来描述语言的语义是直接的。然而，语言定义通常是个体地对每个语法结构给出语义，语言定义仅隐含地刻划了一个虚拟机。语言在不同计算机上的每次实现，实现者都会从语言定义中看到略微（或非常）不同的虚拟机。同一语言的两个不同实现，可能使用不同的数据结构和操作集合（特别是在语法中隐藏的部分）。每个实现者有很大自由度确定自己的虚拟机结构，这些是他的语言实现的基础。当语言在一特定计算机上实现时，实现者首先确定表示语言的语义解释的虚拟机，然后通过基本计算机提供的软、硬件元素来构造虚拟机。语言实现的组织和结构由实现者的许多细微决策确定，需考虑计算机各种软、硬件设施和使用代价。例：虚拟机如有整数加和平方根操作，则整数加可直接用硬件提供的整数加来实现，平方根可用软件仿真，使用一个子程序。整数变量x可直接用存储位置实现，该位置存放x的值；也可带有标记，由标记和指针（扩向存取x值的位置）构成）。实现者还需确定什么通过翻译处理？什么在执行中解决？通常，如果在程序翻译并建立运行时结构的过程中，采用了某些动作，则可以使用一个特定的表示虚拟机数据结构或操作的方式。如果实现者略去这些动作而简化翻译器，则不同的运行时表示可能是必须的。三个因素导致相同语言的不同实现1、实现者虚拟机概念的不同（隐含在语言定义中）2、宿主机提供的设施的不同3、实现者如何用宿主机提供的设施仿真虚拟机元素的选择和如何去构造翻译器支持这些虚拟机选择的不同。计算机层次程序员以某种高级语言编程使用的虚拟机事实上形成了一个虚拟计算机层次。底层：实际的硬件计算机。通常程序员很少直接使用这个计算机，一般地，硬件机被一个或多个软件层（或微程序）变换成一个虚拟机，它可能和硬件机有很大不同。二层：由称为操作系统的例程集合定义的虚拟机（如微程序形成第二层，那么这也可称为第三层）。典型地，OS提供了一系列新的操作和数据结构的仿真（这不是由硬件直接提供的）。如：外部文件结构或文件管理原语。OS也从OS定义的虚拟机上删去了某些硬件原语，使得它们不能由操作系统用户直接访问。如：关于I/O、错误监测、多道程序设计和多道处理的硬件原语。OS定义的虚拟机通常就是高级语言实现者使用的机器。三层：语言实现者提供了一个新的软件层，运行于OS虚拟机上，仿真高级语言虚拟机的操作；也提供了翻译器：将用户程序翻译成语言定义虚拟机的机器语言。四层：高级语言定义的虚拟机并不是层次的最后一层。实际上，程序员编制的程序形成了新的一层虚拟机。那么，什么是这个程序员定义的软件仿真虚拟机的机器语言呢？（这个程序的输入数据将由这个机器语言构成或写成）。一旦程序员建立了一个程序，必须有一个“程序”在该程序定义的虚拟机上运行，这个“程序”通过选择合适的输入数据集合而写成。这个概念之所以难于理解，是因为对很多程序而言，输入数据非常简单，仅仅可称为最平凡的程序设计语言。如：排序程序的机器语言可认为是整数集，即以一定格式构成的整数表为程序。然而，明显的是：每一个在我们上述层次上构造较低层次的程序员必须记住这个观点，因为在每一层构造的程序和数据结构事实上表示了下一层程序员编程使用的虚拟机的仿真。上面讨论中一个隐含的中心概念是：程序和数据是等价的。我们习惯于在编程中将对象区分为“程序”和“数据”，这通常是一种有用的直觉的区分，但如上所讨论，这种区分是一种表面性的。在某语境中的程序可能在另外的语境中变成数据。如：我们写Pascal程序，但对Pascal编译器来说，该程序是被输入处理的数据，其输出是机器语言程序。如果观察程序的执行，你会发现它又是执行计算机中解释器的数据。我们总是将某程序的输入等价为将被处理的数据或将被执行的程序。进一步考虑这个问题（等价性）。如：在C、Fortran语言中，表示可执行程序的存储空间通常是和其数据空间分开的。但在LISP和Prolog中，则没有不同，程序和数据是混合的，只有执行过程可将其区分开来。绑定和绑定时间不严格地说，一个程序元素到某特定特征或性质的绑定，仅是从一个可能性质的集合中性质的简单选择。决定这个选择的程序陈述或处理的时间称为性质对元素的绑定时间。语言中有不同的绑定和不同的绑定时间。绑定时间的类型对绑定类型没有简单的分类，但可区分出一些主要的绑定时间。这里，我们基于一个基本假设：程序的处理总是先翻译，后执行。1、执行时（运行时）很多绑定是在程序执行过程中完成的。如：变量到值的绑定，变量到特定存储位置的绑定（在很多语言中）。进一步可分为：a.进入子程序或块时。大多数语言中，重要的绑定只限制发生在执行中进入子程序或块时，如C、Fortran中形参到实参、以及