形式语言与自动机语言及文法课件.ppt

1、College of Computer Science & Technology, BUPT引言n复习：复习：n什么是形式语言？什么是文法？什么是自动机？n形式语言的定义方式？n研究形式语言与自动机的意义？n问题的提出？本章关注问题的提出？本章关注 语言与文法语言与文法n如何描述（产生）左右括号匹配的语言？n如何描述（产生）数学表达式？College of Computer Science & Technology, BUPT引言n知识点：知识点：n形式语言所研究的问题：产生语言，根据语言中的基本句子和其它句子的形成“规则”，得到（产生）语言所包含的所有句子。College of Comput

2、er Science & Technology, BUPT第一节第一节 语言的定义与运算语言的定义与运算一、一、语言的一些术语：语言的一些术语：n 字母表： 字符的有限集合，记为T。 n字符串： 由字母表T中的字符构成的序列称字母表T上的字符串（句子）。n 常记为u,v,w,x,y,z；n 常用a,b,c,d 标识单个字符。College of Computer Science & Technology, BUPT字字 母母 表表 （AlphabetAlphabet） 概念概念 形式符号的集合形式符号的集合 记号记号 常用常用 T、 表示表示 举例举例- 英文字母表英文字母表 a, b, ,

3、z, A, B , , Z - 英文标点符号表英文标点符号表 , ; : . ? ! “ ” ( ) - 汉字表汉字表 , 自自, , 动动 , , 机机, - 化学元素表化学元素表 H, He, Li, , - T = a, n, y, 任任,意意 College of Computer Science & Technology, BUPT字字 符符 串串 （stringstring） 概念概念 字母表字母表 T 上的一个上的一个字符串字符串（简称（简称串串），或称为），或称为 字字（word），为），为 T 中字符构成的一个有限序列。中字符构成的一个有限序列。 空串空串（empty str

4、ing）, 用用 表示，不包含任何表示，不包含任何 字符。字符。 举例举例 设设 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

5、a1a2 am b1b2 bn 连接运算的性质连接运算的性质 - ( x y ) z x（ y z ）- x x x - x y x + y 关关 于于 字字 符符 串串 的的 运运 算算College of Computer Science & Technology, BUPT 其它其它 如如 取头字符取头字符，取尾部取尾部，子串匹配子串匹配 等等n 设设1, 2, 3是字母表是字母表T上的字符串，称：上的字符串，称：n1是字符串是字符串12的的前缀前缀，n2是字符串是字符串12的的后缀后缀，n2是字符串是字符串123的的子串子串。 n 空串是任何字符串的前缀，后缀及子串。空串是任何字符串的

6、前缀，后缀及子串。n 例例：abc的前缀的前缀 a ab abc . 后缀后缀 c bc abc . 子串子串 a b c ab bc abc , 即一个字符串可以看作是多个字符串的连接。即一个字符串可以看作是多个字符串的连接。 关关 于于 字字 符符 串串 的的 运运 算算College of Computer Science & Technology, BUPTn 字符串字符串的逆用的逆用 表示。表示。 是字符是字符串串的倒置。的倒置。= b1b2bn = bnbn-1b2b1n 空串空串的逆还是的逆还是College of Computer Science & Technology, B

7、UPT字字 母母 表表 的的 幂幂 运运 算算 幂运算幂运算 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闭包的物理意义闭包

8、的物理意义 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）。

9、）。隐含的概念：如何表述子集的隐含的概念：如何表述子集的“特性和规则特性和规则”， 举例举例- 左右括号的匹配。左右括号的匹配。 - 英文单词集英文单词集 , English, , words , - C 语言程序集语言程序集 字母表？字母表？- 汉语成语集汉语成语集 , 马到成功马到成功, - 化学分子式集化学分子式集 , H2O, , NaCl , - any, 任意任意 语 言 （Languages）College of Computer Science & Technology, BUPT语 言 （Languages）举例举例：设：设T = a，b 则则 L1 = anbn | n1

10、L3 = bk | k 是质数是质数 L2 = 只有一个空句子的语言只有一个空句子的语言 L4 = = 空语言空语言 均为字母表均为字母表T上的语言。上的语言。由语言的定义知语言是集合，对于集合的运算可由语言的定义知语言是集合，对于集合的运算可应用于对于语言的计算。如并，交，补，差。应用于对于语言的计算。如并，交，补，差。College of Computer Science & Technology, BUPT语言的基本运算 语言的积：语言的积：两个语言L1 和L2的积L1 L2是由L1和L2中的字符串连接所构成的字符串的集合。即L1中所有字符串分别与L2中的字符串连接得到的集合。设T=a,

11、 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 语言的积不可交换。语言的积不可交换。College of Computer Science & Technology, BUPT语言的基本运算 语言的幂：语言的幂：语言的幂可归纳定义如下语言的幂可归纳定义如下: L0 = Ln = L Ln-1 = Ln-1 L n 1上例中，上例中，L12 =abab, abba, baab, baba L22 =aaaa, aabb

12、, bbaa, bbbb College of Computer Science & Technology, BUPT语言举例例例1：括号匹配的语言及产生：括号匹配的语言及产生该语言指所有左右括号相匹配的字符串如何“产生”这个语言？规则？递归定义提供了集合的定义方式。构造规律。1.基础：定义该集合的最基本的元素，“（）”2.递归：若S是合法串，则：（S）是合法串； SS 是合法串；College of Computer Science & Technology, BUPT语言举例例例2：程序设计语言中算数表达式的语言：程序设计语言中算数表达式的语言运算符运算符A ：+、- -、* *、/ /利

13、用递归定义方式。重点是构造规律。1.基础：单个变量是最基本的串，i,2.递归：若S是合法串，则：SAS 是合法串； （ S）是合法串；College of Computer Science & Technology, BUPT语言举例例例3：标识符语言及产生：标识符语言及产生该语言指所有字母开头后接字母或数字的字符串如何“产生”这个语言？规则？递归定义提供了集合的定义方式。构造规律。1.基础：单个字母是最基本的元素，2.递归：若S是合法串，则：SL 是合法串； SD 是合法串；L：字母；D：数字。College of Computer Science & Technology, BUPT第二节

14、 文法本节提纲本节提纲1.文法的作用文法的作用2.文法的形式定义文法的形式定义3.推导与句型推导与句型4.文法产生语言文法产生语言College of Computer Science & Technology, BUPT2.1 文法的作用n定义：所谓文法是用来定义语言的一个数学模型：所谓文法是用来定义语言的一个数学模型n表示语言的方法：n若语言L是有限集合，可用列举法n若L是无限集合（集合中的每个元素有限长度），用其他方法。n方法一：文法产生系统，由定义的文法规则产生出语言的每个句子n方法二：机器识别系统：当一个字符串能被一个语言的识别系统接受，则这个字符串是该语言的一个句子，否则不属于该语

15、言。College of Computer Science & Technology, BUPT2.12.1文法的作用文法的作用- -元语言元语言n元语言定义元语言定义：描述语言的语言描述语言的语言例如：各种各样的程序设计语言n当人们要解释或讨论程序设计语言本身时，当人们要解释或讨论程序设计语言本身时，又需要一种语言，被讨论的语言叫做对象语又需要一种语言，被讨论的语言叫做对象语言，即某种程序设计语言，讨论对象语言的言，即某种程序设计语言，讨论对象语言的语言称为元语言语言称为元语言。College of Computer Science & Technology, BUPTBNFBNF（巴科斯范

16、式）（巴科斯范式） BNF范式通常被作为讨论某种程序设计语言语法的元语言n := 0|1|2|9 := “定义为”n := A|B|C|Z|a|b|z : = | | . n通过上述定义可知，所有以字母开头的，由字母和数字组成的字符串都是标识符。nBNF定义了一种语言，其中标识符如上定义。nBNF描述它所定义的语言，为元语言。College of Computer Science & Technology, BUPTn例如：汉语语法中定义了句子的结构由主语、谓语、宾语组成。这里主谓宾只是描述了句子的结构，并不是句子。而按照这种结构组成的建立在汉字上的字符串就是句子。 如: 他是学生。Colle

17、ge of Computer Science & Technology, BUPTn文法是一种元语言，一种定义方法。文法是一种元语言，一种定义方法。n根据文法产生出语言的句子。根据文法产生出语言的句子。College of Computer Science & Technology, BUPT2.1文法元语言n例如：BNF := := := :=a|b|z|A|B|Z :=0|1|9将将:= 改为改为表示可被代替表示可被代替用用I, L, D分别表示标识符、字母、数字分别表示标识符、字母、数字;College of Computer Science & Technology, BUPT2.1

18、文法-元语言则上述表达式可以表示为则上述表达式可以表示为 IL IIL IID La|b|.|z D0|1|.9这就是一个文法的生成式集合。这就是一个文法的生成式集合。College of Computer Science & Technology, BUPT2.2 文法的形式定义nChomsky文法体系中，任何一种文法必须包含有两个不同的有限符号的集合，即非终结符集合N和终结符集合T。一个形式规则的有限集合P（生成式集合），一个起始符S。nP中的生成式是用来产生语言句子的规则，而句子则是仅由终结符组成的字符串。这些字符串必须从一个起始符S开始，不断使用P中的生成式而推导出来。n可见文法的核心

19、是生成式的集合，它决定了语言中句子的产生。College of Computer Science & Technology, BUPT2.2 文法的形式定义n文法G是一个四元组G=(N，T，P，S)， 其中N 非终结符的有限集合T 终结符的有限集合 NT=P 形式为的生成式的有限集合。 且(NT)* N+ (NT)* (NT)*S 起始符 且S N。College of Computer Science & Technology, BUPTn将上例用文法表示G=(N，T，P，S)N = I, L, DT = a, b, c,z, 0, 1, 9P = I, La, , D0, , D9S =

20、I n文法是语言的产生系统，研究怎样构造文法能产生出符合要求的句子。College of Computer Science & Technology, BUPT2.3推导与句型1、直接推导设G =（N,T,P,S）是文法，若A是P中的生成式，和是（NT）*中的字符串，则有A= 称A直接推导出，或说是A的直接推导。College of Computer Science & Technology, BUPTn设设G = (N,T,P,S)G = (N,T,P,S)是文法，是文法，、0 0、1 1n n、都都是（是（NTNT）* *中的字符串，且中的字符串，且=0 0、 =n n，其中，其中i i直

21、 接 推 导 出直 接 推 导 出 i + 1i + 1 （ 0 i n0 i n ） , , 则 称 序 列则 称 序 列0 0=1 1=2 2=n n是长度为是长度为n n的推导序列，而的推导序列，而=0 0是长度为是长度为0 0的推导序列。的推导序列。n对对推导出推导出记为记为 ，若推导序列长度大，若推导序列长度大于于0 0，则记为，则记为 。n推导序列的每一步，都产生一个字符串，这些字符串一推导序列的每一步，都产生一个字符串，这些字符串一般称为句型。般称为句型。2.3、推导序列*G G College of Computer Science & Technology, BUPT2.3、

22、句型和句子n句型字符串是文法G的句型，当且仅当S ，且（NT）*。n 句子是G的句子，当且仅当S ,且T*。（是由终结符组成的字符串）例：I =L =a I =IL =LL =zL =zbn句型包含句子*G *G College of Computer Science & Technology, BUPT2.4文法产生的语言由文法G产生的语言记为L(G)。 L(G) = |T*且S 或： L(G)中的一个字符串，必是由终结符组成的，并且是从起始符S推导出来的。*G College of Computer Science & Technology, BUPT2.4 文法产生语言例例1：括号匹配的

23、语言及产生：括号匹配的语言及产生递归定义提供了集合的定义方式。构造规律。1.基础：定义该集合的最基本的元素，“（）”2.递归：若S是合法串，则：（S）是合法串； SS 是合法串；文法产生式集合：S（）（）S（S）SSSCollege of Computer Science & Technology, BUPT2.4 文法产生语言举例例例2：程序设计语言中算数表达式的语言：程序设计语言中算数表达式的语言运算符运算符A ：+、- -、* *、/ /利用递归定义方式。重点是构造规律。1.基础：单个变量是最基本的串，i,2.递归：若S是合法串，则：SAS 是合法串； （ S）是合法串产生式集合：Si

24、; SSAS; S(S);A+; A; A*; A/; College of Computer Science & Technology, BUPT第三节 Chomsky文法体系分类n文法文法 G = (N,T,P,S)； P: 其中其中 （NT）* N+（NT）* （NT）* 属于属于Chomsky文法体系文法体系n该体系对该体系对生成式生成式的形式做了一些规定，分的形式做了一些规定，分为四类，即为四类，即0型、型、1型、型、2型、型、3型文法型文法n0型文法：无限制文法型文法：无限制文法对应的语言：递归可枚举语言，与图灵机等价。College of Computer Science & T

25、echnology, BUPT1型文法n也称上下文有关文法（也称上下文有关文法（CSG：Context-sensitive Grammar)生成式的形式为生成式的形式为，其中其中 |，（NT）+， （NT）*N+（NT）*n对应的语言：上下文有关语言（对应的语言：上下文有关语言（CSL：Context-sensitive Language)n若不考虑若不考虑，与线性有界自动机（，与线性有界自动机（LBA, Linear Bounded Automaton）等价。）等价。College of Computer Science & Technology, BUPT1型文法语言限定约束：1.左部的长

26、度小于右部2.不含A-n上下文有关语言CSL是对实际程序语言结构的抽象：典型的这类语言结构包括：n过程调用时形参与实参的一致性检查等。College of Computer Science & Technology, BUPT2型文法n也称上下文无关文法（也称上下文无关文法（CFG：Context-free Grammar) A, AN, 且且（NT）*n对应的语言：上下文无关语言对应的语言：上下文无关语言 （CFL： Context-free Language)。n对应的自动机：下推自动机（对应的自动机：下推自动机（PDA： Pushdown Automaton)。College of Co

27、mputer Science & Technology, BUPTn语言限定约束：语言限定约束：1.左部是1个非终结符。nCFL对实际语言结构的抽象：对实际语言结构的抽象：n表示句子的语法结构，如：表达式，嵌套结构。n目前的程序设计语言主要采用CFL描述语法结构。College of Computer Science & Technology, BUPT3型文法也称正则文法也称正则文法n右线性文法（Right-linear Grammar）：AB 或 AA、BN, T*。n左线性文法（Left-linear Grammar）：AB或 AA、BN, T*。n对应的语言：正则语言n对应的自动机：有

28、限自动机（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 =bdbddaCollege of Computer Science & Technology, BUPT文法举例文法举例例例2：G

29、 = (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 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型文法型文法 n S =aC =ab nS = aC =aaC

30、CnS =aC =abS =abaC =ababS =ababaC =abababnS =bB =bbBB =bbaSB =bbaaCB =bbaabB =bbaabaCollege of Computer Science & Technology, BUPT文法举例文法举例例例4：G = (A,B,C, a,b,c, P, A) P: ABa； Ac； BCb； Ccn左线性文法n L = c, cba 正则语言n注意：已知语言求文法，文法不是唯一的，注意：已知语言求文法，文法不是唯一的，即可以有不同的表达方法即可以有不同的表达方法。College of Computer Science &

31、 Technology, BUPT四类文法之间的关系n只是对生成式形式加以限制只是对生成式形式加以限制n0型型 无限制无限制n1型型 不允许不允许A形式形式n2型型n3型型 属于属于2型型n不含不含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, BUPTn作业：作业： P47 4,6,7 题题