《第2章形式语言概论.ppt》由会员分享，可在线阅读，更多相关《第2章形式语言概论.ppt（167页珍藏版）》请在三一办公上搜索。
1、第2章 形式语言概论,形式语言理论是编译的重要理论基础。本章主要介绍编译理论中用到的有关形式语言理论的最基本概念，重点介绍如何采用形式化的方法描述程序设计语言。,第2章 形式语言概论,字母表和符号串,文法和语言的形式定义,短语、直接短语和句柄,语法树和文法的二义性,文法和语言的分类,概 述,对程序设计语言的描述是从语法、语义和语用三个因素来考虑。,语法是对语言结构的定义。,语用则是从使用的角度去描述语言。,语义是描述了语言的含义。,概 述,例如 赋值语句s2*3.1416*r*(r+h)的 非形式化的描述为：,语法：赋值语句由一个变量，后随一个赋 值号“”，再在其后面跟一个表达式构成。,语义：
2、首先计算语句右部表达式的值，然后把所得结果送给左部变量中。,语用：赋值语句可用来计算和保存表达式的值。,概 述,这种非形式化的描述,不够清晰和准确,为了精确定义和描述程序设计语言,需采用形式化的方法。所谓形式化的方法,是用一整套带有严格规定的符号体系来描述问题的方法。,形式语言理论是编译的重要理论基础。重点介绍如何采用形式化的方法描述程序设计语言。,字母表和符号串,元素的非空有穷集合。,例如，=a,b,c,1.字母表,根据字母表的定义，是字母表，它由a、b、c三个元素组成。,字母表和符号串,是一个字母表，由0、1两个元素组成。,注意:,例如，=0,1,(2)字母表中的元素,可以是字母、数字或其
3、他符号。,(1)字母表中至少包含一个元素。,字母表和符号串,字母表中的元素称为符号或称为字符。,例如，前述例子中,2.符号（字符）,a、b、c 是字母表中的符号；,0、1 是字母表中的符号。,字母表和符号串,例如，设有字母表=a,b,c,符号的有穷序列称为符号串。,符号串总是建立在某个特定字母表上的且只由字母表上的有穷多个符号组成。,则有符号串 a，b，ab，ba，cba，abc,3.符号串（字）,字母表和符号串,说明:,不包含任何符号的符号串,称为空符号串，用表示。,符号串中符号的顺序是很重要的。,ab和ba是字母表上的两个不同的符号串。,空符号串由0个符号组成，其长度|=0,符号串的运算,
4、设x和y是符号串，则串xy称为它们的连结。,则XYABC10A，YX10AABC。,注意：对任意一个符号串x，,1.符号串的连结,例如，设XABC，Y10A,我们有 xxx。,符号串的运算,2.集合的乘积,设A和B是符号串的集合,则A和B的乘积定义为：,集合的乘积是满足于 xA,yB的所有符号串 xy 所构成的集合。,AB=xy|xA,yB,A=A=A,符号串的运算,例如：,设A=a,b,B=c,d,则AB=ac,ad,bc,bd,由于对任意的符号串x，总有,x=x=x,所以,对任意集合A,我们有:,符号串的运算,特别指出的是，是符号串,不是集合，而表示由空符号串 所组成的集合,但这样的集合不
5、是空集合=。,符号串的运算,3.符号串的幂运算,设x是符号串,则x的幂运算定义为：,x0=,x1=x,x2=xx,x3=xxx,注意：x0 1,符号串的运算,例如,设 xabc 则,x0=,x1=abc,x2=xx=abcabc,符号串的运算,4.集合的幂运算,设A是符号串的集合，则集合A的幂运算定义为：,A0=,A1=A,A2=AA,符号串的运算,例如，设A=a,b，则,A0=,A1=A=a,b,A2=AA=aa,ab,ba,bb,A3=AAA=A2A,=aaa,aab,aba,abb,baa,bab,bba,bbb,符号串的运算,5.集合A的正闭包A与闭包A*,设A是符号串的集合，则A的正
6、闭包A和A的闭包A*的定义为:,A+=A1A2 An,A*=A0 A1A2 An,=A+,符号串的运算,可见,集合A的正闭包表示A上元素a,b构成的所有符号串的集合,集合A的闭包比集合A的正闭包多含一个空符号串。,例如，设A=a,b,则：,A+=a,b,aa,ab,ba,bb,aaa,aab,A*=,a,b,aa,ab,ba,bb,aaa,aab,文法和语言的形式定义,每个形式语言都是某个字母表上按某种规则构成的所有符号串的集合。反之，任何一个字母表上符号串的集合均可定义为一个形式语言。,形式语言,序列的集合称为形式语言。,文法和语言的形式定义,对每个具体语言,都有语法和语义两个方面，形式语言
7、是指不考虑语言的具体意义，即不考虑语义。,文法和语言的形式定义,形式语言的描述,对形式语言的描述有两种方法，一种方法是当语言为有穷集合时，用枚举法来表示语言。,文法和语言的形式定义,均表示字母表A上的一个形式语言。由于这三个语言均是有限符号串的集合，因此，可枚举出其全部句子来表示该语言。,例如，设有字母表A=a,b,c，则,L1=a,b,c,L2=a,aa,ab,ac,L3=c,cc,文法和语言的形式定义,例如，设字母表=0,1,则,+=123,=0,1,00,10,11,01,000,100,当语言为无穷集合时，用文法来描述语言。,文法和语言的形式定义,下面用A表示+，用式子A0表示符号串0
8、A或A生成符号串0，符号“”读作“生成”或“由组成”。则集合A可表示成：,A0,A1,AA0,AA1,+=123,=0,1,00,10,11,01,000,100,文法的形式定义,规则是一个符号与一个符号串的有序对（A,），通常写作：,A（或A),1.规则 也称产生式,规则的作用是告诉我们如何用规则中的符号串生成语言中的序列。,文法的形式定义,例如，前述例中一组规则,描述的语言序列只可能是由0和1组成的符号串。,A0,A1,AA0,AA1,文法的形式定义,规则中出现的符号分为两类，一类是终结符号，另一类是非终结符号。,非终结符号是出现在规则左部能派生出符号或符号串的那些符号，即每个非终结符号表
9、示一定符号串的集合，用大写字母表示或用尖括号把非终结符号括起来。例如，上例中的A。,文法的形式定义,终结符号是不属于非终结符号的那些符号,它是组成语言的基本符号，是一个语言的不可再分的基本符号，通常用小写字母表示。例如，上例中的0和1。,文法的形式定义,规则的非空有穷集合，通常表示成四元组,VN是规则中非终结符号的集合。,VT是规则中终结符号的集合。,P 是文法规则的集合。,2.文法,G=VN,VT,P,S,文法的形式定义,S 是一个非终结符号，称为文法的开始符号或文法的识别符号，它至少要在一条规则中作为左部出现。由它开始，识别出我们所定义的语言。,由文法定义可知，文法是对语言结构的定义和描述
10、，文法四大要素中关键是规则的集合。,文法的形式定义,将它们缩写为：A1|2|n,A1,A2,An,其中每个i有时也称为是A的一个候选式。,为了书写方便，对于若干个左部相同的规则，如,文法的形式定义,我们约定：,第一条规则的左部是识别符号。,对文法G不用四元式显示表示，仅只将规则写出。,文法的形式定义,G=(VN，VT，P，S),VN=A,VT=0，1,P:A 0|1|A0|A1,S=A,前例中描述+的文法是:,文法的形式定义,例1 设字母表=a,b，试设计一个文法，描述语言 L=a2n,b2n|n1,分析 设计一个文法来描述一个语言,关键是设计一组规则生成语言中的符号串。因此，为设计该语言文法
11、，必须分析这个语言是由怎样一些符号串组成的，即首先分析语言中串的结构特征：,文法的形式定义,当n1 L=aa,bb,L=aa,bb,aaaa,bbbb,aaaaaa,bbbbbb,即语言L是由偶数个a，偶数个b这样的符号串组成的集合。,L=a2n,b2n|n1,当n2 L=aaaa,bbbb,当n3 L=aaaaaa,bbbbbb,文法的形式定义,因此，定义语言L的文法,G=(VN，VT，P，S),其中：,VN=A,B,D,VT=a,b,P=Aaa,S=A,Baa,Dbb|bbD,|bb|bbD,注意:VTaa,bb,|aaB,|aaB,文法的形式定义,提出问题:描述该语言的文法是否唯一呢？,
12、显然，G不同于G。由此可见，对于一个给定的语言，描述该语言的文法是不唯一的。,P:AB|D,Baa|aBa,Dbb|bDb,若G和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 试设计一个表示所有标识符的文法,分析 题意是用文法定义标
13、识符，必须确定P中规则。为了设计出一组规则，首先应搞清楚集合中串的结构特征。,文法的形式定义,用I代表标识符；L代表字母；D代表数字;则定义标识符的文法为：,标识符的结构可用下图表示:,文法的形式定义,G=(VN，VT，P，S),其中：,VN=I,L,D,VT=a,b,c,x,y,z,0,1,2,9,P=IL,S=I,La|b|c|x|y|z,D0|1|2|3|9,|I L,|I D,文法的形式定义,若将定义标识符的文法设计成：,其中 VN，VT，S 同上,G=(VN，VT，P，S),P=IL|I D,La|b|c|x|y|z,D0|1|2|3|9,文法的形式定义,该文法不能定义ab，abc
14、仅由字母串组成的标识符，缩小了所定义语言的范围。,P=IL|I D,La|b|c|x|y|z,D0|1|2|3|9,文法的形式定义,用I代表标识符；L代表字母；D代表数字；T代表字母数字串；则定义标识符的文法还可写为：,文法的形式定义,P:IL|LT TL|D|LT|DT La|b|c|x|y|z D0|1|2|3|9,文法的形式定义,例3 用文法定义一个含、*的算术表达式，定义用下述自然语言描述：变量是一个表达式；若 E1和 E2是算术表达式,则 E1E2、E1*E2、(E1)也是算术表达式。,文法的形式定义,分析 算术表达式的定义用自然语言描述，这是对算术表达式的非形式定义，题意用文法来定
15、义算术表达式，即是用形式化的方法定义表达式。定义算术表达式的文法为：,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,分析 该语言中串的结构特征是,当n1 L=aba,L=aa,aba,abba,当n2 L=abba,当n0 L=aa(b0=),文法的形式定义,所以定义语言的文法为：,G=(A,B,a,b,P,A),P=AaBa BBb|,L=aa,aba,ab
16、ba,文法的形式定义,例5 设字母表=(,),试设计一个文法描述语言 L=(n)n|n0,分析 该语言中串的结构特征是,当n=0 L=注:(0)0=,当n=1 L=(),当n=2 L=(),L=,(),(),(),文法的形式定义,P:S|(S),所以定义语言的文法为：,L=(n)n|n0,语言的形式定义,1.直接推导,令G是一文法，我们称 xAy直接推导出 xy，即 xAyxy 仅 A 是 G 的一条规则,且x,y(VNVT)*。也就是说从符号串 xAy 直接推导出 xy 仅使用一次规则。,语言的形式定义,例如，设有文法GS:,S01 使用规则 S01 此时 x，y,P为：S 0 1|0 S
17、1,有如下直接推导：,S0S1 使用规则 S0S1 此时 x，y,语言的形式定义,0S10011 使用规则 S01 此时 x0，y1,00S11000S111 使用规则 S0S1 此时 x00,y11,000S11100001111 使用规则 S01 此时 x000 y111,S 0 1|0 S 1,语言的形式定义,(1)形式上的区别，推导用“”表示，规则用“”表示。,(2)对文法G中任何规则A，我们有A，即推导的依据是规则。,注意推导和规则的区别：,即表示从0 出发，经 一步或若干步 或者说 使用若干次规则可推导出 n。,语言的形式定义,如果存在一个直接推导序列：,则我们称这个序列是一个从0
18、至n的长度为n的推导，记为,2推导,0 1 2 n,语言的形式定义,例如 设有文法GE=(E,T,F,i,+,*,(,),P,E),对 i+i*i 有如下直接推导序列:,我们可记为,其中P为：EE+T|T,TT*F|F,F(E)|i,E,E+T,T+T,F+T,i+T,i+T*F,i+F*F,i+i*F,i+i*i,语言的形式定义,3广义推导,我们有：,对上例 EE+T|T TT*F|F F(E)|i,语言的形式定义,区别：直接推导的长度为1，推导的长度大于等于1，而广义推导的长度大于等于0。,语言的形式定义,4.句型和句子,设有文法GS（S是文法G的开始符号）,语言的形式定义,例1 设有文法
19、GS：,我们有:,显然，符号串01、0S1、00S11和000111 都是文法GS的句型，而01和000111又是文法GS的句子。,S01|0S1,语言的形式定义,例2 设有文法GE：,试证明符号串(i*i+i)是文法GE的一个句子。,分析 只要证明符号串(i*i+i)对文法 G存在一个推导，就可证明符号串(i*i+i)是文法GE的一个句子。,EE+E|E*E|(E)|i,语言的形式定义,EE+E|E*E|(E)|i,E,(E),(E+E),(E*E+E),(i*E+E),(i*i+E),(i*i+i),（2）L(G)是VT*的子集。即属于VT*的符 号串 x 不一定属于L(G)。,语言的形式
20、定义,5语言,文法GS产生的所有句子的集合称为文 法G所定义的语言,记为L(GS)：,由语言定义可知：,（1）一当文法给定，语言也就确定。,语言的形式定义,例3 设有文法GS：S01|0S1,求该文法所描述的语言是什么？,分析 由识别符号S出发，将推出一些什么样的句子，也就是说，L(GS)将由什么样的一些符号串所组成的集合，找出其中的规律，用式子或自然语言描述出来。,语言的形式定义,我们应用第二个规则n1次，然后再应用第一个规则1次，有：,S,0S1,00S11,0n-1S1n-1,0n1n,可见，此文法定义的语言为,L(GS)=0n1n|n1,S01|0S1,语言的形式定义,例4 设有文法G
21、S：S0S|1S|,该文法所定义的语言是什么？,由该文法所确定的语言为,L(GS)=,0,1,00,01,10,11,=x|x0,1*,语言的形式定义,例5 设有文法GA：,该文法所定义的语言是什么？,分析 从文法开始符号A出发可推导出以y开头后面跟一个或多个x结尾的符号串，所以该文法定义的语言为,AyBBxB|x,L(GA)=yxn|n1,语言的形式定义,由此可见，从已知文法确定语言的中心思想是：从文法的开始符号出发，反复连续地使用规则替换、展开非终结符，找出句子的规律，用式子或自然语言描述出来。,语言的形式定义,形式语言理论可以证明如下两点：,(1)给定一种语言，能确定其文法，但这种文法不
22、是唯一的，即：LG1或G2或,(2)给定一个文法，就能从结构上唯一确定其语言，即：GL(G)；,规范推导和规范归约,文法和语言是密切相关的，文法所定义的任一句型和句子,都可以根据文法推导出来。,我们提出一个问题：,这种推导过程是否唯一？,规范推导和规范归约,同一个句型(句子)可以通过不同的推导序列推导出来，这是因为在推导过程中与所选择非终结符的次序无关。,规范推导和规范归约,例如，设有文法GN1,N1N,NND|D,D0|1|2,N1,N,ND,N2,D2,12,N1,N,ND,DD,1D,12,N1,N,ND,DD,D2,12,句子12有下列三种不同的推导序列:,规范推导和规范归约,最左(最
23、右)推导，是指对于一个推导序列中的每一步直接推导,都是对 中的最左(最右)非终结符进行替换。,最右推导也称为规范推导，用规范推导推导出的句型称为规范句型。,规范推导和规范归约,例 设有文法GS:,请给出句子101001的最右、最左推导。,分析 最右推导是指在推导过程中任何一步(和是句型)，都是对中的最右非终结符进行替换。,SAB,AA0|1B,B0|S1,规范推导和规范归约,S,AB,AS1,AAB1,AA01,A1B01,A1001,1B1001,101001,句子101001的最右推导为:,SAB,AA0|1B,B0|S1,规范推导和规范归约,最左推导是指在推导过程中任何一步(和是句型),
24、都是对的最左非终结符进行替换。,句子101001的最左推导为：,SAB,AA0|1B,B0|S1,S,AB,1BB,10B,10S1,10AB1,101BB1,1010B1,101001,规范推导和规范归约,归约是与推导相对的概念，推导是把句型中的非终结符用规则的一个右部来替换的过程，而归约则是把句型中的某个子串用一个非终结符来替换的过程。,xAyxy,规范推导和规范归约,例如，例文法GN1中有规范推导：,则有规范归约：,规范推导的逆过程，称为最左归约，也称为规范归约。,N1,N,ND,N2,D2,12,12,递归规则与文法的递归性,递归规则,如果文法中有规则 AA 称为规则左递归。,如果文法
25、中有规则 A A 称为规则右递归。,如果文法中有规则 A A 称为规则递归。,递归规则与文法的递归性,文法的递归性,递归规则与文法的递归性,例如 文法中有如下规则：,这三条规则都不是递归规则，但有,在文法中使用递归规则，使得我们能用有限的规则去定义无穷集合的语言。,UVx,VUy|z,UVx Uyx,则该文法是左递归的。,递归规则与文法的递归性,例2 考虑文法GA：,由于该文法无递归性，由它所描述的语言是有穷的。该文法描述的语言为:,AaB|bB,Ba|b,L(GA)=aa,ab,ba,bb,递归规则与文法的递归性,例3 考虑文法GN1,该文法有直接左递归规则 NND,则称该文法为左递归文法或
26、说文法左递归，其定义的语言为0,1,2+。,N1N,NND|D,D0|1|2,递归规则与文法的递归性,也就是说，当一个语言是无穷集合时，则定义该语言的文法一定是递归的。,若不用递归规则，则 NND 需要用 ND|DD|DDD|即无穷多条规则来定义由数字0,1,2 组成的所有无符号整数。,短语、直接短语和句柄,短语,令G是一个文法，S是文法的开始符号，假定是文法G的一个句型，如果有,则称 是相对于非终结符A的句型的短语。,短语、直接短语和句柄,则称是直接短语。,直接短语,且 A,令G是一个文法，S是文法的开始符号，假定是文法G的一个句型，如果有,短语、直接短语和句柄,注意：短语和直接短语的区别在
27、于第二个条件,直接短语中的第二个条件表示有文法规则 A，因此，每个直接短语都是某规则右部。,短语、直接短语和句柄,句柄,一个句型的最左直接短语称为该句型的句柄。,句柄特征：,(1)它是直接短语，即某规则右部。,(2)它具有最左性。,短语、直接短语和句柄,注意:短语、直接短语和句柄都是针对某一句型的，都是指句型中的哪些符号串能构成短语和直接短语，离开具体的句型来谈短语、直接短语和句柄是无意义的。,短语、直接短语和句柄,例如 设有文法GS=(S,A,B,a,b,P,S)其中P为：,求句型 baSb的全部短语、直接短语和句柄。,SAB,AAa|bB,Ba|Sb,短语、直接短语和句柄,对文法，首先建立
28、该句型的推导过程：,最左推导:,最右推导:,分析 根据短语定义，可以从句型的推导过程 中找出其全部短语、直接短语和句柄。,句型 baSb,短语、直接短语和句柄,句型baSb中的子串Sb，是(相对于非终结符B)句型baSb的短语，且为直接短语。,B Sb,句型本身是(相对于非终结符S)句型baSb的短语。,根据最左推导:,短语、直接短语和句柄,句型baSb中的子串a，是(相对于非终结符B)句型baSb的短语，且为直接短语、句柄。,句型baSb中的子串ba，是(相对于非终结符A)句型baSb的短语。,B a,根据最右推导:,语法树与文法的二义性,推导和语法树,1.语法树,对句型的推导过程给出一种图
29、形表示,这种表示称为语法树，也称推导树。,推导和语法树,例如 设有文法GE:,构造句型i*i+i的语法树。,首先给出句型的推导过程(最左推导)：,EE+T|ET|T,TT*F|T/F|F,F(E)|i,EE+TT+TT*F+TF*F+Ti*F+T i*i+Ti*i+Fi*i+i,推导和语法树,根据推导过程构造句型i*i+i的语法树如下：,EE+T,E,E,+,T,T+T,T,T*F+T,T,*,F,F*F+T,F,i*F+T,i,i*i+T,i,i*i+F,F,i*i+i,i,推导和语法树,由例可知，语法树的构造过程是从文法的开始符号出发，构造一个推导的过程。,因为文法的每一个句型(句子)都存
30、在一 个推导，所以文法的每个句型(句子)都存在一棵对应的语法树。,EE+T E+F E+i T+i T*F+i T*i+i F*i+i i*i+i,推导和语法树,对句型i*i+i，还可给出最右推导：,推导和语法树,这也就是说，一棵语法树表示了 一个句型的种种可能的(但未必是所 有的)不同推导过程,包括最左(最右)推导。,推导和语法树,2.子树,语法树的子树是由某一结点连同所有分枝组成的部分。,推导和语法树,3.简单子树,语法树的简单子树是指只有单层分枝的子树。,推导和语法树,句型的短语、直接短语和句柄的直观解释是：,短语：子树的末端结点形成的符号串是 相对于子树根的短语。,直接短语：简单子树的
31、末端结点形成的 符号串是相对于简单子树根的直接短语。,句柄：最左简单子树的末端结点形成的 符号串是句柄。,推导和语法树,短语:,i*i+i,i*i,第一个i,第二个i,第三个i,三个i都是直接短语,第一个i是句柄,注意:i+i不是句型的短语,句子 i*i+i,推导和语法树,前例 对文法GS=(S,A,B,a,b,P,S),其中P为：,可用语法树非常直观地求出句型baSb的全部短语，直接短语和句柄。,SAB,AAa|bB,Ba|Sb,推导和语法树,分析 首先根据句型baSb的推导过程画出对 应的语法树如下：,Sb 为句型的相对于B的短语、直接短语,baSb 为句型的相对于S的短语,ba 为句型的
32、相对于A的短语,a 句型的相对于B的短语、直接短语和句柄,SABbBBbaBbaSb,SABASbbBSbbaSb,由语法树可知,文法的二义性,从前面的讨论可以看出，对于文法G中 任一句型的推导序列,我们总能为它构造 一棵语法树，现在我们提出一个问题：,文法的某个句型是否只对应唯一的一棵语法树呢？也就是，它是否只有唯一的一个最左(最右)推导呢？,文法的二义性,例如 设有文法GE：,句子 i*i+i 有两个不同的最左推导，对应两棵不同的语法树。,E E+E|E*E|(E)|i,文法的二义性,最左推导1 EE+EE*E+E i*E+Ei*i+E i*i+i,最左推导2 EE*Ei*E i*E+Ei
33、*i+E i*i+i,文法的二义性,如果一个文法存在某个句子对应两棵不同的语法树，则说这个文法是二义性的。或者说，若一个文法中存在某个句子，它有两个不同的最左(最右)推导，则这个文法是二义性的。,E E+E|E*E|(E)|i,文法二义性的消除,1.不改变文法中原有的语法规则,仅加进一些非形式的语法规定。,文法二义性的消除,2.构造一个等价的无二义性文法。即 把排除二义性的规则合并到原有文法中,改写原有的文法。,例如，对于上例文法GE，将运算符的 优先顺序和结合规则：*优先于;、*左结合加到原有文法中,可构造出无二义 性文法如下：,文法二义性的消除,则句子i*i+i只有唯一一棵语法树：,EE+
34、T|T,TT*F|F,F(E)|i,文法二义性的消除,例2 定义某程序语言条件语句的文法G为:,试证明该文法是二义性的并消除之。,分析 该文法的句子 if b if b A else A 对应下面两棵不同的语法树：,Sif b S,|if b S else S,|A(其它语句）,文法二义性的消除,所以该文法是二义的。,Sif b S|if b S else S|A,句子 if b if b A else A,文法二义性的消除,消除文法的二义性可采用下面两种方法：,不改变已有规则，仅加进一非形式的语法规定：else与前面最接近的不带else的 if 相对。,文法G的句子 if b if b A
35、else A只对应唯一的一棵语法树，消除了二义。,文法二义性的消除,2.改写文法G为G,S S1|S2,S1 if b S1 else S1|A,S2 if b S|if b S1 else S2,G:,Sif b S,|if b S else S,|A(其它语句）,G:,文法二义性的消除,这是因为通过分析，得知引起二义性的原因是:ifelse 语句的 if 后可是if型，因此改写文法时规定:if else之间只能是ifelse语句或其他语句。,文法二义性的消除,S S1|S2,S1 if b S1 else S1|A,S2 if b S|if b S1 else S2,对改写后的文法，句子
36、if b if b A else A 只对应唯一的一棵语法树。,通常我们只说文法的二义性,而不说语言的二义性,这是因为可能有两个不同的文法G和G，而且其中一个是二义性的，另一个是无二义性的,但却有L(G)=L(G),即这两个文法所产生的语言是相同的。,文法二义性的消除,应该指出的是文法的二义性和语言的二义性是两个不同的概念。,文法二义性的消除,将一个语言说成是二义性的，是指对它不存在无二义性的文法，这样的语言称为先天二义性的语言。例如 L=ai bj ck|i=j 或 j=k 且 i,j,k1便是这种语言。,文法和语言的分类,著名的语言学家乔姆斯基(Chomsky)将文法和语言分为四大类，即0
37、型、1型、2型、3型。划分的依据是对文法中的规 则施加不同的限制。,文法和语言的分类,0型文法（无限制文法）,若文法G=(VN,VT,P,S)中的每条规则 是这样一种结构：,而且中至少含一个非终结符,则称G 是0型文法。,(VNVT)+,(VNVT)*,0型文法描述的语言是0型语言。,0型文法没有加任何限制条件，又称为 无限制性文法，相应的语言称为无限制 性语言。,0型语言由图灵机识别。,文法和语言的分类,例如，有0型文法G=(VN,VT,P,S),其中：VN=A,B,S,VT=0,1,其描述的 0 型语言为 L0(GS)=,P:S 0AB,1B 0,B SA|01,A1 SB1,A0 S0B
38、,文法和语言的分类,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,c,P:S aSAB|abB,BA BA,BA AA,AA AB,bA bb,bB bc,cB cc,其描述的1型语言为L1(GS)=anbncn|n1,文法和语言的分类,2型文法（上下文无关
39、文法）,2型文法又称上下文无关文法，其产生的 语言又称为上下文无关的语言。,若文法G=(VN,VT,P,S)中的每一条规则的 形式为 A,其中：,AVN,(VNVT)*,则称G是2型文法。,2型文法描述的语言是2型语言。,2型语言由下推自动机识别。,例如前面描述算术表达式的文法GE:,EE+E|E*E|(E)|i,文法和语言的分类,其描述的语言为 L2(GS)=x|x a,b+且x中a和b的个数相同,例如，有2型文法G=(VN,VT,P,S),其中：VN=S,A,B,VT=a,b,P=S aB|bA,A a|aS|bAA,B b|bS|aBB,文法和语言的分类,文法和语言的分类,3型文法（正规
40、文法）,右线性文法和左线性文法都称为3型文法。,若文法G=(VN,VT,P,S)中的每一条规则的形式 为A aB 或 A a,其中：,A,BVN,a VT*,则称G是右线性文法。,若文法G=(VN,VT,P,S)中的每一条规则的形式 为A Ba 或 A a,其中：,A,BVN,a VT*,则称G是左线性文法。,3型文法描述的语言是3型语言。,3型语言由有穷自动机识别。,3型文法也称正规文法。正规文法产生的语言 称为正规语言。,例如，用左线性正规文法和右线性正规文法定义标识符,文法和语言的分类,用I代表标识符;l代表任意一个字母;d代表任意一个数字;则定义标识符的文法为：,左线性文法:P:I l
41、|Il|Id,右线性文法:P:I l|lT Tl|d|lT|dT,例如，用左线性正规文法和右线性正规文法定义无符号整数,文法和语言的分类,用N代表无符号整数;d代表任意一个数字；则定义的无符号整数文法为：,左线性文法:P:N Nd|d,右线性文法:P:N dN|d,文法和语言的分类,由上述四类文法的定义可知,从0型文法到3型文法,是逐渐增加对规则的限制条件而得到的，因此每一种正规文法都是上下文无关的文法，每一种上下文无关的文法都是上下文有关的文法，而每一种上下文有关的文法都是0型文法,而由它们所定义的语言类是依次缩小的，有 L0 L1 L2 L3。,有关文法的实用限制和变换,文法是用来描述程序
42、设计语言的，在 实际应用中需要对文法加一些限制条件。,1.文法中不能含有形如A A 的规则。这种规则我们称之为有害规则。,对文法的实用限制有以下两点：,有关文法的实用限制和变换,2.文法中不能有多余规则。所谓多余规则是指文法中出现以下两种规则：,(1)某条规则 A 的左部符号A不在所属文法的任何其他规则右部出现，即在推导文法的所有句子中始终都不可能用到的规则。,(2)对文法中的某个非终结符A，无法从它推出任何终结符号串来。,有关文法的实用限制和变换,例如 设有文法GS:,P:S Bd,A Ad|d,B Cd|Ae,C Ce,D e,删除多余规则后的文法变换为:,P:S Bd,A Ad|d,B
43、Ae,有关文法的实用限制和变换,若程序设计语言的文法含有多余规则，其中必定有错误存在，因此检查文法中是否含有多余规则对我们来说是很重要的。,本章重点介绍了语言的语法结构的形式描 述、语法树以及文法的二义性,主要内容有：,1.设计一个文法定义一个已知的语言,(1)文法是一个四元组 G=(VN,VT,P,S)，文法四大要素中，关键是一组规则,它定义（或描述）了一个语言的结构。,从文法定义可知,文法对于程序设计者来 说，文法给出了语言的精确定义和描述。,本章小结,本小结花时45分钟2004/2/28,(2)分析已知语言句子的结构特征,设计 出相应的一组规则，但不唯一。,(4)若语言是无穷集合,设计该
44、语言的文 法一定是递归的。,本章小结,(3)设计的文法必须能定义已知的语言,不能超出或缩小所定义语言的范围。,分析 根据语言句子的结构特征，设计出相 应规则,例1.给出语言 L2=an bm|mn1 的文法,P2:SAB,L2=ab,abb,abbb,aabb,aabbb,aabbbb,aaabbb,aabbbb，,AaAb|ab,BbB|,本章小结,分析 根据语言句子的结构特征，设计出相 应规则,例2.给出语言 L1=a2n+1|n0 的文法,P1:AaB|a,P1：AaAa|a,或,L1=a,aaa,aaaaa,aaaaaaa,aaaaaaaaa，,Baa|aBa,本章小结,本章小结,分析
45、 根据语言句子的结构特征，设计出相应规则,例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|AE,N0|2|4|6|8|BN,或,分析 不以0开头的偶数集合中串的结构特征:,AD|AD,E0|2|4|6|8,D1|2|3|9,D0|1|2
46、|3|9,B1|2|3|9|B0,P4:,本章小结,A 0A1|,P:S 1S0|0A1|,例5.给出语言L=1n0m1m0n|n,m0的 文法。,分析 根据语言句子的结构特征,设计 出相应规则,L=,01,0011,10,1100,1010,100110,110100,11001100,本章小结,P:S a|0S0|1S1,例6.给出语言L=WaWt|W0|1*,Wt 表示W的逆的文法。,分析 根据语言句子的结构特征，设计 出相应规则,L=a,0a0,1a1,01a10,10a01,00a00,11a11,101a101,110a011,100a001,W=,0,1,01,10,00,11,
47、101,110,100,111,本章小结,2.已知一个文法，确定该文法所定义的 语言。,(2)给定一个文法，可根据语言和推导定 义推导出文法的句子，从而确定出该文法 所定义的语言。,本章小结,自然语言描述。例如,L=x|xa,b+且x中a,b个数相同,式子描述。例如 L=a2nbb|n0。,正规式描述。,(3)语言可用,本章小结,例1 文法GA=(A,a,b,AbA|a,A)所生成的语言是什么？,分析 AbAbbAbbbAbnAbna,L(GA)=bna|n0,本章小结,例2 文法GN为:,N ND|DD 0|1|2|3|4|5|6|7|8|9,(1)GN所生成的语言是什么？,(2)给出句子0
48、127的最左、最右推导。,本章小结,L(GN)=|0,1,2,9+,=|为可带前导0的正整数,=|为数字串,最左推导:,NNDN7ND7N27ND27 N127D1270127,最右推导:,NNDNDDNDDDDDDD 0DDD01DD012D0127,N ND|DD 0|1|2|3|4|5|6|7|8|9,本章小结,例3.已知文法GS=(A,B,a,b,c,d,P,S),其中 P 为:,分析 SABaAbBa2Ab2B an-1Abn-1BanbnBanbncBd anbnc2Bd2 anbncm-1Bdm-1anbncmdm,L(GS)=anbncmdm|n,m1,该文法 所生成的语言是什
49、么？,A aAb|ab,B cBd|cd,S AB,本章小结,3.求句型的短语、直接短语和句柄,(1)短语、直接短语和句柄是对某句 型而言的。,(2)短语总是句型的某个子串，它对应 子树未端结点形成的符号串。,(3)直接短语是某条规则右部，它对应 简单子树未端结点形成的符号串。,(4)最左边的直接短语是句柄。,本章小结,例1 已知文法GE：,证明 E+T*F是它的一个句型,指出这个句型的短语直接短语和句柄。,EE+TE+T*F,短语:E+T*F、T*F,E+T*F是它的一个句型。,画出该句型的语法树:,句柄:T*F,直接短语:T*F,EE+T|E-T|T,TT*F|T/F|T,T(E)|i,本
50、章小结,例2 已知文法GS：,试找出符号串(a)和(A(SaA)(b)的短语 直接短语和句柄(如果有的话)。,S(AS)|(b),A(SaA)|(a),符号串(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),S(AS)|(b),A(SaA)|(a),对于句型(A(SaA)(b),
