语言及其文法 本章主要内容 语言概述 ? 基本定义 ? 文法(Grammar)的定义 ? CFG的分析树（Parse Tree） ? 文法的分类 ? 文法的构造 ? 语言概述 ? 什么是语言？ 语言概述 ? 语言特征 ? 自然语言(Natural ? Language) 是人与人的通讯工具 ? 环境、背景知识、语气、二义性 鲁迅对《红楼梦》的评价 ? 单是命意，就因读者的眼光而有种种：经 学家看见《易》，道学家看见淫，才子看 见缠绵，革命家看见排满，流言家 看见宫 闱秘事 。 ? 计算机语言(Computer ? Language) 计算机系统间、人机间通讯工具 ? 严格的语法(Grammar)、语义(semantics) 语言概述 ? 语言的描述方法——现状 ? 自然语言：自然、方便-不易形式化 ? 计算机语言：严格、准确-易于形式化 ? 形式化描述 ? 高度的抽象，严格的数学理论基础和方便的计 算机表示 语言概述 ? 自然语言——形式化的内容提取 ? 语言(Language)：满足一定条件的句子集合 ? 句子(Sentence)：满足一定规则的单词序列 ? 单词(Token)：满足一定规则的字符(Character)串 ? 自然语言语言是字和组合字的规则 ? 例： ? 第译始一天课今开编上节 ? 今天开始上第一节编译课 语言概述 组合规则 语言(表达意义的话) 字 不表达意义的串 无规则使用 语言概述 ? 程序设计语言——形式化的内容提取 ? 程序设计语言(Programming 所有语句的集合。 ? 程序(Program)：满足语法规则的语句序列。 ? 语句(Sentence) ：满足语法规则的单词序列。 ? 单词(Token) ：满足词法规则的字符串。 ? Language)：组成程序的 例： ? 变量=表达式 ? if 条件then 语句 ? while条件do 语句 语言概述 ? 形式化语言理论 ? 用数学方法研究自然语言（如英语）和人工语言（如 程序设计语言）的产生方式、一般性质和规则的理论。 ? 描述形式——文法 ? 语法——语句 ? 语句的组成规则 ? 描述方法：BNF范式、语法(描述)图 ? 词法——单词 ? 单词的组成规则 ? 描述方法：BNF范式、正规式 形式化语言 ? 语言学家Chomsky最初从产生语言的角度研究语言。 ? 1956年，通过抽象，他将语言形式地定义为是由一个字母表中的 字母组成的一些串的集合。可以在字母表上按照一定的规则定义 一个文法（Grammar），该文法所能产生的所有句子组成的集合 就是该文法产生的语言。 ? 克林（Kleene）在1951年到1956年间，从识别语言的角 度研究语言，给出了语言的另一种描述。 ? 克林是在研究神经细胞中，建立了自动机，他用这种自动机来识 别语言：对于按照一定的规则构造的任一个自动机，该自动机就 定义了一个语言，这个语言由该自动机所能识别的所有句子组成。 形式化语言 ? ? 1959年，Chomsky通过深入研究，将他本人的研究成果 与克林的研究成果结合了起来，不仅确定了文法和自动机 分别从生成和识别的角度去表达语言，而且证明了文法与 自动机的等价性。 20世纪50年代，人们用巴科斯范式（Backus Nour Form 或Backus Normal Form，简记为BNF）成功地对高级语 言ALGOL-60进行了描述。实际上，巴科斯范式就是上下 文无关文法（Context Free Grammar）的一种表示形式。 这一成功，使得形式语言在20世纪60年代得到了大力的发 展。 形式化语言 ? ? 形式语言与自动机理论除了在计算机科学领域中 的直接应用外，更在计算学科人才的计算思维的 培养中占有极其重要的地位。 计算思维能力的培养，主要是由基础理论系列课 程实现的，该系列主要由从数学分析开始到形式 语言结束的一些数学和抽象程度比较高的内容的 课程组成。 ? 它们构成的是一个梯级训练系统。在此系统中，连续 数学、离散数学、计算模型等三部分内容要按阶段分 开，三个阶段对应与本学科的学生在大学学习期间的 思维方式和能力的变化与提高过程的三个步骤。 计算思维能力的培养过程 中学数学 数学分析 离散数学 形式语言与 自动机理论 具体、静止 变量、运动 离散、抽象 形式、模型 单一、具体 的计算 一般、形式 化的计算 高水平计算专业人才的计算思维能力的渐进培养! 抽象集合 实数 文法 ? 文法 ? 阐明语法的一种工具 ? 形式化语言理论的基本概念 ? 以有穷的集合刻画无穷的集合 一个形式化例子 ? 句子 → 主语 谓语 ? 主语 → 名词 代词 ? 谓语 → 动词 宾语 ? 宾语 → 名词 代词 ? 名词 →小张小王小李学生篮球 ? 代词 →我你他 ? 动词 →是打 直观地认识文法 例子： 我是学生 文法的定义 如何实现语言结构 的形式化描述？ 文法的形式定义 文法 ? 为一个四元组:Ｇ = (ＶT，ＶN，Ｐ，Ｓ) ? ? ＶT：终结符(Terminal)集 ? ＶN：非终结符集，ＶT∩ＶN=Φ ? 语法成分——代表某个语言的各种子结构 ? Ｓ：开始符号(Start ? Symbol)，S∈ＶN 代表文法所定义的语言，至少在产生式左侧出现一 次 文法的形式定义 ? Ｐ：产生式(Product)集合 ? α→β，被称为产生式（定义式），读作：α定 义为β。其中α∈(ＶT∪ＶN)+，且α中至少有ＶN 中元素的一个出现。β∈(ＶT∪ＶN)*。α称为产 生式α→β的左部( Left Part)，β 称为产生式 α→β的右部(Right Part)。 ? 产生式定义各个语法成分的结构（组成规 则） 句子结构分析例子 ? Ｇ = (ＶT，ＶN，Ｐ，Ｓ) 句子 → 主语 谓语 ? 主语 → 名词 代词 ? 谓语 → 动词 宾语 ? 宾语 → 名词 代词 ? 名词 →小张小王小李学生篮球 ? 代词 →我你他 ? 动词 →是打 例子：标识符的文法 ? ? 在程序设计语言中，假设标识符的命名规则为a、 b、c开头的，字母a、b、c和数字1、2、3的序列。 命名规则： ? 字母 →abc ? 数字 →123 ? 标识符→字母 ? 标识符→ 标识符 字母 ? 标识符→ 标识符 数字 例子： 标识符的文法 ? ? 那么文法是： Ｇ = (ＶT，ＶN，Ｐ，Ｓ) ? ＶN={N, L,D} ? ＶT={a, b, c, 1, 2, 3} ? P: ? ? ? ? ? N →L N →NL N →ND L →abc D →123 L代表字母 D代表数字 N代表标识符 ? N是开始符号 例子:简单算术表达式的文法 ? 定义简单算术表达式的文法，要求： ? 只考虑加、减、乘、除的基本运算； ? 考虑括号。 a+b-c 1+3/a (a+b)*m-n 例子:简单算术表达式的文法 ? 递归定义（中缀表示） ? 标识符(id)（常数、变量）是表达式(E)； ? 表达式加一个表达式是表达式； ? 表达式减一个表达式是表达式； ? 表达式乘一个表达式是表达式； ? 表达式除一个表达式是表达式； ? 表达式加上括号后是表达式. 例子:简单算术表达式的文法 ? ? 考虑简单算术表达式组成的语言 G =({id，+，-，*，/，(，)}，{E}，P，E) ? Ｇ = (ＶT，ＶN，Ｐ， Ｓ) P: ? ? ? ? ? ? E→E + E E→E - E E→E * E E→E / E E→( E ) E→id ? 简写(假设约定：只写产生式) ? E → E + E E- E E * E E / E ( E ) id 形式语言的分类 chomsky 把形式语言分为四类，分别由四类文 法定义；四类文法的区别在于产生式的形式不同： ⑴ 0 型语言 由 0型文法定义 ? 产生式形式为：? - ? ⑵ 1 型语言 由 1型文法定义 ? 产生式形式为：xAy -x?y ⑶ 2 型语言 由 2型文法定义 ? 产生式形式为：A - ? ⑷ 3 型语言 由 3型文法定义 又称 正规文法！ 又称 上下文无关文法！ 又称 无限制文法！ 又称 上下文有关文法！ ? 产生式形式为：A-aB , A-a , A-? 【注】 四类语言为 包含关系，且有 L0 ?L1 ? L2 ? L3； 编译处理中，主要应用后两种文法！