形式语言与自动机语言及文法

形式语言与自动机语言及文法CollegeofComputerScience&Technology,BUPT第1页，课件共47页，创作于2023年2月CollegeofComputerScience&Technology,BUPT引言复习：什么是形式语言？什么是文法？什么是自动机？形式语言的定义方式？研究形式语言与自动机的意义？问题的提出？本章关注语言与文法如何描述（产生）左右括号匹配的语言？如何描述（产生）数学表达式？第2页，课件共47页，创作于2023年2月CollegeofComputerScience&Technology,BUPT引言知识点：形式语言所研究的问题：产生语言，根据语言中的基本句子和其它句子的形成“规则”，得到（产生）语言所包含的所有句子。第3页，课件共47页，创作于2023年2月CollegeofComputerScience&Technology,BUPT第一节语言的定义与运算一、语言的一些术语：

字母表：字符的有限集合，记为T。字符串：由字母表T中的字符构成的序列称字母表T上的字符串（句子）。常记为u,v,w,x,y,z；常用a,b,c,d标识单个字符。第4页，课件共47页，创作于2023年2月CollegeofComputerScience&Technology,BUPT字母表（Alphabet）

概念

形式符号的集合

记号常用T、表示

举例英文字母表a,b,…,z,A,B,…,Z英文标点符号表,;:.?!’‘“”()…汉字表…,自,…,动,…,机,…

化学元素表H,He,Li,…,

T=a,n,y,任,意第5页，课件共47页，创作于2023年2月CollegeofComputerScience&Technology,BUPT字符串（string）

概念字母表T上的一个字符串（简称串），或称为字（word），为T中字符构成的一个有限序列。

空串（emptystring）,用表示，不包含任何字符。

举例设T=a,b，则

,

a,ba,bbaba等都是串

字符串w的长度，记为w，是包含在w中字符的个数

举例=0，bbaba=5ai表示含有i个a的字符串

第6页，课件共47页，创作于2023年2月CollegeofComputerScience&Technology,BUPT

连接（concatenation）

设x,y为串,且xa1a2…am,yb1b2…bn,则x与y的连接

xya1a2…amb1b2…bn

连接运算的性质

(xy)z

x（yz

）

xxx

xyx+y

关于字符串的运算第7页，课件共47页，创作于2023年2月CollegeofComputerScience&Technology,BUPT

其它如取头字符，取尾部，子串匹配

等

设ω1,ω2,ω3是字母表T上的字符串，称：ω1是字符串ω1ω2的前缀，ω2是字符串ω1ω2的后缀，ω2是字符串ω1ω2ω3的子串。空串是任何字符串的前缀，后缀及子串。

例：abc的前缀aababcε.后缀cbcabcε.子串abcabbcabcε,即一个字符串可以看作是多个字符串的连接。

关于字符串的运算第8页，课件共47页，创作于2023年2月CollegeofComputerScience&Technology,BUPT字符串ω的逆用表示。是字符串ω的倒置。ω=b1b2……bn=bnbn-1……b2b1空串ε的逆还是ε第9页，课件共47页，创作于2023年2月CollegeofComputerScience&Technology,BUPT字母表的幂运算

幂运算Tn用来表示该字母表长度为n的所有串的集合。设T为字母表，n为任意自然数，定义（1）T0=（2）设x

Tn-1，a

T，则a

x

Tn（3）

Tn中的元素只能由（1）和（2）生成

闭包

T*=

T0T1T2…

闭包

T+=

T1T2T3…

T*=T+，T+=T*

第10页，课件共47页，创作于2023年2月CollegeofComputerScience&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，…第11页，课件共47页，创作于2023年2月CollegeofComputerScience&Technology,BUPT

概念设T为字母表，则任何集合LT*是字母表T上的一个语言（language）。隐含的概念：如何表述子集的“特性和规则”，

举例-左右括号的匹配。

英文单词集…,English,…,words,…

C语言程序集…字母表？汉语成语集…,马到成功,…

化学分子式集…,H2O,…,NaCl,…

any,任意

语言（Languages）第12页，课件共47页，创作于2023年2月CollegeofComputerScience&Technology,BUPT语言（Languages）举例：设T={a，b}则L1={anbn|n≥1}L3={bk|k是质数}L2={ε}只有一个空句子的语言L4={}=Φ空语言均为字母表T上的语言。由语言的定义知语言是集合，对于集合的运算可应用于对于语言的计算。如并，交，补，差。第13页，课件共47页，创作于2023年2月CollegeofComputerScience&Technology,BUPT语言的基本运算语言的积：

两个语言L1和L2的积L1L2是由L1和L2中的字符串连接所构成的字符串的集合。即L1中所有字符串分别与L2中的字符串连接得到的集合。设T={a,b}，L1和L2是T上的语言。L1={ab,ba}L2={aa,bb}则L1L2={abaa,abbb,baaa,babb}L2L1={aaab,aaba,bbab,bbba}L1L2≠L2L1语言的积不可交换。第14页，课件共47页，创作于2023年2月CollegeofComputerScience&Technology,BUPT语言的基本运算语言的幂： 语言的幂可归纳定义如下: L0={ε}Ln=L·Ln-1=Ln-1·Ln≥1上例中，L12={abab,abba,baab,baba}L22={aaaa,aabb,bbaa,bbbb}

第15页，课件共47页，创作于2023年2月CollegeofComputerScience&Technology,BUPT语言举例例1：括号匹配的语言及产生该语言指所有左右括号相匹配的字符串如何“产生”这个语言？规则？递归定义提供了集合的定义方式。构造规律。基础：定义该集合的最基本的元素，“（）”递归：若S是合法串，则：（S）是合法串； SS是合法串；第16页，课件共47页，创作于2023年2月CollegeofComputerScience&Technology,BUPT语言举例例2：程序设计语言中算数表达式的语言 运算符A：+、-、*、/利用递归定义方式。重点是构造规律。基础：单个变量是最基本的串，i,递归：若S是合法串，则：SAS是合法串； （S）是合法串；第17页，课件共47页，创作于2023年2月CollegeofComputerScience&Technology,BUPT语言举例例3：标识符语言及产生该语言指所有字母开头后接字母或数字的字符串如何“产生”这个语言？规则？递归定义提供了集合的定义方式。构造规律。基础：单个字母是最基本的元素，递归：若S是合法串，则：SL是合法串； SD是合法串；L：字母；D：数字。第18页，课件共47页，创作于2023年2月CollegeofComputerScience&Technology,BUPT第二节文法本节提纲文法的作用文法的形式定义推导与句型文法产生语言第19页，课件共47页，创作于2023年2月CollegeofComputerScience&Technology,BUPT2.1文法的作用定义：所谓文法是用来定义语言的一个数学模型表示语言的方法：若语言L是有限集合，可用列举法若L是无限集合（集合中的每个元素有限长度），用其他方法。方法一：文法产生系统，由定义的文法规则产生出语言的每个句子方法二：机器识别系统：当一个字符串能被一个语言的识别系统接受，则这个字符串是该语言的一个句子，否则不属于该语言。第20页，课件共47页，创作于2023年2月CollegeofComputerScience&Technology,BUPT2.1文法的作用---元语言元语言定义：描述语言的语言 例如：各种各样的程序设计语言当人们要解释或讨论程序设计语言本身时，又需要一种语言，被讨论的语言叫做对象语言，即某种程序设计语言，讨论对象语言的语言称为元语言。第21页，课件共47页，创作于2023年2月CollegeofComputerScience&Technology,BUPTBNF（巴科斯范式） BNF范式通常被作为讨论某种程序设计语言语法的元语言<数字>::=0|1|2|……9::=“定义为”<字母>::=A|B|C|……Z|a|b|……z<标识符>::=<字母>|<标识符><字母>|<标识符><数字>

….通过上述定义可知，所有以字母开头的，由字母和数字组成的字符串都是标识符。BNF定义了一种语言，其中标识符如上定义。BNF描述它所定义的语言，为元语言。第22页，课件共47页，创作于2023年2月CollegeofComputerScience&Technology,BUPT例如：汉语语法中定义了句子的结构由主语、谓语、宾语组成。这里主谓宾只是描述了句子的结构，并不是句子。而按照这种结构组成的建立在汉字上的字符串就是句子。如:他是学生。第23页，课件共47页，创作于2023年2月CollegeofComputerScience&Technology,BUPT文法是一种元语言，一种定义方法。根据文法产生出语言的句子。第24页，课件共47页，创作于2023年2月CollegeofComputerScience&Technology,BUPT2.1文法—元语言例如：BNF<标识符>::=<字母><标识符>::=<标识符><字母><标识符>::=<标识符><数字><字母>::=a|b|……z|A|B|……|Z<数字>::=0|1|……9将::=改为→表示可被代替用I,L,D分别表示标识符、字母、数字;第25页，课件共47页，创作于2023年2月CollegeofComputerScience&Technology,BUPT2.1文法---元语言则上述表达式可以表示为 I→LI→ILI→IDL→a|b|….|zD→0|1|….9这就是一个文法的生成式集合。第26页，课件共47页，创作于2023年2月CollegeofComputerScience&Technology,BUPT2.2文法的形式定义Chomsky文法体系中，任何一种文法必须包含有两个不同的有限符号的集合，即非终结符集合N和终结符集合T。一个形式规则的有限集合P（生成式集合），一个起始符S。P中的生成式是用来产生语言句子的规则，而句子则是仅由终结符组成的字符串。这些字符串必须从一个起始符S开始，不断使用P中的生成式而推导出来。可见文法的核心是生成式的集合，它决定了语言中句子的产生。第27页，课件共47页，创作于2023年2月CollegeofComputerScience&Technology,BUPT2.2文法的形式定义文法G是一个四元组G=(N，T，P，S)，其中 N非终结符的有限集合 T终结符的有限集合N∩T=Φ P形式为α→β的生成式的有限集合。 且α∈(N∪T)*N+(N∪T)*β∈(N∪T)* S起始符且S∈N。第28页，课件共47页，创作于2023年2月CollegeofComputerScience&Technology,BUPT将上例用文法表示 G=(N，T，P，S)N={I,L,D}T={a,b,c,…z,0,1,…9}P={I,La,…,D0,…,D9}S={I}文法是语言的产生系统，研究怎样构造文法能产生出符合要求的句子。第29页，课件共47页，创作于2023年2月CollegeofComputerScience&Technology,BUPT2.3．推导与句型1、直接推导 设G=（N,T,P,S）是文法，若A→β是P中的生成式，α和γ是（N∪T）*中的字符串，则有αAγ=>αβγ称αAγ直接推导出αβγ，或说αβγ是αAγ的直接推导。第30页，课件共47页，创作于2023年2月CollegeofComputerScience&Technology,BUPT设G=(N,T,P,S)是文法，α、α0、α1…αn、α’都是（N∪T）*中的字符串，且α=α0、α’=αn，其中αi直接推导出αi+1（0≤i≤n）,则称序列α0=>α1=>α2=>…=>αn是长度为n的推导序列，而α=α0是长度为0的推导序列。对α推导出α’记为αα’，若推导序列长度大于0，则记为αα’。推导序列的每一步，都产生一个字符串，这些字符串一般称为句型。2.3、推导序列第31页，课件共47页，创作于2023年2月CollegeofComputerScience&Technology,BUPT2.3、句型和句子句型 字符串α是文法G的句型，当且仅当Sα，且α∈（N∪T）*。句子ω是G的句子，当且仅当Sω,且ω∈T*。（ω是由终结符组成的字符串）例：I=>L=>a I=>IL=>LL=>zL=>zb句型包含句子第32页，课件共47页，创作于2023年2月CollegeofComputerScience&Technology,BUPT2.4．文法产生的语言由文法G产生的语言记为L(G)。 L(G)={ω|ω∈T*且Sω}或： L(G)中的一个字符串，必是由终结符组成的，并且是从起始符S推导出来的。第33页，课件共47页，创作于2023年2月CollegeofComputerScience&Technology,BUPT2.4文法产生语言例1：括号匹配的语言及产生递归定义提供了集合的定义方式。构造规律。基础：定义该集合的最基本的元素，“（）”递归：若S是合法串，则：（S）是合法串； SS是合法串；文法产生式集合：S→（）S→（S）S→SS第34页，课件共47页，创作于2023年2月CollegeofComputerScience&Technology,BUPT2.4文法产生语言举例例2：程序设计语言中算数表达式的语言 运算符A：+、-、*、/利用递归定义方式。重点是构造规律。基础：单个变量是最基本的串，i,递归：若S是合法串，则：SAS是合法串； （S）是合法串产生式集合：S→i;S→SAS;S→(S);A→+;A→−;A→*;A→/;第35页，课件共47页，创作于2023年2月CollegeofComputerScience&Technology,BUPT第三节Chomsky文法体系分类文法G=(N,T,P,S)；P:α→β 其中α∈（N∪T）*N+（N∪T）*β∈（N∪T）*属于Chomsky文法体系该体系对生成式的形式做了一些规定，分为四类，即0型、1型、2型、3型文法0型文法：无限制文法 对应的语言：递归可枚举语言，与图灵机等价。第36页，课件共47页，创作于2023年2月CollegeofComputerScience&Technology,BUPT1型文法也称上下文有关文法（CSG：Context-sensitiveGrammar) 生成式的形式为α→β， 其中|α|≤|β|，β∈（N∪T）+， α∈（N∪T）*N+（N∪T）*对应的语言：上下文有关语言（CSL：Context-sensitiveLanguage)若不考虑ε，与线性有界自动机（LBA,LinearBoundedAutomaton）等价。第37页，课件共47页，创作于2023年2月CollegeofComputerScience&Technology,BUPT1型文法语言限定约束：左部的长度小于右部不含A->ε上下文有关语言CSL是对实际程序语言结构的抽象：典型的这类语言结构包括：过程调用时形参与实参的一致性检查等。第38页，课件共47页，创作于2023年2月CollegeofComputerScience&Technology,BUPT2型文法也称上下文无关文法（CFG：Context-freeGrammar) A→α, A∈N,且α∈（N∪T）*对应的语言：上下文无关语言（CFL：Context-freeLanguage)。对应的自动机：下推自动机（PDA：PushdownAutomaton)。第39页，课件共47页，创作于2023年2月CollegeofComputerScience&Technology,BUPT语言限定约束：左部是1个非终结符。CFL对实际语言结构的抽象：表示句子的语法结构，如：表达式，嵌套结构{}。目前的程序设计语言主要采用CFL描述语法结构。第40页，课件共47页，创作于2023年2月CollegeofComputerScience&Technology,BUPT3型文法也称正则文法右线性文法（Right-linearGrammar）：A→ωB或A→ω A、B∈N,ω∈T*。左线性文法（Left-linearGrammar）： A→Bω或A→ω A、B∈N,ω∈T*。对应的语言：正则语言对应的自动机：有限自动机（FiniteAutomaton）。第41页，课件共47页，创作于2023年2月CollegeofComputerScience&Technology,BUPT文法举例例1： G=({A,B,C},{a,b,d},P,A) P:A→AB；AB→CAAB；A→d；B→a；C→b是1型文法。A=>dA=>AB=>dB=>daA=>AB=>ABB=>dBB=>daB=>daaA=>AB=>CAAB=>b