01引论

鲁斌[e-mail]华北电力大学计算机系引论编译技术之一2学习这门课有啥用呢？不用急，马上你就知道了文本编辑软件测试模式识别信息检索系统嵌入式系统开发绘图系统排版系统并行程序设计高级语言程序设计编译技术3课程目标与要求目标：使学生掌握高级语言的编译基本原理和实用方法设计、分析、实现编译程序的基本技能要求：学生能够清楚地了解编译程序基本结构掌握形式化语言文法描述的基本知识掌握基本编译程序设计方法初步具备实现与分析编译程序的能力4编译方法学习指导与实践贺汛机械工业出版社编译技术基础教程鲁斌等清华大学出版社教材参考书籍程序设计语言编译程序陈火旺等国防工业出版社5机器不能理解高级语言鸿沟如何跨越？易编程易调试效率高低级语言高级语言PASCALC++……JAVA汇编语言机器语言面向机器直观性差编程复杂1什么是编译程序6编译：将高级语言的源程序转变为汇编语言或机器语言程序的翻译过程。这种翻译程序称为编译程序。翻译：将一种程序设计语言（源语言）所编写的程序（源程序）转变为与之等价的另一种程序设计语言（目标语言）的程序（目标程序）的过程。解释：以源程序为输入，执行过程中不产生目标程序，而是边解释边执行。鉴于解释程序运行效率不高，本课程的重点在于介绍编译程序的基本设计原理和构造方法，其中许多方法也适用于构造解释程序或汇编程序。71.1编译程序将高级语言程序（源程序）翻译成低级语言程序（目标程序）的程序宿主机：运行编译程序的计算机目标机：运行编译程序所产生目标代码的计算机编译程序分类：诊断编译程序优化编译程序交叉编译程序可变目标编译程序高级语言程序（源程序）低级语言程序（目标程序）编译程序8源程序P目标程序P’运行结果S编译程序数据运行程序计算机A计算机B编译阶段运行阶段编译系统=编译程序+运行系统格式转换、标准函数、动态存储分配子程序等1.2高级语言程序的处理过程91.3编译程序的发展历史20世纪50年代中期，第一个编译程序FORTRAN编译程序开发成功20世纪50年代末期，开始研究编译程序的自动生成工具，如LEX、YACC等20世纪60年代，自展技术用于构造编译程序，如在PASCAL编译程序中的应用101.4其它编译程序尽管种类繁多，但是所必须执行的主要任务基本相同并行编译技术正在深入研究之中编译程序是现今任何计算机系统的最重要的系统程序本课程的目的，在于向大家介绍设计和构造编译程序的基本原理和基本方法，其中许多方法也适用于构造解释程序或汇编程序112编译过程概述编译的各个阶段：源程序目标程序表格管理出错处理词法分析语法分析语义分析中间代码生成代码优化目标代码生成语义分析12外文翻译与编译过程比较外文翻译(1)阅读原文(2)识别单词(3)分析句子语法结构(5)译文修饰(6)写出最终译文(4)初步翻译句子含义编译过程输入并扫描源程序词法分析语法分析代码优化目标代码生成语义分析与中间代码生成132.1词法分析程序（扫描器）任务：识别出源程序的各个单词符号删除无用的空白字符和注释检查拼词错误例：Pascal程序片断如下：varx,y,z:real;x:=y+z*60;y,z:real;x:=y+z*60;id2,id3:real;id1:=id2+id3*60;词法分析varx,varid1,字符流：单词流：14单词流的内部表示为使计算机能够方便地识别和使用，常将单词表示为一个有序对(Class,Value)。Class为一整型数，用于标识该单词的类别；(1)标识符(2)保留字(3)常数(4)算符(5)界符Value用于存放单词的值。varid1,id2,id3:real;id1:=id2+id3*60;(2,‘var’)(1,‘id1’)(5,‘,’)(1,‘id2’)(5,‘,’)(1,‘id3’)(5,‘:’)(2,‘real’)(5,‘;’)(1,‘id1’)(4,‘:=’)(1,‘id2’)(4,‘+’)(1,‘id3’)(4,‘*’)(3,‘60’)有序对152.2语法分析程序（分析器）功能：以扫描器输出的单词流为输入，判断整个单词符号串是否构成一个语法上正确的程序。依据：程序设计语言的语法规则。方法：为源程序构造一个逻辑上的语法树16语法分析续前例varid1,id2,id3:real;id1:=id2+id3*60;:realid3id1id2,,:=id1id2id360*+语法树：17程序结构的递归表示：表达式的表示：①任何标识符是表达式②任何常数（整常数、实常数）是表达式③若表达式1和表达式2都是表达式，那么表达式1+表达式2表达式1*表达式2（表达式1）都是表达式。语句的表示：①标识符:=表达式是语句②while(表达式)do语句和if(表达式)then语句else语句都是语句182.3语义分析程序功能：语义检查（类型匹配、参数匹配等）设置单词符号的属性执行相应的运算或操作依据：程序设计语言的语义规则。方法：语法制导翻译。19续前例语义分析:realid3id1id2,,:=id1id2id360*+语法树：:=id1id2id3*+60itr1234yreal4zreal8………符号表部分内容xreal0202.4中间代码生成依据：为了处理方便和便于代码优化。形式：逆波兰式、三元式、四元式及树形结构等。(1)(itr,60,,T1)(2)(*,id3,T1,T2)(3)(+,id2,T2,T3)(4)(:=,T3,,id1):=id1+id2*id3itr60中间代码产生四元式的形式与作用：(序号)(op,arg1,arg2,result)result:=arg1oparg2续前例T1T2T3212.5代码优化程序目的：生成高质量目标代码标准：空间指标时间指标方法：与机器有关与机器无关(1)(itr,60,,T1)(2)(*,id3,T1,T2)(3)(+,id2,T2,T3)(4)(:=,T3,,id1)(1)(*,id3,60.0,T1)(2)(+,id2,T1,id1)续前例代码优化22FORK:=1TO100DOBEGINM:=I+10*KN:=J+10*KEND;(1)(:=,1,,K)(1)(:=,1,,K)(2)(j,100,K,(9))(2)(:=,I,,M)(3)(*,10,K,T1)(3)(:=,J,,N)(4)(+,I,T1,M)(4)(j,100,K,(9))(5)(*,10,k,T2)(5)(+,M,10,M)(6)(+,J,T2,N)(6)(+,N,10,N)(7)(+,K,1,K)(7)(+,K,1,K)(8)(j,,,(2))(8)(j,,,(4))(9)…(9)…另例232.6目标代码生成程序任务：将中间代码翻译成目标程序。形式：（1）具有绝对地址的机器指令代码；（2）待装配的机器指令模块；（3）汇编语言形式的目标程序。选用方案24LDR1,id3MULR1,60.0LDR2,id2ADDR2,R1STR2,id1R1:=id3R1:=R1*60.0R2:=id2R2:=R2+R1id1:=R2目标代码等价运算id1:=id2+id3*60.0x:=y+z*60对照(1)(*,id3,60.0,T1)(2)(+,id2,T1,id1)续前例目标代码生成25词法分析程序语法分析程序语义分析程序中间代码生成代码优化程序目标代码生成表格管理程序错误检查处理程序源程序目标代码3编译程序的结构26词法分析器：又称扫描器，输入源程序，进行词法分析，输出单词符号语法分析器：简称分析器，对单词符号串进行语法分析，识别出语法单位，判断输入串是否构成语法上正确的“程序”语义分析与中间代码产生器：按照语义规则对语法分析器归约出（或推导出）的语法单位进行语义分析并把他们翻译成一定形式的中间代码优化器：对中间代码进行优化处理目标代码生成器：把中间代码翻译成目标程序27表格与表格管理：在编译程序使用的表格中最重要的是符号表它用来登记源程序中出现的每一个名字以及名字的各种属性。如一个名字是常量名、变量名，还是过程名等；如果是变量名它的类型又是什么、所占内存是多大、地址是什么等编译程序在工作过程中需要保持一系列的表格，用以登记源程序的各类信息和编译各阶段的进展状况合理的设计和使用表格是编译程序构造的一个重要问题与编译的头三个阶段有关的表格有：符号表、常数表、标号表、分程序入口表、中间代码表、过程引用表、循环特征表、等价名表、公用链表、格式表表格的结构大体如下：NAME(名字)INFORMATION(信息)28出错处理：一个编译程序不仅能对书写正确的程序进行编译，而且应能对处现在源程序中的错误进行处理。如果源程序有错，编译程序应设法发现错误，把有关错误报告给用户。这部分的工作是由专门的一组程序（叫做出错处理程序）完成的错误可发生在编译的各个阶段，错误处理也贯穿着编译全过程词法分析阶段可查出的错误，如标识符的组成不符合词法规则；语句结构错误是在语法分析中可查出的错误；还有语义分析阶段可查出的错误，即结构正确，但所涉及的操作无意义或错误在编译时查出的，叫Compile-timeerror，在运行时才表现出来的错误叫Run-timeerror29前端（frontend）：主要依赖于源语言而与目标机器无关的编译阶段。如：词法分析、语法分析、语义分析、中间代码生成、部分优化工作、与前端有关的出错处理工作和符号表管理工作后端（backend）：依赖于目标机而一般不依赖于源语言，只与中间代码有关的编译阶段。如：目标代码生成，以及相关出错处理和符号表操作遍（趟）：对源程序或其等价的中间语言程序从头到尾扫视并完成规定任务的过程。每一遍扫视可完成上述一个阶段或多个阶段的工作304编译程序与程序设计环境编译程序无疑是实现高级语言的一个最重要的工具，但支持程序设计人员进行程序设计开发通常还需要其它一些工具：如编辑程序、连接程序、调试程序等。编译程序与这些程序设计工具一起构成所谓的程序设计环境在一个程序设计环境中，编译程序起着中心的作用。连接程序、调试程序、程序分析等工具直接依赖于编译程序所产生的结果，而其它工具的构造也常常要用到编译的原理、方法和技术31集成化的程序设计环境将编辑程序、连接程序、调试工具与编译程序集成起来32Ada语言的程序设计环境APSE：APSEMAPSEKAPSE宿主机用户界面工具界面最内层是宿主机，它包括硬件，宿主操作系统和其他支持软件。第一层，是核心：KAPSE。第二层，最小：MPAPSE。第三层，APSE。335编译程序的生成以前构造编译程序大多是用机器语言或汇编语言作工具的。为了充分发挥各种不同硬件系统的效率，为了满足各种不同的具体要求，现在许多人仍然使用这种工具来构造编译程序（或编译程序的核心部分）但是越来越多的人已经使用高级语言作工具来编译程序。因为这样可以大大节省程序设计的时间，并且构造出来的编译程序易于阅读、维护和移植34编译程序生成方式有如下六种：直接用机器语言编写编译程序用汇编语言编写编译程序高级语言编写编译工具自编译移植35同一机器不同语言编译程序的实现方法L1语言A代码A代码L2语言A代码L1语言L2语言A代码A代码L1语言编写的L2语言的编译程序的源代码A机器代码实现的L1语言的可执行编译程序A机器代码实现的L2语言的可执行编译程序实现实现36“移植”：不同机器同一语言编译程序的实现方法L语言A代码A代码L语言B代码L语言L语言B代码A代码L语言B代码L语言L语言B代码B代码L编写的可在A上运行的能够产生B代码的L编译程序源代码A代码实现的可生成A代码的L可执行编译程序可在A上运行的能够生成B代码的L可执行编译程序可在B上运行的能够生成B代码的L可执行编译程序实现实现37“自编译方式”产生编译程序先对语言的核心部分构造一个小小的编译程序（可用低级语言实现）在以它为工具