1、编译原理编译原理第一章第一章 引论引论王金伟计算机与信息工程学院天津师范大学TJNU-COCIE-WJW2 22023-8-252023-8-25编译原理编译原理n课程类别：专业选修课课程类别：专业选修课n适用专业：计算机科学与技术、计算机软件适用专业：计算机科学与技术、计算机软件n总总 学学 时：时：51（平均每周（平均每周3学时）学时）n总总 学学 分：分：3n先修课：先修课：C语言、数据结构、离散数学语言、数据结构、离散数学n各班选一位同学担任课代表（收发作业）各班选一位同学担任课代表（收发作业）n考核方法考核方法考勤考勤5%（随机点名（随机点名5次，每次次，每次1分）分）课后作业课后作
2、业5%（5次，每次次，每次1分）分）上机作业上机作业20%（4个，试验报告，每个个，试验报告，每个5分）分）期末期末70%TJNU-COCIE-WJW3 32023-8-252023-8-25主要内容主要内容n编译程序的基本构造原理和基本实现技术编译程序的基本构造原理和基本实现技术形式语言基础知识形式语言基础知识词法分析词法分析语法分析语法分析语法制导翻译语法制导翻译程序优化程序优化代码生成代码生成TJNU-COCIE-WJW4 42023-8-252023-8-25主要章节主要章节n第第1章引论章引论n第第2章高级语言的定义和一般特征章高级语言的定义和一般特征n第第3章词法分析章词法分析n第
3、第4章语法分析章语法分析自上而下分析自上而下分析n第第5章语法分析章语法分析自下而上分析自下而上分析n第第6章属性文法和语法制导翻译章属性文法和语法制导翻译n第第7章语义分析和中间代码生成章语义分析和中间代码生成n第第8章符号表章符号表n第第9章运行时存储空间组织章运行时存储空间组织n第第10章优化章优化n第第11章目标代码生成章目标代码生成TJNU-COCIE-WJW5 52023-8-252023-8-25教材和参考书教材和参考书1.教材：教材：陈火旺等：程序设计语言编译原理（第三版），陈火旺等：程序设计语言编译原理（第三版），国防工业出版社，国防工业出版社，2000年年2.参考书：参考书
4、：1)编译原理和技术（第二版，陈意云编著，中编译原理和技术（第二版，陈意云编著，中国科学技术大学出版社，国科学技术大学出版社，1997）2)吕映芝、张素琴、蒋维杜：编译原理；清华吕映芝、张素琴、蒋维杜：编译原理；清华大学出版社大学出版社 19983)杜淑敏、王永宁：编译程序设计原理；北京杜淑敏、王永宁：编译程序设计原理；北京大学出版社大学出版社 1986TJNU-COCIE-WJW6 62023-8-252023-8-25第一章第一章 引论引论n1.1 什么叫编译程序什么叫编译程序n1.2 编译过程概述编译过程概述n1.3 编译程序的结构编译程序的结构n1.4 编译程序与程序设计环境编译程序与
5、程序设计环境n1.5 编译程序的生成编译程序的生成n1.6 学习学习“编译原理编译原理”课的注意事项课的注意事项TJNU-COCIE-WJW7 72023-8-252023-8-251.1 什么叫编译程序什么叫编译程序n多数用户用高级语言（多数用户用高级语言（C，C+，Pascal）编写）编写程序，以实现他们所需要的应用程序，以实现他们所需要的应用n但目前的计算机执行的是非常低级的语言：机器但目前的计算机执行的是非常低级的语言：机器语言。语言。n问题：高级语言写出的程序最终是怎样在计算机问题：高级语言写出的程序最终是怎样在计算机上执行的呢？上执行的呢？n答案：编译程序答案：编译程序TJNU-C
6、OCIE-WJW8 82023-8-252023-8-251.现实例子现实例子一、编译程序的概念一、编译程序的概念英文书英文书中文书中文书翻译翻译TJNU-COCIE-WJW9 92023-8-252023-8-252.翻译程序翻译程序能够把某一种语言程序转换成另一种语言程序，能够把某一种语言程序转换成另一种语言程序，并且，后者与前者在逻辑上是等价的。并且，后者与前者在逻辑上是等价的。源语言程序源语言程序目标语言程序目标语言程序翻译翻译程序程序Main()int i,j;PROCEDURE MAIN;Var I,J:Integer;Begin End输入输入输出输出c程序程序pascal程序程
7、序TJNU-COCIE-WJW10102023-8-252023-8-253.编译程序编译程序n是翻译程序的一种是翻译程序的一种n特点：目标语言比源语言低级特点：目标语言比源语言低级源语言程序源语言程序目标语言程序目标语言程序翻译翻译程序程序.int a,b,c;a=1;b=2;c=a+b;Mov a,1Mov b,2Add c,a,b输入输入输出输出c程序程序汇编语言程序汇编语言程序编译编译程序程序TJNU-COCIE-WJW11112023-8-252023-8-254.解释程序解释程序n特点：以源语言程序作为输入，但不产生目标特点：以源语言程序作为输入，但不产生目标语言程序，而是边解释边
8、执行语言程序，而是边解释边执行源语言程序源语言程序.public class student public static void main(String args)StringBuffer string=new StringBuffer10;.输入输入执行执行JAVA程序程序解解释释程程序序JVM（JAVA虚拟机）虚拟机）输入输入编编译译程程序序字节流字节流输入输入JAVA字节流字节流javac（JAVA编译器）编译器）TJNU-COCIE-WJW12122023-8-252023-8-25按编译目的不同分类：按编译目的不同分类：1.诊断编译程序诊断编译程序专门用于帮助程序开发和调试的编译程
9、序专门用于帮助程序开发和调试的编译程序2.优化编译程序优化编译程序着重于提高目标代码运行效率的编译程序着重于提高目标代码运行效率的编译程序二、编译程序的分类二、编译程序的分类TJNU-COCIE-WJW13132023-8-252023-8-25按编译目标不同分类：按编译目标不同分类：目标机目标机：运行编译程序所产生目标代码的计算机：运行编译程序所产生目标代码的计算机宿主机宿主机：运行编译程序的计算机：运行编译程序的计算机1.交叉编译程序交叉编译程序产生不同于其宿主机的机器代码产生不同于其宿主机的机器代码2.可变目标编译程序可变目标编译程序不需重写编译程序中与机器代码无关的部分就能不需重写编译
10、程序中与机器代码无关的部分就能改变目标机改变目标机二、编译程序的分类（续）二、编译程序的分类（续）TJNU-COCIE-WJW14142023-8-252023-8-251.机器语言机器语言n计算机能够直接执行的机器指令系统计算机能够直接执行的机器指令系统n例如某种计算机的指令为例如某种计算机的指令为1011011000000000加法操作加法操作1011010100000000减法操作减法操作2.汇编语言汇编语言n用一些助记符号来表示机器指令用一些助记符号来表示机器指令n例如例如A+BLDRAADDRB三、几个概念三、几个概念TJNU-COCIE-WJW15152023-8-252023-8
11、-253.高级语言高级语言n其语法和结构类似于自然语言，容易记忆和其语法和结构类似于自然语言，容易记忆和书写书写n例如例如C语言，语言，Java等等4.源语言源语言n把被翻译（或编译）的语言称为源语言把被翻译（或编译）的语言称为源语言5.目标语言目标语言n把翻译（或编译）之后得到的语言称为目标语言把翻译（或编译）之后得到的语言称为目标语言6.源程序源程序n用源语言编写的程序用源语言编写的程序7.目标程序目标程序n用目标语言编写的程序用目标语言编写的程序TJNU-COCIE-WJW16162023-8-252023-8-251.2 编译过程概述编译过程概述n过程复杂，可与自然语言翻译作类比过程复
12、杂，可与自然语言翻译作类比翻译自然语言翻译自然语言n识别句子中的单词识别句子中的单词n分析句子的语法结构分析句子的语法结构n进行初步翻译进行初步翻译n对译文进行修饰对译文进行修饰n写出最后的译文写出最后的译文编译程序编译程序n词法分析词法分析n语法分析语法分析n语义分析与中间代码生成语义分析与中间代码生成n中间代码优化中间代码优化n目标代码成成目标代码成成TJNU-COCIE-WJW17172023-8-252023-8-25n任务：输入源程序，根据词法规则，对构源程任务：输入源程序，根据词法规则，对构源程序的字符串进行扫描和分解，识别出一个个单序的字符串进行扫描和分解，识别出一个个单词符号词
13、符号n单词符号是程序语言的基本成分单词符号是程序语言的基本成分例例：A=B*C由由5个单词构成：个单词构成：A，等号，等号，B，乘号，乘号，C for I:=1 to 100 do单词符号：单词符号：for,I,:=,1,to,100,don实现方法：实现方法：构造词法分析程序（扫描器）构造词法分析程序（扫描器）一、词法分析阶段一、词法分析阶段TJNU-COCIE-WJW18182023-8-252023-8-25n任务：任务：在词法分析的基础上，根据语言的语法规则把在词法分析的基础上，根据语言的语法规则把识别出的单词符号串，分解成各类语法单位识别出的单词符号串，分解成各类语法单位（语法范畴，
14、如表达式、语句、程序段、过程、（语法范畴，如表达式、语句、程序段、过程、函数、程序等），以确定整个输入串是否构成函数、程序等），以确定整个输入串是否构成语法上正确的语法上正确的“程序程序”。例例：A=B*C B*C是表达式，是表达式，A=B*C是赋值语句是赋值语句n实现方法：实现方法：构造语法分析程序（语法分析器）构造语法分析程序（语法分析器）二、语法分析阶段二、语法分析阶段TJNU-COCIE-WJW19192023-8-252023-8-25n任务：任务：对语法分析所识别出的各类语法范畴，分析其含义，对语法分析所识别出的各类语法范畴，分析其含义，并进行初步翻译（产生中间代码）并进行初步翻译
15、（产生中间代码）静态语义检查：变量是否定义、类型是否正确等静态语义检查：变量是否定义、类型是否正确等进行中间代码翻译进行中间代码翻译例例：C语言中，变量需要在使用前声明语言中，变量需要在使用前声明n实现方法：实现方法：构造语义分析程序构造语义分析程序三、语义分析和中间代码生成阶段三、语义分析和中间代码生成阶段TJNU-COCIE-WJW20202023-8-252023-8-25n中间代码：中间代码：是一种含义明确，便于记忆的记号系统，独立是一种含义明确，便于记忆的记号系统，独立于硬件，与机器指令在形式上有所接近，容易于硬件，与机器指令在形式上有所接近，容易替换成机器指令。替换成机器指令。表示
16、形式：表示形式：p后缀式：表示表达式，把运算量（操作数）后缀式：表示表达式，把运算量（操作数）写在前面，把运算符写在后面（后缀）写在前面，把运算符写在后面（后缀）例例：A+B 写成写成 AB+TJNU-COCIE-WJW21212023-8-252023-8-25p三元式：三元式：算符算符 第一操作对象第一操作对象 第二操作对象第二操作对象表示二地址指令：表示二地址指令：p四元式：四元式：算符算符 第一操作对象第一操作对象 第二操作对象第二操作对象 结果结果表示三地址指令：表示三地址指令：操作码第一地址第二地址操作码第一地址第二地址第三地址TJNU-COCIE-WJW22222023-8-25
17、2023-8-25n任务：任务：对中间代码进行等价变换，使生成目标代码更高效。对中间代码进行等价变换，使生成目标代码更高效。例例：n实现方法：实现方法：构造代码优化程序构造代码优化程序优化优化for k:=1 to 100 do begin M:=i+10*k N:=j+10*k end递归加法递归加法M:=iN:=jfor k:=1 to 100 do begin M:=M+10 N:=N+10 end四、代码优化阶段四、代码优化阶段TJNU-COCIE-WJW23232023-8-252023-8-25n任务：任务：把中间代码变换成特定机器上的低级语言代码。把中间代码变换成特定机器上的低级
18、语言代码。目标代码：机器语言代码、汇编语言代码目标代码：机器语言代码、汇编语言代码 例例：A+BLDRAADD RBn实现方法：实现方法：构造生成目标代码程序构造生成目标代码程序五、目标代码生成阶段五、目标代码生成阶段TJNU-COCIE-WJW24242023-8-252023-8-251.3 编译程序的结构编译程序的结构n由上述由上述5个阶段的实现程序组成个阶段的实现程序组成TJNU-COCIE-WJW25252023-8-252023-8-25 源程序源程序语义分析和中间代码生成器语义分析和中间代码生成器语法分析器语法分析器词法分析器词法分析器代码优化器代码优化器目标代码生成器目标代码生
19、成器 目标程序目标程序表表格格管管理理出出错错处处理理(字符串字符串)单词符号单词符号语法单位语法单位中间代码中间代码中间代码中间代码一、编译程序总框架一、编译程序总框架TJNU-COCIE-WJW26262023-8-252023-8-25编译程序在工作过程中需要建立一系列表格，编译程序在工作过程中需要建立一系列表格，以登记源程序中所提供的或在编译过程中所产以登记源程序中所提供的或在编译过程中所产生的一些信息，编译各个阶段的工作都涉及到生的一些信息，编译各个阶段的工作都涉及到构造、查找、修改或存取有关表格中的信息。构造、查找、修改或存取有关表格中的信息。例例 符号表符号表用来登记源程序中出现
20、的每个名字以及名字的用来登记源程序中出现的每个名字以及名字的属性（常量名、变量名（什么类型）、过程名）属性（常量名、变量名（什么类型）、过程名）名字信息二、表格管理二、表格管理TJNU-COCIE-WJW27272023-8-252023-8-25在翻译各阶段把原程序错误性质和地点通知用户。在翻译各阶段把原程序错误性质和地点通知用户。语法错误语法错误：源程序中不符合语法（词法）规则的错误：源程序中不符合语法（词法）规则的错误例如例如：拼写错误，括号不匹配，非法字符等：拼写错误，括号不匹配，非法字符等语义错误语义错误：源程序中不符合语义规则的错误：源程序中不符合语义规则的错误例如例如：说明错误，
21、作用域错误，类型不一致等：说明错误，作用域错误，类型不一致等三、出错处理三、出错处理TJNU-COCIE-WJW28282023-8-252023-8-25编译五个过程是逻辑上划分，具体实现组织成编译五个过程是逻辑上划分，具体实现组织成“遍遍”遍遍（pass）：）：对源程序或源程序的中间结果从头到尾扫描一次，并对源程序或源程序的中间结果从头到尾扫描一次，并作有关的加工处理，生成新的中间结果或目标程序。作有关的加工处理，生成新的中间结果或目标程序。例如例如：词法分析单独一遍：词法分析单独一遍 词法分析和语法分析合为一遍词法分析和语法分析合为一遍 语法分析和语义分析合为一遍语法分析和语义分析合为一
22、遍 词法分析、语法分析、语义分析合为一遍（三个词法分析、语法分析、语义分析合为一遍（三个不同阶段，语法分析为核心）不同阶段，语法分析为核心）四、遍四、遍TJNU-COCIE-WJW29292023-8-252023-8-25前端前端：主要由与源语言有关但与目标语言无关的那些部分主要由与源语言有关但与目标语言无关的那些部分组成组成例如例如：词法分析、语法分析、中间代码产生、（代：词法分析、语法分析、中间代码产生、（代码优化）码优化）后端后端：由与目标机有关的那些部分组成，不依赖于源语言由与目标机有关的那些部分组成，不依赖于源语言而仅仅依赖于中间语言。而仅仅依赖于中间语言。例如例如：（代码优化）、
23、目标代码生成等：（代码优化）、目标代码生成等五、编译前端和后端五、编译前端和后端TJNU-COCIE-WJW30302023-8-252023-8-25 源程序源程序语义分析和中间代码生成器语义分析和中间代码生成器语法分析器语法分析器词法分析器词法分析器代码优化器代码优化器目标代码生成器目标代码生成器 目标程序目标程序(字符串字符串)单词符号单词符号语法单位语法单位中间代码中间代码中间代码中间代码五、编译前端和后端（续五、编译前端和后端（续1）前端前端 后端后端TJNU-COCIE-WJW31312023-8-252023-8-25五、编译前端和后端（续五、编译前端和后端（续2）C语言语言编译
24、器编译器前端前端中间代码中间代码C语言语言编译器编译器后端后端（X86）C语言语言编译器编译器后端后端（ARM）中间代码中间代码X86代码代码ARM代码代码TJNU-COCIE-WJW32322023-8-252023-8-251.4 编译程序与程序设计环境编译程序与程序设计环境n程序开发过程程序开发过程n程序设计环境程序设计环境编辑编辑程序程序编译编译程序程序链接链接程序程序库代码库代码源源代码代码目标目标代码代码可执行可执行代码代码UEVI等等Linkld等等Windbggdb等等调试调试程序程序Masmas等等程序设计环境程序设计环境TJNU-COCIE-WJW33332023-8-25
25、2023-8-251.4 编译程序与程序设计环境（续）编译程序与程序设计环境（续）n传统的程序设计环境传统的程序设计环境编辑、编译、链接、调试各自独立编辑、编译、链接、调试各自独立n集成化的程序设计环境（集成化的程序设计环境（IDE）Turbo CVisual C+PowerBuilderJ Builder等等等等TJNU-COCIE-WJW34342023-8-252023-8-251.5 编译程序的生成编译程序的生成n早期用机器或汇编语言早期用机器或汇编语言n现在用高级语言编写现在用高级语言编写TJNU-COCIE-WJW35352023-8-252023-8-251.直接编写直接编写n机
26、器语言、汇编语言、高级语言机器语言、汇编语言、高级语言2.自举的方法自举的方法n先对语言的核心部分用机器语言编写先对语言的核心部分用机器语言编写核心部分：程序语言的三个支柱：条件、循环、核心部分：程序语言的三个支柱：条件、循环、调用返回调用返回n然后以此为基础，再编写更多的语言成分然后以此为基础，再编写更多的语言成分3.移植的方法移植的方法n将一个已有的将一个已有的A机器上的编译器移植到机器上的编译器移植到B机器上机器上一、编译程序的构造方法一、编译程序的构造方法TJNU-COCIE-WJW36362023-8-252023-8-25二、二、T形图形图n描述源语言描述源语言S、目标语言、目标语
27、言T和编译程序实现语言和编译程序实现语言I间的关系间的关系 S T ITJNU-COCIE-WJW37372023-8-252023-8-25三、三、T形图的组合方式形图的组合方式1.将第一个将第一个T形图的输出作为第二个形图的输出作为第二个T形图的输形图的输入入已有将语言已有将语言A编译为语言编译为语言B的编译器和将语言的编译器和将语言B到语言到语言C的编译器，用上述方法得到的编译器，用上述方法得到A到到C的编的编译器译器TJNU-COCIE-WJW38382023-8-252023-8-25三、三、T形图的组合方式（续）形图的组合方式（续）2.编译器实现语言的变换编译器实现语言的变换例：我
28、们用例：我们用C语言开发了一个将语言开发了一个将FORTRAN语言语言程序编译为程序编译为JAVA程序的编译器程序的编译器FOR2J，如果我，如果我们已经有一个将们已经有一个将C语言编译为语言编译为X86代码的编译器，代码的编译器，利用上述的方式可以得到一个在利用上述的方式可以得到一个在X86机器上执行机器上执行的的FOR2J编译器编译器编译编译TJNU-COCIE-WJW39392023-8-252023-8-25四、编译器的自举的开发方式四、编译器的自举的开发方式没有高级语言可以用来写编译器，怎么办？没有高级语言可以用来写编译器，怎么办？n用汇编语言开发一个完整的编译器？太繁琐用汇编语言开
29、发一个完整的编译器？太繁琐n用自举的方式：用自举的方式：首先用汇编语言首先用汇编语言M开发一个实现源语言开发一个实现源语言A的一个子集的一个子集A的编译器，这个编译器只要正确即可的编译器，这个编译器只要正确即可用这个子集语言用这个子集语言A开发语言全集的编译器开发语言全集的编译器上述过程可以重复多次，直至得到性能良好的、正确的上述过程可以重复多次，直至得到性能良好的、正确的对语言全集有效的编译器对语言全集有效的编译器编译编译TJNU-COCIE-WJW40402023-8-252023-8-25五、编译器的移植的开发方式五、编译器的移植的开发方式n以以PC机为工具开发机为工具开发M芯片的芯片的
30、C语言编译器语言编译器nPC机上已有机上已有C语言编译器，把移植到语言编译器，把移植到M芯片上芯片上n用用C语言在语言在PC机上开发一个产生机上开发一个产生M代码的代码的C编译器编译器C1n将将C1在在PC机上编译，得到机上编译，得到PC机上运行的交叉编译器机上运行的交叉编译器C2Mn用交叉编译器用交叉编译器C2M在在PC机上对机上对C1重新编译，得到在重新编译，得到在M芯片上运行芯片上运行的的C语言编译器语言编译器PC上的上的C语言编译器语言编译器交叉编译器交叉编译器C2M交叉编译器交叉编译器C2MM上的上的C语言编译器语言编译器C1C1TJNU-COCIE-WJW41412023-8-25
31、2023-8-251.6 学习学习“编译原理编译原理”课的注意事项课的注意事项n1、明确、明确“编译编译”的任务的任务P T Q从数学角度从数学角度:把编译程序看成一个映射函数把编译程序看成一个映射函数Q=T（P）源程序源程序编译程序编译程序目标程序目标程序TJNU-COCIE-WJW42422023-8-252023-8-252.学好编译需掌握三方面知识学好编译需掌握三方面知识n掌握高级语言知识掌握高级语言知识n掌握目标语言知识（汇编）掌握目标语言知识（汇编）n掌握编译方法掌握编译方法3.要学新复旧要学新复旧n离散数学离散数学n数据结构数据结构n高级语言高级语言4.要用动态的观点学习要用动态的观点学习TJNU-COCIE-WJW43432023-8-252023-8-251.写出编译过程的写出编译过程的5个基本阶段。个基本阶段。2.用用T型图描述源语言型图描述源语言P、目标语言、目标语言Q和编译程序实和编译程序实现语言现语言T之间的关系。之间的关系。3.编译方式和解释方式的根本区别是什么？编译方式和解释方式的根本区别是什么？课堂练习课堂练习TJNU-COCIE-WJW44442023-8-252023-8-25作业作业n阅读阅读编译原理编译原理教材，第教材，第1章和第章和第2章章
