第01章_编译概述

1、1234561. 为什么有些语言规定标识符不能超过为什么有些语言规定标识符不能超过8个字符？而有些语个字符？而有些语言对标识符的长度无限制？言对标识符的长度无限制？ 2. 为什么有些语言能实现递归，而有些语言不能？为什么有些语言能实现递归，而有些语言不能？ 3. C语言规定数组下界为语言规定数组下界为0，上界为声明的数减，上界为声明的数减1，为什么？，为什么？ 4. 嵌套的嵌套的IF语句规定语句规定ELSE与上面最近的与上面最近的IF配对，为什么？配对，为什么？5. 为什么有些程序运行一段时间后会导致内存溢出？为什么有些程序运行一段时间后会导致内存溢出？ 当我们学完编译后，这些问题就可以得到解

2、答。当我们学完编译后，这些问题就可以得到解答。78编译系统：编译程序和运行程序编译系统：编译程序和运行程序编译程序编译程序目标程序目标程序源程序源程序91011121314源程序源程序翻译程序翻译程序目标程序目标程序SOURCE PROGRAMTRANSLATER OBJECT PROGRAM1516高级语言高级语言源程序源程序 编译编译程序程序 机器语言机器语言目标程序目标程序 目标程序目标程序 +运行子程序运行子程序 运行运行结果结果 数据数据 编译阶段编译阶段 执行阶段执行阶段 17高级语言源程序高级语言源程序 编译程序编译程序 汇编语言目标程序汇编语言目标程序 汇编程序汇编程序机器语言

3、目标程序机器语言目标程序 运行结果运行结果 目标程序目标程序 + +运行子程序运行子程序 数据数据 编译阶段编译阶段 汇编阶段汇编阶段 运行阶段运行阶段 18源程序源程序 数据数据 解释程序解释程序 结果结果 19词法词法分析分析 语法语法分析分析 语义语义分析分析 代码代码优化优化目标代码目标代码生成生成分析阶段分析阶段综合阶段综合阶段 错误处理错误处理符号表符号表2021S.PO.P语义分析及生成中间代码程序语义分析及生成中间代码程序代码生成程序代码生成程序代码优化程序代码优化程序语法分析程序语法分析程序词法分析程序词法分析程序错错误误处处理理符符号号表表管管理理22字符序列字符序列编码形

4、式编码形式单词单词：是语言的基本语法单位是语言的基本语法单位 保留字保留字（如（如:if:if、elseelse、whilewhile） 标识符标识符（如（如:max:max、minmin、strstr） 常数常数 （如（如:12:12、6.86.8、a a） 分界符分界符（如（如:+:+、- -、* *、/ /、; ;、（、）、（、） ）23例如：例如：a=10+ca=10+c* *2020符号符号记号记号单词单词100IDa21=200NUM1022+100IDc25*200NUM20a=10+C*20a=10+C*20a=10+C*202425我们我们是是一家人一家人我我是是大学生大学生

5、26S.PO.P语义分析及生成中间代码程序语义分析及生成中间代码程序代码生成程序代码生成程序代码优化程序代码优化程序语法分析程序语法分析程序词法分析程序词法分析程序错错误误处处理理符符号号表表管管理理27文法文法 :=:= “= =” :=:= “+ +” | | “* *” :=:=“( (” “) )” | | | | | | 28句子句子 谓语谓语 主语主语 宾语宾语 动词动词( (吃吃) ) 名词名词( (猴子猴子) ) 名词名词( (香蕉香蕉) ) 图图1.51.5句子句子“猴子吃香蕉猴子吃香蕉”的语法分析树的语法分析树 语法分析与语法分析与语文中分析句子成分语文中分析句子成分相类似

6、，根据句子相类似，根据句子由主语、谓语组成，谓语由动词、宾语组成等语言规则，由主语、谓语组成，谓语由动词、宾语组成等语言规则，可对句子可对句子“猴子吃香蕉猴子吃香蕉”的进行分析，分析过程常用语的进行分析，分析过程常用语法树来表示句子。法树来表示句子。29表达式表达式 = ID（a） 项项 + 表达式表达式项项表达式表达式 NUM（20） ID（c） NUM （10） 因子因子 * 因子因子 因子因子项项30S.PO.P语义分析及生成中间代码程序语义分析及生成中间代码程序代码生成程序代码生成程序代码优化程序代码优化程序语法分析程序语法分析程序词法分析程序词法分析程序错错误误处处理理符符号号表表管

7、管理理3132表达式：表达式：a=10+ca=10+c* *2020表达式表达式 = ID（a） 项项 + 表达式表达式项项表达式表达式 NUM（20） ID（c） NUM （10） 因子因子 * 因子因子 因子因子项项33例如表达式例如表达式 (a+b)*(c+d)翻译成四元式的中翻译成四元式的中间代码如下：间代码如下：(+ , a , b , t1)(+ , c , d , t2)(* , t1 , t2 , t3)LOAD a 将将a的内容加载到操作数栈的内容加载到操作数栈LOAD b 将将a的内容加载到操作数栈的内容加载到操作数栈ADD 将操作数栈顶的两个单元的内容相加将操作数栈顶的两

8、个单元的内容相加STO t1 将操作数栈顶的内容存入单元将操作数栈顶的内容存入单元t1LOAD c 将将c的内容加载到操作数栈的内容加载到操作数栈LOAD d 将将d的内容加载到操作数栈的内容加载到操作数栈ADD 将操作数栈顶的两个单元的内容相加将操作数栈顶的两个单元的内容相加STO t2 将操作数栈顶的内容存入单元将操作数栈顶的内容存入单元t2LOAD t1 将将t1的内容加载到操作数栈的内容加载到操作数栈LOAD t2 将将t2的内容加载到操作数栈的内容加载到操作数栈MULT 将操作数栈顶的两个单元的内容相乘将操作数栈顶的两个单元的内容相乘STO t3 将累加器的内容存入单元将累加器的内容

9、存入单元t3 翻译成某个抽象机的翻译成某个抽象机的汇编指令代码：汇编指令代码：中间代码生成34S.PO.P语义分析及生成中间代码程序语义分析及生成中间代码程序代码生成程序代码生成程序代码优化程序代码优化程序语法分析程序语法分析程序词法分析程序词法分析程序错错误误处处理理符符号号表表管管理理35有四元式指令代码如下：有四元式指令代码如下：(*，3.14，2，t1)(=,t1,_,x)(*,2,5,t2)(*,t2,a,t3)(=,t3,_,y)(+,x,1,t4)(=,t4,_,z) 而优化后的代码如下：而优化后的代码如下：(=,6.28,_,x)(*,10,a,y)(=,7.28,_,z) 代

10、码优化不是编译程序的必要组成部分，不同的代码优化不是编译程序的必要组成部分，不同的编译程序所进行的代码优化程度差别很大，能够编译程序所进行的代码优化程度差别很大，能够完成代码优化的编译程序称为完成代码优化的编译程序称为“优化编译程序优化编译程序”。 36S.PO.P语义分析及生成中间代码程序语义分析及生成中间代码程序代码生成程序代码生成程序代码优化程序代码优化程序语法分析程序语法分析程序词法分析程序词法分析程序错错误误处处理理符符号号表表管管理理3738每个阶段中都要有：每个阶段中都要有：符号表管理符号表管理和和错误处理错误处理标识符名标识符名标识符类型标识符类型 类型类型 地址地址 aaa1

11、（表示变量）（表示变量） 1（表示整型）（表示整型） 0001 3940S.PO.P语义分析及生成中间代码程序语义分析及生成中间代码程序代码生成程序代码生成程序代码优化程序代码优化程序语法分析程序语法分析程序词法分析程序词法分析程序错错误误处处理理符符号号表表管管理理41 第一遍第一遍 第二遍第二遍 S.P中间形式中间形式1S.P中间形式中间形式2C2C1S.PO.P 上一遍的结果是下一遍的输入，最后一遍生成目标程序。上一遍的结果是下一遍的输入，最后一遍生成目标程序。42语法分析函数语法分析函数 词法分析子程序；词法分析子程序； 语义分析子程序；语义分析子程序；43词法分析词法分析 源程序源程

12、序 取单词取单词 目标程序目标程序 开始开始 语法分析语法分析 语义分析及代码生成语义分析及代码生成 送单词送单词 典型的单遍编译程序结构如图所示典型的单遍编译程序结构如图所示 1、当语法分析需要读进一个新单词、当语法分析需要读进一个新单词时，就调用词法分析子程序。词法时，就调用词法分析子程序。词法分析子程序则从源程序中依次读入分析子程序则从源程序中依次读入字符，组合成单词符号，并将单词字符，组合成单词符号，并将单词符号返回给语法分析程序。符号返回给语法分析程序。2、当语法分析程序识别出、当语法分析程序识别出一个语法成分时，就调用语一个语法成分时，就调用语义分析子程序进行语义分析，义分析子程序

13、进行语义分析，并生成目标程序。并生成目标程序。3、当源程序处理完后，、当源程序处理完后，进行善后处理，优化目进行善后处理，优化目标程序。标程序。44词法词法分析分析 语法语法分析分析 语义语义分析分析 代码代码优化优化目标代码目标代码生成生成错误处理错误处理符号表符号表目标程序目标程序 源程序源程序 45多遍编译程序的工作过程如下：多遍编译程序的工作过程如下：1. 调用词法分析程序将高级语言源程序转换成用单词符号表示调用词法分析程序将高级语言源程序转换成用单词符号表示的程序，即将字符串程序转换成单词符号串源程序。的程序，即将字符串程序转换成单词符号串源程序。2. 调用语法分析程序对符号串源程序

14、进行语法归类检查。调用语法分析程序对符号串源程序进行语法归类检查。3. 调语义分析程序进行语义检查，并生成中间的代码程序。调语义分析程序进行语义检查，并生成中间的代码程序。4. 调用代码优化程序对中间代码程序进行优化。调用代码优化程序对中间代码程序进行优化。5. 调用目标生成程序将优化后的中间代码程序转换成目标代码调用目标生成程序将优化后的中间代码程序转换成目标代码程序。程序。 词法词法分析分析 语法语法分析分析 语义语义分析分析 代码代码优化优化目标代码目标代码生成生成错误处理错误处理符号表符号表目标程序目标程序 源程序源程序 46分遍的缺点：分遍的缺点：每遍都要读符号、送符号，增加了许多重

15、复性工作，每遍都要读符号、送符号，增加了许多重复性工作，降低编译效率。目前的编译程序中，有单遍的，也有二遍的、三降低编译效率。目前的编译程序中，有单遍的，也有二遍的、三遍的，还有多到十几遍的。遍的，还有多到十几遍的。 编译程序分为多遍，其优点是：编译程序分为多遍，其优点是：1.可以减少内存容量的需求。分遍后，以遍为单位分别调用编译可以减少内存容量的需求。分遍后，以遍为单位分别调用编译的各个程序，各遍程序可以相互覆盖；的各个程序，各遍程序可以相互覆盖；2.可使各遍的编译程序相互独立，结构清晰；可使各遍的编译程序相互独立，结构清晰；3.能够进行充分的优化，产生高质量的目标程序；能够进行充分的优化，

16、产生高质量的目标程序； 4.可将编译程序分为可将编译程序分为“前端前端”和和“后端后端”，有利于编译程序的移，有利于编译程序的移植。植。47 前端：前端：通常将与通常将与源程序源程序有关的编译部分称为前端。有关的编译部分称为前端。 词法分析、语法分析、语义分析、中间代码生成词法分析、语法分析、语义分析、中间代码生成 -分析部分分析部分 特点：与特点：与源语言源语言有关有关 后端：后端：与与目标机目标机有关的部分称为后端。有关的部分称为后端。 代码优化、代码生成代码优化、代码生成 -综合部分综合部分 特点：与特点：与目标机目标机有关有关48 同一前端同一前端+ +不同后端不同后端 不同机器构成同

17、一语言的编译程序不同机器构成同一语言的编译程序例如例如.NET.NET框架框架 49 不同前端不同前端+ +同一后端同一后端 同一机器生成几个语言的编译程序同一机器生成几个语言的编译程序例如例如GCCGCC 5051预处理器预处理器编译程序编译程序汇编程序汇编程序加载、连接编译加载、连接编译框架源程序框架源程序标准源程序标准源程序 目标汇编程序目标汇编程序可重定位的机器代码可重定位的机器代码绝对机器代码绝对机器代码库、可重库、可重定位目标定位目标文件文件程序员编制的程序员编制的程序程序经过预处理后经过预处理后的程序的程序52编译之前，预处理器对源程序进行处理，产生标准源程序。不同编译之前，预处

18、理器对源程序进行处理，产生标准源程序。不同语言的预处理功能有所不同，语言的预处理功能有所不同，C语言编译系统的预处理器主要完语言编译系统的预处理器主要完成以下几个功能：成以下几个功能：宏处理：宏处理：C语言允许用户在程序中定义宏，以便提高编程效率，语言允许用户在程序中定义宏，以便提高编程效率，如如#define PI 3.1415926是一个宏定义，那么在编译之前，预处理是一个宏定义，那么在编译之前，预处理器要将源程序中的所有符号器要将源程序中的所有符号PI换成换成3.1415926。文件包含：文件包含：如果如果C源程序中含有源程序中含有#include “stdio.h”，那么预处理器，那么

19、预处理器处理到这条语句时，就用处理到这条语句时，就用stdio.h的实际内容替换该语句。的实际内容替换该语句。条件编译：条件编译：并非源程序的每一行都要进行编译，有时情况不同要并非源程序的每一行都要进行编译，有时情况不同要编译不同的语句。编译不同的语句。C语言预处理器处理条件编译，将真正要编译语言预处理器处理条件编译，将真正要编译的语句组成标准源程序。的语句组成标准源程序。 53有些编译程序直接产生可重定位的机器语言目标代码，而有些编译程序只有些编译程序直接产生可重定位的机器语言目标代码，而有些编译程序只产生汇编语言目标代码，这样就需要汇编程序做进一步翻译，生成可重定产生汇编语言目标代码，这样

20、就需要汇编程序做进一步翻译，生成可重定位的机器代码。可重定位的机器代码可以装载到内存的任何地方，这种代位的机器代码。可重定位的机器代码可以装载到内存的任何地方，这种代码采用相对地址，起始地址为码采用相对地址，起始地址为0，各条指令及所访问的地址都是相对应于，各条指令及所访问的地址都是相对应于0的逻辑地址。如果加载到内存单元的逻辑地址。如果加载到内存单元L处，则所有指令地址及访问的地址都要处，则所有指令地址及访问的地址都要加上加上L。汇编语言采用助记符表示操作码，用标识符表示存储地址，如完成汇编语言采用助记符表示操作码，用标识符表示存储地址，如完成a=b+5的的80 x86汇编语言程序如下：汇编

21、语言程序如下： MOV a，R1 ADD #2，R1 MOV R1，b其中其中a，b表示存储地址，表示存储地址，R1表示寄存器，表示寄存器，#2表示立即常数。有些汇编语言表示立即常数。有些汇编语言还提供宏指令来提高汇编语言编程效率，这种汇编语言称为宏汇编语言。还提供宏指令来提高汇编语言编程效率，这种汇编语言称为宏汇编语言。 54任何一本关于编译结构的书如果不包括编译过程步骤的示例任何一本关于编译结构的书如果不包括编译过程步骤的示例就不能算完整。因此，写出一个完整的编译器并对其操作进就不能算完整。因此，写出一个完整的编译器并对其操作进行注释仍是很必要的。但要描述真实的编译器非常困难，行注释仍是很

22、必要的。但要描述真实的编译器非常困难，“真正的真正的”编译器内容太复杂而且不易在本教材中掌握。编译器内容太复杂而且不易在本教材中掌握。为了解决上述问题，本教材设计了一种非常小的语言为了解决上述问题，本教材设计了一种非常小的语言TEST，一旦能明白一旦能明白TESTTEST语言的编译技术，就能够很容易地理解各种语言的编译技术，就能够很容易地理解各种语言的编译器了。在第语言的编译器了。在第3 3、4 4、9 9章里，以这种小语言为示例，章里，以这种小语言为示例，讲解编译技术的具体实现，而且在附录讲解编译技术的具体实现，而且在附录B B中列出该语言完整中列出该语言完整的编译程序代码。的编译程序代码。

23、 55例如，例如，TEST语言，计算阶乘。语言，计算阶乘。 int i; int n; int j; j=1; read n; for (i=1;i=n;i=i+1) j=j*i; write j;TEST语言语言的程序结构很简单，它在语法上的程序结构很简单，它在语法上相当于相当于C C的函数体：是由一对花括号扩起来的函数体：是由一对花括号扩起来的语句序列。的语句序列。无过程，无函数，无数组，只有整型数值。无过程，无函数，无数组，只有整型数值。一条声明语句只能声明一个整型简单变量。一条声明语句只能声明一个整型简单变量。控制语句三个：控制语句三个： ifif、whilewhile和和forfor语句。语句。只能计算布尔表达式和整型算术表达式。布只能计算布尔表达式和整型算术表达式。布尔表达式由对两个算术表达式的比较组成，尔表达式由对两个算术表达式的比较组成，该比较使用该比较使用 、= 、=、=和和!=!=比较算符。比较算符。算术表达式可以包括整型常数、变量、参数算术表达式可以包括整型常数、变量、参数以及以及4 4个算符个算符+ +、* *、/ /。输入：输入：readread语句，输出：语句，输出：writewrite语句。语句。注释用注释用