第2节课第二章

1、编译程序编译程序的构成的构成 编译程序主要由八个部分构成：编译程序主要由八个部分构成：1.1.程序（程序（扫描器扫描器 scannerscanner）2.2.程序（程序（分析器分析器 parserparser）3.3.程序程序4.4.程序程序5.5.程序程序6.6.程序程序7.7.程序程序8.8.程序程序1.2 1.2 的的词词法法分分析析程程序序语语法法分分析析程程序序语语义义分分析析程程序序中中间间代代码码生生成成代代码码优优化化程程序序目目标标代代码码生生成成信信 息息 表表 管管 理理 程程 序序错错 误误 检检 查查 和和 处处 理理 程程 序序源源程程序序目目标标代代码码1.3 需

2、要注意的是，前面所说的各部分之间的关系，需要注意的是，前面所说的各部分之间的关系，是指它们之间的是指它们之间的逻辑关系逻辑关系，而不一定是执行时，而不一定是执行时间上的先后顺序。间上的先后顺序。 事实上，可按不同的执行流程来组织上述各部事实上，可按不同的执行流程来组织上述各部分的工作，这在很大程度上依赖于编译过程中分的工作，这在很大程度上依赖于编译过程中对源程序扫描的遍数对源程序扫描的遍数，以及如何划分各遍扫描，以及如何划分各遍扫描所进行的工作。所进行的工作。 此处所说的此处所说的“遍遍”,是指对源程序或其内部表示是指对源程序或其内部表示从头到尾扫视一次从头到尾扫视一次,并进行有关的加工处理工

3、作。并进行有关的加工处理工作。 例如，对于要求经例如，对于要求经一遍扫描一遍扫描就能完成从源程就能完成从源程序到目标代码翻译的编译程序，我们可序到目标代码翻译的编译程序，我们可以语以语法分析程序为中心法分析程序为中心来组织它的工作流程。来组织它的工作流程。 语法分析语法分析程序程序语义分析及语义分析及代码生成程序代码生成程序词法分析词法分析程序程序整理目标程序整理目标程序源程序源程序目标程序目标程序停机停机开始开始图图1-3 以语法分析程序为中心的编译程序逻辑结构以语法分析程序为中心的编译程序逻辑结构 显然，由于整个编译程序只对源程序进行一显然，由于整个编译程序只对源程序进行一次扫描，故次扫描

4、，故不必产生中间代码不必产生中间代码。 对于某些程序语言，例如对于某些程序语言，例如PASCAL和和C，用一，用一遍扫描的编译程序去实现比较困难，宜于采遍扫描的编译程序去实现比较困难，宜于采用用多遍扫描多遍扫描的编译程序结构。的编译程序结构。 本章内容结束本章内容结束第第2章章 在在20世纪世纪50年代，年代，N.Chomsky首先对语言的描首先对语言的描述问题进行了探讨。他提出了一种用来描述语述问题进行了探讨。他提出了一种用来描述语言的数学系统，并以此定义了四类性质不同的言的数学系统，并以此定义了四类性质不同的语言，称为语言，称为语言（文法）的语言（文法）的Chomsky分类分类。 人们把用

5、一组数学符号和规则来描述语言的方人们把用一组数学符号和规则来描述语言的方式称为式称为形式描述形式描述，把所用的数学符号和规则称，把所用的数学符号和规则称为为形式语言形式语言。 目前，目前，形式语言与自动机理论形式语言与自动机理论已成为计算机科已成为计算机科学中的一个重要分支。学中的一个重要分支。2.1 文法及语言的表示文法及语言的表示 首先，我们确定一个概念：什么是语言？据首先，我们确定一个概念：什么是语言？据统计，目前在世界各地，人们所使用的语言统计，目前在世界各地，人们所使用的语言达达2700多种。多种。 Webster的定义：的定义：“为相当大地区的公众所懂为相当大地区的公众所懂得并使用

6、的得并使用的话话，以及组成这些，以及组成这些话话的的方法的统一体方法的统一体”。 上述定义对于建立语言的数学理论而言不够上述定义对于建立语言的数学理论而言不够精确。精确。 所以，有人又将语言定义为：所以，有人又将语言定义为：“某一字母表某一字母表上符号串（句子）的集合上符号串（句子）的集合” 此定义仍需精确化。因为：此定义仍需精确化。因为：1）还应为所定义的句子）还应为所定义的句子提供一种结构性的描述提供一种结构性的描述（语法规则语法规则）；2）最好能再提供一种手段，以便）最好能再提供一种手段，以便能准确地判别能准确地判别什么是该语言中的正确句子（什么是该语言中的正确句子（即识别方法、即识别方

7、法、分析方法等分析方法等）。 遗憾的是，对于自然语言来说，目前尚无能遗憾的是，对于自然语言来说，目前尚无能够完全刻划一语言全部句子的结构的方法。够完全刻划一语言全部句子的结构的方法。 然而，对大多数程序设计语言来说，此问题然而，对大多数程序设计语言来说，此问题已被解决。已被解决。1960年，年，P.Naur & J.Backus首先首先用用BNF（Backus-Naur-Formal（范式）对（范式）对ALGOL语言进行了描述。语言进行了描述。 应指出，应指出，BNF成功地解决了程序设计语言的成功地解决了程序设计语言的语法描述问题，但描述其语义，还必须借助语法描述问题，但描述其语义，还

8、必须借助自然语言。自然语言。 通常，可用如下方式表示或定义一种语言：通常，可用如下方式表示或定义一种语言：（1）若语言的句子有限时，可用）若语言的句子有限时，可用枚举法枚举法。 例如，只含两个句子的语言：例如，只含两个句子的语言： “I am a teacher”, “You are students” ;（2）制定）制定，用于产生所要描述的语，用于产生所要描述的语言的全部句子言的全部句子(可无限多可无限多)，这些规则构成了该，这些规则构成了该语言的语言的文法文法。 例如，文法例如，文法G1标识符标识符 ： 标识符标识符字母字母|标识符字母标识符字母 |标识符数字标识符数字 字母字母 a |

9、b | c | | z 数字数字 0 | 1 | 2 | | 9（3）建立一种）建立一种，它以某字它以某字母表上的符号串为输入，判别该符号串是否母表上的符号串为输入，判别该符号串是否为所描述语言的句子。此装置称为为所描述语言的句子。此装置称为自动机。自动机。cabbcaaSABF2.2 文法和语言的定义文法和语言的定义2.2.1 基本概念和术语基本概念和术语1、字母表（符号表、符号集）字母表（符号表、符号集） 由若干元素（符由若干元素（符 号、字母）所组成的有限非空集合。号、字母）所组成的有限非空集合。2、符号串符号串 用字母表中的符号所组成的任何有限用字母表中的符号所组成的任何有限 序列。序

10、列。 符号串的长度符号串的长度 = 符号串中所含符号的个数。符号串中所含符号的个数。 例：例：aba的长度为的长度为3。记为：。记为：|aba|=3 空串空串 不含任何符号的符号串，记为不含任何符号的符号串，记为 。 显然，显然，| |= 0。 本课约定本课约定 用用A、B、C、 等表示字母表或等表示字母表或符号串集；符号串集； 用用a,b,c,S,T,U 等表示符号；等表示符号； 用用s,t,u,x,y,z, , , 等表示符号串。等表示符号串。3、符号串的前（后）缀及子串符号串的前（后）缀及子串 设设 ， ， ，x 是符号串，是符号串， 若若 x = ，则称，则称 是是 x 的的子串子串；

11、 特别地，特别地， 当当 = （ = ）时，称）时，称 是是 x 的的前（前（后后）缀）缀。4、符号串的连接和方幂符号串的连接和方幂连接连接 设设x , y是符号串，将是符号串，将y直接拼接到直接拼接到x之后所之后所得的新符号串称为得的新符号串称为x与与y的连接，记为的连接，记为xy 。 注意，一般说来，注意，一般说来，xy 不等于不等于 yx；但但 x = x = x 方幂方幂 符号串符号串x与其自身的与其自身的 n-1次连接称为次连接称为 x 的的 n 次方幂，记为：次方幂，记为：nx 011:,.3,2xnxxxxxnn我我们们约约定定这这里里即即5、符号串集合的和与积符号串集合的和与积

12、 设设A，B为两个符号串集合，定义：为两个符号串集合，定义：和：和：A+B（或（或AB）=w | w A，或，或 w B 例如，若例如，若A=a,b,c，B=00,11，则，则 A+B=a,b,c,00,11。 积：积：AB（或（或 AB）= xy | x A, 且且y B 例如，若例如，若A=a,b,c，B=00,11，则，则 AB=a00,a11,b00,b11,c00,c11显然，显然， A+ = +A = A ； A = A = ； A = A = A6、符号串集合的方幂符号串集合的方幂)0(:,110 nAAAAAAAAnnn 的的方方幂幂定定义义是是符符号号串串集集合合设设例如，若

13、例如，若A=a,b，则，则,3210bbbbbababbaaabbabaaabaaaAbbbaabaaAbaAA 7。符号串集合的闭包符号串集合的闭包根据符号串集合的和运算，我们又可分别定义符根据符号串集合的和运算，我们又可分别定义符号串集合号串集合A的的 正闭包正闭包A+ 及及 自反传递闭包自反传递闭包A* 如下：如下： niiAAAAAA21:)(闭闭包包正正的的传传递递 AAAAAii:0* 的的自自反反传传递递闭闭包包例如，若例如，若A=a,b，则，则,bbbbbababbaaabbabaaabaaabbbaabaabaA ,*bbbbbababbaaabbabaaabaaabbbaa

14、baabaA niiAAAAA21 AAAAii0* 例例A=a,b,c,1cbaA ,2cccbcabcbbbaacabaaA ,*abaacbaA 合合上上所所有有符符号号串串构构成成的的集集实实际际上上就就是是AA*2.2 我们从我们从“产生语言产生语言”的角度出发，讨论文法的角度出发，讨论文法和语言的形式定义。和语言的形式定义。产生语言产生语言指制定出有限条规则，借助它指制定出有限条规则，借助它们就能产生出某些语言的句子。们就能产生出某些语言的句子。 我们以几个英语句子构成的语言为例进行讨我们以几个英语句子构成的语言为例进行讨论。并设每个句子都是论。并设每个句子都是“主主-谓谓-宾宾”

15、结构。结构。 其中，每个用其中，每个用 “” 括起来的部分是所要定括起来的部分是所要定义语言中的一个语法实体（称为语法单位、语义语言中的一个语法实体（称为语法单位、语法结构、法结构、语法范畴语法范畴、语法变量等）。、语法变量等）。 “:=” 是用于定义语法结构的符号，其含义是用于定义语法结构的符号，其含义（并读作）（并读作）“定义为定义为”。 语法规则也称为语法规则也称为产生式产生式(Production)。:= := the := := the :=:=:=monkey :=banana:=eat :=has:= the := a 现在讨论如何用上述规则现在讨论如何用上述规则推导推导出相应语

16、言的全出相应语言的全部部句子句子。推导推导 从语言最大的一个从语言最大的一个语法范畴语法范畴（本例中是（本例中是 ）开始，反复用语法规则中）开始，反复用语法规则中“:=” 右侧右侧的符号串取代其左侧符号，直到所得的符号串的符号串取代其左侧符号，直到所得的符号串中不再含有可被替换的中不再含有可被替换的语法范畴语法范畴。 每次替换称为一步（每次替换称为一步（直接直接）推导推导，并用符号，并用符号“”表示。例如，表示。例如， 首先用规则首先用规则进行第一步推导进行第一步推导(derivation)，就，就可得到可得到，记为：记为： 所得的符号串含有两个所得的符号串含有两个语法范畴语法范畴，可对其中任

17、，可对其中任一个一个(如对如对)进行新的进行新的推导推导（替换）：（替换）： 重复上述过程，可得到一个推导序列：重复上述过程，可得到一个推导序列：推导推导 所用所用 所得的符号串所得的符号串步骤步骤 规则规则 1 2 3 the 4 the 5 the monkey 6 the monkey eat 7 the monkey eat a 8 the monkey eat a banana 从前面的推导看，从从前面的推导看，从出发，经出发，经8步推导步推导得到了一个英语句子。故前面的推导称为得到了一个英语句子。故前面的推导称为长度长度为为8的推导的推导。 若不关心推导的中间过程，可将从一符号串到

18、若不关心推导的中间过程，可将从一符号串到 另一符号串的推导用记号另一符号串的推导用记号 表示，例如，表示，例如， 上例中经过上例中经过 5 步的推导记为：步的推导记为： 名名词词冠冠词词动动词词句句子子monkeythe规则的简化表示规则的简化表示 在前面的语法规则定义中在前面的语法规则定义中,有些语法范畴有些语法范畴(如如、)有若干条不同的规则来定义它。有若干条不同的规则来定义它。 为简明起见，我们可以将它们写在同一个左部为简明起见，我们可以将它们写在同一个左部语法范畴下，将其定义值用符号语法范畴下，将其定义值用符号“|” (读作读作或或 )隔开。如隔开。如、的的定义规则可简记为：定义规则可

19、简记为： := monkey | banana := eat | has := the | a语法规则及其产生的语言语法规则及其产生的语言 前面的语法规则可以产生前面的语法规则可以产生16个不同的句子，个不同的句子，。 应指出，所产生的句子中，有些句子的含义是应指出，所产生的句子中，有些句子的含义是荒谬荒谬的（如的（如 the banana eat a monkey 和和 the banana eat the banana 等等）。）。 然而，若不考虑然而，若不考虑语义语义，则我们就必须承认它们，则我们就必须承认它们是语法上是语法上合法合法的句子。的句子。 为得到文法的严格定义，对前面的规则进

20、为得到文法的严格定义，对前面的规则进行如下的概括：行如下的概括： 含有一系列需要定义的语法范畴，通常我们把含有一系列需要定义的语法范畴，通常我们把它们的名字称为它们的名字称为非终结符号非终结符号。 由这些非终结符号组成的集合称为由这些非终结符号组成的集合称为非终结符号非终结符号集集，用，用 VN 记之。对于上例，我们有：记之。对于上例，我们有： VN = 句子句子,主语短语主语短语,动词短语动词短语, 宾语短语宾语短语,名词名词,动词动词,冠词冠词 含有若干个基本符号，由于这些基本符号不含有若干个基本符号，由于这些基本符号不需要进一步定义，故通常将它们称为需要进一步定义，故通常将它们称为终结符

21、终结符号号。 由终结符号组成的集合称为由终结符号组成的集合称为终结符号集终结符号集，以，以VT 记之。对于上例有：记之。对于上例有： VT = monkey, banana, eat, has, the, a TNTNNTNTNVVVVVVSPVVSPVVSGSG且且词词汇汇表表字字汇汇表表称称为为法法的的开开始始符符号号。为为文文产产生生式式集集终终结结符符集集分分别别称称为为非非终终结结符符集集空空有有限限集集为为非非。其其中中是是一一四四元元组组一一文文法法定定义义),(;,12注注：为使用上的方便，我们用为使用上的方便，我们用代替产生式中的代替产生式中的 :=。另外，在不强调开始符号。

22、另外，在不强调开始符号 S 时，可将文法时，可将文法 GS 简记为简记为 G 。 GGTNUPUVUVSPVVS 或或的的直直接接推推导导记记为为是是我我们们把把通通常常。且且其其中中和和可可分分别别写写成成当当且且仅仅当当，直直接接产产生生或或的的直直接接推推导导是是称称是是一一文文法法设设定定义义,)(,22*当然，上述定义中的当然，上述定义中的 、 、 都可以是空串都可以是空串 。另外，。另外，推导符号推导符号下面的下面的G表示推导是以文法表示推导是以文法G的规则进行的规则进行的，若的，若G无须指明，则可简写为无须指明，则可简写为例如，由前面的文法例如，由前面的文法G，可得推导：可得推导

23、： 其中，其中， = , = , = := := the :=)()1(0,),2(;0),1(1,)2(,)1(),(,3 . 20*01010nnnnnnnnVVG 的的推推导导记记为为长长度度通通常常的的推推导导。则则称称为为长长度度为为对对于于步步推推导导称称为为对对于于情情况况使使上上的的符符号号串串序序列列存存在在或或如如果果产产生生的的推推导导是是符符号号串串，称称上上的的两两个个是是为为一一文文法法设设定定义义。产产生生的的句句子子是是则则称称特特别别地地，当当句句型型的的一一个个句句型型。是是则则称称若若是是文文法法设设定定义义),(,4 .2*GVGSVSGTG 例例2.1

24、：GA: A Bb B a 该文法仅有该文法仅有3个句型个句型 A, Bb, ab， 仅有仅有1个句子个句子ab。产产生生的的句句子子是是则则称称特特别别地地，当当句句型型的的一一个个句句型型。是是则则称称若若是是文文法法设设定定义义),(,4 .2*GVGSVSGTG 例例2.2：GS: S aB | Bb B a | b 该文法仅有该文法仅有6个句型个句型S, aB, Bb, aa, ab, bb， 仅有仅有3个句子个句子aa, ab, bb 。上上的的。是是定定义义于于字字母母表表故故由由于于产产生生的的语语言言。称称为为则则是是文文法法设设定定义义TTTGVGLVGLGVwwSwGLS

25、G)(,)(,|)(,5 . 2* 例例2.1：GA: A Bb B a 例例2.2：GS: S aB | Bb B a | b )(abAGL ,)(bbabaaSGL 我们看到，我们看到，L(GA)和和L(GS)是由有限的句是由有限的句子组成的。当语言是无限集时，能否用有限的规子组成的。当语言是无限集时，能否用有限的规则来描述呢？回答是肯定的则来描述呢？回答是肯定的, 只需使用文法的只需使用文法的递递归定义归定义即可。即可。例例2.1：GA: ABb Ba 例例2.2：GS: SaB|Bb Ba|b )(abAGL ,)(bbabaaSGL 例例2.3：GS: S 0S1 | 01 S,01,0S1,0011,00S11,000111,000S111,是句是句 型，其中型，其中01，0011，000111,是句子，故是句子，故 例例2.4： 设设 =a,b, 则则 + 字符串集的字符串集的BNF表示表示 如下：如下： GA: A a | b | Aa | Ab 110)( nSGLnn所谓所谓递归定义递归定义，是是指在定义一个语法成分时，指在定义一个语法成分时，直接或间接地使用了直接或间接地使用了该该语法成