形式语言与自动机绪论.ppt

* 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 三、Chomsky文法体系 例如： BNF 标识符::=字母 标识符::=标识符字母 标识符::= 标识符数字 字母::=a|b|……z|A|B|……|Z 数字::=0|1|……9 将::= 改为→表示可被代替 用I, L, D分别表示标识符、字母、数字; * College of Computer Science Technology, BUPT 则上述表达式可以表示为 I→L I→IL I→ID L→a|b|….|z D→0|1|….9 这就是一个文法的生成式集合。 * College of Computer Science Technology, BUPT Chomsky文法体系中，任何一种文法必须包含有两个不同的有限符号的集合，即非终结符集合N和终结符集合T。一个形式规则的有限集合P（生成式集合），一个起始符S。 P中的生成式是用来产生语言句子的规则，而句子则是仅由终结符组成的字符串。这些字符串必须从一个起始符S开始，不断使用P中的生成式而导出来。 可见文法的核心是生成式的集合，它决定了语言中句子的产生。 * College of Computer Science Technology, BUPT 文法的形式定义 文法G是一个四元组G=(N，T，P，S)， 其中 N 非终结符的有限集合 T 终结符的有限集合 N∩T=Φ P 形式为α→β的生成式的有限集合。 且α∈(N∪T)* N+ (N∪T)* β∈(N∪T)* S 起始符 且S ∈N。 * College of Computer Science 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 文法是语言的产生系统，研究怎样构造文法能产生出符合要求的句子。 * College of Computer Science Technology, BUPT 四．推导与句型 1、直接推导 设G =（N,T,P,S）是文法，若A→β是P中的生成式，α和γ是（N∪T）*中的字符串，则有αAγ= αβγ称αAγ直接推导出αβγ，或说αβγ是αAγ的直接推导。 * College of Computer Science 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、推导序列 * College of Computer Science Technology, BUPT 3、句型和句子 句型 字符串α是文法G的句型，当且仅当 S α，且α∈（N∪T）*。 句子 ω是G的句子，当且仅当S ω,且ω∈T*。（ω是由终结符组成的字符串） 例：I =L =a I =I