形式语言02章文法语言语言.ppt

第二章文法与语言
一个语言的定义可以从两个方面进行:
从语言产生的角度;(形式语言)
从接收(识别)语言的角度。(自动机)
设是一个字母表,L *, L称为字母表上的一个语言(language), x  L, x叫做L的一个句子。
例子语言
例1:括号匹配的语言(该语言是指所有的左、右括号相匹配的串的集合)。
问题:如何产生该语言?即如何生成该集合中的所有的串?
自然语言的描述方式,采用如下的
递归规则:
①( )是合法的该语言的最基本的串;
②若S是一个合法的串,则(S)是合法串;
③若S是一个合法的串,则SS是合法串;
这些规则称为形成规则,根据这些规则,可以
(1)产生任意合法(即符合规则)的该集合中的串;
(2)判断某个串是否是合法的该集合的串(即合法的句子)。
例如: 可以产生串(());
而推断串
(()))
不是合法的串。
规则(的个数)是有限的,但可以产生无限个串和无限长度的串;
因为规则是递归的。
巴科斯和诺尔采用的巴科斯-诺尔范式(BNF--Backus-Naur Form)描述规则:
<括号匹配串>::= ( )
<括号匹配串>::= <括号匹配串> <括号匹配串>
<括号匹配串>::=(<括号匹配串>)
使用尖括号“<”和“>”包括起来的部分,作为一个整体来看待,表示某个语法成分,最终,需要使用字母表中的字母来定义。
符号“::=”是BNF本身的符号(元符号),代表“定义为”或“就是”。
符号“( ”和“)”是字母表的元素。
Chomsky采用的符号化(形式化)的描述方式,运用如下的规则(这些规则被称为产生式):
① S→( )
② S→(S)
③ S→SS