编译原理第一章

1、说明n教材n编译技术第2版 清华大学出版社 张素琴等。n参考书n编译原理 机械工业出版社出版 赵建华，郑滔，戴新宇翻译。n电子课堂n校园网http:/主页中“教学天地”栏目中“电子课堂”中的“计算机系”第一章第一章 引论引论2015年9月第一章 引论n1.0 语言处理器n1.1 什么是编译程序?n1.2 编译过程概述n1.3 编译程序的结构n1.4 编译阶段的组合n1.5 编译技术和软件工具1.0 语言处理器n编译器编译器n编译器就是一个程序；n编译器可以阅读某种语言（源语言）编写的程序，并且把这个程序翻译为一个等价的、用另外一种语言（目标语言）描述的程序；n编译器还有另外一个重要任务就是报告

2、编译过程中出现的错误。n解释器解释器n解释器不通过翻译的方式生成目标程序。n直接利用输入信息，执行源程序中指定的操作，输入一句，执行一句，不保存中间结果。编译器目标程序解释器输出目标程序输出输入输入源程序1.0 语言处理器n编译器与解释器编译器与解释器n编译器产生的机器语言目标程序通常比一个解释器快得多；n解释器的错误诊断效果要比编译器更好。nJAVA语言处理过程编译与解释的结合n首先，JAVA源程序被编译为一个称为字节码的（bytecode）中间表示形式；n然后，虚拟机对字节码进行解释执行。n编译和解释可以在不同的机器上进行，有利于网络应用和跨平台运行。翻译器虚拟机源程序输出输入字节码需要处

3、理的源程序预处理程序源程序编译器目标汇编程序汇编器可重定位的机器代码链接器加载器目标（绝对）机器代码一个源程序可能被分割成多个模块，并且存放在独立的文件中；预处理程序完成这些文件的合并、宏展开等工作，将需要处理的源程序汇集在一起。经过预处理的源程序作为输入传递给编译程序，并且产生一个汇编程序作为输出。大型程序经常被分成多个部分进行编译，因此，可重定位的机器代码有必要和其他可重定位的目标文件以及库文件连接在一起，形成最终的机器代码。语言处理过程系统语言处理过程系统汇编语言程序由汇编器进行处理，并生成可重定位的机器代码。库文件/可重定位的对象文件链接器能够解决外部内存地址的问题，因为，有时一个文件

4、代码可能指向另一个文件中的位置；加载器把所有的可执行目标文件放在内存中执行。1.1 什么是编译程序什么是编译程序?n一个编译程序就是一个语言翻译程序。它把一种语言（称作源语言）书写的程序翻译成另一种语言（称作目标语言）的等价程序。n编译程序是计算机系统的基本组成部分之一，一个计算机系统可以有多个高级语言的编译程序。有的高级程序设计语言甚至配置了几个不同性能的编译程序n编译程序的重要性体现在它使得多数计算机用户不必考虑编译程序的重要性体现在它使得多数计算机用户不必考虑与机器有关的繁琐细节，使程序员和程序设计者独立于机与机器有关的繁琐细节，使程序员和程序设计者独立于机器。适合机器种类和数量的增长器

5、。适合机器种类和数量的增长.编译程序高级语言程序（源程序）低级语言程序（目标程序）n源语言种类成千上万，目标语言也是成千上万，编译程序根据它们的构造不同，所执行的具体功能的差异又分成了各种类型。n尽管存在各种类型的编译程序，但是各种编译程序所必须执行的主要任务基本是一样的，通过理解这些任务，使用同样的基本技术，我们可以为各种各样的源语言和目标语言设计和构造编译程序。n也就是说编译程序的构成是有规律可循的，是值得分析和总结的。编译程序有规律可循编译程序有规律可循全局角度认识编译程序n编译过程就是将源程序映射到语义上等价的目标程序；n映射过程分为两个部分：n分析分析n把源程序分解成为多个组成要素，

6、并在这些要素上加语法结构；n利用这个语法结构创建该源程序的一个中间表示；n分析源程序是否按照语法构成，或者语义是否一致，并且提供相关信息；n将分析过程产生的相关信息存贮在一个符号表数据结构中。n将符号表和中间表示形式一同传递给综合部分。n综合综合n根据符号表和中间表示形式的信息来构造目标程序。1.分析部分通常被称为编译器前端前端；综合部分通常被称为编译器的后端后端细节角度认识编译程序n实际上，编译过程是一组顺序执行的步骤；n每个步骤把源程序的一种表示方式转换成另一种表示方式，一步一步接近最终的目标程序；n实践过程中，往往将多个步骤组合在一起，构成一个阶段，在这个阶段过程中，不需要将每个步骤中间

7、结果表示出来，只需要将这个阶段的中间结果表示出来，传递给下一阶段；n机器无关代码往往作为编译过程前端和后端的分水岭，只是将前一阶段中间代码表示转换为另外一种形式。字符流词法分析器语法分析语义分析中间代码生成器机器无关代码优化器代码生成器机器相关代码优化器目标机器语言符号流语法树语法树中间表示形式中间表示形式目标机器语言1.2 编译过程概述（一）n编译程序完成从源程序到目标程序的翻译工作，是一个复杂的整体的过程。n一个编译程序的整个工作过程是划分成阶段进行的，每个阶段将源程序的一种表示形式转换成另一种表示形式，各个阶段进行的操作在逻辑上是紧密连接在一起的。n编译过程通常划分成词法分析词法分析、语

8、法分析语法分析、语义分析语义分析、中间代码生中间代码生成成、代码优化代码优化和目标代码生成目标代码生成六个阶段。另外有两个重要工作：表格管理和出错处理与上述六项阶段都有联系。n编译过程中源程序的各种信息被保留在种种不同的表格中，编译各阶段的工作都涉及到构造、查找和更新有关表格，因此，需要表格的管理工作。n如果编译过程中发现源程序有错误，编译程序应报告错误的性质和错误发生的地点，并且将错误所造成的影响限制到最小的范围内。使得编译工作得以继续。1.2 编译过程概述（二）n词法分析阶段词法分析阶段：编译过程的第一个阶段。这个阶段的任务是从左到右一个字符一个字符地读入源程序，对构成源程序的字符流进行扫

9、描和分解，从而识别出一个个单词。n逻辑上紧密相连的一组字符，这些字符具有集体含义。n单词：标识符，保留字，算符，界符等。n对于每个单词要素，词法分析产生（输出）如下的表示形式：（单词类型，单词有效值）；包括两个分量。n也就是说经过词法分析，输出中间表示代码形式将传递给下一阶段，语法分析。n描述词法规则的有效工具是正规式和有限自动机。 begin var sum , first , count:real; sum:=first+count*10 end.用id1,id2和id3分别表示sum， first和count三个标识符的内部形式，经过词法分析，上述赋值语句变为：id1:=id2+id3*

10、10保留字保留字标识符标识符运算符运算符界符界符一个一个C C源程序片断：源程序片断：int a;a = a + 2;词法分析后可能返回:单词类型 单词值保留字 int标识符 a界符 ;标识符 a 算符 (赋值) =标识符 a算符 (加) +整数 2界符 ；1.2 编译过程概述（三）n语法分析语法分析：编译过程的第二个阶段。语法分析的任务是在词法分析的基础上将单词序列分解成各类语法短语语法短语，如：“程序”、“语句”、“表达式”等等。n语法分析所依据的是语言的语法规则，即描述程序结构的规则。通过语法分析确定整个输入串是否构成一个语法上正确的程序。n程序的结构通常是由递规规则表示的。n递规规则反

11、映出语法单位的层次结构。n语法规则通常用上下文无关文法描述。例：sum:=first+count*10 ;规则 :=“:=” :=“+” :=“*” :=“(”“)” := := :=语法分析的一种表示方法一组递一组递归语法归语法规则描规则描述述“赋赋值语句值语句”这个语这个语法单元。法单元。整数（整数（10）赋值语句赋值语句标识符标识符 ：= 表达式表达式表达式表达式 + 表达式表达式表达式表达式 * 表达式表达式标识符标识符id2(first)标识符标识符id3(count)id1(sum)语法树表示方法语法树表示方法从上向下的分析方法。从上向下的分析方法。1.2 编译过程概述（四）n词法

12、分析和语法分析本质上都对源程序的结构进行分析。n词法分析的任务仅对源程序进行线性扫描即可完成，比如识别标识符，因为标识符的结构是字母打头的字母和数字串，这只要顺序扫描输入流，遇到既不是字母又不是数字字符时，将前面所发现的所有字母和数字组合在一起而构成单词标识符。n语法分析识别递归定义的语法成分（单元）。1.2 编译过程概述（五）n语义分析阶段语义分析阶段：使用语法树和符号表中的信息来检查源程序是否和语言定义一致；审查源程序有无语义错误，为代码生成阶段收集类型信息。n语义分析的一个工作是进行类型审查，审查每个算符是否具有语言规范允许的运算对象，当不符合语言规范时，编译程序应报告错误。n比如使用了

13、没有声明的变量；或者给一个过程名赋值；或者调用函数时参数类型不合适或者参加运算的两个变量类型不匹配等等。 ：=Id1(sum)Id2(first)Id3(count)+*Inttoreal（整型转实型）（整型转实型）10比如下边的程序片段：int arr2,c;c = arr1 * 10 ;其中的赋值语句是符合语法规则的，但是因为没有声明变量arr1，而存在语义错。 语义分析主要的任务语义分析主要的任务n完成静态语义审查和处理n上下文相关性审查n类型匹配审查n类型转换 1.2 编译过程概述（六）n将一个源程序翻译为目标代码的过程中，可能会构造出一个或者多个中间表示形式。语法树就是其中的一种，它

14、在语法分析和语义分析中使用；n中间代码生成中间代码生成：在进行了上述的语法分析和语义分析阶段的工作以后，有的编译程序将源程序变成一种内部表示形式，这种内部表示形式叫做中间语言或中间代码。n这种中间代码是一种明确的低级的或者类机器语言的中间表示。可以看作是某种抽象机器的程序某种抽象机器的程序；n所谓“中间代码”是一种结构简单、含义明确的记号系统，这种记号系统可以设计为多种多样形式，重要的设计原则是两点：一是容易生成，二是容易将它翻译成目标代码。n中间代码的形式很多。主要有四元式、三元式、间接三元式、逆波兰式、树等形式。sum:=first+count*10中间代码的形式：中间代码的形式：(int

15、oreal 10 - t1 )(* id3 t1 t2 )(+ id2 t2 t3 )(:= t3 - id1)1.2 编译过程概述（七）n代码优化代码优化：此阶段的任务是对前阶段产生的中间代码进行变换或进行改造，目的是使生成的目标代码更为高效，即省时间和省空间。n优化分与机器相关和机器无关。n编译所产生的目标程序，其执行的次数和编译次数无关。可以多次运行，编译产生的代码质量越高，运行时间和占用空间越少。n删除公共因子、强度消弱、循环优化等。1.2 编译过程概述（八）n目标代码生成目标代码生成：这一阶段的任务是把中间代码变换成特定机器上的绝对指令代码或可重定位的指令代码或汇编指令代码。这是编译

16、的最后阶段，它的工作与硬件系统结构和指令含义有关，这个阶段的工作很复杂，涉及到硬件系统功能部件的运用、机器指令的选择、各种数据类型变量的存贮空间分配以及寄存器和后缓冲器的调度等。1.2 编译过程概述（九）n上述编译过程的阶段划分是一种典型的处理模式，事实上并非所有的编译程序都包括这样几个阶段。n有些编译程序并不要中间代码，即不存在中间代码生成阶段；有些编译程序不进行优化，优化阶段即可省去;有些最简单的编译程序只有词法分析，语法分析；语义分析和目标代码生成。1.2 编译过程概述（十）n编译程序的另外两个重要的工作是表格管理和出错处理.他们与上述六个阶段都有联系。n编译过程中源程序的各种信息被保留

17、在种种不同的表格里，编译各阶段的工作都涉及到构造、查找或更新有关的表格，因此需要有表格管理的工作；n如果编译过程中发现源程序有错误，编译程序应报告错误的性质和错误发生的地点，并且将错误所造成的影响限制在尽可能小的范围内，使得源程序的其余部分能继续被编译下去，有些编译程序还能自动校正错误，这些工作称之为出错处理。n最重要的一种表格是符号表。符号表中记录源程序中使用的名字和收集到的每个名字的各种属性信息，诸如类型、作用域、分配存储信息。在第二章你会看到一种符号表，在第九章你会对符号表的组织和管理了解的更深入。n出错处理程序的任务包括检查错误、报告出错信息、排错、恢复编译工作。1.3 编译程序的结构

18、源程序词法分析程序语法分析程序语义分析程序中间代码生成程序代码优化程序目标代码生成程序目标程序出 错 处 理 程 序表 格 管 理 程 序1.4 编译阶段的组合（一）n编译过程除了用六个阶段划分,也可以用其他的角度描述编译过程。n编译过程分成前端和后端；编译过程也可以看成是分成一遍、两遍编译过程分成前端和后端；编译过程也可以看成是分成一遍、两遍或多遍。或多遍。n前端前端的主要工作依赖于源语言而与目标机无关。包括词法分析、语法分析、语义分析和中间代码生成，以及一些优化代码生成的工作，同时包括与每个工作相关的出错管理和表格管理的工作。n后端后端工作指那些依赖于目标机而一般不依赖于源语言，只与中间代

19、码有关的那些阶段，即目标代码生成，以及相关出错处理和符号表管理。n某一编译程序的前端加上相应不同的后端则可以为不同的机器构成同一个源语言的编译程序；不同语言编译的前端生成同一种中间语言,再使用一个共同的后端，则可为同一机器生成几个语言的编译程序。1.4 编译阶段的组合（二）n编译过程中所谓的“遍”，也称作“趟”，是对源程序或其等价的中间语言程序从头到尾扫视并完成规定任务的过程。n每一遍扫视可完成上述一个阶段或多个阶段的工作。n编译程序究竟分成几遍，参考的因素主要是源语言和机器（目标机）的特征。即源语言的结构直接影响编译的遍的划分；机器的情况，即编译程序工作的环境也影响编译程序的遍数的划分。n一

20、个多遍的编译程序可以较之一遍的编译程序少占内存，遍数多一点，整个编译程序的逻辑结构可能清晰一些，但是遍数多读取次数增加，编译速度慢。1.5高级语言编译与解释 n运行高级语言的程序,主要有两个途径：第一个途径是把该程序翻译为这个计算机的指令代码序列，这就是我们已经描述的编译过程。第二个途径是编写一个程序，它解释所遇到的高级语言程序中的语句并且完成这些语句的动作，这样的程序就叫解释程序。n从功能上说，一个解释程序能让计算机执行高级语言。它与编译程序的主要不同是它不生成目标代码，它每遇到一个语句，就要对这个语句进行分析以决定语句的含义，执行相应的动作。n编译系统生成的目标代码由计算机执行才能生成结果

21、。使用编译系统时会区分编译阶段和运行阶段，编译阶段对源程序进行编译，运行阶段是指目标程序的运行(类似于英语的笔译)。n而解释系统则是边解释边执行(类似于英语的口译)。1.5高级语言编译与解释 n从存储组织来看，在编译阶段，存储区一般要有源程序缓冲区，目标代码缓冲区，名字表以及编译程序使用的源程序中间表示和各种表格等等。在运行阶段，存储区只有目标代码和数据区了。对解释系统来说，在它工作的自始至终，存储区中要有源程序，名字表，标号表等表格，输入输出缓冲区以及数据区等等. 1.5高级语言编译与解释源程序缓冲区名字表目标代码缓冲区编译程序用中间表示及各种表格目标代码区数据区解释系统源程序工作单元及名字

22、表标号表缓冲区（输入输出）栈区编译阶段和运行阶段的存贮区内容编译阶段运行阶段解释程序的存贮区内容1.6 程序设计语言的发展n发展过程n第一代语言第一代语言：机器语言。基于计算机的，属于低级语言。n第二代语言第二代语言：汇编语言。它也是依赖于不同计算机的，如Intel80 x86、基于各种单片机的，也是低级语言。n第三代语言第三代语言：高级程序设计语言。与计算机无关（不是绝对，需要编译的后端调整），如FORTRAN、COBOL、C、C+、C#及JAVA等等。n第四代语言第四代语言：特定应用设计的语言。如数据库查询语言SQL等。n第五代语言第五代语言：基于逻辑和约束的语言。如Prolog等1.6

23、程序设计语言的发展n程序设计语言另外一种分类方式n强制式语言强制式语言：描述如何完成如何完成一个计算任务的语言。如C、C+、C#、JAVA等语言都是强制式语言。n声明式语言声明式语言：只是描述要进行哪些进行哪些计算任务。约束逻辑语言通常是声明式语言。n冯冯.诺依曼语言诺依曼语言：指按照冯.诺依曼计算机体系结构为计算模型的程序设计语言。如FORTRAN、COBOL、C等。n面向对象语言面向对象语言：支持面向对象编程的语言。用一组相互作用的对象组成程序的编程风格。如C+、C#、JAVA等语言。n脚本语言脚本语言：具有高层次运算符的解释型语言，它通常被用于把多个计算过程“粘合”在一起。这些计算过程叫做脚本。如JavaScript等。1.6 程序设计语言的发展n程序设计语言的发展对编译的影响n程序设计语言的设计与编译器有密切的关系。编译器需要设计相应的算法和表示方式来翻译和支持新的语言特性，并且尽可能地利用新硬件的能力；n通过降低高级程序语言执行