文法和语言的基本知识.ppt

《文法和语言的基本知识.ppt》由会员分享，可在线阅读，更多相关《文法和语言的基本知识.ppt（92页珍藏版）》请在装配图网上搜索。

1、第2章 文法和语言的基本知识,形式语言理论是编译的重要理论基础。本章主要介绍编译理论中用到的有关形式语言理论的最基本概念，重点介绍如何采用形式化的方法描述程序设计语言。,第2章 文法和语言的基本知识,字母表和符号串,文法和语言的形式定义,短语、直接短语和句柄,语法树和文法的二义性,文法和语言的分类,2.1 概 述,对程序设计语言的描述是从语法、语义和语用三个因素来考虑。,语法是对语言结构的定义。,语用则是从使用的角度去描述语言。,语义是描述了语言的含义。,2.1 概 述,例如 赋值语句s2*3.1416*r*(r+h)的 非形式化的描述为：,语法：赋值语句由一个变量，后随一个赋 值号“”，其后

2、面再跟一个表达式构成。,语义：首先计算语句右部表达式的值，然后把所得结果送给左部变量中。,语用：赋值语句可用来计算和保存表达式的值。,2.1 概 述,这种非形式化的描述,不够清晰和准确,为了精确定义和描述程序设计语言,需采用形式化的方法。所谓形式化的方法,是用一整套带有严格规定的符号体系来描述问题的方法。,形式语言理论是编译的重要理论基础。重点介绍如何采用形式化的方法描述程序设计语言。,2.2 字母表和符号串的基本概念,内容主要包括： 1.字母表和符号串的定义 2.符号串的运算,2.2.1 字母表和符号串,元素的非空有穷集合。,例如，= a, b, c ,1. 字母表,根据字母表的定义，是字母

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

4、3. 符号串（字）,2.2 字母表和符号串,说明:,不包含任何符号的符号串, 称为空符号串，用表示。,符号串中符号的顺序是很重要的。,ab和ba是字母表上的两个不同的符号串。,空符号串由0个符号组成，其长度|=0,我们有 x x x。,2.2 .2 符号串的运算,设x和y是符号串，则串xy称为它们的连结。,则XY_，YX _ 。,注意：对任意一个符号串x，,1. 符号串的连结,例如，设XABC，Y10A,2.2.2 符号串的运算,2. 集合的乘积,设A和B是符号串的集合, 则A和B的乘积定义为：,集合的乘积是满足于 xA, yB的所有符号串 xy 所构成的集合。,AB=xy | xA, yB,

5、A A A,2.2.2 符号串的运算,例如：,设A= a, b , B= c, d ,则AB= ac, ad, bc, bd ,由于对任意的符号串x，总有,x=x=x,所以, 对任意集合A, 我们有:,2.2.2 符号串的运算,特别指出的是， 是符号串, 不是集合，而表示由空符号串 所组成的集合, 但这样的集合不是空集合= 。,2.2.2 符号串的运算,3. 符号串的幂运算,设x是符号串, 则x的幂运算定义为：,x0= ,x1= x,x2= xx,x3= xxx,注意：x0 1,2.2.2 符号串的运算,例如, 设 xabc 则,x0= _,x1= _,x2=xx= _,2.2.2 符号串的运

6、算,4. 集合的幂运算,设A是符号串的集合，则集合A的幂运算定义为：,A0=,A1=A,A2=AA,2.2.2 符号串的运算,例如，设A= a, b ，则,A0= _,A1=A= a, b ,A2=AA= _,A3=AAA=A2A,= aaa, aab, aba, abb, baa, bab, bba, bbb ,2.2.2 符号串的运算,5. 集合A的正闭包A与闭包A*,设A是符号串的集合，则A的正闭包A和A的闭包A*的定义为:,A+=A1A2 An ,A*= A0 A1A2 An ,=A+,2.2.2 符号串的运算,可见,集合A的正闭包表示A上元素a,b构成的所有符号串的集合,集合A的闭包

7、比集合A的正闭包多含一个空符号串。,例如，设A= a, b , 则：,A+= a, b, aa, ab, ba, bb, aaa, aab, ,A*= , a, b, aa, ab, ba, bb, aaa, aab, ,2.3 文法和语言的形式定义,每个形式语言都是某个字母表上按某种规则构成的所有符号串的集合。反之，任何一个字母表上符号串的集合均可定义为一个形式语言。,2.3.1形式语言,序列的集合称为形式语言。,2.3.1 形式语言,对每个具体语言,都有语法和语义两个方面，形式语言是指不考虑语言的具体意义，即不考虑语义。,2.3.1 形式语言,形式语言的描述,对形式语言的描述有两种方法，一

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

9、”。则集合A可表示成：,A0,A1,AA0,AA1,+=123,= 0, 1, 00, 10, 11, 01, 000, 100, ,2.3.1 文法的形式定义,规则是一个符号与一个符号串的有序对（A,），通常写作：,A（或A ),1. 规则 也称产生式,规则的作用是告诉我们如何用规则中的符号串生成语言中的序列。,2.3.2 文法的形式定义,例如，前述例中一组规则,描述的语言序列只可能是由0和1组成的符号串。,A0,A1,AA0,AA1,2.3.2 文法的形式定义,规则中出现的符号分为两类，一类是终结符号，另一类是非终结符号。,非终结符号是出现在规则左部能派生出符号或符号串的那些符号，即每个非

10、终结符号表示一定符号串的集合，用大写字母表示或用尖括号把非终结符号括起来。例如，上例中的A。,2.3.2 文法的形式定义,终结符号是不属于非终结符号的那些符号, 它是组成语言的基本符号，是一个语言的不可再分的基本符号，通常用小写字母表示。 例如，上例中的0和1。,2.3.2 文法的形式定义,规则的非空有穷集合，通常表示成四元组,VN是规则中非终结符号的集合。,VT是规则中终结符号的集合。,P 是文法规则的集合。,2. 文法,G=(VN,VT, P, S ),2.3.2 文法的形式定义,S 是一个非终结符号，称为文法的开始符号或文法的识别符号，它至少要在一条规则中作为左部出现。由它开始，识别出我

11、们所定义的语言。,由文法定义可知，文法是对语言结构的定义和描述，文法四大要素中关键是规则的集合。,2.3.2 文法的形式定义,将它们缩写为：A1 | 2 | | n,A1,A2,An,其中每个i有时也称为A的一个候选式。,为了书写方便，对于若干个左部相同的规则，如,2.3.2 文法的形式定义,我们约定：, 第一条规则的左部是识别符号。,对文法G不用四元式显示表示，仅只将规则写出。,2.3.1 文法的形式定义,G=(VN，VT，P，S ),VN=A,VT=0，1,P: A 0 | 1 | A0 | A1,S=A,前例中描述+的文法是:,2.3.2 文法的形式定义,例1 设字母表=a, b，试设计

12、一个文法，描述语言 L= a2n, b2n | n1 ,分析 设计一个文法来描述一个语言, 关键是设计一组规则生成语言中的符号串。因此，为设计该语言文法，必须分析这个语言是由怎样一些符号串组成的，即首先分析语言中串的结构特征：,2.3.2 文法的形式定义,当n1 L=_, ,L=aa, bb, aaaa, bbbb, aaaaaa, bbbbbb, ,即语言L是由偶数个a，偶数个b这样的符号串组成的集合。,L=a2n, b2n | n1,当n2 L=_,当n3 L=aaaaaa, bbbbbb,2.3.2 文法的形式定义,因此，定义语言L的文法,G=( VN，VT，P，S ),其中：,VN=A

13、, B, D,VT=a, b,P= Aaa,S=A,Baa,Dbb | bbD ,| bb | bbD,注意: VTaa,bb,| aaB,| aaB,2.3.2 文法的形式定义,提出问题: 描述该语言的文法是否唯一呢？,显然，G不同于G。由此可见，对于一个给定的语言，描述该语言的文法是不唯一的。,P : AB | D,Baa | aBa,Dbb | bDb,若G和G是两个不同的文法，如果它们描述的语言相同，那么，称G和G 为等价文法。,2.3.2 文法的形式定义,描述该语言的文法是否G“？,2.3.2 文法的形式定义,对此例，我们提出下面这样一个问题：,G“=( A, a, b, P“, A

14、 ),其中P“= Aaa | bb | Aaa | Abb ,对于文法G“来说，它所产生的有些符号串，如aabb，bbaa， 不属于语言L，即设计的文法超出了所定义语言的范围。,2.3.2 文法的形式定义,P“= Aaa | bb | Aaa | Abb ,2.3.2 文法的形式定义,例2 试设计一个表示所有标识符的文法,分析 题意是用文法定义标识符，必须确定P中规则。为了设计出一组规则，首先应搞清楚集合中串的结构特征。,2.3.2 文法的形式定义,用I代表标识符；L代表字母；D代表数字; 则定义标识符的文法为：,标识符的结构可用下图表示:,2.3.2 文法的形式定义,G=(VN，VT，P，S

15、),其中：,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,2.3.2 文法的形式定义,若将定义标识符的文法设计成：,其中 VN，VT ，S 同上,G=(VN，VT，P，S ),P= IL | I D,La | b | c | |x|y|z,D0 | 1 | 2 | 3 | |9 ,2.3.2 文法的形式定义,该文法不能定义ab，abc 仅由字母串组成的标识符，缩小了所定义语言的范围。,P= IL | I D,La | b | c

16、| |x|y|z,D0 | 1 | 2 | 3 | |9 ,2.3.2 文法的形式定义,用I代表标识符；L代表字母；D代表数字；T代表字母数字串；则定义标识符的文法还可写为：,2.3.2 文法的形式定义,P: IL | LT TL | D | LT | DT La | b | c | |x|y|z D0 | 1 | 2 | 3 | | 9,2.3.2 文法的形式定义,例3 用文法定义一个含、*的算术表达式，定义用下述自然语言描述： 变量是一个表达式； 若 E1和 E2是算术表达式, 则 E1E2、E1*E2、(E1) 也是算术表达式。,2.3.2 文法的形式定义,分析 算术表达式的定义用自然语

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

18、2 L= abba ,当n0 L= aa (b0=),2.3.2 文法的形式定义,所以定义语言的文法为：,G=( A, B, a, b, P, A ),P= AaBa BBb | ,L= aa, aba, abba, ,2.3.2 文法的形式定义,例5 设字母表= (, ) ,试设计一个文法描述语言 L= (n )n | n0,分析 该语言中串的结构特征是,当n=0 L= 注: (0 )0= ,当n=1 L= ( ) ,当n=2 L= ( ) ,L= , ( ), ( ), ( ), ,2.3.2 文法的形式定义,P: S | ( S ),所以定义语言的文法为：,L= (n )n | n0,2

19、.3.3 语言的形式定义,1. 直接推导,令G是一文法，我们称 xAy直接推导出 xy ，即 xAyxy 仅 A 是 G 的一条规则, 且 x, y(VNVT)*。也就是说从符号串 xAy 直接推导出 xy 仅使用一次规则。,2.3.3 语言的形式定义,例如，设有文法GS:,S01 使用规则 S01 此时 x， y,P为：S 0 1 | 0 S 1,有如下直接推导：,S0S1 使用规则 S0S1 此时 x， y,2.3.3 语言的形式定义,0S10011 使用规则 S01 此时 x0， y1,00S11000S111 使用规则 S0S1 此时 x00 , y11,000S11100001111

20、 使用规则 S01 此时 x000 y111,S 0 1 | 0 S 1,2.3.3 语言的形式定义,(1) 形式上的区别，推导用“”表示，规则用“”表示 。,(2) 对文法G中任何规则A，我们有A，即推导的依据是规则。,注意推导和规则的区别：,即表示从0 出发，经 一步或若干步 或者说 使用若干次规则可推导出 n。,2.3.3 语言的形式定义,如果存在一个直接推导序列：,则我们称这个序列是一个从0至n的长度为n的推导，记为,2推导,0 1 2 n,2.3.3 语言的形式定义,例如 设有文法GE=(E,T,F,i,+,*,(,),P,E),对 i+i*i 有如下直接推导序列:,我们可记为,其中

21、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,2.3.3 语言的形式定义,3广义推导,我们有：,对上例 EE+T | T TT*F | F F(E) | i,2.3.3 语言的形式定义,区别：直接推导的长度为1，推导的长度大于等于1，而广义推导的长度大于等于0。,句型和句子,4. 句型和句子,设有文法GS（S是文法G的开始符号）,2.3.3 语言的形式定义,例1 设有文法GS：,我们有:,显然，符号串01、0S1、00S11和000111 都是文法GS的句型，而01和000111又是文法GS的句子

22、。,S01 | 0S1,2.3.3 语言的形式定义,例2 设有文法GE：,试证明符号串 (i*i+i) 是文法GE的一个句子。,分析 只要证明符号串 (i*i+i) 对文法 G存在一个推导，就可证明符号串 (i*i+i) 是文法GE的一个句子。,EE+E | E*E | (E) | i,2.3.3 语言的形式定义,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)。,2.3.3 语言的形式定义,5语言,文法GS产生的所有句子的集合称为文

23、 法G所定义的语言,记为L(GS)：,由语言定义可知：,（1）一当文法给定，语言也就确定。,2.3.3 语言的形式定义,例3 设有文法GS ：S01 | 0S1,求该文法所描述的语言是什么？,分析 由识别符号S出发，将推出一些什么样的句子，也就是说，L(GS)将由什么样的一些符号串所组成的集合，找出其中的规律，用式子或自然语言描述出来。,2.3.3 语言的形式定义,我们应用第二个规则n1次，然后再应用第一个规则1次，有：,S,0S1,00S11,0n-1S1n-1,0n1n,可见，此文法定义的语言为,L(GS)= 0n1n | n1,S01 | 0S1,2.3.3 语言的形式定义,例4 设有文

24、法GS：S0S | 1S |,该文法所定义的语言是什么？,由该文法所确定的语言为,L(GS)=, 0, 1, 00, 01, 10, 11, = x | x0,1* ,2.3.3 语言的形式定义,例5 设有文法GA：,该文法所定义的语言是什么？,分析 从文法开始符号A出发可推导出以y开头后面跟一个或多个x结尾的符号串，所以该文法定义的语言为,AyB B xB | x,L(GA)= yxn | n1,2.3.3 语言的形式定义,由此可见，从已知文法确定语言的中心思想是：从文法的开始符号出发，反复连续地使用规则替换、展开非终结符，找出句子的规律，用式子或自然语言描述出来。,2.3.3 语言的形式定

25、义,形式语言理论可以证明如下两点：,(1) 给定一种语言，能确定其文法，但这种文法不是唯一的，即：LG1或G2或,(2) 给定一个文法，就能从结构上唯一确 定其语言，即：GL(G)；,2.3.4 规范推导和规范归约,文法和语言是密切相关的，文法所定义的任一句型和句子, 都可以根据文法推导出来。,我们提出一个问题：,这种推导过程是否唯一？,2.3.4 规范推导和规范归约,同一个句型(句子)可以通过不同的推导序列推导出来，这是因为在推导过程中与所选择非终结符的次序无关。,2.3.4 规范推导和规范归约,例如，设有文法GN1,N1N,NND | D,D0 | 1 | 2,N1,N,ND,N2,D2,

26、12,N1,N,ND,DD,1D,12,N1,N,ND,DD,D2,12,句子12有下列三种不同的推导序列:,2.3.4 规范推导和规范归约,最左(最右)推导，是指对于一个推导序列中的每一步直接推导 , 都是对 中的最左(最右)非终结符进行替换。,最右推导也称为规范推导，用规范推导推导出的句型称为规范句型。,2.3.4 规范推导和规范归约,例 设有文法GS:,请给出句子101001的最右、最左推导。,分析 最右推导是指在推导过程中任何一步 (和是句型)，都是对中的最右非终结符进行替换。,SAB,AA0 | 1B,B0 | S1,2.3.4 规范推导和规范归约,S,AB,AS1,AAB1,AA0

27、1,A1B01,A1001,1B1001,101001,句子101001的最右推导为:,SAB,AA0 | 1B,B0 | S1,2.3.4 规范推导和规范归约,最左推导是指在推导过程中任何一步 (和是句型), 都是对的最左非终结符进行替换。,句子101001的最左推导为：,SAB,AA0 | 1B,B0 | S1,S,AB,1BB,10B,10S1,10AB1,101BB1,1010B1,101001,2.3.4 规范推导和规范归约,归约是与推导相对的概念，推导是把句型中的非终结符用规则的一个右部来替换的过程，而归约则是把句型中的某个子串用一个非终结符来替换的过程。,xAyxy,2.3.4

28、规范推导和规范归约,例如，例文法GN1中有规范推导：,则有规范归约：,规范推导的逆过程，称为最左归约，也称为规范归约。,N1,N,ND,N2,D2,12,12,2.3.5 递归规则与文法的递归性,递归规则,如果文法中有规则 AA 称为规则左递归。,如果文法中有规则 A A 称为规则右递归。,如果文法中有规则 A A 称为规则递归。,2.3.5 递归规则与文法的递归性,文法的递归性,2.3.5 递归规则与文法的递归性,例如 文法中有如下规则：,这三条规则都不是递归规则，但有,在文法中使用递归规则，使得我们能用有限的规则去定义无穷集合的语言。,UVx,VUy | z,UVx Uyx ,则该文法是左

29、递归的。,2.3.5 递归规则与文法的递归性,例2 考虑文法GA：,由于该文法无递归性，由它所描述的语言是有穷的。该文法描述的语言为:,AaB | bB,Ba | b,L(GA)= aa, ab, ba, bb ,2.3.5 递归规则与文法的递归性,例3 考虑文法GN1,该文法有直接左递归规则 NND, 则称该文法为左递归文法或说文法左递归，其定义的语言为0,1,2+。,N1N,NND | D,D0 | 1 | 2,2.3.5 递归规则与文法的递归性,也就是说，当一个语言是无穷集合时，则定义该语言的文法一定是递归的。,若不用递归规则，则 NND 需要用 ND | DD | DDD | 即无穷多条规则来定义由数字0,1,2 组成的所有无符号整数。,课堂练习,1 设文法的规则如下：AA1|A0|Aa|Ac|a|b|c ， 该文法的句子是 。 A.bc10 B.bbbb C.bcbc D.1001 2 若一个不含多余规则的文法是递归的，则该文法生成语言的句子个数_。 A. 是有穷的 B. 是无穷的 C. 对具体文法才可以确定 D. 无法确定,