编译原理课件第章.ppt

第2章?高级语言及其文法 2.1 语言概述 2.2 基本定义 2.3 文法的定义 2.4 文法的分类 2.5 CFG的语法树 2.6 CFG的二义性 2.7 本章小结 2.1 语言概述 什么是语言？ 2.1 语言概述 信息交流的基础是什么？ 按照共同约定的生成规则和理解规则去生成“句子”和理解“句子” 例： “今节日上课始开译第一编” “今日开始上第一节编译课” 2.1 语言概述 语言的特征 自然语言(Natural Language) 是人与人的通讯工具 语义(semantics):环境、背景知识、语气、二义性——难以形式化 计算机语言(Computer Language) 计算机系统间、人机间通讯工具 严格的语法(Grammar)、语义(semantics) ——易于形式化：严格 2.1 语言概述 语言的描述方法——现状 自然语言：自然、方便-非形式化 数学语言（符号）：严格、准确-形式化 形式化描述 高度的抽象、严格的理论基础和方便的计算机表示 2.1 语言概述 语言——形式化的内容提取 语言(Language)：满足一定条件的句子集合 句子(Sentence)：满足一定规则的单词序列 单词(Token)：满足一定规则的字符(Character)串 语言是字和组合字的规则 例（自然语言：第译始二天课今开编上节） 今天开始上第二节编译课 2.1 语言概述 2.1 语言概述 程序设计语言——形式化的内容提取 程序设计语言(Programming Language)：组成程序的所有语句的集合。 程序(Program)：满足语法规则的语句序列。 语句(Sentence) ：满足语法规则的单词序列。 单词(Token) ：满足词法规则的字符串。 例：变量:=表达式 if 条件表达式 then 语句 while 条件表达式 do 语句 call 过程名(参数表) 2.1 语言概述 描述形式——文法 语法——语句 语句的组成规则 描述方法：BNF范式、语法(描述)图 词法——单词 单词的组成规则 描述方法：BNF范式、正规式 形式语言与自动机理论的产生与作用 语言学家Chomsky最初从产生语言的角度研究语言。 1956年，通过抽象，他将语言形式地定义为是由一个字母表中的字母组成的一些串的集合。可以在字母表上按照一定的规则定义一个文法（Grammar），该文法所能产生的所有句子组成的集合就是该文法产生的语言。 形式语言与自动机理论的产生与作用 克林（Kleene）在1951年到1956年间，从识别语言的角度研究语言，给出了语言的另一种描述 克林是在研究神经细胞中，建立了自动机 对于按照一定的规则构造的任一个自动机，该自动机就定义了一个语言，这个语言由该自动机所能识别的所有句子组成 形式语言与自动机理论的产生与作用 1959年，Chomsky通过深入研究，将他本人的研究成果与克林的研究成果结合了起来，不仅确定了文法和自动机分别从生成和识别的角度去表达语言，而且证明了文法与自动机的等价性。 形式语言与自动机理论的产生与作用 20世纪50年代，人们用巴科斯范式（Backus Nour Form 或 Backus Normal Form，简记为BNF）成功地描述ALGOL-60 促进形式语言在20世纪60年代的大发展 巴科斯范式就是上下文无关文法（Context Free Grammar）的一种表示形式 2.2 基本定义 定义2.1 字母表（Alphabet）∑是一个非空有穷集合，字母表中的元素称为该字母表的一个字母（Letter），也叫字符（Character） 例 以下是不同的字母表： ⑴ {a，b，c，d} ⑵ {a，b，c，……，z} ⑶ {0，1} (4) {+, -, *, /, !, ……, \t, \n} 2.2 基本定义 定义2.2 设∑1、∑2是两个字母表，∑1与∑2 的乘积(Product)定义为∑1∑2={ab|a∈∑1，b∈∑2} 例:∑1={0,1}, ∑2={a,b}, ∑1∑2 ={0a,0b,1a,1b} 定义2.3 设∑是一个字母表，∑的n次幂(Power)递归地定义为： ⑴ ∑0={ε} ⑵ ∑n=∑n-1∑ n≥1 例： ∑13 ={000,001,010,011,100,101,110,111} ∑14 ={0000,0001,0010,0011,0100,……,1111} 2.2 基本定义 定义2.4 设∑是一个字母表，∑的正闭包(Positive Closure)定义为： ∑+=∑∪∑2∪∑3∪∑4∪…… ∑的克林闭包(Kleene Closure)为： ∑*=∑0∪∑+ =∑0∪∑∪∑2∪∑3∪…… 2.2 基本定义 例 {0,1