文法和语言09年9月.ppt

1、1,第3章 文法和语言,3.1 文法的直观理解 3.2 字符串及其运算 3.3 文法的形式定义 3.4 文法的类型 3.5 递归规则与递归文法 3.6 规范推导与句柄 3.7 语法树和二义性 3.8 语言和文法构造讨论和小结 3.9 文法的实用限制和变换,2,3.1 文法的直观理解,在C语言中的赋值语句： a=b+c*60; a+b=c*60; 问： 1、如何分析哪句是非法的？ 2、计算机不知道它们是赋值语句，如何确定使用哪一套句型？,3,语言的基本概念,（1）语法指一组规则，使用这组规则，可以产生一个合适的程序； 包括：词法规则（字符组成单词） 语法规则（单词组成语法单元） （2）语义赋予程

2、序意义的规则 例如：数据类型匹配、变量是否声明、变量作用域 静态语义：合乎语法的程序要遵守的语义规则 动态语义：表明程序要做什么,4,文法：即 语言的表述方法,把一门语言的句子描述清楚，就把这门语言表述出来了，这种表述方法就称为文法。,两种方式： 1、有穷语言只需列出句子2、无穷语言要给出有穷表示法,5,用一组规则表述语言的例子,构成规则： | 我 | 你 | 他 王明 | 大学生 | 英语 是 | 学习 | 从上述规则产生句子“我是大学生”的例子： 我我我是我是我是大学生,“”表示： 使用一条规则，代替左端的某个符号，产生右端的符号串,6,文法的直观表示 文法由四部分组成： 一组非终结符：，

3、一组终结符：我，你，他，王明，一个开始符号：一组产生式：，,7,3.2 字符串及其运算,字母表： 元素的非空有穷集合。 例：0，1，a，b，c。 V1 = a, b, c, , z 英语小写字母表 V2 = book, pencil, pen, paper V2 也是字母表（单词表） 字母表中的元素称为符号，字母表也称符号集。程序语言的字母表由字母数字和若干专用符号组成。,8,符号串：由字母表中的符号组成的任何有穷序列称为该字母表上的符号串。 例：字母表0，1，a，b，c 0，00，01，10，等是上的符号串。 a，b，c，ab，aaca，是A上的符号串。 不含任何符号的符号串称为空串，用表示

4、。 符号串长度表示符号串中含有符号的个数。 例：|abc|3，|0,3.2 字符串及其运算,9,串的连接： 符号串x和y的连接xy，是把y的符号写在x的符号之后得到的符号串。 例如 xST，yabu，则 xySTabu 显然 x x x,3.2 字符串及其运算,10,设z = xy是符号串，则称x是z的头，y是z的 尾。 若y非空，则x是z的真（固有）头或真前缀。 若x非空，则y是z的真（固有）尾或真后缀。 例7: 设z = abc, 则 z的头有, a, ab, abc, 除了abc，其余都 是固有头；,11,串的方幂： 符号串x自身n次连接记作xn ，称为串x的方幂。 x0 (n0) x1

5、x (n1) x2xx (n2) xnxxn-1xn-1x (n0)例：xAB， x0， x1AB， x2ABAB,3.2 字符串及其运算,12,串的集合：由某字母表上的符号串组成的集合称为该字母表上的符号串集合，简称串集合。 串集合的乘积：符号串集合A和B的乘积AB定义为： AB xy|xA且yB，即AB是由A中的串x和B中的串y连接而成的串xy组成的集合。例：设 Aa，b ，Bc，d， 则 ABac，ad，bc，bd 显然AAA,3.2 字符串及其运算,13,串集合的闭包：符号串集合A的闭包A* 定义如下： A*A0A1A2A3例：设字母表 =0，1, (字母表是串集合) 则*012 ,0

6、,1,00,01,10,11,即*表示字母表上符号的任意串的集合。,3.2 字符串及其运算,+123称为A的正闭包。显然 *0+0 星闭包 +*,14,3.3 文法的形式定义,定义 文法G定义为四元组（VN，VT，P，S）, 其中：VN：非终结符集； VT：终结符集， 并且 VNVT； P：产生式集合；S： 开始符号或识别符号； P中产生式形式为：，,其中：V+且至少含一个非终结符，V*， 而 VVNVT，V 称为文法 G 的字母表。,例：G（S，0，1，S0S1，S01，S）,15,文法的简化表示法 通常不用将文法G的四元组显示表示，只写出产生式。约定： 第一条产生式的左部是开始符号或用GS

7、表示S是开始符号； 用大写字母(或用尖括号括起来)表示非终结符； 用小写字母表示终结符。 左部相同的产生式A，A可以记为： A|，其中“|”是“或”的意思， ，分别称为侯选式。,3.3 文法的形式定义,16,例：文法GS： SA | SA | SD Aa | b | | z D0 | 1 | | 9 参看 课本P35例3.2,3.3 文法的形式定义,17,3.3 文法的形式定义,例：给定一个简化的表达式的文法Ge，设： Ge = ( VN, VT, P, S )； VN = E ；VT =+,* , ( , ) , i ；S=E； P由下列产生式组成： EE+E EE*E E(E) Ei,18

8、,直接推出与直接规约 直接推出：当是一个产生式，且,V*。如果有，我们称直接推出。 例：有产生式S0S1，则有S0S1；0S100S11 直接推出就是用产生式的右部替换产生式的左部的过程。,3.3 文法的形式定义,19,直接归约：当是一个产生式，且,V*。如果有，我们称是的直接规约。可记为。 直接规约就是用产生式的左部替换产生式的右部的过程。,3.3 文法的形式定义,20,推导与规约如果存在直接推导的序列： w0w1w2wn则称该序列是从w0至wn的一个推导，或wn到w0的规约。若存在w0到wn的推导，则称w0可推导出wn，或wn可规约到w0 。用w0wn表示从w0经至少一步可推导出wn。用w

9、0wn表示从w0经0步或若干步可推导出wn。,3.3 文法的形式定义,+,*,21,3.3 文法的形式定义,句型、句子与语言 句型：由文法开始符号S推导出的符号串 （即S）称为文法GS的句型。句子：仅由终结符组成的句型（即S，VT*）称为文法GS的句子。 语言：文法GS的一切句子的集合称为语言，记做L（G），即L（G）| S，且VT* ,*,*,22,3.3 文法的形式定义,例：GS：S0S1|01 S0S100S11000111 S，0S1，00S11，000111都是句型，000111是句子。L（G）01,0011,000111, 0n1n | n1 ,23,3.3 文法的形式定义,例：给

10、定一个简化的表达式的文法Ge，设： Ge = ( VN, VT, P, S )； VN = E ；VT =+,* , ( , ) , i ；S=E； P由下列产生式组成： EE+E推导：E=(E) EE*E =(E+E) E(E) =(i+E) Ei = (i+i) ,24,v w 所用规则 x y E (E) (E) (E+E) ( ) (E+E) (i+E) ( +E) (i+E) (i+i) ( i + ),例24 以下是上例的推导过程,25,3.3 文法的形式定义,等价文法若L（G1）L（G2），则称文法G1和G2等价例：G1: SO S 1|0 1 G2: A0 R|0 1RA 1

11、因为 L(G1) 0n1n | n1 ，L(G2) 0n1n | n1 L(G1)，所以 G1与G2等价。 不同的文法产生相同的语言,26,书写符号约定,非终结符用大写字母A,B,C,表示,S,Z用作开始符 终结符用小写字母a,b,c, 表示 Z,Y,X, 表示文法符号 u,v,w,x, 表示符号串 第一条规则的左部符号是开始符,在上述约定下，给出规则式集合，也就给出了文法,27,3.4 文法的类型,Chomsky按产生式的形式把文法分成4类： 0型、1型、2型和3型。 后三种类型文法，是通过对0型文法的产生式施加限制而形成的。,28,0 型文法,3.4 文法的类型,定义：每个产生式都满足：

12、V+且至少含一个非终结符，V*。 0型文法对产生式没有加上任何限制。又称短语文法，有时也称为无限制文法。 0型语言由图灵机（Turing machine-TM）识别。,29,1 型文法,3.4 文法的类型,定义1：对每一个产生式都满足： |， 仅仅 S除外。 定义2：每一个产生式都形如： 1A212；其中：1、2、V*且 ，AVN。 上下文有关语言用线形界限自动机 (Liner bounded automata-LBA) 识别,只有当A出现在1和2的上下文中，才允许用替换A。,课本P37 例3.3,30,2 型文法,3.4 文法的类型,定义：对每一个产生式A都满足：AVN，V*。 即用取代非终

13、结符A时,与A所在的上下文无关。 上下文无关语言用下推自动机（push down automata-PDA）识别。上下文无关文法用于描述程序语言的语法规则。,31,3 型文法,3.4 文法的类型,定义：每个产生式都形如：AaB或Aa， 其中：A、BVN，aVT。也称为：正规文法。 即用取代非终结符A时,与A所在的上下文无关。 正则语言用有穷自动机（finite automataFA）识别。正规文法用于描述程序语言的词法规则。,32,四种文法之间的关系：,3.4 文法的类型,由于四种文法是按照将产生式做进一步限制而 定义的，所以它们之间是逐级“包含”的关系，由四 种文法产生的语言也是逐级“包含”

14、的关系。即： 3型语言类 2型语言类 1型语言类 0型语言类,课本P39各例，,33,3.5 规范推导与句柄,最左(最右)推导如果在句子的每步推导中都坚持替换当前句型中的最左（最右）非终结符，那么句子的这种推导过程称为最左（最右）推导。 最右推导也称为规范推导；由规范推导产生的句型称为规范句型。,34,例：文法G：EE+T | TTE*F | FF（E）| i句子i+i*i 的推导过程如下：最左推导： EE+TT+TF+Ti+Ti+T*F i+F*Fi+i*Fi+i*i最右推导： EE+TE+T*FE+T*iE+F*i E+i*iT+i*iF+i*ii+i*i,3.5 规范推导与句柄,35,注

15、意： 最右推导的逆过程是最左归约，称为规范归约。 最左（右）推导推出的句型称为左（右）句型。 右句型又称为规范句型。 任何句子都有规范推导，但句型则不一定有规范推导。,3.5 规范推导与句柄,36,定义：设是文法GS中的一个句型，如果 有SA且A，则称是句型相对于非终结符A的短语。 特别地如有A，则称是句型相对于规则A的直接短语 (简单短语)。 一个句型的最左直接短语称为该句型的句柄。,*,+,3.5 规范推导与句柄,37,例： T*(i+T)+F是文法Ge的句型，求其全 部短语、简单短语和句柄：,3.5 规范推导与句柄,38,3.5 规范推导与句柄,39,例：文法GE的一个句型T*F+i 短

16、语有： T*F，i，T*F+i 直接短语有：T*F，i 句柄为： T*F,3.5 规范推导与句柄,40,3.6 语法树和二义性,定义给定文法GS，满足以下条件的有序树称为GS的一棵语法树(推导树）。 每个结点都被标记为某个终结符或非终结符。 非叶子结点只能用非终结符标记。 树根用开始符S标记。 如果结点A有n个孩子结点(从左到右)：X1,X2,Xn, 则GS 一定有产生式：AX1X2Xn ； XiV,41,3.6 语法树和二义性,例：文法Ge中的一棵语法树,语法树是文法中有关句型的语法树。对于文法中的任何句型都能构造与之关联的语法树。 叶子结点没有孩子的结点 分支非叶子结点连同其全部孩子(直接

17、孩子)。 简单分支如果分支的孩子结点全是叶子结点 子树非叶子结点连同其全部后裔（直接孩子和间接孩子）。,42,3.6 语法树和二义性,例：构造文法Ge的句型T*(i+T)+F的语法树(推导的每一步对应一个分支),E=E+T,=T*F+T,=T*(E)+T,=T*(E+T)+T,=T*(T+T)+T,=T*(F+T)+T,=T*(i+T)+T,=T*(i+T)+F,43,3.6 语法树和二义性,例32：对于句型T*(i+T)+F的语法树逐次减去 一个叶子分支的孩子，可得到一个归约序列。,E+T =,T*F+T=,T*(E)+T =,T*(E+T)+T =,T*(T+T)+T =,T*(F+T)+

18、T =,T*(i+T)+T =,T*(i+T)+F,E=,44,3.6 语法树和二义性,对语法树有以下结论： 语法树的叶子结点从左至右组成的符号串 对应文法中的一个句型 每一句型推导都有一棵对应的语法树，但 每一语法树至少对应一个推导。语法树与推 导顺序无关，更能从本质上反映语法结构。 每一分支表示一个直接推导,45,3.6 语法树和二义性,子树与短语的关系： 每个子树的叶子串是相对于该子树的根的短语 每个叶子分支(简单子树)的叶子串是一简单短语 最左的叶子分支的叶子串是句柄（最左简单短语）,当u满足： S=xAy 且 A=u u是句型xuy的短语，也就是说 1) u可以归约到A； 2)原句型

19、归约后仍为一个句型。,*,+,46,3.6 语法树和二义性,定义如果一个句子存在不止一棵语法树， 则称该句子是二义性的。如果一个文法包含有二 义性的句子，则称该文法是二义性的。 注意： 二义性是指文法，不是指语言。如果一个语言不存在无二义性文法，才是二义性的语言。 句子的二义性是指文法上的，不是语义的。 文法的二义性是不可判定的，实践中只能给出一些判断的充分条件。,47,3.6 语法树和二义性,例：二义性文法 Ge: EE+E | E*E | (E) | i 对句子i*i+i可画出两棵不同的语法树： 对应有两个不同的最左推导 E=E+E=E*E+E=i*E+E=i*i+E=i*i+i E=E+

20、E=i*E=i*E+E=i*i+E=i*i+i,48,例：文法GIF也是二义性的 GIF: Sif b then S else S Sif b then S Sa 句子if b then if b then a else a对应两棵语法树： S S if b then S if b then S else S if b then S else S if b then S a a a a,3.6 语法树和二义性,49,3.6 语法树和二义性,对二义性的处理： 把二义性文法变换为无二义性的。如可把文法Ge变换为文法GE Ge: EE+E|E*E|(E)|i GE: EE+T|T TT*F|F F(

21、E)|i 附加去掉二义性的信息。 如if语句，规定else只与紧前的未配对 的then配对。,3.7 语言和文法构造讨论,已知文法，写出相应语言描述（是唯一的） 例如：文法GS： SbS | a 已知语言描述，写出相应文法（可能不止 一个） 例如：若语言由0、1符号串组成，串中0 和1的个数相同，构造其文法。,3.7 语言和文法构造讨论,例：设文法为G1 = ( VN, VT, P, N )，其中 VN = N, D , VT = 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 , P =产生一个合法的句子使用规则次数为： NND ND D0|1|2|3|4|5|6|7|8|9 ,m

22、-1 NDm-1,1 Dm,m dm,如: N = ND = NDD = NDDD = DDDD = 2DDD = 20DD = 200D = 2005,则语言L (G1) = m位整数 | m0 ,52,例：设文法G2=(VN,VT,P,S)，其中 VN = S, A, B , VT = a , b , P = 产生一个合法句子使用规则次数为 SAB AaA Aa BBb Bb ,1 AB,m-1 am-1AB,1 amB,1 ambn,n-1 amBbn-1,如：S = AB = aAB = aaAB = aaaB = aaab,则语言L(G2) = ambn | m,n0 ,3.7 语言

23、和文法构造讨论,53,例：设文法G3 = (VN,VT,P,S)，其中 VN =S,B,C, VT=a,b,c, P = 产生一个合法句子使用规则次数为 SaSBC SaBC CBBC aBab bBbb bCbc cCcc ,n-1 an-1S(BC) n-1,n-1 anbnCn,n-1 anbncn,1 an (BC)n,1 anbBn-1Cn,1 anbncCn-1,? anBnCn,如：S =aSBC =aaSBCBC =aaaBCBCBC =aaabCBCBC =aaabBCCBC =aaabBCBCC =aaabBBCCC,3.7 语言和文法构造讨论,54,= aaabbBCCC

24、 = aaabbbCCC = aaabbbcCC = aaabbbccC = aaabbbccc,则语言L(G3)= anbncn | n0,3.7 语言和文法构造讨论,可转向37页,55,例：已知语言L= an | n0 ，构造相应的文法。 观察语言L中的句子 a , aa , aaa , ,G1S：S aS ；S a G2S：S Sa ；S a,3.7 语言和文法构造讨论,56,语言和文法构造方法小结,3.7 语言和文法构造讨论,57,3.7 语言和文法构造讨论,3.8 递归规则与递归文法,1、递归的概念 所谓递归，是指： 同一个（或一组）操作的连续重复； 一种处理过程的性质，这种过程的某

25、一步要用到它自身的上一步（或上几步）的结果。 递归定义是指在定义某事物时，又用到该事物本身。,3.8 递归规则与递归文法,递归规则是指在规则的左部和右部具有相同的非终结符的规则。一条规则实际上是对左部的非终结符的定义，因此，递归规则就是一条递归定义。 例：规则式 + * () 是递归规则。,3.8 递归规则与递归文法,定义：形如AAy 的规则称为左递归规则； 形如AxA 的规则称为右递归规则； 形如AxAy且x,y的规则称为内递归规 则，或自嵌入规则； 若文法中至少包含一条递归规则，则称此 文法是直接递归的。 若对文法以下推导成立 A=Ay 或 A =xA 或 A =xAy (x,y) 则称文

26、法为间接左递归，或间接右递归，或间接内递归。,3.8 递归规则与递归文法,递归文法的判别 若文法中存在A，可建立推导A=xAy，则该文法是递归的。 例：文法G:SaB | bB Ba | b 是非递归的。 表达式文法Ge是递归的。 递归文法的作用 可用有穷的文法描述无穷语言。因此，描述程序设计语言的文法必定都是递归文法。,例：一种算术表达式的递归定义： 变量 i 是算术表达式； 若E1和E2是算术表达式，则E1+E2，E1*E2和（E1）也是算术表达式。 用文法来描述：,文法Ge：E i | E+E | E*E | ( E ) 定义了由变量、+、*、（ 和 ）组成的算术表达式的语法结构。,3.

27、8 递归规则与递归文法,递归文法能定义什么样的语言？课本P37例3.3，参看,63,3.9 文法的实用限制和变换,文法G中形如UU的规则，称为有害规则。 文法G中某一规则， Uu，若满足下列条件之一，称为多余规则： （1）左部非终结符号U不出现在任何其他规则的右部（U为开始符号除外）； （2）若在推导中使用该规则，则再也不能推出终结符号串。 例：请找出下面文法的有害规则和多余规则 SBe AAe|A|e BCe|Af CCf Df,64,对于文法的实用限制主要有两点： 不能有有害规则和多余规则。 另外，实际处理中，可能还有以下的限制： 1）文法中开始符号S不出现在规则的右部； 2）文法中不含有

28、形如 AB , A,B Vn 的特殊规则； 3）文法中不含有左递归规则AAa ； 4）文法中不允许有空规则 A。 如果文法G中所有规则均满足实用限制条件， 则称文法G是压缩或简化过的。,3.9 文法的实用限制和变换,65,定理对任一个型文法G，都可以构造 文法G，使得L(G)=L(G)，并且G具有下 述特点： (1) 开始符S不出现在规则的右部； (2) 每个非终结符A都能推出终结符串； (3) 每个非终结符A都能出现在某个句型中； (4) 没有AB形式的规则； (5) 没有空规则（相差一个）； (6) 不含左递归规则。,3.9 文法的实用限制和变换,66,由G构造G的算法： ( 1 )开始符

29、S不出现在规则的右部； 引入新的开始符S0，并令 VN=VNS0 =PS0S ( 2 )每个非终结符A都能推出终结符串； 令N=A | 存在At且tVT* 递归扩充N N=NB | 存在Bx且x(VTN)* = Cy|CN或存在Dy且DN ,3.9 文法的实用限制和变换,可能不止B一个，其它的以此类推。,67,例：设有文法G G:ABcd 则G的构造过程为 AdDN=B BABN=BA=A,B Bb 从G删去关于D和E的规则 DEa以及右部包含E和D的所有 DAD规则得 DDBG:ABcd EDa BAB EEb Bb,3.9 文法的实用限制和变换,( 3 )每个非终结符A都能出现在某个句型中； 令N=S 递归扩充N N=NB | 存在Ax且AN, Bx P=PCy | CN,69,( 4 ) 消除单规则AB 对每个非终结符A， 求N=B | A=B, BVN =PAx|存在BxP, BN,xV* = AB | A,BVN = Cy | Cy是无用规则,3.9 文法的实用限制和变换,+,用新规