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