形式语言与自动机语言及文法课件.ppt
College of Computer Science&Technology,BUPT,引言,复习：什么是形式语言？什么是文法？什么是自动机？形式语言的定义方式？研究形式语言与自动机的意义？问题的提出？本章关注 语言与文法如何描述（产生）左右括号匹配的语言？如何描述（产生）数学表达式？,College of Computer Science&Technology,BUPT,引言,知识点：形式语言所研究的问题：产生语言，根据语言中的基本句子和其它句子的形成“规则”，得到（产生）语言所包含的所有句子。,College of Computer Science&Technology,BUPT,第一节 语言的定义与运算,一、语言的一些术语：字母表：字符的有限集合，记为T。字符串：由字母表T中的字符构成的序列称字母表T上的字符串（句子）。常记为u,v,w,x,y,z；常用a,b,c,d 标识单个字符。,College of Computer Science&Technology,BUPT,字 母 表（Alphabet）,概念 形式符号的集合 记号 常用 T、表示 举例 英文字母表 a,b,z,A,B,Z 英文标点符号表,;:.?!“”()汉字表,自,动,机,化学元素表 H,He,Li,T=a,n,y,任,意,College of Computer Science&Technology,BUPT,字 符 串（string）,概念 字母表 T 上的一个字符串（简称串），或称为 字（word），为 T 中字符构成的一个有限序列。空串（empty string）,用 表示，不包含任何 字符。举例 设 T=a,b，则,a,ba,bbaba 等都是串 字符串 w 的长度，记为 w，是包含在 w 中字符的个数 举例=0，bbaba=5 ai 表示含有i个a的字符串,College of Computer Science&Technology,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,关 于 字 符 串 的 运 算,College of Computer Science&Technology,BUPT,其它 如 取头字符，取尾部，子串匹配 等 设1,2,3是字母表T上的字符串，称：1是字符串12的前缀，2是字符串12的后缀，2是字符串123的子串。空串是任何字符串的前缀，后缀及子串。例：abc的前缀 a ab abc.后缀 c bc abc.子串 a b c ab bc abc,即一个字符串可以看作是多个字符串的连接。,关 于 字 符 串 的 运 算,College of Computer Science&Technology,BUPT,字符串的逆用 表示。是字符串的倒置。=b1b2bn=bnbn-1b2b1 空串的逆还是,College of Computer Science&Technology,BUPT,字 母 表 的 幂 运 算,幂运算 Tn 用来表示 该字母表长度为n的所有串的集合。设 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*,College of Computer Science&Technology,BUPT,闭包的物理意义,T的星号闭包T*：字母表T上的所有字符串和空串的集合。T的正闭包T+：字母表T上的所有字符串构成的集合。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，,College of Computer Science&Technology,BUPT,概念 设 T 为字母表，则任何集合 L T*是字母表T上的一个语言（language）。隐含的概念：如何表述子集的“特性和规则”，举例-左右括号的匹配。英文单词集,English,words,C 语言程序集 字母表？汉语成语集,马到成功,化学分子式集,H2O,NaCl,any,任意,语 言（Languages）,College of Computer Science&Technology,BUPT,语 言（Languages）,举例：设T=a，b 则 L1=anbn|n1 L3=bk|k 是质数 L2=只有一个空句子的语言 L4=空语言 均为字母表T上的语言。由语言的定义知语言是集合，对于集合的运算可应用于对于语言的计算。如并，交，补，差。,College of Computer Science&Technology,BUPT,语言的基本运算,语言的积：两个语言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,bbba L1 L2 L2 L1 语言的积不可交换。,College of Computer Science&Technology,BUPT,语言的基本运算,语言的幂：语言的幂可归纳定义如下:L0=Ln=L Ln-1=Ln-1 L n 1上例中，L12=abab,abba,baab,baba L22=aaaa,aabb,bbaa,bbbb,College of Computer Science&Technology,BUPT,语言举例,例1：括号匹配的语言及产生该语言指所有左右括号相匹配的字符串如何“产生”这个语言？规则？递归定义提供了集合的定义方式。构造规律。基础：定义该集合的最基本的元素，“（）”递归：若S是合法串，则：（S）是合法串；SS 是合法串；,College of Computer Science&Technology,BUPT,语言举例,例2：程序设计语言中算数表达式的语言运算符A：+、-、*、/利用递归定义方式。重点是构造规律。基础：单个变量是最基本的串，i,递归：若S是合法串，则：SAS 是合法串；（S）是合法串；,College of Computer Science&Technology,BUPT,语言举例,例3：标识符语言及产生该语言指所有字母开头后接字母或数字的字符串如何“产生”这个语言？规则？递归定义提供了集合的定义方式。构造规律。基础：单个字母是最基本的元素，递归：若S是合法串，则：SL 是合法串；SD 是合法串；L：字母；D：数字。,College of Computer Science&Technology,BUPT,第二节 文法,本节提纲文法的作用文法的形式定义推导与句型文法产生语言,College of Computer Science&Technology,BUPT,2.1 文法的作用,定义：所谓文法是用来定义语言的一个数学模型表示语言的方法：若语言L是有限集合，可用列举法若L是无限集合（集合中的每个元素有限长度），用其他方法。方法一：文法产生系统，由定义的文法规则产生出语言的每个句子方法二：机器识别系统：当一个字符串能被一个语言的识别系统接受，则这个字符串是该语言的一个句子，否则不属于该语言。,College of Computer Science&Technology,BUPT,2.1文法的作用-元语言,元语言定义：描述语言的语言例如：各种各样的程序设计语言当人们要解释或讨论程序设计语言本身时，又需要一种语言，被讨论的语言叫做对象语言，即某种程序设计语言，讨论对象语言的语言称为元语言。,College of Computer Science&Technology,BUPT,BNF（巴科斯范式）,BNF范式通常被作为讨论某种程序设计语言语法的元语言:=0|1|2|9:=“定义为”:=A|B|C|Z|a|b|z:=|.通过上述定义可知，所有以字母开头的，由字母和数字组成的字符串都是标识符。BNF定义了一种语言，其中标识符如上定义。BNF描述它所定义的语言，为元语言。,College of Computer Science&Technology,BUPT,例如：汉语语法中定义了句子的结构由主语、谓语、宾语组成。这里主谓宾只是描述了句子的结构，并不是句子。而按照这种结构组成的建立在汉字上的字符串就是句子。如:他是学生。,College of Computer Science&Technology,BUPT,文法是一种元语言，一种定义方法。根据文法产生出语言的句子。,College of Computer Science&Technology,BUPT,2.1文法元语言,例如：BNF:=:=:=:=a|b|z|A|B|Z:=0|1|9将:=改为表示可被代替用I,L,D分别表示标识符、字母、数字;,College of Computer Science&Technology,BUPT,2.1 文法-元语言,则上述表达式可以表示为 IL IIL IID La|b|.|z D0|1|.9这就是一个文法的生成式集合。,College of Computer Science&Technology,BUPT,2.2 文法的形式定义,Chomsky文法体系中，任何一种文法必须包含有两个不同的有限符号的集合，即非终结符集合N和终结符集合T。一个形式规则的有限集合P（生成式集合），一个起始符S。P中的生成式是用来产生语言句子的规则，而句子则是仅由终结符组成的字符串。这些字符串必须从一个起始符S开始，不断使用P中的生成式而推导出来。可见文法的核心是生成式的集合，它决定了语言中句子的产生。,College of Computer Science&Technology,BUPT,2.2 文法的形式定义,文法G是一个四元组G=(N，T，P，S)，其中N 非终结符的有限集合T 终结符的有限集合 NT=P 形式为的生成式的有限集合。且(NT)*N+(NT)*(NT)*S 起始符 且S N。,College of Computer Science&Technology,BUPT,将上例用文法表示G=(N，T，P，S)N=I,L,DT=a,b,c,z,0,1,9P=I,La,D0,D9S=I 文法是语言的产生系统，研究怎样构造文法能产生出符合要求的句子。,College of Computer Science&Technology,BUPT,2.3推导与句型,1、直接推导设G=（N,T,P,S）是文法，若A是P中的生成式，和是（NT）*中的字符串，则有A=称A直接推导出，或说是A的直接推导。,College of Computer Science&Technology,BUPT,设G=(N,T,P,S)是文法，、0、1n、都是（NT）*中的字符串，且=0、=n，其中i直接推导出i+1（0in）,则称序列0=1=2=n是长度为n的推导序列，而=0是长度为0的推导序列。对推导出记为，若推导序列长度大于0，则记为。推导序列的每一步，都产生一个字符串，这些字符串一般称为句型。,2.3、推导序列,College of Computer Science&Technology,BUPT,2.3、句型和句子,句型字符串是文法G的句型，当且仅当S，且（NT）*。句子是G的句子，当且仅当S,且T*。（是由终结符组成的字符串）例：I=L=a I=IL=LL=zL=zb句型包含句子,College of Computer Science&Technology,BUPT,2.4文法产生的语言,由文法G产生的语言记为L(G)。L(G)=|T*且S 或：L(G)中的一个字符串，必是由终结符组成的，并且是从起始符S推导出来的。,College of Computer Science&Technology,BUPT,2.4 文法产生语言,例1：括号匹配的语言及产生递归定义提供了集合的定义方式。构造规律。基础：定义该集合的最基本的元素，“（）”递归：若S是合法串，则：（S）是合法串；SS 是合法串；文法产生式集合：S（）S（S）SSS,College of Computer Science&Technology,BUPT,2.4 文法产生语言举例,例2：程序设计语言中算数表达式的语言运算符A：+、-、*、/利用递归定义方式。重点是构造规律。基础：单个变量是最基本的串，i,递归：若S是合法串，则：SAS 是合法串；（S）是合法串产生式集合：Si;SSAS;S(S);A+;A;A*;A/;,College of Computer Science&Technology,BUPT,第三节 Chomsky文法体系分类,文法 G=(N,T,P,S)；P:其中（NT）*N+（NT）*（NT）*属于Chomsky文法体系该体系对生成式的形式做了一些规定，分为四类，即0型、1型、2型、3型文法0型文法：无限制文法对应的语言：递归可枚举语言，与图灵机等价。,College of Computer Science&Technology,BUPT,1型文法,也称上下文有关文法（CSG：Context-sensitive Grammar)生成式的形式为，其中|，（NT）+，（NT）*N+（NT）*对应的语言：上下文有关语言（CSL：Context-sensitive Language)若不考虑，与线性有界自动机（LBA,Linear Bounded Automaton）等价。,College of Computer Science&Technology,BUPT,1型文法,语言限定约束：左部的长度小于右部不含A-上下文有关语言CSL是对实际程序语言结构的抽象：典型的这类语言结构包括：过程调用时形参与实参的一致性检查等。,College of Computer Science&Technology,BUPT,2型文法,也称上下文无关文法（CFG：Context-free Grammar)A,AN,且（NT）*对应的语言：上下文无关语言（CFL：Context-free Language)。对应的自动机：下推自动机（PDA：Pushdown Automaton)。,College of Computer Science&Technology,BUPT,语言限定约束：左部是1个非终结符。CFL对实际语言结构的抽象：表示句子的语法结构，如：表达式，嵌套结构。目前的程序设计语言主要采用CFL描述语法结构。,College of Computer Science&Technology,BUPT,3型文法,也称正则文法右线性文法（Right-linear Grammar）：AB 或 AA、BN,T*。左线性文法（Left-linear Grammar）：AB或 AA、BN,T*。对应的语言：正则语言对应的自动机：有限自动机（Finite Automaton）。,College of Computer Science&Technology,BUPT,文法举例,例1：G=(A,B,C,a,b,d,P,A)P:AAB；ABCAAB；Ad；Ba；Cb 是1型文法。A=dA=AB=dB=daA=AB=ABB=dBB=daB=daaA=AB=CAAB=bAAB=bdAB=bdCAAB=bdbAAB=bdbdAB=bdbddB=bdbdda,College of Computer Science&Technology,BUPT,文法举例,例2：G=(A,B,C,a,b,c,P,A)P:Aabc AaBbc BbbB BcCbcc bCCb aCaaB aCaa 是1型文法。其定义的 L=anbncn|n1 A=abc A=aBbc=abBc=abCbcc=aCbbcc=aabbcc,College of Computer Science&Technology,BUPT,文法举例,例3：G=(S,B,C,a,b,P,A)P:SaC；SbB；BaS；BbBB Ba；CbS；CaCC；Cb 是2型文法 S=aC=ab S=aC=aaCCS=aC=abS=abaC=ababS=ababaC=abababS=bB=bbBB=bbaSB=bbaaCB=bbaabB=bbaaba,College of Computer Science&Technology,BUPT,文法举例,例4：G=(A,B,C,a,b,c,P,A)P:ABa；Ac；BCb；Cc左线性文法 L=c,cba 正则语言注意：已知语言求文法，文法不是唯一的，即可以有不同的表达方法。,College of Computer Science&Technology,BUPT,四类文法之间的关系,只是对生成式形式加以限制0型 无限制1型 不允许A形式2型3型 属于2型不含A的2型、3型属于1型，1型、2型、3型均属于0型。,College of Computer Science&Technology,BUPT,精品课件！,College of Computer Science&Technology,BUPT,精品课件！,College of Computer Science&Technology,BUPT,作业：P47 4,6,7 题,
