第二章 形式语言基础(1)

26
编译程序如何将源程序变成目标程序？
第一：就是语法分析，看源程序是否符合该语言的语法关系 第二：就是语义分析，根据该语言语义生成目标代码 这是两个核心问题。
27
第二章
§2.2
形式语言基础知识
用文法生成法对语言进行描述
一、巴科斯范式 二、语法和语义
1.语法 2.语义
三、语法树
28
§2.2
用文法生成法对语言进行描述
<谓语>
33
三、语法树
除了上面可以根据语言语法规则来推导出句子，还可以用图解形式来 表示。以图解（树）形式来描述句子语法结构关系，称语法树。
17
①〈句子〉∷=〈主语〉〈谓语〉 ②〈主语〉∷=<冠词><形容词>〈名词〉 ③〈冠词〉∷=the ④<形容词> ∷= big ⑤〈谓语〉∷=〈动词〉〈宾语〉 ⑥ 〈动词〉∷=ate ⑦ 〈宾语〉∷=〈冠词〉〈名词〉 ⑧〈名词〉∷=elephant | peanut 我们把这种描述语法规则方法称巴科斯范式，也称巴科斯--瑙尔范式 (Backus Normal Form)，简称BNF。 根据以上规则，可以推导出句子The big elephant ate the peanut. 过程如下：
形式语言与自动机理论正式诞生，成为 计算机科学理论一个重要分支，迅速在计 算机科学技术领域的得到了应用。
9
形式语言理论研究的对象不仅是自然语 言，也有人工语言（包括计算机编程的高 级语言）。乔姆斯基的形式语言理论得到 了多重验证，于是才为语言学界和计算机 科学界所折服， “引发了语言学中的伽利略式的科学革 命的开端”
§2.5 文法和语言分类
一、文法分类 二、文法和自动机 三、压缩过文法
§2.3 形式语言基本概念和 术语
一、元语言 二、符号和符号串 三、产生式（规则） 四、文法 五、推导和归约 六、句型和句子 七、语言
§2.6 文法其他表示法
一、扩充巴科斯范式 二、语法图
14
第二章
§2.2
形式语言基础知识
用文法生成法对语言进行描述
§2.2 用文法生成法对语言 进行描述
一、巴科斯分析初步
一、自顶向下语法分析 二、自底向上语法分析
§2.5 文法和语言分类
一、文法分类 二、文法和自动机 三、压缩过文法
§2.3 形式语言基本概念和 术语
一、元语言 二、符号和符号串 三、产生式（规则） 四、文法 五、推导和归约 六、句型和句子 七、语言
三、语法树
除了上面可以根据语言语法规则来推导出句子，还可以用图 解形式来表示。以图解（树）形式来描述句子语法结构关系， 称语法树。
29
句子 the man has a book
①〈句子〉∷=〈主语〉〈谓语〉 ②〈主语〉∷=<冠词><形容词>〈名词〉 ③〈冠词〉∷=the ④<形容词> ∷= big ⑤〈谓语〉∷=〈动词〉〈宾语〉 ⑥ 〈动词〉∷=ate ⑦ 〈宾语〉∷=〈冠词〉〈名词〉 ⑧〈名词〉∷=elephant | peanut
一、巴科斯范式 二、语法和语义
1.语法 2.语义
三、语法树
15
第二章
§2.2
形式语言基础知识
用文法生成法对语言进行描述
一、巴科斯范式 二、语法和语义
1.语法 2.语义
三、语法树
16
§2.2
用文法生成法对语言进行描述
一、巴科斯范式
巴科斯范式 BNF--Backus Normal Form The big elephant ate the peanut.(大象吃花生） The little boy ran quickly.(小男孩跑得快） The man has a pig.(这人有一只猪） 以上都是符合英语语法规则的句子，即它们是在英语语法规则中成立 的句子。 如何描述一个给定的句子在给定规则下是否成立呢？ 我们以“∷=”符号(或“→”符号)表示定义为，以“|”符号表示 “或”， 以“〈 〉”符号表示语法实体(语法单位)，这些符号是元语言符号， 那么上面叙述<句子>的语法规则可写为：
一、自顶向下语法分析 二、自底向上语法分析
§2.5 文法和语言分类
一、文法分类 二、文法和自动机 三、压缩过文法
§2.3 形式语言基本概念和 术语
一、元语言 二、符号和符号串 三、产生式（规则） 四、文法 五、推导和归约 六、句型和句子 七、语言
§2.6 文法其他表示法
一、扩充巴科斯范式 二、语法图
10
第二章
§2.1 引言
形式语言基础知识
一、形式语言提出 二、语言描述方法
11
§2.1
引言
二、语言描述方法
无论是自然语言或者是程序设计语言，都是由许多句子组成，当然 这些句子是由本语言字母表上符号并按照一定规则组成的符号串。对 一个语言的描述，就是如何刻画一个语言中哪些句子是属于该语言的 句子，哪些句子是不属于该语言的句子。 我们可以用三种方法来描述语言，枚举法、文法生成法和自动机 识别法 。 1. 枚举法 ：如果一个语言仅含有有限个句子，就可以采用枚举法 来描述此语言，即把语言中全部句子一一列举出来即可。然而，绝大 多数重要语言都有无穷多个语句，因此枚举法显然失效。
6
1956年N.Chomsky(乔姆斯基）在研究 自然语言过程中提出一种文法数学模型 ，为形式语言理论打下了基础。
7
数学家Kleene（克林）在研究神经细胞 时建立了自动机模型，使用该模型来识别 一个语言。
输入文件
控制部件
存 储
输出
8
乔姆斯基1959将形式语言的研究成果和自 动机的研究成果结合
用文法生成法对语言进行描述
二、语法和语义
2.语义
语义是按照语法规则所构成结构的含义 。 对于自然语言，语义是所要表达的意思；对于程序设计语言，语义 是一个程序所要完成工作，或者某个语法成分的含义。显然，一个句子 语法上正确不等于语义上也是正确的。例如，“人吃石头”在语法上是 正确，在语义上是荒谬的。 在PASCAL语言中，标识符以字母开头是语法，而标识符使用必须加 以说明则是语义。 对于语法目前研究比较成熟，可以进行形式描述，但 对语义的描述还没能形式化，还得借助于自然语言。
21
第二章
§2.2
形式语言基础知识
用文法生成法对语言进行描述
一、巴科斯范式 二、语法和语义
1.语法 2.语义
三、语法树
22
第二章
§2.2
形式语言基础知识
用文法生成法对语言进行描述
一、巴科斯范式 二、语法和语义
1.语法 2.语义
三、语法树
23
§2.2
用文法生成法对语言进行描述
二、语法和语义
1.语法
3
第二章
§2.1 引言
形式语言基础知识
一、形式语言提出 二、语言描述方法
4
第二章
§2.1 引言
形式语言基础知识
一、形式语言提出 二、语言描述方法
5
§2.1
引言
一、形式语言提出
形式语言是研究符号的语言，它仅考虑符号间的关系，不考虑含义 即用数学方法（主要是代数方法）对语言进行形式化描述。 一开始，我们介绍了什么是语言，那是非形式描述，是人们交流思想 的工具，从语言学本身来说也是一门古老的科学，但是在很早以前人们就 用数学方法开始对语言学进行研究。 1847年，俄国数学家布拉库夫斯基就用概率论进行语法词源及语言 历史比较研究。 1904年，波兰语言学家指出，语言学家不仅要掌握初等数学而且还要 掌握高等数学。 1931年，俄国数学家就用概率论研究俄语元音字母和辅音字母序列。 特别是1946年电子计算机问世以来更加促使数学和语言学结合研究。
19
巴科斯范式是描述语法规则一种表示方法,它是由巴科 斯为了在ALGOL60 报告中来描述ALGOL语言首先提出的。采 用这种形式体系方式定义语法规则,可以用简洁的公式把各 种语法规则严格而清晰描述出来。例如,在高级语言中大家 所熟知的〈标识符〉这种语法成分,它用巴科斯范式描述为:
〈标识符〉∷=〈字母〉|〈标识符〉〈字母〉|〈标识符〉〈数字〉 而 〈字母〉∷=A|B|C|D|…|Z 〈数字〉∷=0|1|2|…|9 这样便刻画出了〈标识符〉是以字母开始的一串字母和数字任意组 合这种特点。
20
用巴科斯范式描述语言能给研究问题带来很大方便。如下面9个句子都是 正确的： ①We ran ② He ran ③I ran ④We ate ⑤ He ate ⑥I ate ⑦We sat ⑧ He sat ⑨I sat 如果我们用巴科斯范式来描述上面9个句子只要几条规则就行了。 ①〈句子〉∷=〈主语〉〈谓语〉 ②〈主语〉∷=We |He |I ③ 〈谓语〉∷=ran|ate|sat 可见，如果一个语言有无穷多个句子，那么用上述规则来描述更有实际 意义.它用一组规则来代替枚举法，用有穷来描述无限。
31
句子 the man has a book 的推导过程及对应的语法树
<句子>
32
三、语法树
除了上面可以根据语言语法规则来推导出句子，还可以用图解形式来 表示。以图解（树）形式来描述句子语法结构关系，称语法树。
（句子the man has a book的推导过程及对应的语法树） <句子>
<主语>
编 译 原 理
Compiler Principles 南京邮电大学计算机学院 蒋凌云 jianglingyun@
教材：《编译技术原理及其实现方法》王汝传 编著
1
第二章
§2.1 引言
一、形式语言提出 二、语言描述方法
形式语言基础知识
八、 递归文法 九、短语和简单短语 十、最左推导和最右推导 十一、文法二义性
30