第二章 形式语言基础.ppt

编译原理
Compiler Principles
南京邮电大学计算机学院
徐佳
My E-mail: ******@njupt.
My Web:
教学网站:
教材:
《编译技术原理及其实现方法》王汝传编著
1
§ 引言
一、形式语言提出
二、语言描述方法
§ 用文法生成法对语言
进行描述
一、巴科斯范式
二、语法和语义
三、语法树
§ 形式语言基本概念和
术语
一、元语言
二、符号和符号串
三、产生式(规则)
四、文法
五、推导和归约
六、句型和句子
七、语言
八、递归文法
九、短语和简单短语
十、最左推导和最右推导
十一、文法二义性
§ 语法分析初步
一、自顶向下语法分析
二、自底向上语法分析
§ 文法和语言分类
一、文法分类
二、文法和自动机
三、压缩过文法
§ 文法其他表示法
一、扩充巴科斯范式
二、语法图
第二章形式语言基础知识
2
§ 引言
一、形式语言提出
二、语言描述方法
§ 用文法生成法对语言
进行描述
一、巴科斯范式
二、语法和语义
三、语法树
§ 形式语言基本概念和
术语
一、元语言
二、符号和符号串
三、产生式(规则)
四、文法
五、推导和归约
六、句型和句子
七、语言
八、递归文法
九、短语和简单短语
十、最左推导和最右推导
十一、文法二义性
§ 语法分析初步
一、自顶向下语法分析
二、自底向上语法分析
§ 文法和语言分类
一、文法分类
二、文法和自动机
三、压缩过文法
§ 文法其他表示法
一、扩充巴科斯范式
二、语法图
第二章形式语言基础知识
3
§ 引言
一、形式语言提出
二、语言描述方法
第二章形式语言基础知识
4
§ 引言
一、形式语言提出
二、语言描述方法
第二章形式语言基础知识
5
一、形式语言提出
形式语言是研究符号的语言,它仅考虑符号间的关系,不考虑含义
即用数学方法(主要是代数方法)对语言进行形式化描述。
一开始,我们介绍了什么是语言,那是非形式描述,是人们交流思想
的工具,从语言学本身来说也是一门古老的科学,但是在很早以前人们就
用数学方法开始对语言学进行研究。
1847年,俄国数学家布拉库夫斯基就用概率论进行语法词源及语言
历史比较研究。
1904年,波兰语言学家指出,语言学家不仅要掌握初等数学而且还要
掌握高等数学。
1931年,俄国数学家就用概率论研究俄语元音字母和辅音字母序列。
特别是1946年电子计算机问世以来更加促使数学和语言学结合的研究。
§ 引言
6
(乔姆斯基)在研究自然语言过程中提出一种
文法数学模型,为形式语言理论打下了基础,成为计算机科学理论
的一个重要分支,即形式语言与自动机。
为什么要提出形式语言呢?
1. 控制论的出现,促使对语言的深入研究。
2. 用计算机进行科技文献检索,自动生成文摘及其它信息处理时
要求将自然语言转换成一定形式的信息。
3. 在计算机上从一种自然语言翻译成另一种自然语言也需要对
语言进行形式描述,以便机器对其分析和综合。
4. 计算机编译理论、人工智能、数据库等需要对语言进行形式
描述。
7
§ 引言
一、形式语言提出
二、语言描述方法
第二章形式语言基础知识
8
二、语言描述方法
无论是自然语言或者是程序设计语言,都是由许多句子组成,当
然这些句子是由本语言字母表上符号并按照一定规则组成的符号串。
对一个语言的描述,就是如何刻画一个语言中哪些句子是属于该语言
的句子,哪些句子是不属于该语言的句子。
我们可以用三种方法来描述语言,枚举法、文法生成法和自动机
识别法。
:如果一个语言仅含有有限个句子,就可以采用枚举法
来描述此语言,即把语言中全部句子一一列举出来即可。然而,绝大
多数重要语言都有无穷多个语句,因此枚举法显然失效。
:就是用有限个规则来产生出语言中无限个句子,
这种规则集合称文法。
§ 引言
9
下面我们着重讨论用文法生成法来描述语言。
3. 自动机识别法:用自动机对语言中的句子进行识别,自动机是描述离散变量的一个系统(数学模型),因在形式语言中称为识别器,也可看成是一个识别程序。不同语言对应不同自动机,对应某个语言的自动机能接受该语言的句子,否则不接受。
10