第2章形式语言概论课件

资源描述

《第2章形式语言概论课件》由会员分享，可在线阅读，更多相关《第2章形式语言概论课件（167页珍藏版）》请在金锄头文库上搜索。

1、第第2章章形式语言概论形式语言概论形式语言理论是编译的重要理论基础。本章主要介绍编译理论中用到的有关形式语言理论的最基本概念最基本概念，重点介绍如何采用形式化的方法描述程序设计语言。第第2章章形式语言概论形式语言概论q字母表和符号串字母表和符号串q文法和语言的形式定义文法和语言的形式定义q短语、直接短语和句柄短语、直接短语和句柄q语法树和文法的二义性语法树和文法的二义性q文法和语言的分类文法和语言的分类概概述述对程序设计语言的描述是从语法、语义和语用三个因素来考虑。语法是对语言结构的定义。语用则是从使用的角度去描述语言。语义是描述了语言的含义。概概述述例如例如赋值语句赋值语句s

2、 s2*3.1416*r*(r+h)2*3.1416*r*(r+h)的的非形式化的描述为：非形式化的描述为：语法：赋值语句由一个变量，后随一个赋值号“”，再在其后面跟一个表达式构成。语义：首先计算语句右部表达式的值，然后把所得结果送给左部变量中。语用：赋值语句可用来计算和保存表达式的值。概述这种非形式化的描述,不够清晰和准确,为了精确定义和描述程序设计语言,需采用形式化的方法。所谓形式化的方法,是用一整套带有严格规定的符号体系来描述问题的方法。形式语言理论是编译的重要理论基础。重点介绍如何采用形式化的方法描述程序设计语言。字母表和符号串元素的非空有穷集合。例如，=a,b,c1.字母表

3、根据字母表的定义，是字母表，它由a、b、c三个元素组成。字母表和符号串是一个字母表，由0、1两个元素组成。注意:例如，=0,1(2)字母表中的元素,可以是字母、数字或其他符号。(1)字母表中至少包含一个元素。字母表和符号串字母表中的元素称为符号或称为字符。例如，前述例子中2.符号（字符）a、b、c是字母表中的符号；0、1是字母表中的符号。字母表和符号串例如，设有字母表=a,b,c符号的有穷序列称为符号串。符号串总是建立在某个特定字母表上的且只由字母表上的有穷多个符号组成。则有符号串a，b，ab，ba，cba，abc3.符号串（字）字母表和符号串说明说明: :不包含任何符号的符号串, 称为空符

4、号串，用表示。符号串中符号的顺序是很重要的。ab和ba是字母表上的两个不同的符号串。空符号串由0个符号组成，其长度| |=0|=0符号串的运算符号串的运算设x和y是符号串，则串xy称为它们的连结。则XYABC10A，YX10AABC。注意：对任意一个符号串x，1. 符号串的连结符号串的连结例如，设XABC，Y10A我们有xxx。符号串的运算符号串的运算2. 集合的乘积集合的乘积设A和B是符号串的集合,则A和B的乘积定义为：集合的乘积是满足于xA,yB的所有符号串xy所构成的集合。AB=xy|xA,yBA=A=A符号串的运算符号串的运算例如：设A=a,b,B=c,d则AB=ac,ad,bc,bd

5、由于对任意的符号串x，总有x=x=x所以,对任意集合A,我们有:符号串的运算符号串的运算特别指出的是，是符号串,不是集合，而表示由空符号串所组成的集合,但这样的集合不是空集合=。符号串的运算符号串的运算 3. 符号串的幂运算符号串的幂运算设x是符号串,则x的幂运算定义为：x0=x1=xx2=xxx3=xxxxn=xxx=xxn-1(n0) n注意：x01符号串的运算符号串的运算例如,设xabc则x0=x1=abcx2=xx=abcabc符号串的运算符号串的运算 4. 集合的幂运算集合的幂运算设A是符号串的集合，则集合A的幂运算定义为：A0=A1=AA2=AAAn=AAA=AAn-1(n0)n符

6、号串的运算符号串的运算例如，设A=a,b，则A0=A1=A=a,bA2=AA=aa,ab,ba,bbA3=AAA=A2A=aaa,aab,aba,abb,baa,bab,bba,bbb符号串的运算符号串的运算5. 集合集合A的正闭包的正闭包A与闭包与闭包A*设A是符号串的集合，则A的正闭包A和A的闭包A*的定义为:A+=A1A2AnA*=A0A1A2An=A+符号串的运算符号串的运算可见,集合A的正闭包表示A上元素a,b构成的所有符号串的集合,集合A的闭包比集合A的正闭包多含一个空符号串。例如，设A=a,b,则：A+=a,b,aa,ab,ba,bb,aaa,aab,A*=,a,b,aa,ab

7、,ba,bb,aaa,aab,文法和语言的形式定义文法和语言的形式定义每个形式语言都是某个字母表上按某种规则构成的所有符号串的集合。反之，任何一个字母表上符号串的集合均可定义为一个形式语言。形式语言形式语言序列的集合称为形式语言。文法和语言的形式定义文法和语言的形式定义对每个具体语言,都有语法和语义两个方面，形式语言是指不考虑语言的具体意义，即不考虑语义。文法和语言的形式定义文法和语言的形式定义形式语言的描述形式语言的描述对形式语言的描述有两种方法，一种方法是当语言为有穷集合时，用枚举法来表示语言。文法和语言的形式定义文法和语言的形式定义均表示字母表A上的一个形式语言。由于这三个语言均是

8、有限符号串的集合，因此，可枚举出其全部句子来表示该语言。例如，设有字母表A=a,b,c，则L1=a,b,cL2=a,aa,ab,acL3=c,cc文法和语言的形式定义文法和语言的形式定义例如，设字母表=0,1,则+=123=0,1,00,10,11,01,000,100,当语言为无穷集合时，用文法来描述语言。文法和语言的形式定义文法和语言的形式定义下面用A表示+，用式子A0表示符号串0A或A生成符号串0，符号“”读作“生成”或“由组成”。则集合A可表示成：A0A1AA0AA1+=123=0,1,00,10,11,01,000,100,文法的形式定义文法的形式定义规则是一个符号与一个符号串的

9、有序对（A,），通常写作： A（或A)1.1. 规则规则也称产生式也称产生式规则的作用是告诉我们如何用规则中的符号串生成语言中的序列。文法的形式定义文法的形式定义例如，前述例中一组规则描述的语言序列只可能是由0和1组成的符号串。A0A1AA0AA1文法的形式定义文法的形式定义规则中出现的符号分为两类，一类是终结符号，另一类是非终结符号。非终结符号是出现在规则左部能派生出符号或符号串的那些符号，即每个非终结符号表示一定符号串的集合，用大写字母表示或用尖括号把非终结符号括起来。例如，上例中的A。文法的形式定义文法的形式定义终结符号是不属于非终结符号的那些符号,它是组成语言的基本符号，是

10、一个语言的不可再分的基本符号，通常用小写字母表示。例如，上例中的0和1。文法的形式定义文法的形式定义规则的非空有穷集合，通常表示成四元组VN是规则中非终结符号的集合。VT是规则中终结符号的集合。P是文法规则的集合。 2. 文法文法G=VN,VT,P,S文法的形式定义文法的形式定义 S 是一个非终结符号，称为文法的开始符号或文法的识别符号，它至少要在一条规则中作为左部出现。由它开始，识别出我们所定义的语言。由文法定义可知，文法是对语言结构的定义和描述，文法四大要素中关键是规则的集合。文法的形式定义文法的形式定义将它们缩写为：A1|2|nA1A2An其中每个i有时也称为是A的一个候选式。为

11、了书写方便，对于若干个左部相同的规则，如文法的形式定义文法的形式定义我们约定：第一条规则的左部是识别符号。对文法G不用四元式显示表示，仅只将规则写出。文法的形式定义文法的形式定义G=(VN，VT，P，S)VN=AVT=0，1P:A0|1|A0|A1S=A前例中描述+的文法是:文法的形式定义文法的形式定义例1设字母表=a,b，试设计一个文法，描述语言L=a2n,b2n|n1分析设计一个文法来描述一个语言, 关键是设计一组规则生成语言中的符号串。因此，为设计该语言文法，必须分析这个语言是由怎样一些符号串组成的，即首先分析语言中串的结构特征：文法的形式定义文法的形式定义当n1L=aa,bb

13、和G是两个不同的文法，如果它们描述的语言相同，那么，称G和G为等价文法。文法的形式定义文法的形式定义描述该语言的文法是否G？文法的形式定义文法的形式定义对此例，我们提出下面这样一个问题：G=(A,a,b,P,A)P=Aaa|bb|Aaa|Abb对于文法G来说，它所产生的有些符号串，如aabb，bbaa，不属于语言L，即设计的文法超出了所定义语言的范围。文法的形式定义文法的形式定义P=Aaa|bb|Aaa|Abb文法的形式定义文法的形式定义例2试设计一个表示所有标识符的文法分析题意是用文法定义标识符，必须确定P中规则。为了设计出一组规则，首先应搞清楚集合中串的结首先应搞清楚集合中串的结构特征

14、构特征。文法的形式定义文法的形式定义用I代表标识符；L代表字母；D代表数字;则定义标识符的文法为：字母字母或数字串标识符的结构可用下图表示:文法的形式定义文法的形式定义G=(VN，VT，P，S)其中： VN=I,L,DVT=a,b,c,x,y,z,0,1,2, ,9P=ILS=ILa|b|c|x|y|zD0|1|2|3|9|IL|ID文法的形式定义文法的形式定义若将定义标识符的文法设计成：其中VN，VT，S同上 G=(VN，VT，P，S)P=IL|IDLa|b|c|x|y|zD0|1|2|3| |9 文法的形式定义文法的形式定义该文法不能定义ab，abc仅由字母串组成的标识符，缩小了所定

15、义语言的范围。P=IL|IDLa|b|c|x|y|zD0|1|2|3| |9 文法的形式定义文法的形式定义用I代表标识符；L代表字母；D代表数字；T代表字母数字串；则定义标识符的文法还可写为：字母字母或数字串文法的形式定义文法的形式定义P:IL|LTTL|D|LT|DTLa|b|c|x|y|zD0|1|2|3| |9字母字母或数字串文法的形式定义文法的形式定义例3用文法定义一个含、*的算术表达式，定义用下述自然语言描述：变量是一个表达式；若E1和E2是算术表达式,则E1E2、E1*E2、(E1)也是算术表达式。文法的形式定义文法的形式定义分析算术表达式的定义用自然语言描述，这是对算术表达式的非

16、形式定义，题意用文法来定义算术表达式，即是用形式化的方法定义表达式。定义算术表达式的文法为：G=(E,i,+,*,(,),P,E)其中P为：Ei|E+E|E*E|(E)文法的形式定义文法的形式定义P为：Ei|E+E|E*E|(E)i,i+i,i*i,i+i*i,(i+i),注意：是符号串的集合文法的形式定义文法的形式定义例4设字母表=a,b,试设计一个文法，描述语言L=abna|n0分析该语言中串的结构特征是当n1L=abaL=aa,aba,abba,当n2L=abba当n0L=aa(b0=)文法的形式定义文法的形式定义所以定义语言的文法为： G=(A,B,a,b,P,A)P=AaBaBB

17、b|L=aa,aba,abba,文法的形式定义文法的形式定义例5设字母表=(,),试设计一个文法描述语言L=(n)n|n0分析该语言中串的结构特征是当n=0L=注:(0)0=当n=1L=()当n=2L=()L=,(),(),(), 文法的形式定义文法的形式定义P:S|(S)所以定义语言的文法为： L=(n)n|n0语言的形式定义语言的形式定义 1.直接推导令G是一文法，我们称xAy直接推导出xy，即xAyxy仅A是G的一条规则,且x,y(VNVT)*。也就是说从符号串xAy直接推导出xy仅使用一次规则。语言的形式定义语言的形式定义例如，设有文法GS: S01使用规则S01 此时 x，yP

18、为：S01|0S1有如下直接推导：S0S1使用规则S0S1此时x，y语言的形式定义语言的形式定义0S10011使用规则S01此时x0，y100S11000S111使用规则S0S1此时x00,y11000S11100001111使用规则S01此时x000y111S01|0S1语言的形式定义语言的形式定义 (1)形式上的区别，推导用“”表示，规则用“”表示。(2)对文法G中任何规则A，我们有A，即推导的依据是规则。注意推导和规则的区别：即表示从0出发，经一步或若干步或者说使用若干次规则可推导出n。语言的形式定义语言的形式定义如果存在一个直接推导序列：则我们称这个序列是一个从0至n的长度为n的推导

19、，记为2推导012 n+0n语言的形式定义语言的形式定义例如设有文法GE=(E,T,F,i,+,*,(,),P,E)对 i+i*i有如下直接推导序列: 我们可记为其中P为：EE+T|TTT*F|FF(E)|iEE+TT+TF+Ti+Ti+T*Fi+F*Fi+i*Fi+i*iEi+i*i+语言的形式定义语言的形式定义 3广义推导我们有：0n表示从0出发，经0步或若干步，可推导出n。*也就是说0n意味着0n或者0=n。*+EE*Ei+i*i*对上例EE+T|TTT*F|FF(E)|i语言的形式定义语言的形式定义区别：直接推导的长度为1，推导的长度大于等于1，而广义推导的长度大于等于0。语言

20、的形式定义语言的形式定义 4.句型和句子设有文法GS（S是文法G的开始符号）如果Sx, x (VNVT)*则称符号串x 为文法GS的句型。*如果Sx, x VT*则称符号串x为文法GS的句子。*语言的形式定义语言的形式定义例1设有文法GS：我们有:显然，符号串01、0S1、00S11和000111都是文法GS的句型，而01和000111又是文法GS的句子。S01|0S1S01*S0S1*S00S11*S000111*语言的形式定义语言的形式定义例2设有文法GE：试证明符号串(i*i+i)是文法GE的一个句子。分析只要证明符号串(i*i+i)对文法G存在一个推导，就可证明符号串(i*i+i)

21、是文法GE的一个句子。EE+E|E*E|(E)|i语言的形式定义语言的形式定义 EE+E|E*E|(E)|iE(E)(E+E)(E*E+E)(i*E+E)(i*i+E) (i*i+i)即有E(i*i+i),所以符号串(i+i*i)是文法GE的一个句子。*（2）L(G)是VT*的子集。即属于VT*的符号串x不一定属于L(G)。语言的形式定义语言的形式定义 5语言文法GS产生的所有句子的集合称为文法G所定义的语言,记为L(GS)：由语言定义可知：（1）一当文法给定，语言也就确定。L(GS)=x|Sx且xVT*语言的形式定义语言的形式定义例3设有文法GS：S01|0S1求该文法所描述的语言是什么？

22、分析由识别符号S出发，将推出一些什么样的句子，也就是说，L(GS)将由什么样的一些符号串所组成的集合，找出其中的规律，用式子或自然语言描述出来。语言的形式定义语言的形式定义我们应用第二个规则n1次，然后再应用第一个规则1次，有：S0S100S110n-1S1n-10n1n即S0n1n*可见，此文法定义的语言为L(GS)=0n1n|n1S01|0S1语言的形式定义语言的形式定义例4设有文法GS：S0S|1S|该文法所定义的语言是什么？由该文法所确定的语言为L(GS)=,0,1,00,01,10,11,=x|x0,1*语言的形式定义语言的形式定义例5设有文法GA：该文法所定义的语言是什么？分

23、析从文法开始符号A出发可推导出以y开头后面跟一个或多个x结尾的符号串，所以该文法定义的语言为AyBBxB|xL(GA)=yxn|n1语言的形式定义语言的形式定义由此可见，从已知文法确定语言的中心思想是：从文法的开始符号出发，反复连续地使用规则替换、展开非终结符，找出句子的规律，用式子或自然语言描述出来。语言的形式定义语言的形式定义形式语言理论可以证明如下两点：(1)给定一种语言，能确定其文法，但这种文法不是唯一的，即：LG1或G2或(2)给定一个文法，就能从结构上唯一确定其语言，即：GL(G)；规范推导和规范归约规范推导和规范归约文法和语言是密切相关的，文法所定义的任一句型和句子,都可以根

24、据文法推导出来。我们提出一个问题：这种推导过程是否唯一？这种推导过程是否唯一？规范推导和规范归约规范推导和规范归约同一个句型(句子)可以通过不同的推导序列推导出来，这是因为在推导过程中与所选择非终结符的次序无关。规范推导和规范归约规范推导和规范归约例如，设有文法GN1N1NNND|DD0|1|2 N1NNDN2D212 N1NNDDD1D12 N1NNDDDD212句子12有下列三种不同的推导序列:规范推导和规范归约规范推导和规范归约最左(最右)推导，是指对于一个推导序列中的每一步直接推导,都是对中的最左(最右)非终结符进行替换。最右推导也称为规范推导，用规范推导推导出的句型称为规范句型。规范

25、推导和规范归约规范推导和规范归约例设有文法GS:请给出句子101001的最右、最左推导。分析最右推导是指在推导过程中任何一步(和是句型)，都是对中的最右非终结符进行替换。SABAA0|1BB0|S1规范推导和规范归约规范推导和规范归约SABAS1AAB1AA01A1B01A10011B1001101001句子101001的最右推导为:SABAA0|1BB0|S1规范推导和规范归约规范推导和规范归约最左推导是指在推导过程中任何一步(和是句型),都是对的最左非终结符进行替换。句子101001的最左推导为：SABAA0|1BB0|S1SAB1BB10B10S110AB1101BB11010B1101

26、001规范推导和规范归约规范推导和规范归约归约是与推导相对的概念，推导是把句型中的非终结符用规则的一个右部来替换的过程，而归约则是把句型中的某个子串用一个非终结符来替换的过程。若用表示归约，设A是文法G中的一个规则，则我们有：.xAyxyxyxAy.规范推导和规范归约规范推导和规范归约例如，例文法GN1中有规范推导：则有规范归约：规范推导的逆过程，称为最左归约，也称为规范归约。N1NNDN2D21212D2.N2.ND.N.N1.递归规则与文法的递归性递归规则与文法的递归性递归规则如果文法中有规则AA称为规则左递归。如果文法中有规则AA称为规则右递归。如果文法中有规则AA称为规则递归。递归规则

27、与文法的递归性递归规则与文法的递归性文法的递归性若文法中有推导AA称文法左递归。+若文法中有推导AA称文法右递归。+若文法中有推导AA称文法递归。+递归规则与文法的递归性递归规则与文法的递归性例如文法中有如下规则：这三条规则都不是递归规则，但有在文法中使用递归规则，使得我们能用有限的规则去定义无穷集合的语言。 UVxVUy|zUVxUyx, 则该文法是左递归的。递归规则与文法的递归性递归规则与文法的递归性例2考虑文法GA：由于该文法无递归性，由它所描述的语言是有穷的。该文法描述的语言为:AaB|bBBa|bL(GA)=aa,ab,ba,bb递归规则与文法的递归性递归规则与文法的递归性例3

28、考虑文法GN1该文法有直接左递归规则NND,则称该文法为左递归文法或说文法左递归，其定义的语言为0,1,2+。N1NNND|DD0|1|2递归规则与文法的递归性递归规则与文法的递归性也就是说，当一个语言是无穷集合时，则定义该语言的文法一定是递归的。若不用递归规则，则NND需要用ND|DD|DDD|即无穷多条规则来定义由数字0,1,2组成的所有无符号整数。短语、直接短语和句柄短语、直接短语和句柄短语短语令G是一个文法，S是文法的开始符号，假定是文法G的一个句型，如果有则称是相对于非终结符A的句型的短语。SA*+且A短语、直接短语和句柄短语、直接短语和句柄则称是直接短语。直接短语直接短语SA*

29、且A令G是一个文法，S是文法的开始符号，假定是文法G的一个句型，如果有短语、直接短语和句柄短语、直接短语和句柄注意：短语和直接短语的区别在于第二个条件,直接短语中的第二个条件表示有文法规则A，因此，每个直接短语都是某规则右部。短语、直接短语和句柄短语、直接短语和句柄句柄句柄一个句型的最左直接短语称为该句型的句柄。句柄特征：(1)它是直接短语，即某规则右部。(2)它具有最左性。短语、直接短语和句柄短语、直接短语和句柄注意:短语、直接短语和句柄都是针对某一句型的，都是指句型中的哪些符号串能构成短语和直接短语，离开具体的句型来谈短语、直接短语和句柄是无意义的。短语、直接短语和句柄短语、直接短语和句柄

30、例如设有文法GS=(S,A,B,a,b,P,S)其中P为：求句型baSb的全部短语、直接短语和句柄。SABAAa|bBBa|Sb短语、直接短语和句柄短语、直接短语和句柄对文法，首先建立该句型的推导过程：最左推导:最右推导:SABAAa|bBBa|SbSABASbbBSbbaSbSABbaBbaSbbBB分析根据短语定义，可以从句型的推导过程中找出其全部短语、直接短语和句柄。句型baSb短语、直接短语和句柄短语、直接短语和句柄句型baSb中的子串Sb，是(相对于非终结符B)句型baSb的短语，且为直接短语。SABbBBbaBbaSb(2)SbaB*BSb(1)SS*SbaSb+句型本身是(相对于

31、非终结符S)句型baSb的短语。根据最左推导:SA*+A短语、直接短语和句柄短语、直接短语和句柄句型baSb中的子串a，是(相对于非终结符B)句型baSb的短语，且为直接短语、句柄。句型baSb中的子串ba，是(相对于非终结符A)句型baSb的短语。Ba(3)SbBSb*根据最右推导:SAB ASb bBSbbaSb(4)SASb*Aba+SA*+A语法树与文法的二义性语法树与文法的二义性推导和语法树推导和语法树1.语法树语法树对句型的推导过程给出一种图形表示,这种表示称为语法树，也称推导树。推导和语法树推导和语法树例如设有文法GE:构造句型i*i+i的语法树。首先给出句型的推导过程(最左推

32、导)：EE+T|ET|TTT*F|T/F|FF(E)|iEE+TT+TT*F+TF*F+Ti*F+Ti*i+Ti*i+Fi*i+i推导和语法树推导和语法树根据推导过程构造句型i*i+i的语法树如下：EE+TEE+TT+TTT*F+TT*FF*F+TFi*F+Tii*i+Tii*i+FFi*i+ii推导和语法树推导和语法树由例可知，语法树的构造过程是从文法的开始符号出发，构造一个推导的过程。因为文法的每一个句型(句子)都存在一个推导，所以文法的每个句型(句子)都存在一棵对应的语法树。EE+TE+FE+iT+iT*F+iT*i+iF*i+ii*i+i推导和语法树推导和语法树对句型i*i+i，还

33、可给出最右推导：EE+TTT*FFiiFi推导和语法树推导和语法树这也就是说，一棵语法树表示了一个句型的种种可能的(但未必是所有的)不同推导过程,包括最左(最右)推导。推导和语法树推导和语法树 2.子树语法树的子树是由某一结点连同所有分枝组成的部分。EE+TTT*FFiiFi推导和语法树推导和语法树 3.简单子树语法树的简单子树是指只有单层分枝的子树。EE+TTT*FFiiFi推导和语法树推导和语法树句型的短语、直接短语和句柄的直观解释是：短语：子树的末端结点形成的符号串是相对于子树根的短语。直接短语：简单子树的末端结点形成的符号串是相对于简单子树根的直接短语。句柄：最左简单子树的末端结点

34、形成的符号串是句柄。推导和语法树推导和语法树EE+TTT*FFiiFi短语:ni*i+ini*in第一个in第二个in第三个in三个i都是直接短语n第一个i是句柄注意:i+i不是句型的短语句子i*i+i推导和语法树推导和语法树前例对文法GS=(S,A,B,a,b,P,S)其中P为：可用语法树非常直观地求出句型baSb的全部短语，直接短语和句柄。SABAAa|bBBa|Sb推导和语法树推导和语法树分析首先根据句型baSb的推导过程画出对应的语法树如下：Sb为句型的相对于B的短语、直接短语baSb为句型的相对于S的短语ba为句型的相对于A的短语a句型的相对于B的短语、直接短语和句柄SABbB

35、BbaBbaSbSABASbbBSbbaSbSABbB Sba由语法树可知文法的二义性文法的二义性从前面的讨论可以看出，对于文法G中任一句型的推导序列,我们总能为它构造一棵语法树，现在我们提出一个问题：文法的某个句型是否只对应唯一的一棵语法树呢？也就是，它是否只有唯一的一个最左(最右)推导呢？文法的二义性文法的二义性例如设有文法GE：句子i*i+i有两个不同的最左推导，对应两棵不同的语法树。EE+E|E*E|(E)|i文法的二义性文法的二义性最左推导1EE+EE*E+Ei*E+Ei*i+Ei*i+i最左推导2EE*Ei*Ei*E+Ei*i+Ei*i+iEE*EE+EiiiEE+EE*E

36、iii文法的二义性文法的二义性如果一个文法存在某个句子对应两棵不同的语法树，则说这个文法是二义性的。或者说，若一个文法中存在某个句子，它有两个不同的最左(最右)推导，则这个文法是二义性的。EE+E|E*E|(E)|i文法二义性的消除文法二义性的消除 1.不改变文法中原有的语法规则,仅加进一些非形式的语法规定。EE+EE*Eiii文法二义性的消除文法二义性的消除2.构造一个等价的无二义性文法。即把排除二义性的规则合并到原有文法中, 改写原有的文法。例如，对于上例文法GE，将运算符的优先顺序和结合规则：*优先于;、* 左结合加到原有文法中,可构造出无二义性文法如下：文法二义性的消除文法二义性的

38、非形式的语法规3.定：else与前面最接近4.的不带else的if相对。SifbSbSSifAelseA文法G的句子ifbifbAelseA只对应唯一的一棵语法树，消除了二义。文法二义性的消除文法二义性的消除2.改写文法G为GSS1|S2S1ifbS1elseS1|AS2ifbS|ifbS1elseS2G:SifbS|ifbSelseS|A(其它语句）G:文法二义性的消除文法二义性的消除这是因为通过分析，得知引起二义性的原因是: ifelse 语句的 if 后可是if型，因此改写文法时规定:if else之间只能是ifelse语句或其他语句。文法二义性的消除文法二义性的消除SS1|S2S1if

39、bS1elseS1|AS2ifbS|ifbS1elseS2ifbSbifAelseASS2S1S1S1对改写后的文法，句子ifbifbAelseA只对应唯一的一棵语法树。通常我们只说文法的二义性,而不说语言的二义性,这是因为可能有两个不同的文法G和G，而且其中一个是二义性的，另一个是无二义性的,但却有L(G)=L(G),即这两个文法所产生的语言是相同的。文法二义性的消除文法二义性的消除应该指出的是文法的二义性和语言的二义性是两个不同的概念。文法二义性的消除文法二义性的消除将一个语言说成是二义性的，是指对它不存在无二义性的文法，这样的语言称为先天二义性的语言。例如L=aibjck|i=j或j

40、=k且i,j,k1便是这种语言。文法和语言的分类文法和语言的分类著名的语言学家乔姆斯基(Chomsky)将文法和语言分为四大类，即0型、1型、2型、3型。划分的依据是对文法中的规则施加不同的限制。文法和语言的分类文法和语言的分类 0型文法（无限制文法）若文法G=(VN,VT,P,S)中的每条规则是这样一种结构：而且中至少含一个非终结符,则称G是0型文法。(VNVT)+, (VNVT)*0型文法描述的语言是0型语言。0型文法没有加任何限制条件，又称为无限制性文法，相应的语言称为无限制性语言。0型语言由图灵机识别。文法和语言的分类文法和语言的分类例如，有0型文法G=(VN,VT,P,S)其中：

41、VN=A,B,S,VT=0,1其描述的0型语言为L0(GS)=P:S0AB1B0BSA|01A1SB1A0S0B文法和语言的分类文法和语言的分类 1型文法（上下文有关文法）1型文法也称为上下文有关文法，相应的语言又称为上下文有关语言。若文法G=(VN,VT,P,S)中的每一条规则的形式为A,其中：,(VNVT)*,AVN,则称G是1型文法。1型文法描述的语言是1型语言。1型语言由线性界限自动机识别。(VNVT)+文法和语言的分类文法和语言的分类例如，有1型文法G=(VN,VT,P,S)其中：VN=S,A,B,VT=a,b,cP:SaSAB|abBBABABAAAAAABbAbbbBbccBc

43、S|bAABb|bS|aBB文法和语言的分类文法和语言的分类文法和语言的分类文法和语言的分类 3型文法（正规文法）右线性文法和左线性文法都称为3型文法。若文法G=(VN,VT,P,S)中的每一条规则的形式为AaB或Aa,其中：A,BVN,aVT*,则称G是右线性文法。若文法G=(VN,VT,P,S)中的每一条规则的形式为ABa或Aa,其中：A,BVN,aVT*,则称G是左线性文法。3型文法描述的语言是3型语言。3型语言由有穷自动机识别。3型文法也称正规文法。正规文法产生的语言称为正规语言。例如，用左线性正规文法和右线性正规文法定义标识符文法和语言的分类文法和语言的分类用I代表标识符;l代表

45、是依次缩小的，有L0L1L2L3。有关文法的实用限制和变换有关文法的实用限制和变换文法是用来描述程序设计语言的，在实际应用中需要对文法加一些限制条件。1.文法中不能含有形如AA的规则。这种规则我们称之为有害规则。对文法的实用限制有以下两点：有关文法的实用限制和变换有关文法的实用限制和变换 2.文法中不能有多余规则。所谓多余规则是指文法中出现以下两种规则：(1)某条规则A的左部符号A不在所属文法的任何其他规则右部出现，即在推导文法的所有句子中始终都不可能用到的规则。(2)对文法中的某个非终结符A，无法从它推出任何终结符号串来。有关文法的实用限制和变换有关文法的实用限制和变换例如设有文法G

46、S:P:SBdAAd|dBCd|AeCCeDe删除多余规则后的文法变换为:P:SBdAAd|dBAe有关文法的实用限制和变换有关文法的实用限制和变换若程序设计语言的文法含有多余规则，其中必定有错误存在，因此检查文法中是否含有多余规则对我们来说是很重要的。本章重点介绍了语言的语法结构的形式描述、语法树以及文法的二义性,主要内容有：1.设计一个文法定义一个已知的语言(1)文法是一个四元组G=(VN,VT,P,S)，文法四大要素中，关键是一组规则,它定义（或描述）了一个语言的结构。从文法定义可知,文法对于程序设计者来说，文法给出了语言的精确定义和描述。本章小结本章小结本小结花时45分钟2004/2

47、/28(2)分析已知语言句子的结构特征,设计出相应的一组规则，但不唯一。(4)若语言是无穷集合,设计该语言的文法一定是递归的。本章小结本章小结(3)设计的文法必须能定义已知的语言,不能超出或缩小所定义语言的范围。分析根据语言句子的结构特征，设计出相应规则例1.给出语言L2=anbm|mn1的文法P2:SABL2=ab,abb,abbb,aabb,aabbb,aabbbb,aaabbb,aabbbb，AaAb|abBbB|本章小结本章小结分析根据语言句子的结构特征，设计出相应规则例2.给出语言L1=a2n+1|n0的文法P1:AaB|aP1：AaAa|a 或或L1=a,aaa,aaaaa,aaa

48、aaaa,aaaaaaaaa，Baa|aBa本章小结本章小结本章小结本章小结分析根据语言句子的结构特征，设计出相应规则例3.给出语言L3=anbmck|n,m,k0的文法P3:AaA|bB|cC|P3:AaA|B或或L3=,a,aa,aaa,b,bb,bbb,c,cc,ccc,ab,abb,bc,bcc，CcC|BbB|cC|CcC|BbB|C本章小结本章小结L4=0,2,4,6,8,10,12,14,16,18,20,22,24,26,例4.写一个文法,使其语言是正偶数的集合,每个偶数不以0开头。P4:NE|AEN0|2|4|6|8|BN或或分析不以0开头的偶数集合中串的结构特征:AD|AD

49、E0|2|4|6|8D1|2|3|9D0|1|2|3|9B1|2|3|9|B0P4:本章小结本章小结A0A1|P:S1S0|0A1|例5.给出语言L=1n0m1m0n|n,m0的文法。分析根据语言句子的结构特征,设计出相应规则L=,01,0011,10,1100,1010,100110,110100,11001100本章小结本章小结P:Sa|0S0|1S1例6.给出语言L=WaWt|W0|1*,Wt 表示W的逆的文法。分析根据语言句子的结构特征，设计出相应规则L=a,0a0,1a1,01a10,10a01,00a00,11a11,101a101,110a011,100a001,W=,0,1,0

50、1,10,00,11,101,110,100,111,本章小结本章小结2.已知一个文法，确定该文法所定义的语言。(2)给定一个文法，可根据语言和推导定义推导出文法的句子，从而确定出该文法所定义的语言。(1)文法所定义的语言L(GS)=x|Sx且xVT*本章小结本章小结自然语言描述。例如,L=x|xa,b+且x中a,b个数相同式子描述。例如L=a2nbb|n0。正规式描述。(3)语言可用本章小结本章小结例1文法GA=(A,a,b,AbA|a,A)所生成的语言是什么？分析AbAbbAbbbAbnAbnaL(GA)=bna|n0本章小结本章小结例2文法GN为:NND|DD0|1|2|3|4|5|6|

51、7|8|9(1)GN所生成的语言是什么？(2)给出句子0127的最左、最右推导。本章小结本章小结L(GN)=|0,1,2,9+=|为可带前导0的正整数=|为数字串最左推导:NNDN7ND7N27ND27N127D1270127最右推导:NNDNDDNDDDDDDD0DDD01DD012D0127NND|DD0|1|2|3|4|5|6|7|8|9本章小结本章小结例3.已知文法GS=(A,B,a,b,c,d,P,S),其中P为:分析SABaAbBa2Ab2Ban-1Abn-1BanbnBanbncBdanbnc2Bd2anbncm-1Bdm-1anbncmdmL(GS)=anbncmdm|n,m1

52、该文法所生成的语言是什么？AaAb|abBcBd|cdSAB本章小结本章小结3.求句型的短语、直接短语和句柄(1)短语、直接短语和句柄是对某句型而言的。(2)短语总是句型的某个子串，它对应子树未端结点形成的符号串。(3)直接短语是某条规则右部，它对应简单子树未端结点形成的符号串。(4)最左边的直接短语是句柄。本章小结本章小结例1已知文法GE：证明 E+T*F是它的一个句型,指出这个句型的短语直接短语和句柄。 EE+TE+T*F短语:E+T*F、T*FE+T*F是它的一个句型。画出该句型的语法树:句柄:T*F直接短语:T*FETFT+E*EE+T|E-T|TTT*F|T/F|TT(E)|i本章

53、小结本章小结例2已知文法GS：试找出符号串(a)和(A(SaA)(b)的短语直接短语和句柄(如果有的话)。S(AS)|(b)A(SaA)|(a)符号串(a)不是文法的句型，因此它没有短语直接短语和句柄。分析S(AS)(a)S)(a)/本章小结本章小结S(AS)(A(AS)(A(A(b)(A(SaA)(b)符号串(A(SaA)(b)是文法的句型，画出该句型的语法树如下图：S(AS)|(b)A(SaA)|(a)本章小结从句型的语法树求短语: (A(SaA)(b)(SaA)(b)(SaA)(b)直接短语：(SaA)、(b)句柄：(SaA)SA(S)A(S)(S aA)b(S(AS)|(b)A(Sa

54、A)|(a)对于句型(A(SaA)(b)本章小结本章小结4文法二义性的判断一个文法存在某个句子对应两棵不同的语法树或对应两个不同的最左（最右）推导，则该文法是二义性的。本章小结本章小结例1设有文法GS:SiSeS|iS|i试证明文法GS有二义性。分析因为对文法的句子iiiei有如下两棵不同的语法树与之对应，所以该文法是二义的本章小结本章小结SiSeS|iS|i句子iiiei对应下面两颗语法树：SSie SiSiiSiSiSie Si本章小结本章小结NSE|ESSD|DE0|2|4|6|8|10D0|1|2|3|4|5|6|7|8|91.试证明文法GN有二义性。2.此文法所描述的语言是什么？3.试写出另一文法G使L(G)=L(G)且G是无二义性的。例2设有文法GN:本章小结本章小结分析因为对文法的句子10有两棵不同的语法树与之对应，所以该文法是二义的NES0D1NE01NSE|ESSD|DE0|2|4|6|8|10D0|1|2|3|4|5|6|7|8|9本章小结本章小结该文法所描述的语言是所有无符号偶数的集合(可以0开头)。改写后的文法GS为:NSE|ESSD|DE0|2|4|6|8D0|1|2|3|4|5|6|7|8|9NSE|ESSD|DE0|2|4|6|8|10D0|1|2|3|4|5|6|7|8|9

展开阅读全文

第2章形式语言概论课件

最新文档