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

第二章 语言及文法 主要内容： 定义形式语言的术语 给出文法的定义和文法的分类 要求掌握： 语言和文法的形式定义 文法如何设计 CHOMSKY文法体系的分类。 引言 复习： 什么是形式语言？什么是文法？什么是自动机？ 形式语言的定义方式？ 研究形式语言与自动机的意义？ 问题的提出？本章关注 语言与文法 如何描述（产生）左右括号匹配的语言？ 如何描述（产生）数学表达式？ 引言 知识点： 形式语言所研究的问题：产生语言，根据语言中的基本句子和其它句子的形成“规则”，得到（产生）语言所包含的所有句子。 第一节 语言的定义与运算 一、语言的一些术语： 字母表： 字符的有限集合，记为T。 字符串： 由字母表T中的字符构成的序列称字母表T上的字符串（句子）。 常记为u,v,w,x,y,z； 常用a,b,c,d 标识单个字符。 语 言 （Languages） 语言举例 例1：括号匹配的语言及产生 该语言指所有左右括号相匹配的字符串 如何“产生”这个语言？规则？ 递归定义提供了集合的定义方式。构造规律。 基础：定义该集合的最基本的元素，“（）” 递归：若S是合法串，则：（S）是合法串； SS 是合法串； 语言举例 例2：程序设计语言中算数表达式的语言 运算符A ：+、-、*、/ 利用递归定义方式。重点是构造规律。 基础：单个变量是最基本的串，i, 递归：若S是合法串，则：SAS 是合法串； （ S）是合法串； 语言举例 例3：标识符语言及产生 该语言指所有字母开头后接字母或数字的字符串 如何“产生”这个语言？规则？ 递归定义提供了集合的定义方式。构造规律。 基础：单个字母是最基本的元素， 递归：若S是合法串，则：SL 是合法串； SD 是合法串； L：字母；D：数字。 第二节 文法 本节提纲 文法的作用 文法的形式定义 推导与句型 文法产生语言 2.1 文法的作用 定义：所谓文法是用来定义语言的一个数学模型 表示语言的方法： 若语言L是有限集合，可用列举法 若L是无限集合（集合中的每个元素有限长度），用其他方法。 方法一：文法产生系统，由定义的文法规则产生出语言的每个句子 方法二：机器识别系统：当一个字符串能被一个语言的识别系统接受，则这个字符串是该语言的一个句子，否则不属于该语言。 2.1文法的作用---元语言 元语言定义：描述语言的语言 例如：各种各样的程序设计语言 当人们要解释或讨论程序设计语言本身时，又需要一种语言，被讨论的语言叫做对象语言，即某种程序设计语言，讨论对象语言的语言称为元语言。 BNF（巴科斯范式） BNF范式通常被作为讨论某种程序设计语言语法的元语言 数字 ::= 0|1|2|……9 ::= “定义为” 字母 ::= A|B|C|……Z|a|b|……z 标识符 :: =字母 | 标识符字母 | 标识符数字 …. 通过上述定义可知，所有以字母开头的，由字母和数字组成的字符串都是标识符。 BNF定义了一种语言，其中标识符如上定义。 BNF描述它所定义的语言，为元语言。 例如：汉语语法中定义了句子的结构由主语、谓语、宾语组成。这里主谓宾只是描述了句子的结构，并不是句子。而按照这种结构组成的建立在汉字上的字符串就是句子。 如: 他是学生。 文法是一种元语言，一种定义方法。 根据文法产生出语言的句子。 2.1文法—元语言 例如： BNF 标识符::=字母 标识符::=标识符字母 标识符::= 标识符数字 字母::=a|b|……z|A|B|……|Z 数字::=0|1|……9 将::= 改为→表示可被代替 用I, L, D分别表示标识符、字母、数字; 2.1 文法---元语言 则上述表达式可以表示为 I→L I→IL I→ID L→a|b|….|z D→0|1|….9 这就是一个文法的生成式集合。 2.2 文法的形式定义 Chomsky文法体系中，任何一种文法必须包含有两个不同的有限符号的集合，即非终结符集合N和终结符集合T。一个形式规则的有限集合P（生成式集合），一个起始符S。 P中的生成式是用来产生语言句子的规则，而句子则是仅由终结符组成的字符串。这些字符串必须从一个起始符S开始，不断使用P中的生成式而推导出来。 可见文法的核心是生成式的集合，它决定了语言中句子的产生。 2.2 文法的形式定义 文法G是一个四元组