编译原理第一章

1、1编译原理编译原理 主讲:陈小娟 E-mail: 西南大学荣昌校区信息管理系2本课程的考核：本课程的考核：l平时作业平时作业:20%l平时考勤平时考勤:10%l实验考核实验考核:20%l期末考试期末考试(闭卷闭卷):50%第一章引论引论1.1 什么是编译程序？什么是编译程序？从功能上看，一个编译程序就是一个语言翻译程序从功能上看，一个编译程序就是一个语言翻译程序,它把一种语言它把一种语言(称作源语言称作源语言)书写的程序翻译成另一种书写的程序翻译成另一种语言语言(称作目标语言称作目标语言)的等价的程序。的等价的程序。比如汇编程序是一个翻译程序，它把汇编语言程序翻比如汇编程序是一个翻译程序，它把

2、汇编语言程序翻译成机器语言。如果把编译程序看成是一个译成机器语言。如果把编译程序看成是一个“黑盒黑盒子子”，它执行的转化工作如下图：，它执行的转化工作如下图：编译程序高 级 语 言 书写 的 程 序（源程序）低级语言程序（目标程序）4 编译程序的重要性体现在它使得多数计算编译程序的重要性体现在它使得多数计算机用户不必考虑与机器有关的烦琐细节，机用户不必考虑与机器有关的烦琐细节，使程序员和程序设计专家独立于机器。这使程序员和程序设计专家独立于机器。这对于当今机器的数量和种类持续不断地增对于当今机器的数量和种类持续不断地增长的年代尤为重要。长的年代尤为重要。51.2编译过程和编译程序的结构编译过程

3、和编译程序的结构o编译程序完成从源程序到目标程序的翻译工作，编译程序完成从源程序到目标程序的翻译工作，是一个复杂的整体的过程。从概念上来讲，一个是一个复杂的整体的过程。从概念上来讲，一个编译程序的整个工作过程是划分成阶段进行的，编译程序的整个工作过程是划分成阶段进行的，每个阶段将源程序的一种表示形式转换成另一种每个阶段将源程序的一种表示形式转换成另一种表示形式，各个阶段进行的操作在逻辑上是紧密表示形式，各个阶段进行的操作在逻辑上是紧密连接在一起的。连接在一起的。o一般一个编译过程划分成一般一个编译过程划分成词法分析、语法分析、词法分析、语法分析、语义分析、中间代码生成，代码优化和目标代码语义分

4、析、中间代码生成，代码优化和目标代码生成生成六个阶段六个阶段,这是一种典型的划分方法。这是一种典型的划分方法。 编译程序的结构词法分析器语法分析器语义分析与中间代码产生器语义分析与中间代码产生器优化器目标代码生成器出错处理表格管理源程序单词符号语法单位中间代码中间代码目标代码71.词法分析词法分析o功能功能:从左到右读入源程序的每个字符，对构成从左到右读入源程序的每个字符，对构成源程序的字符流进行扫描和分解，从而识别出源程序的字符流进行扫描和分解，从而识别出一个个单词（也叫单词符号或符号）。一个个单词（也叫单词符号或符号）。o单词：逻辑上紧密相连的一组字符，这些字符单词：逻辑上紧密相连的一组字

5、符，这些字符具有集体含义。如：标识符、保留字（关键字具有集体含义。如：标识符、保留字（关键字或基本字）、算符、界符等。或基本字）、算符、界符等。例. 某源程序片断如下：begin var sum , first , count : real ; sum := first + count * 10end.词法分析阶段将他们组成如右图的单词序列.（注意:程序代码中的空格在编译时被过滤.）如果使用id1,id2,id3分别表示sum ，first ，count经过分析后：sum := first + count * 10则表示为id1:=id2+id3*10又如一个C源程序片断： int a; a

6、= a + 2;词法分析后可能返回:单词类型单词类型 单词值单词值 保留字 int标识符(变量名) a界符 ;标识符(变量名) a算符(赋值) =标识符(变量名) a算符(加) +整数 2界符 ；102.语法分析（语法分析（Syntax analysis或或Parsing）语法分析是编译过程的一个逻辑阶段。语法分析是编译过程的一个逻辑阶段。语法分析的任务是在词法分析的基础上将单词序语法分析的任务是在词法分析的基础上将单词序列组合成各类语法短语，如列组合成各类语法短语，如“程序程序”，“语句语句”，“表达式表达式”等等。语法分析程序判断源程序在结等等。语法分析程序判断源程序在结构上是否正确。构上

7、是否正确。源程序的结构由上下文无关文法描述。语法分析源程序的结构由上下文无关文法描述。语法分析程序可以用程序可以用YACC等工具自动生成。等工具自动生成。11语法分析器的两个重要作用：语法分析器的两个重要作用：根据词法分析器提供的记号流，为语法正根据词法分析器提供的记号流，为语法正确的输入构造分析树（或语法树）。确的输入构造分析树（或语法树）。检查输入中的语法（可能包括词法）错误，检查输入中的语法（可能包括词法）错误，并调用出错处理器进行适当处理。并调用出错处理器进行适当处理。下图是语法分析器在编译器模型中的位置：下图是语法分析器在编译器模型中的位置： 12语法分析器在编译器模型中的位置语法分

8、析器在编译器模型中的位置词 法分析器记 号取下一个记号源程序图1.3 语法分析器在编译器模型中的位置分析树前端其余部分语法分析器分析树符号表o语法分析得到的语法短语也称为语法单位。可以语法分析得到的语法短语也称为语法单位。可以表示成一棵树。表示成一棵树。o如：表达式如：表达式id1:=id2+id3*10 的语法树如下的语法树如下表达式表达式id1:=id2+id3*10 的语法树的另一种表达形式：的语法树的另一种表达形式：15o语法分析的依据：语言的语法规则。语法分析的依据：语言的语法规则。o每种程序设计语言都有描述程序语法结构的规每种程序设计语言都有描述程序语法结构的规则。例如，则。例如，

9、Pascal程序由程序块（又叫分程序）程序由程序块（又叫分程序）构成，程序块由语句组成，语句由表达式组成，构成，程序块由语句组成，语句由表达式组成，表达式由记号组成等等。这些规则可以用上下表达式由记号组成等等。这些规则可以用上下文无关文法或文无关文法或BNF范式（范式（Backus-Naur Form）描述。描述。16o程序的结构通常是用递归规则表示的，例如：程序的结构通常是用递归规则表示的，例如：o表达式的表示：表达式的表示：o任何标识符是表达式。任何标识符是表达式。o任何常数（整常数、实常数）是表达式。任何常数（整常数、实常数）是表达式。o若表达式若表达式1和表达式和表达式2都是表达式，那

10、么都是表达式，那么o表达式表达式1+表达式表达式2o表达式表达式1*表达式表达式2o（表达式（表达式1）o都是表达式。都是表达式。o类似地语句的表示：类似地语句的表示：o标识符标识符:=表达式表达式 是语句。是语句。owhile (表达式表达式) do 语句语句 和和if (表达式表达式) then 语句语句 else 语句语句都是语句。都是语句。173.语义分析语义分析o语义分析阶段的任务是审查源程序有无语义错误，为代码生成阶段收集类型信息。比如，语义分析的一个工作是进行进行类型审查。源程序中有些语法成分，按照语法规则去判断，它是正确的，但它不符合语义规则。比如使用了没有声明的变量；或者给一

11、个过程名赋值；或者调用函数时参数类型不合适或者参加运算的两个变量类型不匹配等等。比如下边的程序片段： o int arr2,c; c = arr1 * 10 ;其中的赋值语句是符合语法规则的，但是因为没有声明变量arr1，而存在语义错。 o又比如某些语言规定运算对象可以被强制又比如某些语言规定运算对象可以被强制,那么当二目运算那么当二目运算施于一整型和一实型对象时施于一整型和一实型对象时,编译程序将整型转化为实型而编译程序将整型转化为实型而不认为是源程序的错误，假如语句不认为是源程序的错误，假如语句sum := first + count * 10中中* 的两个运算对象：的两个运算对象： co

12、unt是实型，是实型，10是整型，则在是整型，则在语义分析阶段进行类型审查之后，在语法分析得到的分析语义分析阶段进行类型审查之后，在语法分析得到的分析树上增加一语义处理结点，表示整型转化实型的一目运算树上增加一语义处理结点，表示整型转化实型的一目运算符符inttoreal,其树如下：其树如下：194.中间代码生成中间代码生成o在进行了上述的词法分析，语法分析和语义分析阶在进行了上述的词法分析，语法分析和语义分析阶段的工作之后，有的编译程序将源程序变成一种内段的工作之后，有的编译程序将源程序变成一种内部表示形式，这种内部表示形式叫做中间语言或中部表示形式，这种内部表示形式叫做中间语言或中间代码。

13、间代码。o所谓所谓“中间代码中间代码”是一种结构简单、含义明确的记是一种结构简单、含义明确的记号系统，这种记号系统可以设计为多种多样的形式，号系统，这种记号系统可以设计为多种多样的形式，重要的设计原则为两点：一是容易生成；二是容易重要的设计原则为两点：一是容易生成；二是容易将它翻译成目标代码。很多编译程序采用了一种近将它翻译成目标代码。很多编译程序采用了一种近似似“三地址指令三地址指令”的的“四元式四元式”中间代码，这种四中间代码，这种四元式的形式为：元式的形式为：o(运算符，运算对象运算符，运算对象1，运算对象，运算对象2，结果，结果)。20215.代码优化代码优化o代码优化阶段的任务是对前

14、阶段产生的中代码优化阶段的任务是对前阶段产生的中间代码进行变换或进行改造，目的是使生间代码进行变换或进行改造，目的是使生成的目标代码更为高效，即省时间和省空成的目标代码更为高效，即省时间和省空间，或两者都有。间，或两者都有。 22依据优化所涉及的程序范围，又可分为局部优化、依据优化所涉及的程序范围，又可分为局部优化、循环优化和全局优化三个不同的级别。循环优化和全局优化三个不同的级别。236.目标代码生成目标代码生成o目标代码生成阶段的任务是把中间代码变换成目标代码生成阶段的任务是把中间代码变换成特定机器上的绝对指令代码或可重定位的指令特定机器上的绝对指令代码或可重定位的指令代码或汇编指令代码。

15、这是编译的最后阶段，代码或汇编指令代码。这是编译的最后阶段，它的工作与硬件系统结构和指令含义有关，这它的工作与硬件系统结构和指令含义有关，这个阶段的工作很复杂，涉及到硬件系统功能部个阶段的工作很复杂，涉及到硬件系统功能部件的运用、机器指令的选择、各种数据类型变件的运用、机器指令的选择、各种数据类型变量的存储空间分配以及寄存器和后缓寄存器的量的存储空间分配以及寄存器和后缓寄存器的调度等。调度等。2425o上述编译过程的六个阶段的任务，再加上用表格管理程序建立变量、常量和过程标识符的说明与引用之间的信息联系等，用出错处理程序对词法和语法分析遇到的错误给出在源程序中出错的错误性质、位置等，可分别由几

16、个模块或程序完成，它们分别称作词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、代码优化程序、目标代码生成程序、表格管理程序和出错处理程序。从而可给出一个典型的编译程序结构框图，如图1-3-1所示 261.2.3编译阶段的组合编译阶段的组合o在前面所讨论的编译过程中阶段的划分是编译程序的逻辑在前面所讨论的编译过程中阶段的划分是编译程序的逻辑组织。有时，常常把编译的过程分为前端组织。有时，常常把编译的过程分为前端(front end)和后和后端端(back end)，前端的工作主要依赖于源语言而与目标机，前端的工作主要依赖于源语言而与目标机无关无关, 后端工作依赖于目标机而一般不依赖源

17、语言后端工作依赖于目标机而一般不依赖源语言.通常前通常前端包括词法分析、语法分析、语义分析和中间代码生成这端包括词法分析、语法分析、语义分析和中间代码生成这些阶段，某些优化工作些阶段，某些优化工作, 即中间代码优化也可在前端做，也即中间代码优化也可在前端做，也包括与前端每个阶段相关的出错处理工作和符号表管理等包括与前端每个阶段相关的出错处理工作和符号表管理等工作。后端工作包括目标代码生成和目标代码优化，以及工作。后端工作包括目标代码生成和目标代码优化，以及相关出错处理和符号表操作。相关出错处理和符号表操作。 27遍遍o一个编译过程可由一遍、两遍或多遍完成。一个编译过程可由一遍、两遍或多遍完成。

18、所谓所谓“遍遍”，也称作，也称作“趟趟”，是对源程序或其等价的中间，是对源程序或其等价的中间语言程序从头到尾扫视并完成规定任务的过程。语言程序从头到尾扫视并完成规定任务的过程。每一每一遍扫视可完成上述一个阶段或多个阶段的工作。例如遍扫视可完成上述一个阶段或多个阶段的工作。例如一遍可以只完成词法分析工作；一遍完成词法分析和一遍可以只完成词法分析工作；一遍完成词法分析和语法分析工作；甚至一遍完成整个编译工作。对于多语法分析工作；甚至一遍完成整个编译工作。对于多遍的编译程序，第一遍的输入是用户书写的源程序，遍的编译程序，第一遍的输入是用户书写的源程序，最后一遍的输出是目标语言程序，其余是上一遍的输最

19、后一遍的输出是目标语言程序，其余是上一遍的输出为下一遍的输入。出为下一遍的输入。 o在实际的编译系统的设计中，编译的几个阶段的工作究竟应该怎样组合，即编译程序究竟分成几遍，参考的因素主要是源语言和机器（目标机）的特征。o比如源语言的结构直接影响编译的遍的划分； 像PL/1或ALGOL68那样的语言，允许名字的说明出现在名字的使用之后，那么在看到名字之前是不便为包含该名字的表达式生成代码的，这种语言的编译程序至少分成两遍才容易生成代码。另外机器的情况，即编译程序工作的环境也影响编译程序的遍数的划分。一个多遍的编译程序可以较之一遍的编译程序少占内存，遍数多一点，整个编译程序的逻辑结构可能清晰些，但

20、遍数多即意味着增加读写中间文件的次数，势必消耗较多时间，显然会比一遍的编译要慢。291.3 解释程序和一些软件工具解释程序和一些软件工具o1.3.1解释程序解释程序o为了实现在一个计算机上运行高级语言的程序为了实现在一个计算机上运行高级语言的程序,主要有两个途径：主要有两个途径：o第一个途径是把该程序翻译为这个计算机的指令代码序列，这就是我第一个途径是把该程序翻译为这个计算机的指令代码序列，这就是我们已经描述的编译过程。们已经描述的编译过程。o第二个途径是编写一个程序，它解释所遇到的高级语言程序中的语句第二个途径是编写一个程序，它解释所遇到的高级语言程序中的语句并且完成这些语句的动作，这样的程

21、序就叫并且完成这些语句的动作，这样的程序就叫解释程序解释程序。从功能上说，。从功能上说，一个解释程序能让计算机执行高级语言。它与编译程序的主要不同是一个解释程序能让计算机执行高级语言。它与编译程序的主要不同是它不生成目标代码，它每遇到一个语句，就要对这个语句进行分析以它不生成目标代码，它每遇到一个语句，就要对这个语句进行分析以决定语句的含义，执行相应的动作。决定语句的含义，执行相应的动作。30o用一图来表示如下用一图来表示如下:31o编译系统生成的目标代码由计算机执行才能生成结果。使用编译系统时会区分编译阶段和运行阶段，编译阶段对源程序进行编译，运行阶段是指目标程序的运行。o而解释系统则是边解

22、释边执行。从存储组织来看，在编译阶段，存储区一般要有源程序缓冲区，目标代码缓冲区，名字表以及编译程序使用的源程序中间表示和各种表格等等。在运行阶段，存储区只有目标代码和数据区了。对解释系统来说，在它工作的自始至终，存储区中要有源程序，名字表，标号表等表格，输入输出缓冲区以及数据区等等 o解释执行解释执行 不生成目标代码 能支持交互环境（同增量式编译系统） 优点：交互方便，节省空间。缺点：效率低。因对源程序的循环语句部分要反复解释执行。共同点：都需进行词法、语法、语义分析。可比喻为：编译是笔译（产生目标程序）解释是口译（不产生目标程序） 很多语言如BASIC,LISP和PROLOG等等最初都是解

23、释执行的，后来也都有了编译系统。号称最具生命力的JAVA环境同时需要解释和编译系统的支持 1.4 编译器中的主要数据结构编译器中的主要数据结构o(1) 记号（t o k e n）o当扫描程序将字符收集到一个记号中时，它通常是以符号表示这个记号；这也就是说，作为一个枚举数据类型的值来表示源程序的记号集。有时还必须保留字符串本身或由此派生出的其他信息（例如：与标识符记号相关的名字或数字记号值）。在大多数语言中，扫描程序一次只需要生成一个记号（这称为单符号先行（ single symbol lookahead）。在这种情况下，可以用全程变量放置记号信息；而在别的情况（最为明显的是FORT RAN）下

24、，则可能会需要一个记号数组。o(2) 语法树（syntax tree）o如果分析程序确实生成了语法树，它的构造通常为基于指针的标准结构，在进行分析时动态分配该结构，则整棵树可作为一个指向根节点的单个变量保存。结构中的每一个节点都是一个记录，它的域表示由分析程序和之后的语义分析程序收集的信息。例如，一个表达式的数据类型可作为表达式的语法树节点中的域。有时为了节省空间，这些域也是动态分配或存放在诸如符号表的其他数据结构中，这样就可以有选择地进行分配和释放。实际上，根据它所表示的语言结构的类型（例如：表达式节点对于语句节点或声明节点都有不同的要求），每一个语法树节点本身都可能要求存储不同的属性。在这

25、种情况下，可由不同的记录表示语法树中的每个节点，每个节点类型只包含与本身相关的信息。o(3) 符号表（symbol table）o这个数据结构中的信息与标识符有关：函数、变量、常量以及数据类型。符号表几乎与编译器的所有阶段交互：扫描程序、分析程序或将标识符输入到表格中的语义分析程序；语义分析程序将增加数据类型和其他信息；优化阶段和代码生成阶段也将利用由符号表提供的信息选出恰当的代码。因为对符号表的访问如此频繁，所以插入、删除和访问操作都必须比常规操作更有效。尽管可以使用各种树的结构，但杂凑表却是达到这一要求的标准数据结构。有时在一个列表或栈中可使用若干个表格。o(4) 常数表（literal table）o常数表的功能是存放在程序中用到的