编译方法刘秉瀚陈晖,第1章

1、1教材教材Compilers:Principle,Technique,and Tools机械工业出版社机械工业出版社2n语言处理器语言处理器n编译过程编译过程n编译器的结构编译器的结构n编译器的构造编译器的构造n编译技术的应用编译技术的应用 n程序设计语言基础程序设计语言基础3 n语言分三个层次：机器语言、汇编语言和高级语言。语言分三个层次：机器语言、汇编语言和高级语言。低级语言高级语言程序设计语言机器语言汇编语言过程式语言函数式语言逻辑式语言对象式语言C7 06 0000 0002MOV X,2X=2翻译翻译4 编译程序编译程序 翻译翻译一种语言（源语言）的程序成为等一种语言（源语言）的程序

2、成为等价的另一种语言（目标语言）的程序，价的另一种语言（目标语言）的程序，并能报告源语言程序中错误的一种程序。并能报告源语言程序中错误的一种程序。Source program 源程序源程序Target Program目标程序目标程序CompilerError messages出错信息出错信息5编译过程编译过程解释过程解释过程6语言处理系统语言处理系统 源程序源程序预处理器预处理器编译器编译器汇编器汇编器链接器链接器/加载器加载器经过预处理的源程序经过预处理的源程序目标汇编语言程序目标汇编语言程序可重定位机器代码可重定位机器代码目标机器代码目标机器代码库文件库文件可重定位对象文件可重定位对象文件

3、编译器的输入可能由预编译器的输入可能由预处理产生，而编译器的处理产生，而编译器的输出也可能需要进一步输出也可能需要进一步的处理才能成为可执行的处理才能成为可执行的机器代码的机器代码。7Provide Input to Compilers1. Macro Processing宏处理宏处理#define in C: does text substitution before compiling#define Y A*B+C#define Z getchar()82. File Inclusion#include in C - bring in another file before compili

4、ngdefs.h/main.c#include “defs.h”-/-9n汇编代码是机器码容易记忆的形式，使用标识符名称而不是汇编代码是机器码容易记忆的形式，使用标识符名称而不是2进进制代码表示操作和存储地址。制代码表示操作和存储地址。 n两遍扫描汇编两遍扫描汇编: First Pass:一个标识符的存储单元在第一次被遇到时分配的，一个标识符的存储单元在第一次被遇到时分配的，假定每个标识符占假定每个标识符占4字节存储空间。字节存储空间。(0-offset)e.g. substitute 0 for a, and 4 for b Second Pass:将每个操作符翻译成机器语言中代表相应操作将

5、每个操作符翻译成机器语言中代表相应操作的二进制码；将代表存储单元的每个标识符翻译成符号表中的二进制码；将代表存储单元的每个标识符翻译成符号表中该标识符的地址。该标识符的地址。MOV a, R1ADD #2, R1MOV R1, b0001 01 00 00000000 *0011 01 10 000000100010 01 00 00000100 *b=a+210n连接编辑程序连接编辑程序Link-editor：将多个可重定位的机器代：将多个可重定位的机器代码程序的文件组装成一个程序，其中，一个或多个可码程序的文件组装成一个程序，其中，一个或多个可能是库程序文件。能是库程序文件。n装入程序装入

6、程序Loader： 使可重定位的（使可重定位的（ relocatable ）机）机器代码改变其地址并把改变的指令放入内存。器代码改变其地址并把改变的指令放入内存。0001 01 00 00001111 *0011 01 10 000000100010 01 00 00010011 *起始地址起始地址L=00001111，则，则a=00001111，b=000100110001 01 00 00000000 *0011 01 10 000000100010 01 00 00000100 *11二、二、 编译过程概述编译过程概述源程序源程序目标程序目标程序编译程序编译程序词词法法分分析析语语法法分

7、分析析语语义义分分析析中中间间代代码码生生成成中中间间代代码码优优化化目目标标代代码码生生成成编译的各个阶段编译的各个阶段目目标标代代码码优优化化12 n词法分析的任务是：对输入的源程序词法分析的任务是：对输入的源程序字符流字符流进行从左到右的扫描，进行从左到右的扫描，识别出一个个识别出一个个词法单元词法单元(称单词或记号称单词或记号token)，并输出记号的内部，并输出记号的内部表示形式。表示形式。n记号一般分为记号一般分为5类：保留字（类：保留字（begin、end、if、for、while等）、等）、标识符、常数、运算符和分界符（标点符号、括号、注释符号等）标识符、常数、运算符和分界符（

8、标点符号、括号、注释符号等）n完成词法分析任务的程序称为词法分析器（完成词法分析任务的程序称为词法分析器（scanner）。）。13For Example: position = initial + rate * 60 ; All are tokens2. 其次将源程序转换为内部形式输出：其次将源程序转换为内部形式输出： 1. 首先识别出程序中出现的记号及其类型首先识别出程序中出现的记号及其类型 记号值position=initial+rate*60；类型标识符运算符=标识符运算符+标识符运算符*常数界符；内部表示3. 在词法分析过程中，还要对源程序做一些简单处理，如滤掉空在词法分析过程中，还

9、要对源程序做一些简单处理，如滤掉空格、去掉注释、报告错误等。格、去掉注释、报告错误等。14n任务：在词法分析基础上，将单词串（任务：在词法分析基础上，将单词串（记号串记号串）组成各类）组成各类语法单语法单位位（如表达式、语句、程序等），通过分析确定整个输入串是否（如表达式、语句、程序等），通过分析确定整个输入串是否构成语法上正确的程序，如果不能，给出语法错误。这种语法单构成语法上正确的程序，如果不能，给出语法错误。这种语法单位（语法范畴）可以表示成语法树。完成语法分析任务的程序称位（语法范畴）可以表示成语法树。完成语法分析任务的程序称为语法分析程序（为语法分析程序（parser）。）。 n功能

10、：依据源语言的功能：依据源语言的语法规则语法规则把源程序的单词序列组成语法短语把源程序的单词序列组成语法短语(表示成分析树表示成分析树/语法树语法树)。15n语法分析所依据的是语言的语法规则，文法是规则的集合，它们语法分析所依据的是语言的语法规则，文法是规则的集合，它们支配了支配了tokens 中的相互依赖和结构。中的相互依赖和结构。n语言的语法规则通常是由递归规则来定义，如上述例子中表达式语言的语法规则通常是由递归规则来定义，如上述例子中表达式和语句可由下述递归规则来定义：和语句可由下述递归规则来定义：statement是是expression, or while statement, or

11、 if statement, or .expressionis anidentifier = expression, or (expression), or expression + expression, or expression * expression, or number, or identifier, or .16分析树（分析树（Parse Tree）程序字符流程序字符流 : position = initial + rate * 60tokens序列序列: identifieridentifierexpressionidentifierexpressionnumberexpres

12、sionexpressionexpressionexpression(position)=+*(60)(initial)(rate)树的结点是利用该语言的树的结点是利用该语言的文法文法来建造的来建造的expression is an identifier = expressionexpression is an expression + expressionexpression is an identifierexpression is an expression * expressionexpression is an numberexpression is an identifiersta

13、tementstatement is an expression17语法树是分析树的一种压缩表示=positioninitialrate60+*树的内结点表示树的内结点表示操作符操作符，相应的操作数是该节点的子节点。，相应的操作数是该节点的子节点。18n找复杂的语义错误找复杂的语义错误语义审查，同时收集类型信息，语义审查，同时收集类型信息，把信息存放在语法树或符号表中。把信息存放在语法树或符号表中。n支持代码生成支持代码生成分析树根据语义动作进行扩展分析树根据语义动作进行扩展语义审查语义审查-上下文相关性、类型匹配、类型转换上下文相关性、类型匹配、类型转换例:void p();float ra

14、te;void initial();position = initial + rate * 60； /* error */ /* error */ /* warning */;19=positioninitialrate60+*=positioninitialrate inttofloat+*Conversion Action60Compressed Tree20nMost Important Activity in This Phase: Type Checking 类型检查- Legality of OperandsnMany Different Situations:float = in

15、t + char ;Aint = Areal + int ;while char int do. Etc.21n所谓所谓中间代码中间代码，是一种含义明确、便于处理的记号系统，通常独，是一种含义明确、便于处理的记号系统，通常独立于具体硬件，与现有计算机的指令系统非常相似，比较容易转立于具体硬件，与现有计算机的指令系统非常相似，比较容易转换成特定计算机的机器指令。常用的中间代码有：三元式、四元换成特定计算机的机器指令。常用的中间代码有：三元式、四元式、逆波兰式等。不管用哪种表示形式，其设计原则是容易生成，式、逆波兰式等。不管用哪种表示形式，其设计原则是容易生成，也容易转换成计算机的机器指令。也容易

16、转换成计算机的机器指令。n很多编译程序采用三地址码形式的中间代码，其形式为：很多编译程序采用三地址码形式的中间代码，其形式为： x=y op zx=y op z， x x、y y、z z是名字、常量或变量，是名字、常量或变量，opop代表操作符。代表操作符。n三地址赋值指令右部最多只有一个运算符，有些运算分量少于三三地址赋值指令右部最多只有一个运算符，有些运算分量少于三个。个。22 t1 = inttofloat(60)t1 = inttofloat(60)t2 = id3 t2 = id3 * * t1 t1t3 = id2 + t2t3 = id2 + t2id1= t3id1= t3=i

17、d1id2id3 inttofloat+*60 23n代码优化的任务是：对产生的中间代码进行等代码优化的任务是：对产生的中间代码进行等价变换，使生成的目标代码更为高效（时间和价变换，使生成的目标代码更为高效（时间和空间）。优化的目的主要是提高运行效率，节空间）。优化的目的主要是提高运行效率，节省存储空间。优化主要有两类，一是与机器有省存储空间。优化主要有两类，一是与机器有关的优化，主要设计如何分配寄存器，如何选关的优化，主要设计如何分配寄存器，如何选择指令，这类优化是在生成目标代码时进行的；择指令，这类优化是在生成目标代码时进行的；另一类优化与机器无关，主要是对中间代码的另一类优化与机器无关，

18、主要是对中间代码的优化。主要有局部优化、循环优化等。优化。主要有局部优化、循环优化等。24代码优化代码优化 id1=id2+id3*60t1 = inttofloat(60)t1 = inttofloat(60)t2 = id3 t2 = id3 * * t1 t1t3 = id2 + t2t3 = id2 + t2id1= t3id1= t3t1 =id3 t1 =id3 * * 60.0 60.0id1= id2 +t1id1= id2 +t1变换变换优化方法包括：公共子表达式的提取、循环优化、删除无用代码等。优化方法包括：公共子表达式的提取、循环优化、删除无用代码等。25 n目标代码生成

19、的任务是：把中间代码（或经优目标代码生成的任务是：把中间代码（或经优化的中间代码）变换成特定机器上的低级语言化的中间代码）变换成特定机器上的低级语言代码（可重定位的指令代码或汇编指令代码）。代码（可重定位的指令代码或汇编指令代码）。这一阶段的工作依赖于机器的硬件系统结构和这一阶段的工作依赖于机器的硬件系统结构和机器指令的含义。工作较复杂，涉及到硬件系机器指令的含义。工作较复杂，涉及到硬件系统功能部件的运用、机器指令的选择、各种数统功能部件的运用、机器指令的选择、各种数据类型变量的存储空间分配以及寄存器的分配据类型变量的存储空间分配以及寄存器的分配和调度。和调度。 26目标代码生成t1 = id

20、3 * 60.0id1 = id2 + t1LDF R2 , id3MULF R2, R2 , #60.0LDF R1 , id2ADDF R1, R1 , R2 STF id1, R127三、编译器结构三、编译器结构n编译程序的七个阶段的功能可分别用七个模编译程序的七个阶段的功能可分别用七个模块来完成，分别称为块来完成，分别称为词法分析器词法分析器、语法分析语法分析器器、语义分析器语义分析器、中间代码生成器中间代码生成器、中间代中间代码优化器、目标代码生成器码优化器、目标代码生成器和和目标代码优化目标代码优化器器。此外，一个完整的编译程序还必须包括。此外，一个完整的编译程序还必须包括“表格管

21、理表格管理”和和“出错处理出错处理”两部分。整个两部分。整个编译过程从逻辑上来说可以划分为各自独立编译过程从逻辑上来说可以划分为各自独立的若干阶段，一个阶段的输出成为下一个阶的若干阶段，一个阶段的输出成为下一个阶段的输入。段的输入。28源程序（字符流）源程序（字符流）1.词法分析器词法分析器2. 语法分析语法分析3. 语义分析语义分析4. 中间代码生成器中间代码生成器5.(机器无关机器无关) 代码优化代码优化6. 代码生成器代码生成器记号流记号流语法单位（语法树）语法单位（语法树）语法树语法树中间代码中间代码中间代码中间代码Target ProgramSymbol-table ManagerE

22、rror Handler1, 2, 3 , 4 , 5 : Analysis - Our Focus6 , 7 : Synthesis7.(机器相关机器相关) 代码优化代码优化目标机器语言目标机器语言但在实现时，为了提高但在实现时，为了提高编译效率通常采用语法编译效率通常采用语法制导的方法。整个编译制导的方法。整个编译过程以过程以语法分析语法分析为中心，为中心，整合词法分析、语义分整合词法分析、语义分析和中间代码生成成为析和中间代码生成成为一个高效、有机连接的一个高效、有机连接的整体。整体。29对于多遍扫描的编译程序，第一遍的输入是什么？最后一遍的输出是什么？阶段如何组合？分成几“遍”？主要依

23、据源语言和目标机器的特征。 n将编译程序阶段划分为编译将编译程序阶段划分为编译前端前端（front end）和）和后端后端（back end），），编译前端由词法分析、语法分析、语义分析和中间代码生成，以及中编译前端由词法分析、语法分析、语义分析和中间代码生成，以及中间代码优化工作，它主要与源语言有关，与目标机器无关，是对源程间代码优化工作，它主要与源语言有关，与目标机器无关，是对源程序进行分析的过程；编译后端包括目标代码生成和目标代码优化，依序进行分析的过程；编译后端包括目标代码生成和目标代码优化，依赖于中间语言而与源语言无关，是对分析过程的综合，将中间代码生赖于中间语言而与源语言无关，是对

24、分析过程的综合，将中间代码生成目标代码。成目标代码。n遍遍（趟）从头到尾扫描源程序（趟）从头到尾扫描源程序/中间表示（各种形式）一遍中间表示（各种形式）一遍(pass)并完并完成规定任务的过程。成规定任务的过程。为n种语言m种机器构造编译器 跟目标机无关跟源语言无关30支持分析过程的两个阶段支持分析过程的两个阶段n符号表建立/维护n标识符的属性信息表明该标识符的存储位置、类型、作用域等信标识符的属性信息表明该标识符的存储位置、类型、作用域等信息。当标识符是一个过程名时，他的属性信息还包括：参数的个息。当标识符是一个过程名时，他的属性信息还包括：参数的个数与类型、每个参数的传递方法以及返回值的类

25、型等信息。数与类型、每个参数的传递方法以及返回值的类型等信息。n符号表是一个数据结构，每个标识符在符号表中都有一个记录，符号表是一个数据结构，每个标识符在符号表中都有一个记录，记录的每个域对应于记号的一个属性。在词法、语法及语义分析记录的每个域对应于记号的一个属性。在词法、语法及语义分析阶段建立并初始化，在分析与综合阶段被利用并更新。阶段建立并初始化，在分析与综合阶段被利用并更新。 n出错处理：检查错误、报告出错信息、排错、恢复编译工作检查错误、报告出错信息、排错、恢复编译工作n编译程序在各个阶段应编译程序在各个阶段应诊断和报告源程序中的错误，包括词法错诊断和报告源程序中的错误，包括词法错误，

26、语法错误，语义错误。误，语法错误，语义错误。n编译程序应编译程序应报告出错地点，并给出简明准确的提示信息。报告出错地点，并给出简明准确的提示信息。31Errorsposition = initial + rate * 60lexical analyzersyntax analyzersemantic analyzerintermediate code generator =id1id2id3+*60=id1id2id3+*inttoreal60Symbol Tableposition .initial .rate.32Errorsintermediate code generatorcode

27、optimizerfinal code generatort1 = inttoreal(60)t2 = id3 * t1t3 = id2 + t2id1 = t3t1 = id3 * 60.0id1 = id2 + t1LDF R2 , id3MULF R2, R2 , #60.0LDF R1 , id2ADDF R1, R1 , R2 STF id1, R1position .initial .rate.Symbol Table3 address code33四、编译器的构造四、编译器的构造 n要在一台机器上为某种语言构造一个编译程序，必须从下述三方要在一台机器上为某种语言构造一个编译程序，

28、必须从下述三方面入手：面入手：n(1) 源语言：是编译程序处理的对象。对被编译的源语言要深刻源语言：是编译程序处理的对象。对被编译的源语言要深刻理解其结构和含义，即该语言的词法、语法和语义规则，以及有理解其结构和含义，即该语言的词法、语法和语义规则，以及有关的约束和特点；关的约束和特点；n(2) 目标语言与目标机：是编译程序处理的结果和运行环境。目目标语言与目标机：是编译程序处理的结果和运行环境。目标语言是汇编语言或机器语言，必须对硬件系统结构，操作系统标语言是汇编语言或机器语言，必须对硬件系统结构，操作系统的功能，指令系统等很清楚；的功能，指令系统等很清楚；n(3) 编译方法与工具：是生成编

29、译程序的关键。必须准确掌握把编译方法与工具：是生成编译程序的关键。必须准确掌握把一种语言的程序翻译为另一种语言的程序的方法。同时应考虑所一种语言的程序翻译为另一种语言的程序的方法。同时应考虑所使用的方法与既定的源语言、目标语言是否相符合，构造是否方使用的方法与既定的源语言、目标语言是否相符合，构造是否方便，从时间、空间上考虑是否高效，实现的可能性和代价等诸多便，从时间、空间上考虑是否高效，实现的可能性和代价等诸多因素，并尽可能考虑使用先进、方便的生成工具。因素，并尽可能考虑使用先进、方便的生成工具。 34编译器构造工具编译器构造工具语法分析器的生成器语法分析器的生成器: 根据程序设计语言的语法

30、描述自动生成语根据程序设计语言的语法描述自动生成语法分析程序。法分析程序。扫描器的生成器扫描器的生成器: 根据语言的单词正则表达式生成词法分析程序根据语言的单词正则表达式生成词法分析程序语法指导的翻译引擎语法指导的翻译引擎: 生成一组用于遍历分析树并生成中间代码生成一组用于遍历分析树并生成中间代码的例程。的例程。自动代码生成程序自动代码生成程序: 依据一组将中间代码翻译成机器语言的规则依据一组将中间代码翻译成机器语言的规则，生成一个代码生成程序。，生成一个代码生成程序。数据流引擎数据流引擎: 帮助收集数据流信息，支持优化。帮助收集数据流信息，支持优化。编译器构造工具集编译器构造工具集：提供用于

31、构造编译器不同阶段的例程的工具：提供用于构造编译器不同阶段的例程的工具集合。集合。35编译程序的实现方式编译程序的实现方式 生成编译程序的方法有：生成编译程序的方法有：1直接用机器语言或汇编语言编写（编译程序核心部分直接用机器语言或汇编语言编写（编译程序核心部分常用汇编语言编写）；常用汇编语言编写）；2用高级语言编写编译程序（这是普遍采用的方法）；用高级语言编写编译程序（这是普遍采用的方法）；3自编译（用某种高级语言书写自己的编译程序）；自编译（用某种高级语言书写自己的编译程序）；4用编译工具自动生成部分程序：用编译工具自动生成部分程序：LEX（词法分析）与（词法分析）与YACC（用（用LAL

32、R分析方法自动生成语法分析器）；分析方法自动生成语法分析器）；5. 移植（同种语言的编译程序在不同类型的机器之间移移植（同种语言的编译程序在不同类型的机器之间移植）。植）。36五、编译技术的应用五、编译技术的应用n编译编译并不并不限于程序设计语言的应用限于程序设计语言的应用 Text Formatters正文格式化程序正文格式化程序 输入是一个字符流，输出的是排版好的字符串。输入是一个字符流，输出的是排版好的字符串。 Silicon Compilers硅片编译程序硅片编译程序 输入是一个源程序，输出是一个电路设计。输入是一个源程序，输出是一个电路设计。 Database Query Proce

33、ssors数据库查询处理程序数据库查询处理程序 Database Query Languages Are Also a Programming Language 查询解释器把含有关系和布尔运算的谓词翻译成数据库命查询解释器把含有关系和布尔运算的谓词翻译成数据库命令，在数据库中查询满足该谓词的记录令，在数据库中查询满足该谓词的记录37六、程序设计语言基础六、程序设计语言基础n静态与动态区别静态与动态区别n环境与状态环境与状态n静态作用域静态作用域n动态作用域动态作用域n参数传递参数传递n别名别名38静态与动态区别静态与动态区别n静态策略：编译时刻可以决定问题的策略静态策略：编译时刻可以决定问题的

34、策略n动态策略：在运行时刻才能决定问题的策略动态策略：在运行时刻才能决定问题的策略n静态作用域：通过阅读程序可以确定声明的作用域静态作用域：通过阅读程序可以确定声明的作用域n动态作用域：运行时，同一个对动态作用域：运行时，同一个对x的使用会指向的使用会指向x几个声明中的某几个声明中的某一个一个n例子：例子：Java类中成员变量类中成员变量x声明的作用域声明的作用域 public int x;-动态策略，动态策略，每个对象都有自己用于存放每个对象都有自己用于存放 x 的位置，的位置，因此编译是无法预先确定这些位置。因此编译是无法预先确定这些位置。public static int x;-x为类变

35、量，静态策略，为类变量，静态策略，在编译时可以确定存在编译时可以确定存放放 x 的内存位置。的内存位置。 39环境与状态环境与状态n环境：从名字到内存的映射。声明环境：从名字到内存的映射。声明决定其环境，名字决定其环境，名字变量映射。变量映射。n状态：内存位置到其值的映射。状态：内存位置到其值的映射。 x=y+1：该语句改变了：该语句改变了 x 的状态。的状态。int i ;/*全局全局i */void f() int i ;/*局部局部i */ i = 3; /*对局部对局部 i 的使用的使用*/ x = i + 5; /*对全局对全局 i 的使用的使用*/环境与状态大部分是动环境与状态大部分是动态绑定的。态绑定的。静态绑定：静态绑定：环境环境-static声明声明状态状态宏定义宏定义 #define AYSIZE 1000标识符标识符：字母开头的、由字：字母开头的、由字母和数字组成的字符串母和数字组成的字符串名字名字：可以是标识符，也可：可以是标识符，也可以是表达式。如：以是表达式。如：x.y受限受限名字名字变量变量：分配存储位置的名字。：分