编译原理第二章.ppt

1
第2章高级语言及其文法
主讲:闫健恩
计算机网络与信息安全中心
Email:yanjianen(@)
2
语言概述
基本定义
文法(Grammar)的定义
文法的分类
文法的构造
本章主要内容
3
语言概述
什么是语言?
4
语言概述
语言特征
自然语言(Natural Language)
是人与人的通讯工具
语义(semantics):环境、背景知识、语气、二义性——难以形式化
puter Language)
计算机系统间、人机间通讯工具
严格的语法(Grammar)、语义(semantics) ——易于形式化:严格
5

语言的描述方法——现状
自然语言:自然、方便-非形式化
数学语言(符号):严格、准确-形式化
形式化描述
高度的抽象,严格的理论基础和方便的计算机表示。
6
语言概述
语言——形式化的内容提取
语言(Language):满足一定条件的句子集合
句子(Sentence):满足一定规则的单词序列
单词(Token):满足一定规则的字符(Character)串
语言是字和组合字的规则
例(自然语言:第译始一天课今开编上节)
今天开始上第一节编译课
7
语言概述
程序设计语言——形式化的内容提取
程序设计语言(Programming Language):组成程序的所有语句的集合。
程序(Program):满足语法规则的语句序列。
语句(Sentence) :满足语法规则的单词序列。
单词(Token) :满足词法规则的字符串。
例:变量:=表达式
if 条件 then 语句
while条件 do 语句
call 过程名(参数表)
8
语言概述
描述形式——文法
语法——语句
语句的组成规则
描述方法:Chomsky范式、BNF范式、语法(描述)图
词法——单词
单词的组成规则
描述方法:BNF范式、正规式
9
形式语言于自动机理论的产生与作用
语言学家Chomsky最初从产生语言的角度研究语言。
1956年,通过抽象,他将语言形式地定义为是由一个字母表中的字母组成的一些串的集合。可以在字母表上按照一定的规则定义一个文法(Grammar),该文法所能产生的所有句子组成的集合就是该文法产生的语言。
克林(Kleene)在1951年到1956年间,从识别语言的角度研究语言,给出了语言的另一种描述。
克林是在研究神经细胞中,建立了自动机,他用这种自动机来识别语言:对于按照一定的规则构造的任一个自动机,该自动机就定义了一个语言,这个语言由该自动机所能识别的所有句子组成。
10
形式语言于自动机理论的产生与作用
1959年,Chomsky通过深入研究,将他本人的研究成果与克林的研究成果结合了起来,不仅确定了文法和自动机分别从生成和识别的角度去表达语言,而且证明了文法与自动机的等价性。
20世纪50年代,人们用巴科斯范式(Backus Nour Form 或 Backus Normal Form,简记为BNF)成功地对高级语言ALGOL-60进行了描述。实际上,巴科斯范式就是上下文无关文法(Context Free Grammar)的一种表示形式。这一成功,使得形式语言在20世纪60年代得到了大力的发展。