语言及其文法
本章主要内容 语言概述 基本定义 文法(Grammar)的定义 CFG的分析树（Parse Tree） 文法的分类 文法的构造
语言概述 什么是语言？
语言概述 语言特征 自然语言(Natural Language) 是人与人的通讯工具 环境、背景知识、语气、二义性
鲁迅对《红楼梦》的评价 单是命意，就因读者的眼光而有种种：经学家看见《易》，道学家看见淫，才子看见缠绵，革命家看见排满，流言家 看见宫闱秘事 。
计算机语言(Computer Language) 计算机系统间、人机间通讯工具 严格的语法(Grammar)、语义(semantics)
语言概述 语言的描述方法——现状 形式化描述 自然语言：自然、方便-不易形式化 计算机语言：严格、准确-易于形式化 高度的抽象，严格的数学理论基础和方便的计算机表示
语言概述 自然语言——形式化的内容提取 自然语言语言是字和组合字的规则 语言(Language)：满足一定条件的句子集合 句子(Sentence)：满足一定规则的单词序列 单词(Token)：满足一定规则的字符(Character)串 自然语言语言是字和组合字的规则 例： 第译始一天课今开编上节 今天开始上第一节编译课
语言概述 组合规则 语言(表达意义的话) 字 不表达意义的串 无规则使用
语言概述 程序设计语言——形式化的内容提取 例： 程序设计语言(Programming Language)：组成程序的所有语句的集合。 语句(Sentence) ：满足语法规则的单词序列。 单词(Token) ：满足词法规则的字符串。 例： 变量=表达式 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的序列。 命名规则： <数字> →1|2|3 <标识符>→<字母> <标识符>→ <标识符> <字母> <标识符>→ <标识符> <数字>
例子： 标识符的文法 那么文法是： Ｇ = (ＶT，ＶN，Ｐ，Ｓ) ＶN={N, L,D} ＶT={a, b, c, 1, 2, 3} P: N →ND L →a|b|c D →1|2|3 N是开始符号 L代表<字母> D代表<数字> N代表<标识符>
例子:简单算术表达式的文法 定义简单算术表达式的文法，要求： 只考虑加、减、乘、除的基本运算； 考虑括号。 a+b-c 1+3/a (a+b)*m-n
例子:简单算术表达式的文法 递归定义（中缀表示） 标识符(id)（常数、变量）是表达式(E)； 表达式加一个表达式是表达式； 表达式减一个表达式是表达式； 表达式乘一个表达式是表达式； 表达式除一个表达式是表达式； 表达式加上括号后是表达式.
例子:简单算术表达式的文法 考虑简单算术表达式组成的语言 G =({id，+，-，*，/，(，)}，{E}，P，E) Ｇ = (ＶT，ＶN，Ｐ，Ｓ) 考虑简单算术表达式组成的语言 G =({id，+，-，*，/，(，)}，{E}，P，E) 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 ->xy 又称 上下文无关文法！ ⑶ 2 型语言 由 2型文法定义 产生式形式为：A -> 又称 正规文法！ ⑷ 3 型语言 由 3型文法定义 产生式形式为：A->aB , A->a , A-> 【注】 四类语言为 包含关系，且有 L0 ⊃L1 ⊃ L2 ⊃ L3； 编译处理中，主要应用后两种文法！