程序设计语言原理复习-第0章 绪论

第章绪论0语言是交换信息的媒介，是人们相互通信的工具，也是信息的载体，人们借助这些载体来卜m力丁住自五省阜田维什丁且“7II1然语善苣1类之

三、工活与自屣斗%中发展起来的语言是人类群体为群体内交换信息的一种约定汉语、英语、法语、俄语、西班牙语……都是自然语言我们知道，一种自然语言主要是一组发声规则、语音语调的声音语言，以及对应的一套基于符号文字的书面语言然而，哑语、盲文又扩大了自然语言内涵的范畴，至今难于准确定义什么是自然语言为与本书讨论的高级程序设计语言比较，我们先看看自然语言的性质

0.1语言的一般性质•媒体性人们传递信息常常要用到自身器官所能表达的一切手段，声音是最重要的传递手段，但姿态、动作、情绪（形、象）却不可少为了记录转瞬即逝的信息，辅助信息记忆（存储），人们发明了与声音对应的文字符号语言符号文字实质上是图形的抽象，图形又是自然景象的抽象声、图、文、象成了表达自然语言的基本手段，它们相互补充随着人类历史的进展，加上媒体本身固有的性质，它们既相似又各不同在每一个发展方向上又派生出若干分支，例如，符号语言派生出数学符号语言以表达逻辑和推理思维，派生出音乐符号的五线谱便于对乐器的操纵声音语言总是当前用于交换的语言，它有时间性，并且是驱动自然语言发展的最活跃分支文字语言相反，它有很强的稳定性古文、时文留下不同历史时期的自然语言版本文字语言也往往是语言规范的依据声、图、象随着计算机技术的发展，它将成为表达人类形象思维的有力工具符号文字、语言则成为逻辑思维的表达工具不同媒体语言都是自然语言的组成，相互补充而又无法完全取代•规范性语言是通信工具，通信者之间若无事先约定的规则，信息传递必然失真任何语言都有一组约定的基本元素（音素、图素、符号集、象元）以及它们合法组合的规则集，即语法；以及这些基本元素在合法的组合中的意义，即语义；还有这些有意义的组合在不同应用环境下所表达的真实含义，即语用一种语言，有一致的基本元素、语法、语义、语用的规则本来是不言而喻的然而，由于使用语言的是人人们往往寻求自己意志更好的表达方式向趋简、扩大概括范围、随意舒发，加上不同行业、阶层、地域的差别，使得方言、行话、俚语、黑话层出不穷简化字，缩略语、外来语比比皆是在交通通信不发达的古代，只能做到统一文字规范，方言甚至发展到全然不懂的程度，例如中国的南北方言规范化和方言化这一对矛盾始终推动着语言的发展，即使在通信高度发展规范化要求很高的今天，行话、俚语也不能完全消除•演进性语言必然随社会信息量的总增长而发展随着社会文化的发展语言也向纵深发展它往往从专业的专门需要而扩展到全社会例如，符号语言的数学分枝，当社会上数学普及时就成为通用语言的一部分，如算术符号，等号，代数公式，积分号等；商业词条随着商业文化普及，也成为大众语言的一部分，如“投入”、“产出”、“透支”作为语言表达基本概念部分的字典日益增厚，大英牛津离典词条已达130余万作为语言规则的另一部分，也从古英语变为现代英语，古汉语变为现代汉语自然语言的演进随社会经济、文化发展有其自身的规律，沿规范化一一方言化缓慢但不停滞地交替进展，并深深受到政治影响秦始皇的“书同文”，清代的“康熙字典”，以及我国解放后的“汉字简化方案”、民国的“国语”和以后的“普通话”，都是规范化的重大步骤而每次规范化都纳入方言化中合理的进展如果经济文化未发展到某种程度，政治影响不足，即使是非常好的演进文字，其效果也不理想例如，本世纪初的世界语由于没有经济文化托，至今敌不过英语的普及以致于人们产生错觉自然语言是难于进化的其实是人们运用语言的惯性演进性与惯性这一对矛盾在自然语言中也确实存在人们往往习惯于从小养成的某种表达方式而拒绝“更好”的表达方式方言地区的普通话一听就可以听出来，“日本英语”很难听就更不用说了但惯性的影响只在一代、半代人最多十几代人的时间，从语言发展的历史看演进性是明显的，而且愈来愈快•抽象性客观事物总是普遍联系相当复杂的，且处于永恒的运动变化之中人们表达的信息总是抽取某个需要的侧面以其主要特征概括该事物从表达的简易性来看人们总是力图抽象，愈是抽象它表达的事物外延愈大，如“人”，它包括“白人”，“黑人”，“亚人”，“非洲人”……甚至包括“泥人”，“铁人”所以，在语言中主干词往往是比较抽象的，形容词、副词使之具体化代词一般更抽象汉语中的虚词（之、乎、也、者、矣、焉、哉）更是无所不能信息表达中利用简单的抽象构造复杂的抽象是扩大表达能力的基本手段随着人类文明的发展，从组合抽象上升到概括抽象是非常明显的愈是文明古国的语言，抽象概念愈多例如:爱斯基摩人说“雪”有十六种具体的雪，唯独抽象不出“雪”字但抽象语言有时也会失于贴切和准确我国翻译家常常为找不到贴切的形容词和副词翻译英文而头疼•冗余与多义性随着信息质和量的扩大，借鉴表达和重复表达同时存在一词多义、一意多词在自然语言中比比皆是，语言情况更严重，汉语早就有“九Li十八Chen”的说法这带来释义的困难必须根据上下文的语义才能完成释义尽管如此，误解、误用比比皆是绝对的冗余随着规范化的进展会逐渐消除但有些冗余已深入到语言本身已无法消除例如，汉语中“感觉”、“平平稳稳”，无法用“感到”、“觉得”、“平稳”替代有些冗余甚至成为法定语法，例如，英语中的时态与时间副词的重用I finishedthe workyesterday.finished若不用过去时即为错句双重保险冗余是必要的再如，同一语义可用主动句语法也可以用被动句语法这种冗余带来表达的方便多义源于借喻和类比，最为典型的是成语，成语一般只取其抽象涵义，如“一针见血”在绝大多数情况下不是讨论“针如何扎出血”之类的问题，而任何不接触实质的问题都可用它评判另一个来源是一词多词性，如英语SET一词有33个解汉语“画画”“扇扇”……等等，有时造成难以分辨的混乱，如中国队大胜中国队大败中国队大胜美国队中国队大败美国队正是由于冗余和多义性，自然语言在短期内不可能作为程序设计语言因为机器还不能像人那样聪明程序设计语言的一般性质

0.2程序设计语言是表达软件的工具，任何软件都是计算机系统行为的预先规划这个规划就是以某种语言编写的程序系统计算机系统理解了程序并按程序的规定完成一步步的动作所以，程序设计语言也是人一一机通信工具从用户的观点，程序设计语言是一台虚拟的机器语言的表达能力和效率，就是机器的能力与效率学会了某种语言（当然包括系统命令）就是学会了使用机器，甚至可以不懂硬件工作原理从用户观点，程序设计语言也是人一一人交换信息（如何用程序模型“问题世界”的运动）的工具这点对当今软件开发的工程方式尤其重要我们从表达、通信、使用三个方面描绘了程序设计语言功能实质作为语言它也有和自然语言相似之处（如下述），但最大的不同是•程序设计语言是人工语言这里所说“人工”指一个语言从定义一一实现一一到流行不象自然语言那样要经过数百年到数千年，而是几年到几十年因此，规范化一一方言化，演进性一一，惯性矛盾加骤新语言、新版本层出不穷1975年美国国防部曾统计当时美国软件所用语言及方言多达1500种，当今开发一个新语言由于有完善的工具，不用一人年，因此，其数量不可胜数•主要通信对象是机器这首先要求程序设计语言定义、实现要精确，决不能有含混和遗漏所以，到目前为止程序设计语言都是有严格定义的符号语言，即形式语言计算机科学家积极研究形式语法，形式语义，以求得到准确的解释其次，机器由于使用目的不同，制造厂家不同，容量、速度、指令及格式差异是客观存在的而用某种程序设计语言表达的程序要能在各型机上运行，它就不能有依赖机器的特征然而，哪怕有一个重耍特征被抽象略去，耍充分发挥硬件设备的能力也无异于空谈所以早期语言没有一个是完全独立于机器的，甚至包括（Pascal、C）o同样，语言也不应有依赖运行支持（即OS、运行支持例程和支持库）的特征•用于表达软件如同数理符号系统对于数学、五线谱对于音乐，程序设计语言应方便于表达软件，能反映当前软件开发技术，能为用户提供所需要的特征但要弄清楚的是，软件开发技术和程序设计语言的表达没有直接关系即技术高超的程序员能用过时的老语言编制反映最新技术的程序但往往以牺牲可读性、易维护性、安全性为代价好的程序设计语言使用方便，符合软件工程诸原则，从而有助于提高软件的开发效率除以上三点与自然语言不同之外程序设计语言也有媒体性，特别是当今多媒体技术蓬蓬勃勃地发展，声控程序，图形编程，动画设计陆续走上实用但当今整个的程序设计语言学仍然建立在符号学的基础上，即以正文字符作为程序设计语言媒体其他形式媒体只是被处理的对象，故本书讨论的程序设计语言仍限于正文符号语言程序设计语言的人工性决定了演进很快，从1954年FORTRAN研制至今已有七个正式版本Turbo-Pascal,Borland-C,MSC更快，几乎1年半就有一新版本程序设计语言演进这么快说明了两个问题一是软件技术发展很快，二是人们还没有找到相对满意的程序设计语言估计在今后一段相当长的时间也不会稳定这也是本课程开设的目的制约语言演进的因素是与老版本开发出的软件兼容把老版本改造成新版本的投资量并不比重新开发少很多（这是软件工业的特点）不利用又造成极大浪费，所以老语言规范改版比新语言困难、慢得多语言惯性在程序设计语言中依然存在所以第一门入门语言对软件工作者影响极大语言惯性也制约着新型性能良好的语言推广程序设计语言更能说明抽象性因为说到底机器只会取出一条指令执行一条指令，改变内存某些单元的数据人们对机器一次运行的结果作出的解释就是程序的语义机器语言只有操作码（存、取、比较、四则算术）和地址码的定义人们制造了变量、数组、赋值、控制函数、过程、块等语义概念，经翻译成为操作码、地址码实现这些概念，从而人们可以编制过程式程序如果再把数据结构和操作进一步封装起来，就可以实现对象式程序……总之，愈向前发展愈是提供更接近问题域的概念编程，愈远离原始的地址码和操作码语义基本的技术是高层抽象其不意图如图0T一个问题域中的问题，经需求分析建立解题模型，如果是函数、逻辑、对象式模型则可直接以程序中函数，谓词推理规则、对象的表达机制编制程序而不涉及指令及地址细节如果是过程式编程，除了程序对象及其相互关系之外，还必须设计对象实现的过程，但也不涉及指令和地址细节汇编程序则需由程序员把计算模型转换成面向机器的指令和地址最后这些不同层次语言编制的程序都经编译（或解释）器变为可执行目标码面向机器一面向过程f面向对象一面向问题这是当今程序设计语言发展的趋势程序设计语言的多义与冗余也同样存在特殊符号从最早的高级程序设计语言即有多义，如FORTRAN中的括号（），可声明数组大小、维度；数组元素引用；条件语句中的条件；函数和过程的参数表；隐循环；格式语句的格式说明；表达式中优先算符现代语言把多义扩充到标识符，如Ada,C++的函数重载，即同一函数名代表不同的函数这个趋势随着编译分辨能力增强会更明显，其目的是方便因为一个系统由若干程序员分别开发常用名词术语都差不多只许唯一的名字管理实在太麻烦冗余也一样，我们都知道结构化程序设计理论指出只要有三种特征顺序、条件和循环即可编出任何程序，迭代只要while-do语句就够了然而，标准的结构化语言Pascal循环有三种（while_do,for_do,do_until）此外，从控制执行流程说来只要条件表达式加上goto句」任何控制回征均能袤o达然而，所有保留got语句的语言都定义了许多控制特征，即使是转语句FORTRAN中就有四种（转、计算转、标号转、算术条件转）这些冗余无非是为了方便和编程效率为什么要研究程序设计语言

0.3自1945年有现代计算机以来，程序设计语言研究始终是最活跃的领域到目前为止，还没有趋于稳定传统的程序设计语言已暴露出不适应新技术的需求，然而又离不了它们新语言虽层出不穷，又一时难于占据统治地位其中的原因、趋势很值得研究具体说来•它是计算机软硬件技术的窗口软、硬件技术发展最终必然要反映到人一一机界面的语言上例如，硬件高速、存储容量增大，图形界面、可视计算就有可能，相应图符语言得到发展软件重用技术的发展，可重用库标准化，才有第4代语言的诞生这些新发展都会改变传统的使用计算机方式和程序设计语言的概念和定义所以，只要软硬件技术在发展，新版本还会不断出现•它是人们研究计算表达的形式计算机科学的本质是研究如何把问题世界的对象及其运动映射为程序对象及其交互通信即从计算的角度观察、模型客观世界，然后在模型理论的基础上建立表达（即语言）、实施计算程序设计语言学不涉及模型理论本身但是是表达成果的手段例如模糊逻辑要求模糊程序设计语言，函数式模型要求表达高阶函数的函数式语言所以，随着人们对计算本质的认识加深，新范型，新语种总会出现•它和计算机理论研究联系最紧密计算机科学就是从集合论

（1895）、符号逻辑

（1910）、不完全理论

（1931）发展起来的至30年代Post系统、递归函数论、可计算性理论奠定了计算机科学基石从研究停机问题的Post系统和形式语言理论基础上，发展出完善的形式语法，编译理论，编译器的编译器至可扩充语法的EL/1系统从递归函数论的一个分支，建立了操作和指称语义学，直至类型理论此外，当今并发、分布、协调理论，CSP、CCST均与并发分布式程序设计语言相关有关计算科学理论基础和形式语义学发展见图0-2,图0-3因此，学习程序设计语言的理论和实践为进一步学习计算机理论打下基础1900集合论

（1895）G.PeanoI1910符号逻辑

（1910）A.N.Whitehead和B.Russell不完全理论Goeder

（1931）1930Post系统====递归函数论二=可计算性理论Charch,Rosser（1930s）Turing

（1936）1940信息论Shannon形式语言理论Chomsky1950开关理论形式语法义（I960）自动机理论1960Backus,Naur Rabin,Scott计算复杂性理论hartmanis,Blum语法分析方法Knuth1970编译器的编译器可计算密码学

（1976）扩充语法EL/1Diffie,heliman通用键钥系统

（1978）随机算法Rivest,Shamir198019901920自动数学Post图0-2计算机科学理论基础•研究程序设计语言还有利于提高软件开发人员素质对程序设计语言清晰的理解能扬长避短地使用某种语言；善于捕捉潜在的软件缺陷；会选择适宜的语种或版本1930Post系统递归函数论二可计算性理论Church,Rosser Turing

（1936）1940入演算

（1941）Church1950程序正确性证明（60年代）1960引用透明性Strachey形式形式语义定义PL/1维也纳定义

（1967）!并发性

（1968）Dijkstra1970指称语义学

（1971）IScott,StracheyICSP

（1978）,分布式计算类型理论Milner

（1978）Hoare LamportI!1980函数式语言ML Miranda协调计算

（1988）Haskel]1990图0-3形式语义学理论的发展•有利于开发专用语言或界面语言专用语言可大幅度提高软件生产率，使用户使用更方便随着语言技术向更抽象方向发展，计算机技术向各行业渗透，开发近于各行业术语和工作规程的非常高级的语言是必然趋势这样各行业人员经过极少的计算机培训即可用计算机解决自己的业务问题•有利于新领域语言的发展当前处于热门的规格说明语言、并发程序设计语言、4GL、多媒体语言（5GL）远不及顺序过程式语言成熟对于不太成熟语言的使用者，必须有较好的程序设计语言的理论功底，一方面能减少不必要的错误，另一方面也能促进新语言的发展•有利于通用语言的标准化规范化对于广大的软件工作人员说来，如果不是专业的程序设计语言工作者，语言标准化就不是份内的工作但熟知语言的理论和实践对理解、推行的标准，不无端制造方言都有好处而“必要的方言”又是下次标准化的候选扩充版本程序设计语言定义与处理器

0.4一个程序设计语言的物理存在就是该“语言的引用（参考）手册（LRM）,俗称“语言定义文本”，术语是该“语言的规格说明它是一个文档，引用手册规定了该语言的语法和它的语义，以及用该语言元素写的程序如何组织（即如何提供一个完整的程序）一个程序设计语言的实际存在是该语言程序的处理器它是一个软件，机器配备了这个软件，机器就具备处理该种语言程序的能力处理器将独立于机器的源程序翻译为可在该种机型上运行的目标代码程序因此，按执行的模式处理器有编译型的和解释型的解释器读入一段相对完整源代码（多数情况下是一句）翻译为目标代码后，立即解释执行交互式环境的语言即采用这种方式一般说来，解释器能够迅速给出正确结果，但程序效率较差这不等于说只适合于交互式的小语言庞大的Ada程序设计语言的第一个实现就是解释型的因为，当时急于验证语言定义是否完整正确编译器读入一个独立的编译单元（程序的逻辑单元，如主程序、函数，子程序或若干个逻辑单元组成的编译单元，如文件、模块、包）翻译为可执行的目标代码单元，经过连接必要的库支持例程成为可执行内存映象，加载到内存中运行，由于是按单元翻译，可以经过上下文分析作若干次优化，目标代码质量高对于运行量大要求高效的应用则采用编译型语言，此外，还有翻译器从一种语言翻译为另一种语言的软件统称翻译器编译器、解释器将源代码翻译为目标码是它的两种特例将用户定义的界面语言翻译为某种高级语言（如Pascal,C,Ada）,C语言的预处理器就是翻译器的实例预处理器将语法定义以外的特征翻译为符合该语法定义的表示，是扩充程序语言的手段一般说来，程序设计语言的定义是第一性的，不依赖于处理器的实现但验证语言的功能和性能却要在某个具体的机器上运行该语言的处理器这是目前验证语言设计仅有办法Ada的ACVC测试程序用例近一万个，通过不了则不承认你是Ada的编译器正因为如此，在定义程序设计语言的机制时，它一方面要根据应用域的需要定义各种语法特征（提供相对独立语义概念的语法规定），同时也要顾及到该种特征实现的可能性例如，重载标识符，必须有分辩信息，故一般变量不宜重载，函数名可以早期的语言引用手册以元语言（metalanguage）表达每一个语法特征，并以自然语言对各特征作语义说明或限定早期元语言的概念指“描述语言的语言”，而不是当今“更加本原”的高抽象“元”的概念元语言一般包括•字符集、词条表由它们提供标识符、运算符、关键字、空格、限制符、各种数字量、字符串常量等语法概念•注释注释符号之内（或以后）的符号串是为人们阅读，处理器要略去的•语法结构定义定义以上符号组合的合法结构它给出语句、表达式、程序单元、块（如FORTRAN的循环域）、作用域、嵌套与结合等语法概念早期的语言语句定义是最主要的语法结构元语言是严格形式定义的，例如，COBOL的ADD语句定义为r标识符]「标识符]IADDS-TO标识符[ROUNDED][,标识符[ROUNDED]]…〔数值J L数值J[;[ON]SIZE ERROR语句]其中｛｝括着的列，其各项是可任取一的[]括着的项是可选的…表示重复项字词下面横线表示基（相当于关键）字，有的文本以黑体给出，若选此项必写此词元语言描述是面向程序员使用的其实它的词条表，就是语法中的词法标记（Lexical token）o重复项，替换项在巴库斯（BNF）范式中以更加数学化的符号“|”代替早期元语言的形式定义最大的问题是，它只定义了语法结构的形式，没有规定这些结构是如何产生的，致使在说明中作更多的附加说明尽管如此，语言编译的实现者还经常因理解的不同产生微妙差异而验证编译器是否正确目前尚无简易办法，若无大量测试，只能投入市场实际使用以求反馈信息这种代价是巨大的计算机理论家、语言学家认为如果语法和语义能以更加数学化地描述，则不必经过大量测试在纸上即可验明其正确性，发现它的问题，即时修改经过60-70年代的努力，形式语言学得到发展形式语法尤其完善，形式语义尚未完全成熟；尽管如此，程序设计语言的实现者仍力图借助这些形式理论，解决实现语言时的许多含混问题目前，程序设计语言引用手册（为使用者所用）已不回避BNF、EBNF等面向实现者的描述方法语义方面仍然是自然语言和示例解释，是非形式的形式语义仅当需要时由语言实现者、研究者另外作出但是，一些基于经验的语言（如C）,至今拒绝EBNF描述语法，仍用元语言形式，因为严格的数学化会取消它们的许多灵活性

0.5本书的目的与组织本书是为有一定编程经验的系统程序员、应用开发者编写的，作为深入了解高级程序设计语言，选用设计语言的教材书中也有一些实现编译器或解释器的内容，但不是设计实现语言处理器的指导教材通过程序设计语言发展和更新，读者可以了解软件发展中与计算和表达有关的主要理论和实践问题也许这比学会设计出小型程序设计语言处理器更重耍本书力图复盖美“ACM/IEEE-CS计算1991教程”有关程序设计语言部分本书的具体目标是•对各种类型高级程序设计语言有清晰的理解它们的基本原理、概念和程序设计范型•了解常用高级程序设计语言的优缺点以便有选择，有限制地使用或更改扩充•了解程序设计语言发展中的问题与趋向，以及程序设计语言在软件技术中的地位•掌握程序设计语言各主要成分设计中的关键问题学会分析、选择、调合、折衷，以便设计新特征•掌握设计程序设计语言的主要步骤和表示法和理论分析、表达的基本技能本书共分四大部分第零章至第二章是有关程序设计语言的一般论述并简述形式语法第三章至第九章是程序设计语言的基本元素和特征机制第十章至第十五章是各种程序设计范型第十六章至第十七章为形式语义，第十八章是附录。