第二章高级语言及其语法描述.

第二章高级语言及其语法描述授课人:卫志华[e-mail]概述要学习和构造编译程序，理解和定义高级语言是必不可少的本章概述高级语言的结构和主要共同特征，重点介绍程序设计语言的语法描述方法2内容线索程序设计语言的定义高级语言的一般特性程序语言的语法描述3程序设计语言的定义程序设计语言是为书写计算机程序而人为设计的符号语言。机器语言汇编语言高级语言4各级语言的比较比较机器语言汇编语言高级语言硬件识别是唯一可以识别的语言不可识别不可识别是否可直接执行可直接执行不可，需汇编、连接不可，需编译/解释、连接特点面向机器占用内存少执行速度快使用不方便面向机器占用内存少执行速度快较为直观与机器语言一一对应面向问题/对象占用内存大执行速度相对慢标准化程度高便于程序交换，使用方便定位低级语言，极少使用低级语言，很少使用高级语言，种类多，常用5程序语言的内涵语法语义语用表示构成语言句子的各个记号之间的组合规律(构成规则)。表示按照各种表示方法所表示的各个记号的特定含义（各个记号和记号所表示的对象之间的关系）。表示各个记号或语言词句与其使用之间的关系。6举例：C语言的赋值语句语法语义语用赋值语句由一个变量，后随一个符号“=”，再在后面跟一个表达式所构成。赋值语句先对该语句的右部表达式求值，然后把所得结果与语句左部的变量相结合，并取代该变量原有的值。赋值语句可用来计算和保存表达式的值。7语法语言的语法是指可以形成和产生合式程序的一组规则。它包括词法规则和语法规则。词法规则是指程序中单词符号的形成规则。单词符号一般包括：标识符、基本字、常量、算符和界符。语法规则是指程序中语法单位的形成规则。程序语言的语法单位有：表达式、语句、分程序、过程、函数、程序。描述方式：词法规则和语法规则都可以用自然语言、语法图、BNF范式、或文法等描述。8语法描述方式（1）（1）自然语言例1.标识符是由字母后跟若干个（包括0个）字母或数字的符号串组成的。例2.赋值语句由一个变量，后随一个符号“=”，再在后面跟一个表达式所构成。（2）语法图是用图解形式描述程序设计语言语法规则的工具。例1.标识符的构成规则用语法图描述为：标识符字母数字字母9语法描述方式（2）（3）BNF范式巴科斯范式(BNF:Backus-NaurForm的缩写)是由JohnBackus和PeterNaur首先引入的用来描述计算机语言语法的符号集。现在，新的编程语言几乎都使用巴科斯范式来定义编程语言的语法规则。10简单算术表达式的BNF范式简单表达式∷＝简单表达式+简单表达式简单表达式∷＝简单表达式*简单表达式简单表达式∷＝(简单表达式)简单表达式∷＝i或者简单表达式∷＝简单表达式+简单表达式|简单表达式*简单表达式|(简单表达式)|i11附：BNF表示α→β表示为α∷＝β非终结符用“”和“”括起来终结符：基本符号集其他β(α1|α2…|αn)≡βα1|βα2…|βαn{α1|α2…|αn}mn[α]≡α|ε……12语义对于一个语言来说，不仅要给出它的词法、语法规则，而且要定义它的单词符号和语法单位的意义。这就是语义问题。语义是指这样的一组规则，使用它可以定义一个程序的意义。我们采用的方法为：基于属性文法的语法制导翻译方法。13程序语言的功能一个程序语言的基本功能是描述数据和对数据的运算。所谓程序，从本质上来说是描述一定数据的处理过程。在现今的程序语言中，一个程序大体可以视为如图所示的层次结构数据引用算符函数调用表达式语句子程序/分程序程序14内容线索程序设计语言的定义高级语言的一般特性程序语言的语法描述15高级语言的分类(1)强制式：ImperativeLanguage形式：语句序列举例：Fortran、C、Pascal(2)应用式：ApplicativeLanguage形式：func1(…func(n))举例：Lisp(3)基于规则：Rule-BasedLanguage形式：bird(x):-fly(x)&feather(x)举例：Prolog(4)面向对象：Object-OrientedLanguage形式：class,举例：Smalltalk、C++、Java16高级语言的一般特性程序结构数据类型与操作语句与控制结构17程序结构——单层结构Fortran程序结构主程序＋若干个辅程序段（子程序、函数）ProgramMainRead(I,J)Callmax(I,J,K)Write(100,K)100Format(…)endsubroutinemax(x,y,z)integerx,y,zifxythenz＝xelsez＝yend18程序结构——多层结构Pascal程序结构程序允许嵌套定义ProgramP;vara,x:integer;procedureQ(b:integer);vari:integer;procedureR(u:integer;Varv:integer);varc,d:integer;begin…endbegin…endbegin….end19作用域：一个名字能被使用的区域范围称作这个名字的作用域。允许同一个标识符在不同的过程中代表不同的名字。名字作用域规则--最近嵌套原则一个在子程序B1中说明的名字X只在B1中有效（局部于B1）；如果B2是B1的一个内层子程序且B2中对标识符X没有新的说明，则原来的名字X在B2中仍然有效。如果B2对X重新作了说明，那么，B2对X的任何引用都是指重新说明过的这个X。20programmainvarA,B:real;…procedureP1varB:boolean;…begin…endprocedureP2varA:integer;…begin…endbegin…endA(real)B(real)B(bool)A(integer)21初等类型、复合类型到抽象数据类型类型本不存在内存里存储的内容，你认为它是什么，它就是什么高级语言设计了初等数据类型：整型、浮点型、字符型等。不同的语言也会定义不同的初等类型等。初等数据类型并不能方便地解决所有问题复合数据类型是初等数据类型迭代派生而来典型的代表就是“结构”，数组也可算作此类抽象数据类型(ADT)在复合数据类型的基础上增加了对数据的操作抽象数据类型进而进化为“类(Class)”22类型每个被计算对象都带有自己的类型，以类型作为值的属性的概括，因此每个类型都意味着一个值的集合。不同类型的值具有不同的操作运算类型是一个值的集合和定义在这个值集上的一组操作的总称。如C语言中的整型变量(int)，其值集为某个区间上的整数，定义在其上的操作为+,-,*,/等23数据类型数据类型通常包括以下三种要素：a.用于区别这种类型的数据对象的属性b.这种类型的数据对象可以具有的值c.可以作用于这种类型数据对象的操作24抽象数据类型一个抽象数据类型（AbstractDataType，ADT）定义为：（1）一个数据对象集，数据对象由一个或多个类型定义；（2）一个作用于这些数据对象的抽象操作集；（3）完全封装，用户除了能使用该类型的操作来处理这类数据对象之外，不能作其他的处理。抽象数据类型有两个重要特征：信息隐蔽和数据封装，使用与实现相分离25抽象数据类型…FirstComeFirstService（queue）InQueueOutQueueIsEmptyOverflowQueue（ADT）对外操作接口结构数据维护接口结构数据的物理实现26抽象数据类型（续）FirstComeFirstService（queue）InQueueOutQueueIsEmptyOverflowQueue（ADT）对外操作接口结构数据维护接口结构数据的物理实现27抽象数据类型的特点数据抽象用ADT描述程序处理的实体时，强调的是其本质的特征、其所能完成的功能以及它和外部用户的接口（即外界使用它的方法）。数据封装将实体的外部特性和其内部实现细节分离，并且对外部用户隐藏其内部实现细节。28数据抽象的优点程序组织和修改可读性、可靠性、可维护性通过隐藏数据表示，用户代码不能直接访问该类型对象，不依赖于其表示，因此可以修改该类型对象的表示而不影响用户代码29语句与控制结构表达式语句简单语句：不含其它语句成分的基本句。说明语句赋值语句控制语句过程调用语句复合语句：句中有句的语句30表达式表达式：一个表达式是由运算量（亦称操作数，即数据引用或函数调用）和算符组成的。对于大多数程序语言来说，表达式的形成规则可概括为：（1）变量（包括下标变量）、常数是表达式；（2）若E1、E2为表达式，θ为二元算符，则E1θE2为表达式；（3）若E为表达式，θ为一元算符，则θE为表达式；（4）若E为表达式，则（E)是表达式。31语句不同程序语言含有不同形式和功能的各种语句。从功能上说语句大体可分执行性语句和说明性语句两大类：说明性语句旨在定义不同数据类型的变量或运算。执行性语句旨在描述程序的动作。执行性语句又可分为赋值语句、控制语句和输入/输出语句从形式上说，语句可分为简单句、复合句和分程序等。32赋值语句A:=B意义是：“把B的值送入A所代表的单元”在赋值句中，赋值号‘：=’左右两边的变量名扮演着两种不同的角色。对赋值号右边的B我们需要的是它的值；对于左边的A我们需要的是它们的所代表的存储单元（的地址）。为了区分一个名字的这两种特征，我们把一个名字所代表的那个存储单元（地址）称为该名字的左值；把一个名字的值称为该名字的右值。33控制语句多数语言中所含的控制语句有：无条件转移语句:gotoL条件语句：ifBthenSifBthenS1elseS2循环语句：whileBdoSrepeatSuntilBfori:=E1stepE2untilE3doS过程调用语句：callP(X1,X2,…,Xn)返回语句：return(E)34说明语句说明语句旨在定义名字的性质。编译程序把这些性质登记在符号表中，并检查程序中名字的引用和说明是否相一致。35内容线索程序设计语言的定义高级语言的一般特性程序语言的语法描述36概述对于高级程序语言及编译程序而言，语言的语法定义是非常重要的。本节将介绍语法结构的形式描述问题。编译原理=形式语言理论+编译技术37形式语言自然语言人们平时说话时所使用的一种语言，不同的国家和民族有着不同的语言。形式语言通过人们公认的符号、表达方式所描述的一种语言，是一种通用语言，没有国籍之分。形式语言是某个字母表上的字符串的集合，有一定的描述范围。38为什么用形式语言形式语言的最初起因：语言学家乔姆斯基（Chomsky）想用一套形式化方法来描述语言。形式语言在自然语言研究中起步，在计算机科学中得到广泛应用。最初的应用：编译现在已广泛应用在人工智能、图象处理、通信协议、通信软件等多个领域在计算机理论科学方面：是可计算理论（算法―在有限步骤内求得解、算法复杂性、停机问题、）、定理自动证明、程序转换（程序自动生成）、模式识别等的基础。39形式语言与自动机理论的发展1956年，乔姆斯基（Chomsky）从产生的角度研究语言文法1951-1956年间，克林（Kleene）从识别的角度研究语言自动机1959年，乔姆斯基不仅确定了文法和自动机分别从生成和识别的角度去表达语言，而且证明了文法与自动机的等价性。形式语言真正诞生40基本概念字母表：元素的非空有穷集合。例：{a,b,c,…,z}（拉丁字母表）{α,β,γ,…,ω}(希腊字母表）{0,1}（二进制数字字母表）符号：字母表中的元素。如a,b,…41基本概念符号串：字母表中的符号组成的任何有穷序列。例.设字母表∑={a,b,c}其符号串有：a,b,c,ab,ac,aa,abc,…符号串与符号组