高级语言及其语法描述精选PPT讲稿.ppt

《高级语言及其语法描述精选PPT讲稿.ppt》由会员分享，可在线阅读，更多相关《高级语言及其语法描述精选PPT讲稿.ppt（95页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、关于高级语言及其语法描述第一页，讲稿共九十五页哦2概述n要学要学习和构造和构造编译程序，理解和定程序，理解和定义高高级语言是必不言是必不可少的可少的n本章概述高本章概述高级语言的言的结构和主要共同特征，重点介构和主要共同特征，重点介绍程程序序设计语言的言的语法描述方法法描述方法第二页，讲稿共九十五页哦3内容线索n程序程序设计语言的定言的定义n高高级语言的一般特性言的一般特性n程序程序语言的言的语法描述法描述第三页，讲稿共九十五页哦4程序设计语言的定义n程序程序设计语言是言是为书写写计算机程序而人算机程序而人为设计的符号的符号语言。言。机器语言机器语言汇编语言汇编语言高级语言高级语言第四页，讲稿

2、共九十五页哦5各级语言的比较比较比较 机器语言机器语言汇编语言汇编语言高级语言高级语言硬件识别硬件识别是唯一可以识别是唯一可以识别的语言的语言不可识别不可识别不可识别不可识别是否可直接是否可直接执行执行可直接执行可直接执行不可，需汇编、不可，需汇编、连接连接不可，需编译不可，需编译/解释、解释、连接连接特点特点面向机器面向机器占用内存少占用内存少执行速度快执行速度快使用不方便使用不方便面向机器面向机器占用内存少占用内存少执行速度快执行速度快较为直观较为直观与机器语言一与机器语言一一对应一对应n面向问题面向问题/对象对象n占用内存大占用内存大n执行速度相对慢执行速度相对慢n标准化程度高标准化程度

3、高n便于程序交换，使用便于程序交换，使用方便方便定位定位低级语言，极少低级语言，极少使用使用低级语言，很少低级语言，很少使用使用高级语言，种类多，高级语言，种类多，常用常用第五页，讲稿共九十五页哦6程序语言的内涵语法语法语义语义语用语用表示构成表示构成语言句子的各个言句子的各个记号之号之间的的组合合规律律(构成构成规则)。表示按照各种表示方法所表示的各个表示按照各种表示方法所表示的各个记号号的特定含的特定含义（各个（各个记号和号和记号所表示的号所表示的对象之象之间的关系）。的关系）。表示各个表示各个记号或号或语言言词句与其使用之句与其使用之间的关系。的关系。第六页，讲稿共九十五页哦7举例：C语

4、言的赋值语句语法语法语义语义语用语用赋值语句由一个句由一个变量，后随一个量，后随一个符号符号“=”，再，再在后面跟一个在后面跟一个表达式所构成。表达式所构成。赋值语句赋值语句先先对该语句的右部句的右部表达式求表达式求值，然后，然后把所得把所得结果与果与语句句左部的左部的变量相量相结合，合，并取代并取代该变量原有量原有的的值。赋值语句可用来句可用来计算和保存表达算和保存表达式的式的值。第七页，讲稿共九十五页哦8语法n语言的言的语法是指可以形成和法是指可以形成和产生合式程序的一生合式程序的一组规则。它包。它包括括词法法规则和和语法法规则。词法法规则是指程序中是指程序中单词符号的形成符号的形成规则。

5、单词符号一般包括：符号一般包括：标识符、符、基本字、常量、算符和界符。基本字、常量、算符和界符。语法法规则是指程序中是指程序中语法法单位的形成位的形成规则。程序。程序语言的言的语法法单位有：表位有：表达式、达式、语句、分程序、句、分程序、过程、函数、程序。程、函数、程序。n描述方式：描述方式：词法法规则和和语法法规则都可以用自然都可以用自然语言、言、语法法图、BNF范式、或文法等描述。范式、或文法等描述。第八页，讲稿共九十五页哦9语法描述方式（1）（1）自然）自然语言言例例1.标识符是由字母后跟若干个（包括符是由字母后跟若干个（包括0个）字母或数字的符号串个）字母或数字的符号串组成的。成的。例

6、例2.赋值语句由一个句由一个变量，后随一个符号量，后随一个符号“=”，再在后面跟一个表达式所构，再在后面跟一个表达式所构成。成。（2）语法法图是用是用图解形式描述程序解形式描述程序设计语言言语法法规则的工具。的工具。例例1.标识符的构成符的构成规则用用语法法图描述描述为：标识符标识符字母字母数字数字字母字母第九页，讲稿共九十五页哦10语法描述方式（2）（3）BNF范式范式巴科斯范式巴科斯范式(BNF:Backus-NaurForm的的缩写写)是由是由JohnBackus和和PeterNaur首先引入的用来描述首先引入的用来描述计算机算机语言言语法的符号集。法的符号集。现在，新的在，新的编程程语

7、言几乎都使用巴科斯范式来定言几乎都使用巴科斯范式来定义编程程语言的言的语法法规则。第十页，讲稿共九十五页哦11简单算术表达式的BNF范式+*()in或者或者+|*|()|i第十一页，讲稿共九十五页哦12附：BNF表示n表示表示为 n非非终结符用符用“”括起来括起来n终结符：基本符号集符：基本符号集n其他其他(1|2|n)1|2|n1|2|nmn|第十二页，讲稿共九十五页哦13语义n对于一个于一个语言来言来说，不，不仅要要给出它的出它的词法、法、语法法规则，而且要定，而且要定义它的它的单词符号和符号和语法法单位的意位的意义。这就是就是语义问题。n语义是指是指这样的一的一组规则，使用它可以定，使用

8、它可以定义一个程序的意一个程序的意义。n我我们采用的方法采用的方法为：基于属性文法的：基于属性文法的语法制法制导翻翻译方法。方法。第十三页，讲稿共九十五页哦14程序语言的功能n一个程序一个程序语言的基本功能是言的基本功能是描述描述数据数据和和对数据的运算数据的运算。n所所谓程序，从本程序，从本质上来上来说是描是描述一定数据的述一定数据的处理理过程。程。n在在现今的程序今的程序语言中，一个程言中，一个程序大体可以序大体可以视为如如图所示的所示的层次次结构构第十四页，讲稿共九十五页哦15内容线索程序程序设计语言的定言的定义高高级语言的一般特性言的一般特性程序程序语言的言的语法描述法描述第十五页，讲

9、稿共九十五页哦16高级语言的分类(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+、Java第十六页，讲稿共九十五页哦17高级语言的一般特性n

10、程序程序结构构n数据数据类型与操作型与操作n语句与控制句与控制结构构第十七页，讲稿共九十五页哦18程序结构单层结构nFortran程序程序结构构主程序若干个主程序若干个辅程序段（子程序、函数）程序段（子程序、函数）Program Main Read(I,J)Call max(I,J,K)Write(100,K)100 Format()endsubroutine max(x,y,z)integer x,y,z if xy then zx else z y end第十八页，讲稿共九十五页哦19程序结构多层结构nPascal程序程序结构构程序允程序允许嵌套定嵌套定义Program P;var a,x

11、:integer;procedure Q(b:integer);var i:integer;procedure R(u:integer;Var v:integer);var c,d:integer;begin end begin end begin .end第十九页，讲稿共九十五页哦20作用域作用域：一个名字能被使用的区域范：一个名字能被使用的区域范围围称作称作这这个名字的作用域。个名字的作用域。允允许同一个同一个标识符在不同的符在不同的过程中代表不同的名字。程中代表不同的名字。名字作用域名字作用域规则规则-最近嵌套原最近嵌套原则则 n一个在子程序一个在子程序B1中中说明的名字明的名字X只在只

12、在B1中有效中有效（局部于（局部于B1）；）；n如果如果B2是是B1的一个内的一个内层子程序且子程序且B2中中对标识符符X没有新的没有新的说明，明，则原来的名字原来的名字X在在B2中仍然有效。中仍然有效。如果如果B2对X重新作了重新作了说明，那么，明，那么，B2对X的任何的任何引用都是指重新引用都是指重新说明明过的的这个个X。第二十页，讲稿共九十五页哦21programmainvarA,B:real;procedureP1varB:boolean;beginendprocedureP2varA:integer;beginendbeginendA(real)B(real)B(bool)A(int

13、eger)第二十一页，讲稿共九十五页哦22初等类型、复合类型到抽象数据类型n类型本不存在型本不存在内存里存内存里存储的内容，你的内容，你认为它是什么，它就是什么它是什么，它就是什么n高高级语言言设计了初等数据了初等数据类型：整型、浮点型、字符型等。不同的型：整型、浮点型、字符型等。不同的语言言也会定也会定义不同的初等不同的初等类型等。型等。初等数据初等数据类型并不能方便地解决所有型并不能方便地解决所有问题n复合数据复合数据类型是初等数据型是初等数据类型迭代派生而来型迭代派生而来典型的代表就是典型的代表就是“结构构”，数，数组也可算作此也可算作此类n抽象数据抽象数据类型型(ADT)在复合数据在复

14、合数据类型的基型的基础上增加了上增加了对数据的操作数据的操作抽象数据抽象数据类型型进而而进化化为“类(Class)”第二十二页，讲稿共九十五页哦23类型n每个被每个被计算算对象都象都带有自己的有自己的类型，以型，以类型作型作为值的属的属性的概括，因此每个性的概括，因此每个类型都意味着一个型都意味着一个值的集合。的集合。n不同不同类型的型的值具有不同的操作运算具有不同的操作运算n类型是一个型是一个值的集合和定的集合和定义在在这个个值集上的一集上的一组操作操作的的总称。称。如如C语言中的整型言中的整型变量量(int)，其，其值集集为某个区某个区间上的整数，上的整数，定定义在其上的操作在其上的操作为

15、+,-,*,/等等第二十三页，讲稿共九十五页哦24数据类型n数据数据类型通常包括以下三种要素：型通常包括以下三种要素：a.用于区用于区别这种种类型的数据型的数据对象的属性象的属性b.这种种类型的数据型的数据对象可以具有的象可以具有的值c.可以作用于可以作用于这种种类型数据型数据对象的操作象的操作第二十四页，讲稿共九十五页哦25抽象数据类型n一个抽象数据一个抽象数据类型（型（AbstractDataType，ADT）定）定义为：（1）一个数据）一个数据对象集，数据象集，数据对象由一个或多个象由一个或多个类型定型定义；（2）一个作用于）一个作用于这些数据些数据对象的抽象操作集；象的抽象操作集；（3

16、）完全封装，用）完全封装，用户除了能使用除了能使用该类型的操作来型的操作来处理理这类数据数据对象之外，不能象之外，不能作其他的作其他的处理。理。n抽象数据抽象数据类型有两个重要特征：型有两个重要特征：信息信息隐蔽蔽和和数据封装数据封装，使用与，使用与实现相分离相分离第二十五页，讲稿共九十五页哦26抽象数据类型FirstComeFirstService（queue）InQueueOutQueueIsEmptyOverflowQueue（ADT）对外操作接口结构数据维护接口结构数据的物理实现第二十六页，讲稿共九十五页哦27抽象数据类型（续）FirstComeFirstService（queue）I

17、nQueueOutQueueIsEmptyOverflowQueue（ADT）对外操作接口结构数据维护接口结构数据的物理实现第二十七页，讲稿共九十五页哦28抽象数据类型的特点n数据抽象用数据抽象用ADT描述程序描述程序处理的理的实体体时，强调的是其的是其本本质的特征的特征、其、其所能完成的功能所能完成的功能以及以及它和外部用它和外部用户的的接口接口（即外界使用它的方法）。（即外界使用它的方法）。n数据封装将数据封装将实体的外部特性和其内部体的外部特性和其内部实现细节分离，并分离，并且且对外部用外部用户隐藏其内部藏其内部实现细节。第二十八页，讲稿共九十五页哦29数据抽象的优点n程序程序组织和修改

18、和修改n可可读性、可靠性、可性、可靠性、可维护性性通通过隐藏数据表示，用藏数据表示，用户代代码不能直接不能直接访问该类型型对象，不依象，不依赖于其表示，因此可以修改于其表示，因此可以修改该类型型对象的表示而不影响用象的表示而不影响用户代代码第二十九页，讲稿共九十五页哦30语句与控制结构n表达式表达式n语句句简单语句句：不含其它不含其它语句成分的基本句。句成分的基本句。n说明明语句句n赋值语句句n控制控制语句句n过程程调用用语句句复合复合语句：句中有句的句：句中有句的语句句第三十页，讲稿共九十五页哦31表达式n表达式：一个表达式是由运算量（亦称操作数，即数据引用或函数表达式：一个表达式是由运算量

19、（亦称操作数，即数据引用或函数调用）和算符用）和算符组成的。成的。n对于大多数程序于大多数程序语言来言来说，表达式的形成，表达式的形成规则可概括可概括为：（1）变量（包括下量（包括下标变量）、常数是表达式；量）、常数是表达式；（2）若）若E1、E2为表达式，表达式，为二元算符，二元算符，则E1E2为表达式；表达式；（3）若）若E为表达式，表达式，为一元算符，一元算符，则E为表达式；表达式；（4）若）若E为表达式，表达式，则（E)是表达式。是表达式。第三十一页，讲稿共九十五页哦32语句n不同程序不同程序语言含有不同形式和功能的各种言含有不同形式和功能的各种语句。句。n从功能上从功能上说语句大体可

20、分句大体可分执行性行性语句句和和说明性明性语句句两大两大类：说明性明性语句旨在定句旨在定义不同数据不同数据类型的型的变量或运算。量或运算。执行性行性语句旨在描述程序的句旨在描述程序的动作。作。n执行性行性语句又可分句又可分为赋值语句、控制句、控制语句和句和输入入/输出出语句句n从形式上从形式上说，语句可分句可分为简单句句、复合句复合句和和分程序分程序等。等。第三十二页，讲稿共九十五页哦33赋值语句A:=Bn意意义是：是：“把把B的的值送入送入A所代表的所代表的单元元”在在赋值句中，句中，赋值号号：=左右两左右两边的的变量名扮演着两种不同的角色。量名扮演着两种不同的角色。对赋值号右号右边的的B我

21、我们需要的是它的需要的是它的值；对于左于左边的的A我我们需要的是它需要的是它们的所代表的存的所代表的存储单元（的地址）。元（的地址）。n为了区分一个名字的了区分一个名字的这两种特征，我两种特征，我们把一个名字所代表的那把一个名字所代表的那个存个存储单元（地址）称元（地址）称为该名字的名字的左左值；把一个名字的；把一个名字的值称称为该名字的名字的右右值。第三十三页，讲稿共九十五页哦34控制语句n多数多数语言中所含的控制言中所含的控制语句有：句有：无条件无条件转移移语句句:gotoL条件条件语句：句：ifBthenSifBthenS1elseS2循循环语句：句：whileBdoSrepeatSun

22、tilBfori:=E1stepE2untilE3doS过程程调用用语句：句：callP(X1,X2,Xn)返回返回语句：句：return(E)第三十四页，讲稿共九十五页哦35说明语句n说明明语句旨在定句旨在定义名字的性名字的性质。n编译程序把程序把这些性些性质登登记在符号表中，并在符号表中，并检查程序中名程序中名字的引用和字的引用和说明是否相一致。明是否相一致。第三十五页，讲稿共九十五页哦36内容线索程序程序设计语言的定言的定义高高级语言的一般特性言的一般特性程序程序语言的言的语法描述法描述第三十六页，讲稿共九十五页哦37概述n对于高于高级程序程序语言及言及编译程序而言，程序而言，语言的言的

23、语法定法定义是是非常重要的。本非常重要的。本节将介将介绍语法法结构的形式描述构的形式描述问题。编译原理编译原理=形式语言理论形式语言理论+编译技术编译技术第三十七页，讲稿共九十五页哦38形式语言n自然自然语语言言人人们们平平时说话时时说话时所使用的一种所使用的一种语语言，不同的国家和民族有着不同的言，不同的国家和民族有着不同的语语言。言。n形式形式语语言言通通过过人人们们公公认认的符号、表达方式所描述的一种的符号、表达方式所描述的一种语语言，是一种通用言，是一种通用语语言，言，没有国籍之分。没有国籍之分。形式形式语语言是某个言是某个字母表上的字符串的集合字母表上的字符串的集合，有一定的描述范，

24、有一定的描述范围围。第三十八页，讲稿共九十五页哦39为什么用形式语言n形式形式语语言的最初起因：言的最初起因：语语言学家言学家乔乔姆斯基（姆斯基（Chomsky）想用一套形式化方法）想用一套形式化方法来描述来描述语语言。言。n形式形式语语言在自然言在自然语语言研究中起步，在言研究中起步，在计计算机科学中得到广泛算机科学中得到广泛应应用。用。最初的最初的应应用：用：编译编译现现在已广泛在已广泛应应用在人工智能、用在人工智能、图图象象处处理、通信理、通信协议协议、通信、通信软软件等多个件等多个领领域域在在计计算机理算机理论论科学方面：科学方面：n是可是可计计算理算理论论（算法（算法在有限步在有限步

25、骤骤内求得解、算法复内求得解、算法复杂杂性、停机性、停机问题问题、）、定理自、）、定理自动证动证明、明、程序程序转换转换（程序自（程序自动动生成）、模式生成）、模式识别识别等的基等的基础础。第三十九页，讲稿共九十五页哦40形式语言与自动机理论的发展n1956年，年，乔乔姆斯基（姆斯基（Chomsky）从）从产产生的角度研究生的角度研究语语言言文法文法n1951-1956年年间间，克林（，克林（Kleene）从）从识别识别的角度研究的角度研究语语言言自自动动机机n1959年，年，乔乔姆斯基不姆斯基不仅仅确定了文法和自确定了文法和自动动机分机分别别从生成和从生成和识别识别的的角度去表达角度去表达语

26、语言，而且言，而且证证明了文法与自明了文法与自动动机的等价性。机的等价性。形式语言真正诞生形式语言真正诞生第四十页，讲稿共九十五页哦41基本概念n字母表字母表：元素的非空有：元素的非空有穷集合。集合。例：例：a,b,c,z（拉丁字母表）（拉丁字母表）,(希腊字母表）希腊字母表）0,1（二（二进制数字字母表）制数字字母表）n符号符号：字母表中的元素。如：字母表中的元素。如a,b,第四十一页，讲稿共九十五页哦42基本概念n符号串符号串：字母表中的符号：字母表中的符号组成的任何有成的任何有穷序列。序列。例例.设字母表字母表=a,b,c其符号串有：其符号串有：a,b,c,ab,ac,aa,abc,符号

27、串与符号符号串与符号组成的成的顺序有关。序有关。n符号串的符号串的长度度：符号串中符号的数目：符号串中符号的数目,用用|x|表示表示n空符号串空符号串（空字）：不包含任何符号的符号串，（空字）：不包含任何符号的符号串，记为。第四十二页，讲稿共九十五页哦43子符号串n设有非空符号串有非空符号串u=xvy，则称称v为符号串符号串u的的子符号串子符号串。例例.符号串符号串x=a+b-(c+d)则a,a+b-,(c+d)等都是等都是x的子符号串，的子符号串，且其且其长度分度分别为：|a|=1,|a+b-|=4,|(c+d)|=5第四十三页，讲稿共九十五页哦44符号串的前缀与后缀n符号串的符号串的前前缀

28、与与后后缀符号串左部的任意子串，称符号串左部的任意子串，称为符号串的前符号串的前缀；符号串右部的任意子串，称符号串右部的任意子串，称为符号串的后符号串的后缀。例例.字母表字母表A=a,b,c上的符号串上的符号串x=ab,则x的的前前缀有：有：、a、ab；后后缀有：有：、b、ab。第四十四页，讲稿共九十五页哦45基本概念n符号串集合符号串集合：若集合中所有元素都是某字母表：若集合中所有元素都是某字母表 上的符上的符号串，号串，则称之称之为该字母表上的符号串集合。字母表上的符号串集合。用用*表示表示 上的所有符号串的全体，空字也包括在其中。上的所有符号串的全体，空字也包括在其中。例例.若若=a,b

29、则*=,a,b,aa,ab,bb,aaa,。表示不含任何元素的表示不含任何元素的空集空集n注意区分注意区分：、第四十五页，讲稿共九十五页哦46（连接）积n*的子集的子集U和和V中的（中的（连接）接）积定定义为:UV=U&V即集合即集合UV中的符号串是由中的符号串是由U和和V的符号串的符号串连接而成的。接而成的。例例.设U=a,b,V=，则UV=a,a,a,b,b,bn注意：一般注意：一般UV VU，但（，但（UV)W=U(VW).第四十六页，讲稿共九十五页哦47n次（连接）积nV自身的自身的n次次（连接）接）积记为：规定定V0=.令：令：V*=V0 V1 V2，称，称V*是是V的的闭包包。闭包

30、包V*中的每个符号都是由中的每个符号都是由V中的符号串中的符号串经有限次有限次连接而成的。接而成的。记V+=VV*,称称V+是是V的的正正则闭包包。Vn=VVVVn第四十七页，讲稿共九十五页哦48闭包n定理定理.若若A是符号串集合，是符号串集合，则A*=(A*)*。则x AM，因此推得，因此推得x A*，所以所以(A*)*A*，故故A*=(A*)*。证明明：显然然A*(A*)*,现证(A*)*A*任任给符号串符号串x(A*)*，则存在存在n，使得，使得x(A*)n，x必必存在存在n个子串个子串x1,xn，使得使得x=x1xn，且，且xi A*(i=1,n)。由由xi A*，必存在整数，必存在整

31、数pi,使得使得xi Api，令令 第四十八页，讲稿共九十五页哦49文法（Grammar）n所所谓谓文法文法是用来定是用来定义语义语言的一个数学模型。言的一个数学模型。n表示表示语语言的方法：言的方法：若若语语言言L是有限集合，可用列是有限集合，可用列举举法法若若L是无限集合（集合中的每个元素有限是无限集合（集合中的每个元素有限长长度），用其他方法。度），用其他方法。方法一：文法方法一：文法产产生系生系统统，由定，由定义义的文法的文法规则产规则产生出生出语语言的每个句子言的每个句子方法二：机器方法二：机器识别识别系系统统：当一个字符串能被一个：当一个字符串能被一个语语言的言的识别识别系系统统接

32、受，接受，则这则这个字符串是个字符串是该语该语言的一个句子，否言的一个句子，否则则不属于不属于该语该语言。言。第四十九页，讲稿共九十五页哦50Chomsky文法体系nChomsky文法体系中，任何一种文法必文法体系中，任何一种文法必须须包含包含两个不同的有限符号的集合两个不同的有限符号的集合n非非终结终结符集合符集合VNn终结终结符集合符集合VT一个起始符一个起始符S一个形式一个形式规则规则的有限集合的有限集合（产产生式集合）。生式集合）。n注意注意中的中的产产生式是用来生式是用来产产生生语语言句子的言句子的规则规则，而，而句子句子则则是是仅仅由由终结终结符符组组成的字符串。成的字符串。这这些

33、字符串必些字符串必须须从一个起始符从一个起始符S开始，不断使用中的开始，不断使用中的产产生式而生式而导导出来。出来。文法的核心是文法的核心是产产生式的集合，它决定了生式的集合，它决定了语语言中句子的言中句子的产产生。生。第五十页，讲稿共九十五页哦51文法的形式定义n文法文法G是一个四元是一个四元组组G=(VN,VT,S,)，其中，其中VN：非：非终结终结符的有限集合符的有限集合VT：终结终结符的有限集合，符的有限集合，VNVT=S：开始符号且：开始符号且S VN。：形式：形式为为P的的产产生式的有限集合，生式的有限集合，且且P(VN VT)*VN(VN VT)*，(VN VT)*第五十一页，讲

34、稿共九十五页哦52文法示例n文法文法G1=(N,0,1,N0N,N1N,N0,N1,N)其中：其中：VN=N，VT=0,1，S=N。=N0N,N1N,N0,N1，第五十二页，讲稿共九十五页哦53文法的解释（1）n非非终结符号符号：需要：需要进一步定一步定义的符号，不会出的符号，不会出现在程序中。在程序中。用来代表用来代表语法范畴。如法范畴。如“算算术表达式表达式”、“布布尔表达式表达式”、“过程程”等。等。一个非一个非终结符代表一个一定的符代表一个一定的语法概念，因此非法概念，因此非终结符是一个符是一个类（或集（或集合）合）记号，而不是个体号，而不是个体记号。号。n终结符号符号：不需要再定：不

35、需要再定义，会出，会出现在程序中。在程序中。组成成语言的基本符号，即在程序言的基本符号，即在程序语言中的言中的单词符号，如符号，如标识符，常数，算符符，常数，算符和界符等和界符等n开始符号开始符号S至少必至少必须在某个在某个产生式的左部出生式的左部出现一次一次.第五十三页，讲稿共九十五页哦54文法的解释（1）n产产生式生式（规则规则）：定）：定义语义语法法单单位的一种位的一种书书写写规则规则它的形式它的形式为为：P（或（或P:=）其中其中“”读读作作“定定义为义为”，P，为为符号串，箭符号串，箭头头左左边边称称为产为产生式左部，生式左部，箭箭头头右右边边称称为产为产生式右部。生式右部。例例：S

36、0S1，0S01若干个左部相同的若干个左部相同的产产生式如生式如P1,P2,P3,.,Pn可合并可合并成一个成一个,缩缩写写为为P1|2|3|.|n,其中其中,每个每个i称称为为是是P的一个的一个候候选选式式.第五十四页，讲稿共九十五页哦55习惯写法nVN:大写字母大写字母A、B、C、S等等nVT:小写字母，小写字母，09，+、等运算符，等运算符，n、:文法符号串文法符号串,(VT VN)*nS:开始符号，第一个开始符号，第一个产生式中出生式中出现n:定定义符号（推出）符号（推出）n|：或：或第五十五页，讲稿共九十五页哦56文法的约定n为了了简化，文法表示化，文法表示只写出只写出产生式部分生式

37、部分约定第一个定第一个产生式的左部符号生式的左部符号为初始符号初始符号或或在在产生式前写上生式前写上“GA”，其中，其中G为文法名，文法名，A为初始符号初始符号.例例.文法文法GN:N0N,N1N,N0,N1文法文法GE:EE+EE*E(E)i第五十六页，讲稿共九十五页哦57如何由文法产生语言的句子？n基本思想基本思想：从：从识别符号开始，把当前符号开始，把当前产生的符号生的符号串中的串中的非非终结符号符号替替换为相相应产生式右部的生式右部的符号符号串串，直到最，直到最终全由全由终结符号符号组成。成。这种替种替换过程程称称为推推导或或产生句子的生句子的过程，每一步称程，每一步称为直接直接推推导

38、或或直接直接产生生。第五十七页，讲稿共九十五页哦58直接推导与归约n直接推直接推导如果如果A是一个是一个产生式，而生式，而，（VT VN）*，则将将产生生式式A用于符号串用于符号串A 得到符号串得到符号串，记为A，称称A直接推出直接推出。n归约是推是推导的逆的逆过程程若存在若存在A，则称称能能够直接直接归约成成A。第五十八页，讲稿共九十五页哦59推导n推推导：设1,2,n(n0)(VT VN)*，且有，且有12n则称称这个序列是从个序列是从1到到n的一个推的一个推导。n若存在一个若存在一个1到到n的推的推导，则称称1可推可推导出出n。n1n(经一步或若干步推一步或若干步推导）n1n（经0步或若

39、干步推步或若干步推导）+*第五十九页，讲稿共九十五页哦60最左（右）推导（规约）n若在推若在推导关系中，每次最先替关系中，每次最先替换最左（右）最左（右）的非的非终结符，符，则称称为最左（右）推最左（右）推导；n若在若在归约过程中，每次最先程中，每次最先归约最左（右）最左（右）的非的非终结符，符，则称称为最左（右）最左（右）归约。第六十页，讲稿共九十五页哦61n例例.文法文法GS:SABAA0|1BB0|S1，请给出句子出句子101001的最左和最右推的最左和最右推导。最右推最右推导：SABAS1AAB1AA01A1B01A10011B1001101001最左推最左推导：SAB1BB10B10

40、S110AB1101BB11010B1101001第六十一页，讲稿共九十五页哦62句型、句子和语言n句型句型：假定：假定G是一个文法，是一个文法，E是它的开始符号，如果是它的开始符号，如果E，则称称是文法是文法G的一个句型。的一个句型。例例(E+E),(i+E),(i+i),E都是都是GE的句型。的句型。n句子句子：仅由由终结符符组成的句型称成的句型称为句子。句子。例例(ii+i),(i+i)都是都是GE的句子。的句子。n语言言：文法：文法G所所产生句子的全体，即：生句子的全体，即：L(G)=|S，VT*+第六十二页，讲稿共九十五页哦63例例.设有文法有文法G1S:SbA,AaA|a试求此文法

41、所描述的求此文法所描述的语言。言。解：因解：因为从开始符号从开始符号S出出发可推出下列句子：可推出下列句子：SbAbaSbAbaAbaaSbAbaAbaaAbaaaSbAbaAbaaa所以，所以，L(G1)=ban|n1第六十三页，讲稿共九十五页哦64例例.设文法文法G2S：SABAaA|aBbB|b该文法所描述的文法所描述的语言是言是什么？什么？解：从文法开始符号解：从文法开始符号S出出发，可推出下列句子：，可推出下列句子：S AB abS AB aAB aaB aabS AB aAB aaB aabB aabbB aabbbS AB aaabbbmn所以，所以，L(G2)=ambn|m,n

42、=1第六十四页，讲稿共九十五页哦65例例.试对如下如下语言言L(G3)=anbn|n=1构造文法构造文法G3。解：解：L(G3)由以下一些符号串由以下一些符号串x组成：成：n=1,x=abn=2,x=aabbn=3,x=aaabbbL(G3)=ab,aabb,aaabbb,由此可由此可见，集合，集合L（G3）有如）有如下特点：下特点：n每个符号串呈每个符号串呈对称形式，称形式，即即a,b成成对出出现；nL(G3)为无无穷集合，描述集合，描述它的它的规则中含中含递归定定义；n文法中文法中终结符只有符只有a,b。因此可用以下两条因此可用以下两条产生式定生式定义语言言L(G3)SaSb|ab即：即：

43、G3=（S，a,b，SaSb|ab，S)第六十五页，讲稿共九十五页哦66例例.文法文法G：0|1|2|3|4|5|6|7|8|9语言言L(G)为非非负整数。整数。非负整数的另一定义：非负整数的另一定义：0|1|2|3|4|5|6|7|8|9123456789思考其他定义思考其他定义形式形式第六十六页，讲稿共九十五页哦67例例.写一文法写一文法G3，使其描述的，使其描述的语言言为正奇数集合。正奇数集合。令令G3=VN,VT,P,，其中，其中，VT=0,1,2,3,4,5,6,7,8,9，VN=,S：P：1357902468思考思考：如果要求开：如果要求开头元素非零，如何改造？元素非零，如何改造？

44、第六十七页，讲稿共九十五页哦681234567891357902468或者：或者：S,A,E,B,C,D.SABABBCDC0EADEAE2468A13579第六十八页，讲稿共九十五页哦69同一句型有不同的推导序列n设有文法有文法GN1:N1NNND|DD0|1|2则句子句子12可由若干种不同的推可由若干种不同的推导序列推序列推导出来：出来：(1)N1NNDN2D212(2)N1NNDDD1D12n可可见，同一句型（句子）可以通，同一句型（句子）可以通过不同的推不同的推导序序列推列推导出来。出来。第六十九页，讲稿共九十五页哦70Chomsky文法体系分类n文法文法G=(VN,VT,S,)，：P

45、，其中，其中P(VN VT)*VN(VN VT)*，(VN VT)*属于属于Chomsky文法体系文法体系n该该体系体系对产对产生式的形式做了一些生式的形式做了一些规规定，分定，分为为四四类类，即，即0型、型、1型、型、2型、型、3型文法型文法第七十页，讲稿共九十五页哦713型文法n也称正也称正规规文法文法右右线线性文法（性文法（Right-linearGrammar）：）：AB或或A，其中，其中A、B VN,VT*。左左线线性文法（性文法（Left-linearGrammar）：）：AB或或A，其中，其中A、B VN,VT*。对应对应的的语语言：正言：正规语规语言言对应对应的自的自动动机：有

46、限自机：有限自动动机（机（FiniteAutomaton）。）。n例例.文法文法SaS，Sa对应对应正正规规式：式：a+，或者，或者a*a第七十一页，讲稿共九十五页哦722型文法n也称上下文无关文法（也称上下文无关文法（CFG：Context-freeGrammar)n产产生式的形式生式的形式为为P,其中其中P VN，且，且(VN VT)*对应对应的的语语言：上下文无关言：上下文无关语语言言（CFL：Context-freeLanguage)对应对应的自的自动动机：下推自机：下推自动动机（机（PDA：PushdownAutomaton)。第七十二页，讲稿共九十五页哦732型文法示例n例例.上下

47、文无关文法上下文无关文法 S01S0S1产产生的生的语语言是言是L=0n1n n 1，如如0011,000111,01 L,而而10,1001,010 L.但没有任何有限自但没有任何有限自动动机能机能够够接受接受语语言言L.第七十三页，讲稿共九十五页哦741型文法n也称上下文有关文法（也称上下文有关文法（CSG：Context-sensitiveGrammar)n产产生式的形式生式的形式为为P,其中其中|P|，(VN VT)*，P(VN VT)*VN(VN VT)*对应对应的的语语言：上下文有关言：上下文有关语语言（言（CSL：Context-sensitiveLanguage)若不考若不考虑

48、虑，与，与线线性有界自性有界自动动机（机（LBA,LinearBoundedAutomaton）等价。等价。第七十四页，讲稿共九十五页哦751型文法示例n例例.下列文法是下列文法是1型文法型文法SaBC|aSBCCBBCaBabbBbbbCbccCcc第七十五页，讲稿共九十五页哦760型文法n0型文法：无限制文法，短型文法：无限制文法，短语语文法文法对应对应的的语语言：言：递归递归可枚可枚举语举语言言与与图图灵机等价。灵机等价。n例例.下列文法是下列文法是0型文法型文法SaBC|aSBCCBBCaBabbBbbbBbbCbccCcccCc第七十六页，讲稿共九十五页哦77Chomsky文法体系3

49、012第七十七页，讲稿共九十五页哦78文法、形式语言和自动机的对应关系递归可枚举递归可枚举语言语言图灵机图灵机0型文法型文法上下文有上下文有关语言关语言线性有界自线性有界自动机动机1型文法型文法上下文无关上下文无关语言语言下推自动机下推自动机2型文法型文法正规语言正规语言有限自动有限自动机机3型文法型文法第七十八页，讲稿共九十五页哦79总结（1）n自然自然语言是上下文有关的。言是上下文有关的。n但是上下文无关文法有足但是上下文无关文法有足够的能力描述的能力描述现今多数程今多数程序序设计语言的言的语法法结构构算算术表达式表达式语句句n赋值语句句n条件条件语句句n读语句句第七十九页，讲稿共九十五页

50、哦80上下文无关文法描述语言语法结构n算算术表达式表达式的上下文无关文法表示的上下文无关文法表示文法文法G=(E,+,*,i,(,),P,EP:EiEE+EEE*EE(E)n条件条件语句的上下文无关文法表示句的上下文无关文法表示ifthen|ifthenelse第八十页，讲稿共九十五页哦81总结（2）n基于基于正正规文法文法讨论词法分析法分析问题，n基于基于上下文无关文法上下文无关文法讨论语法分析法分析问题。n所以，所以，现在都用上下文无关文法和正在都用上下文无关文法和正则文法文法描述描述语言言语法，而其中上下文有关的法，而其中上下文有关的问题，可通可通过表格表格处理解决。理解决。第八十一页，