[政史地]第2节课第二章.ppt

编译程序的构成 编译程序主要由八个部分构成： 1.词法分析程序（扫描器 scanner） 2.语法分析程序（分析器 parser） 3.语义分析程序 4.中间代码生成程序 5.代码优化程序 6.目标代码生成程序 7.错误检查和处理程序 8.各种信息表格的管理程序 1.3 编译程序的组织 需要注意的是，前面所说的各部分之间的关系，是指它们之间的逻辑关系，而不一定是执行时间上的先后顺序。 事实上，可按不同的执行流程来组织上述各部分的工作，这在很大程度上依赖于编译过程中对源程序扫描的遍数，以及如何划分各遍扫描所进行的工作。 此处所说的“遍”,是指对源程序或其内部表示从头到尾扫视一次,并进行有关的加工处理工作。 例如，对于要求经一遍扫描就能完成从源程序到目标代码翻译的编译程序，我们可以语法分析程序为中心来组织它的工作流程。 显然，由于整个编译程序只对源程序进行一次扫描，故不必产生中间代码。 对于某些程序语言，例如PASCAL和C，用一遍扫描的编译程序去实现比较困难，宜于采用多遍扫描的编译程序结构。 第2章 前后文无关文法和语言 在20世纪50年代，N.Chomsky首先对语言的描述问题进行了探讨。他提出了一种用来描述语言的数学系统，并以此定义了四类性质不同的语言，称为语言（文法）的Chomsky分类。 人们把用一组数学符号和规则来描述语言的方式称为形式描述，把所用的数学符号和规则称为形式语言。 目前，形式语言与自动机理论已成为计算机科学中的一个重要分支。 2.1 文法及语言的表示 首先，我们确定一个概念：什么是语言？据统计，目前在世界各地，人们所使用的语言达2700多种。 Webster的定义：“为相当大地区的公众所懂得并使用的‘话’，以及组成这些‘话’的方法的统一体”。 上述定义对于建立语言的数学理论而言不够精确。 所以，有人又将语言定义为：“某一字母表上符号串（句子）的集合” 此定义仍需精确化。因为： 1）还应为所定义的句子提供一种结构性的描述（语法规则）； 2）最好能再提供一种手段，以便能准确地判别什么是该语言中的正确句子（即识别方法、分析方法等）。 遗憾的是，对于自然语言来说，目前尚无能够完全刻划一语言全部句子的结构的方法。 然而，对大多数程序设计语言来说，此问题已被解决。1960年，P.Naur J.Backus首先用BNF（Backus-Naur-Formal（范式））对ALGOL语言进行了描述。 应指出，BNF成功地解决了程序设计语言的语法描述问题，但描述其语义，还必须借助自然语言。 通常，可用如下方式表示或定义一种语言： （1）若语言的句子有限时，可用枚举法。 例如，只含两个句子的语言： { “I am a teacher”, “You are students” }; （2）制定有限条规则，用于产生所要描述的语言的全部句子(可无限多)，这些规则构成了该语言的文法。 例如，文法G1[〈标识符〉] ： 〈标识符〉→〈字母〉|〈标识符〉〈字母〉 |〈标识符〉〈数字〉 〈字母〉→ a | b | c | … | z 〈数字〉→ 0 | 1 | 2 | … | 9 （3）建立一种装置（算法或过程），它以某字母表上的符号串为输入，判别该符号串是否为所描述语言的句子。此装置称为自动机。 2.2 文法和语言的定义2.2.1 基本概念和术语 1、字母表（符号表、符号集） 由若干元素（符 号、字母）所组成的有限非空集合。 2、符号串 用字母表中的符号所组成的任何有限 序列。 符号串的长度 = 符号串中所含符号的个数。 例：aba的长度为3。记为：|aba|=3 空串 不含任何符号的符号串，记为 ? 。 显然，| ? |= 0。 本课约定 用A、B、C、?等表示字母表或 符号串集； 用a,b,c,S,T,U 等表示符号； 用s,t,u,x,y,z,?,?,? 等表示符号串。 3、符号串的前（后）缀及子串 设 ?，?，?，x 是符号串， 若 x = ??? ，则称 ? 是 x 的子串； 特别地， 当 ?=?（?=?）时，称 ? 是 x 的前（后）缀。 4、符号串的连接和方幂 连接 设x , y是符号串，将y直接拼接到x之后所得的新符号串称为x与y的连接，记为xy 。 注意，一般说来，xy 不等于 yx；但 ?x = x? = x 方幂