文法与语言在线视频

同学们好

从这节课开始

我们来介绍文法与语言

首先来看

语言的形式化描述

编译程序是一种语言处理系统

功能是将

高级程序设计语言编写的程序

翻译为目标代码

首先 我们要明确一个概念

就是什么是语言

又如何形式化的描述呢

这可以说是编译程序

首要面临的问题

据统计 目前在世界各地

人们所使用的语言多到2700多种

通俗来说

语言就是人们所说的话

也可以说

是某一字母表上符号串（句子）的集合

但是这种说法

都不能构成形式化的描述语言

如果一种语言的句子是有限的

那么我们就可以用句子的有限集

来表示这个语言了

但是一般情况下

一个语言的句子是无穷的

那么我们就需要一种

形式化的描述方法

比如说汉语是由句子组成的

汉语的句子自然是无穷多个了

我们无法逐一列出

但是我们都知道

汉语的句子是由词汇

按照一定的规则组成的

就可以用这些规则来描述汉语

假设一个简单的汉语句子

是由主语跟谓语构成的

谓语是由动词和直接宾语构成的

这种描述方法实际上就是

在描述汉语的语法规则

这里我们采用巴科斯范式来表示

一个汉语简单句子的构成规则

大家看这里就是句子的定义规则

通常这里“∷=”

我们把它读作“定义为”

这些规则就是我们判别句子

结构合法与否的依据

也就是说

这些规则可以看作是一种元语言

用它来描述汉语

有了这一组规则

我们就可以运用规则

来推导或者产生句子

我们来判断 “我是大学生”

是不是符合这些规则的句子呢

首先从第一条规则出发

我们将句子推导出来

〈主语〉〈谓语〉

这个符号

也就是 “=>”

我们把它读作“推导”

它的含义就是使用了一条规则

将规则左边的某个符号

推导出来规则右边的符号串

再看第二条规则

〈主语〉∷=〈代词〉|〈名词〉

我们运用规则〈主语〉∷=〈代词〉

将“〈主语〉〈谓语〉”

推导得到〈代词〉〈谓语〉

再用第三条规则

〈代词〉∷= 我

推导可以得到 =>我〈谓语〉

依次类推

我们可以推导出来

“我是大学生”这个句子

显然 依照规则

我们还能产生“王明是大学生”

“我学习英语”等等其他的句子

从这个例子可以看出

可以使用有限的规则

来描述无限的句子

自然语言是由句子组成的集合

句子又是由单词 标点符号组成的序列

一个高级设计语言是由类似的

main int float等等这些符号 字母

数字基本符号组成的

所以 语言可以说是在基本符号集上

按照一定规则构成的符号串集合

下面我们来看符号

符号串的有关概念

（1）字母表

字母表就是符号的有限集合

我们通常也把它称之为

符号表 符号集

不同的语言有不同的字母表

汉字的字母表包括有

汉字 数字 标点符号等等

C语言的字母表包括有

字母 数字 专用符号 保留字等等

（2）符号串

符号串是用字母表中的符号所组成的

任何有限的序列

我们来看

有一个字母表 Σ

这个字母表中只有两个字符a和b

那么ε，a，b，aa，ab，aabba…

都是这个字母表上的符号串

再来看一个

字母表 Σ=｛0，1｝

那么ε，0，1，01，11…

都是这个字母表Σ上的符号串

对于一个符号串的长度

又是指符号串中所含符号的个数

aba这个符号串它的长度是3

空串是指不含任何符号的符号串

我们通常记为

它的长度就是0

我们再来看符号串的连接

假设x和y是符号串

我们将y直接地拼接到x之后

所得到的新符号串

我们称之为x与y的连接

比如说 x=ab y=cd

那么 xy=abcd

这里注意

非空串和空串的连接是这个非空串本身

我们再来看方幂

符号串a

与其自身连接n次得到的符号串

我们称之为a的n次方幂

那么a的1次方就是a自己

a的2次方就是aa

这里特别提醒

a的0次方是ε

也就是空串

我们再来看符号串集合

符号串集合

假定有一个集合A

那么集合A中的一切元素

都是某个字母表上的符号串

那么我们将这个A

就称之为字母表上的符号串集合

来看一个例子

有一个字母表∑

其中只包含字母0和1

那么A={ 00,11,10，01}

那么A就是字母表{0，1}上的符号串集合

再来看一下符号串集合的乘积

假设有两个符号串集合A和B

这里给出了两个符号串

集合乘积的定义

来看一个例子

假如说集合A=｛ab，cde｝　

那B=｛0，1｝

这两个集合的乘积AB就是

AB=｛ab1，ab0，cde0，cde1｝

对于任意符号串X

和空串的连接是其本身

所以 空集和一个符合串的连接

自然是其本身了

∑*等于∑0

并上∑1 ∑2

一直并到∑n

那通常我们把∑*称之为Σ的闭包

∑上的除了ε外的所有符号串

组成的集合

我们称之为∑+

∑+ 称之为Σ的正闭包

这里是它的公式

也就是说 字母表∑上的一个语言

是∑上的符号串的集合

也可以理解为字母表∑上的

每一个语言是∑* 的一个子集

来看字母表a b

那么∑*

是包含空在内的

a b组成的

所有的可能的字符串组成的集合

∑+不包含空

大家看这里给出了∑*和∑+

那么语言集合A

就是字母表Σ上的一个语言

我们可以把它描述为

就是a的n次方

和b的n次方的连接

很明显这个语言集合

是Σ*的一个子集

语言集合B={a,aa,aaa,…}

是字母表Σ=｛a，b｝上的一个语言

同样我们也可以把它形式化的描述为

a的n次方

再来看一个例子

有两个字母表

L1 ={a,b,…y,z}

M1 ={1,2…8,9 }

这里是L1∪M1

再来看这里给出了L1M1

大家看

L1（L1∪M1）*

表示的语言集合是什么

它表示的语言集合就是

第一个符号是字母

后面跟若干个数字或字母组成的序列

实际上就是标识符的定义

所以 语言我们可以理解为

某一个字母表上的字符

按照一定规则

形成的符号串（句子）的集合

在编译系统中

语言的定义我们还需要进一步的精确化

首先 要为所定义的句子提供一种

结构性的描述

也就是语法规则

然后 还有提供一种手段

判别什么样的句子

是这种语言的正确句子

也就是进行识别和分析

好 这节课就讲到这里

谢谢大家