1、12023/6/7School of Computer Science,BUPT第二章第二章 语言及文法语言及文法n主要内容主要内容：n定定义形式形式语言的言的术语n给出文法的定出文法的定义和文法的分和文法的分类n要求掌握：要求掌握：n语言和文法的形式定言和文法的形式定义nCHOMSKY文法体系的分文法体系的分类。22023/6/7School of Computer Science,BUPT第一节第一节 语言的定义与运算语言的定义与运算一、一、语言的一些言的一些术语：n 字母表：字母表：字符的有限集合，字符的有限集合，记为T。n字符串：字符串：由字母表由字母表T中的字符构成的序中的字符构成的
2、序列称字母表列称字母表T上的字符串（句子）。上的字符串（句子）。n 常常记为u,v,w,x,y,z；n 常用常用a,b,c,d 标识单个字符。个字符。32023/6/7School of Computer Science,BUPT字字 母母 表表（Alphabet）概念概念 形式符号的集合形式符号的集合 记号号 常用常用 T、表示表示 举例例-英文字母表英文字母表 a,b,z,A,B,Z -英文英文标点符号表点符号表 ,;:.?!“”()-汉字表字表 ,自自,动,机机,-化学元素表化学元素表 H,He,Li,-T=a,n,y,42023/6/7School of Computer Scienc
3、e,BUPT字字 符符 串串（string）概念概念 字母表字母表 T 上的一个上的一个字符串字符串（简称称串串），或称），或称为 字字（word），），为 T 中字符构成的一个有限序列。中字符构成的一个有限序列。空串空串（empty string）,用用 表示，不包含任何字符。表示，不包含任何字符。举例例 设 T=a,b ，则 ,a,ba,bbaba 等都是串等都是串 字符串字符串 w 的的长度度，记为 w ，是包含在是包含在 w 中字符的中字符的个数。个数。举例例 =0，bbaba =5 ai 表示含有表示含有i个个a的字符串的字符串 52023/6/7School of Computer
4、 Science,BUPT 连接（接（concatenation）设 x,y为串串,且且 x a1a2 am,y b1b2 bn,则 x 与与 y 的的连接接 x y a1a2 am b1b2 bn 连接运算的性接运算的性质 -(x y)z x（y z）-x x x-x y x+y 关关 于于 字字 符符 串串 的的 运运 算算62023/6/7School of Computer Science,BUPT 其它其它 如如 取取头字符字符，取尾部取尾部，子串匹配子串匹配 等等n 设1,2,3是是字字母母表表T上上的的字字符符串串，称称1是是字字符符串串12的的前前缀，2是是字字符符串串12的的
5、后后缀，且且2是是字符串字符串123的子串。的子串。n 空串是任何字符串的前空串是任何字符串的前缀，后，后缀及子串。及子串。n 例例：abc的前的前缀 a ab abc.后后缀 c bc abc.子串子串 a b c ab bc abc ,即一个字符串可以看作是多个字符串的即一个字符串可以看作是多个字符串的连接。接。关关 于于 字字 符符 串串 的的 运运 算算72023/6/7School of Computer Science,BUPTn 字符串字符串的逆用的逆用 表示。表示。是是字符串字符串的倒置。的倒置。=b1b2bn =bnbn-1b2b1n 空串空串的逆的逆还是是82023/6/7
6、School of Computer Science,BUPT字字 母母 表表 的的 幂 运运 算算 幂运算运算 设 T 为字母表，字母表，n 为任意自然数，任意自然数，定定义（1）T0=（2）设 x Tn-1，a T，则a x Tn （3）Tn 中的元素只能由（中的元素只能由（1）和）和（2）生成）生成 闭包包 T*=T0 T1 T2 闭包包 T+=T1 T2 T3 T*=T+，T+=T*92023/6/7School of Computer Science,BUPT闭包的物理意包的物理意义 T的星号的星号闭包包T*：字母表T上的所有字符串和空串的集合。T的正的正闭包包T+：字母表T上的所有
7、字符串构成的集合。T*=T+举例例 设 T=0，1 ，则 T0=，T1=0，1 ，T2=00，01，10，11 ，T*=，0，1，00，01，10，11，T+=0，1，00，01，10，11，102023/6/7School of Computer Science,BUPT语 言（Languages）概念概念 设设 T 为字母表，则任何集合为字母表，则任何集合 L T*是是字字母表母表T上的上的一个语言（一个语言（language）举例举例 -英文单词集英文单词集 ,English,words,-C 语言程序集语言程序集 字母表？字母表？-汉语成语集汉语成语集 ,马到成功马到成功,-化学分子式
8、集化学分子式集 ,H2O,NaCl,-any,112023/6/7School of Computer Science,BUPT语 言（Languages）举例举例：设T=a，b 则 L1 =anbn|n1 L3=bk|k 是是质数数 L2 =只有一个空句子的只有一个空句子的语言言 L4=空空语言言 均均为字母表字母表T上的上的语言。言。由由语言的定言的定义知知语言是集合，言是集合，对于集合的运算可于集合的运算可应用于用于对于于语言的言的计算。如并，交，算。如并，交，补，差。，差。122023/6/7School of Computer Science,BUPT语言的基本运算 语言的积：语言的
9、积：两个语言L1 和L2的积L1 L2是由L1和L2中的字符串连接所构成的字符串的集合。即L1中所有字符串分别与L2中的字符串连接得到的集合。设T=a,b，L1和 L2是T上的语言。L1=ab,ba L2=aa,bb则 L1 L2=abaa,abbb,baaa,babb L2 L1=aaab,aaba,bbab,bbban L1 L2 L2 L1 语言的言的积不可交不可交换。132023/6/7School of Computer Science,BUPT语言的基本运算 语言的幂：语言的幂：语言的言的幂可可归纳定定义如下如下:L0=Ln=L Ln-1=Ln-1 L n 1上例中，上例中，L12
10、=abab,abba,baab,baba L22=aaaa,aabb,bbaa,bbbb 142023/6/7School of Computer Science,BUPT第二节 文法n定义：所：所谓文法是用来定文法是用来定义语言的一个数学模型言的一个数学模型n表示语言的方法：n若若语言言L是有限集合，可用是有限集合，可用列举法n若若L是是无无限限集集合合（集集合合中中的的每每个个元元素素有有限限长度度），用其他方法。用其他方法。n方方法法一一：文文法法产生生系系统，由由定定义的的文文法法规则产生出生出语言的每个句子言的每个句子n方方法法二二：机机器器识别系系统：当当一一个个字字符符串串能能被
11、被一一个个语言言的的识别系系统接接受受，则这个个字字符符串串是是该语言的一个句子，否言的一个句子，否则不属于不属于该语言。言。152023/6/7School of Computer Science,BUPT元语言元语言n定定义：描述描述语言的言的语言言例如：各种各例如：各种各样的程序的程序设计语言言n当当人人们要要解解释或或讨论程程序序设计语言言本本身身时，又又需需要要一一种种语言言，被被讨论的的语言言叫叫做做对象象语言言，即即某某种种程程序序设计语言，言，讨论对象象语言的言的语言称言称为元元语言言。162023/6/7School of Computer Science,BUPTBNF（巴
12、科斯范式）巴科斯范式）BNF范式通常被作为讨论某种程序设计语言语法的元语言n:=0|1|2|9 :=“定义为”n:=A|B|C|Z|a|b|z :=|.n通过上述定义可知，所有以字母开头的，由字母和数字组成的字符串都是标识符。nBNF定义了一种语言，其中标识符如上定义。nBNF描述它所定义的语言，为元语言。172023/6/7School of Computer Science,BUPTn例如：汉语语法中定义了句子的结构由主语、谓语、宾语组成。这里主谓宾只是描述了句子的结构，并不是句子。而按照这种结构组成的建立在汉字上的字符串就是句子。如他是学生。n文文法法是是一一种种元元语言言，一一种种方方
13、法法，根根据据文文法法产生出生出语言的句子。言的句子。182023/6/7School of Computer Science,BUPT三、Chomsky文法体系n例如：BNF:=:=:=:=a|b|z|A|B|Z :=0|1|9将:=改为表示可被代替用I,L,D分别表示标识符、字母、数字;192023/6/7School of Computer Science,BUPT则上述表达式可以表示上述表达式可以表示为 IL IIL IID La|b|.|z D0|1|.9这就是一个文法的生成式集合。就是一个文法的生成式集合。202023/6/7School of Computer Science,B
14、UPTnChomsky文法体系中，任何一种文法必须包含有两个不同的有限符号的集合，即非终结符集合N和终结符集合T。一个形式规则的有限集合P（生成式集合），一个起始符S。nP中的生成式是用来产生语言句子的规则，而句子则是仅由终结符组成的字符串。这些字符串必须从一个起始符S开始，不断使用P中的生成式而导出来。n可见文法的核心是生成式的集合，它决定了语言中句子的产生。212023/6/7School of Computer Science,BUPT文法的形式定义n文法G是一个四元组G=(N，T，P，S)，其中N 非终结符的有限集合T 终结符的有限集合 NT=P 形式为的生成式的有限集合。且(NT)*
15、N+(NT)*,(NT)*S 起始符 且S N。222023/6/7School of Computer Science,BUPTn将上例用文法表示G=(N，T，P，S)N=I,L,DT=a,b,c,z,0,1,9P=I,La,D0,D9S=I n文法是语言的产生系统，研究怎样构造文法能产生出符合要求的句子。232023/6/7School of Computer Science,BUPT四推导与句型1、直接推导设G=（N,T,P,S）是文法，若A是P中的生成式，和是（NT）*中的字符串，则有A=称A直接推导出，或说是A的直接推导。242023/6/7School of Computer Sc
16、ience,BUPTn设 G=(N,T,P,S)是 文 法，、0、1n、都 是（NT）*中的字符串，且=0、=n，其中i直接推导出i+1（0in）,则称序列0=1=2=n是长度为n的推导序列，而=0是长度为0的推导序列。n对推导出记为，若推导序列长度大于0，则记为 。n推导序列的每一步，都产生一个字符串，这些字符串一般称为句型。2、推导序列252023/6/7School of Computer Science,BUPT3、句型和句子n句型字符串字符串是文法是文法G的句型，当且的句型，当且仅当当S ，且且（NT）*。n 句子是是G的的句句子子，当当且且仅当当S,且且T*。（是由是由终结符符组成
17、的字符串）成的字符串）例：例：I=L=a I=IL=LL=zL=zbn句型包含句子262023/6/7School of Computer Science,BUPT4文法产生的语言由文法由文法G产生的生的语言言记为L(G)。L(G)=|T*且且S 或：或：L(G)中中的的一一个个字字符符串串，必必是是由由终结符符组成的，并且是从起始符成的，并且是从起始符S推推导出来的。出来的。272023/6/7School of Computer Science,BUPT第三节 Chomsky文法体系分类n文法文法 G=(N,T,P,S)；P:其中其中（NT）*N+（NT）*（NT）*属于属于Chomsky
18、文法体系文法体系n该体体系系对生生成成式式的的形形式式做做了了一一些些规定定，分分为四四类，即，即0型、型、1型、型、2型、型、3型文法型文法n0型文法：无限制文法型文法：无限制文法对应的语言：递归可枚举语言，与图灵机等价。282023/6/7School of Computer Science,BUPT1型文法n也称上下文有关文法（也称上下文有关文法（CSG：Context-sensitive Grammar)生成式的形式生成式的形式为，其中其中|，（NT）+，（NT）*N+（NT）*n对应的的语言：上下文有关言：上下文有关语言（言（CSL：Context-sensitive Languag
19、e)n若不考若不考虑，与与线性有界自性有界自动机（机（LBA,Linear Bounded Automaton）等价。等价。292023/6/7School of Computer Science,BUPT2型文法n也也称称上上下下文文无无关关文文法法（CFG：Context-free Grammar)A,AN,且且（NT）*n对应的的语言言：上上下下文文无无关关语言言（CFL：Context-free Language)。n对 应 的的 自自 动 机机：下下 推推 自自 动 机机（PDA：Pushdown Automaton)。302023/6/7School of Computer Sci
20、ence,BUPT3型文法也称正也称正则文法文法n右右线性文法（性文法（Right-linear Grammar）：）：AB 或或 AA、BN,T*。n左左线性文法（性文法（Left-linear Grammar）：）：AB或或 AA、BN,T*。n对应的的语言：正言：正则语言言n对 应 的的 自自 动 机机：有有 限限 自自 动 机机（Finite Automaton）。）。312023/6/7School of Computer Science,BUPT例例1：G=(A,B,C,a,b,d,P,A)P:AAB，ABCAAB，Ad，Ba，Cb 是是1型文法。型文法。A=dA=AB=dB=da
21、A=AB=ABB=dBB=daB=daaA=AB=CAAB=bAAB=bdAB=bdCAAB=bdbAAB=bdbdAB=bdbddB=bdbdda322023/6/7School of Computer Science,BUPT例例2：G=(A,B,C,a,b,c,P,A)P:Aabc AaBbc BbbB BcCbcc bCCb aCaaB aCaa 是是1型文法。型文法。其定其定义的的 L=anbncn|n1n A=abcn A=aBbc=abBc=abCbcc=aCbbcc=aabbcc =aaBbbcc332023/6/7School of Computer Science,BUPT
22、例例3：G=(S,B,C,a,b,P,A)P:SaC,SbB,BaS,BbBB,Ba,CbS,CaCC,Cb 是是2型文法型文法 n S=aC=ab nS=aC=aaCCnS=aC=abS=abaC=ababS=ababaC=abababnS=bB=bbBB=bbaSB=bbaaCB=bbaabB=bbaaba342023/6/7School of Computer Science,BUPT例例4：G=(A,B,C,a,b,c,P,A)P:ABa；Ac；BCb；Ccn左左线性文法性文法n L=c,cba 正正则语言言n注注意意：已已知知语言言求求文文法法，文文法法不不是是唯唯一一的的，即即可可以以有不同的表达方法有不同的表达方法。352023/6/7School of Computer Science,BUPT四类文法之间的关系n只是只是对生成式形式加以限制生成式形式加以限制n0型型 无限制无限制n1型型 不允不允许A形式形式n2型型n3型型 属于属于2型型n不不含含A的的2型型、3型型属属于于1型型，1型型、2型、型、3型均属于型均属于0型。型。
个人主页
