第一章 编译器概述.ppt

《第一章 编译器概述.ppt》由会员分享，可在线阅读，更多相关《第一章 编译器概述.ppt（39页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、编编 译译 原原 理理夏夏夏夏 斌斌斌斌 关于编译原理课程关于编译原理课程n n内容内容 编译原理是介绍如何将高级程序设计语言变编译原理是介绍如何将高级程序设计语言变编译原理是介绍如何将高级程序设计语言变编译原理是介绍如何将高级程序设计语言变换成计算机硬件所能识别的机器语言，以便计算换成计算机硬件所能识别的机器语言，以便计算换成计算机硬件所能识别的机器语言，以便计算换成计算机硬件所能识别的机器语言，以便计算机进行处理。机进行处理。机进行处理。机进行处理。l l介绍编译系统的工作原理介绍编译系统的工作原理介绍编译系统的工作原理介绍编译系统的工作原理l l介绍编译系统的构造方法介绍编译系统的构造方

2、法介绍编译系统的构造方法介绍编译系统的构造方法先行课程先行课程：高等数学、高等数学、高等数学、高等数学、(PASCAL)(PASCAL)(PASCAL)(PASCAL)、离散数学、离散数学、离散数学、离散数学、汇编语言、数据结构汇编语言、数据结构汇编语言、数据结构汇编语言、数据结构编译原理课程应用领域编译原理课程应用领域编译器的设计编译器的设计一般的软件设计一般的软件设计例如：例如：例如：例如：v文本编辑器、信息检索系统、文本编辑器、信息检索系统、文本编辑器、信息检索系统、文本编辑器、信息检索系统、模式识别器模式识别器模式识别器模式识别器v打字程序、绘图系统打字程序、绘图系统打字程序、绘图系统

3、打字程序、绘图系统v优化程序优化程序优化程序优化程序本课程的地位本课程的地位 n n是计算机专业的学生必修的一门主干课是计算机专业的学生必修的一门主干课 n n是本学科研究生入学考试的课程之一是本学科研究生入学考试的课程之一n n是软件技术基础是软件技术基础 学习方法学习方法1 1、认真听课，认真理解书中的基本概念、基、认真听课，认真理解书中的基本概念、基 本原理与基本算法本原理与基本算法 2 2、认真做作业、认真做作业 3 3、在看书时或理解例题时，一定要画出相应、在看书时或理解例题时，一定要画出相应 的细节变化过程，通过画图来加深理解的细节变化过程，通过画图来加深理解4 4、在理解的基础上

4、记忆、在理解的基础上记忆5 5、理论结合实践、理论结合实践编译原理编译原理编译原理编译原理吕映芝吕映芝吕映芝吕映芝清华大学出版社清华大学出版社清华大学出版社清华大学出版社 编译原理编译原理 技术与工具技术与工具 人民邮电出版社人民邮电出版社人民邮电出版社人民邮电出版社Compiler Construction Compiler Construction Compiler Construction Compiler Construction Principle and Principle and Principle and Principle and PraticePraticePraticeP

5、ratice编译原理及实践编译原理及实践编译原理及实践编译原理及实践Kenneth Kenneth Kenneth Kenneth C.LoudenC.LoudenC.LoudenC.Louden机械工业出版社机械工业出版社机械工业出版社机械工业出版社参参参参考考考考书书书书籍籍籍籍参参参参考考考考书书书书籍籍籍籍Compilers Compilers Compilers Compilers Principles,Techniques,Principles,Techniques,Principles,Techniques,Principles,Techniques,andandandand T

6、ools Tools Tools Tools 龙书龙书龙书龙书第一章第一章 引论引论本章内容：本章内容：n n 什么是编译程序什么是编译程序什么是编译程序什么是编译程序n n 编译程序各阶段的主要功能编译程序各阶段的主要功能编译程序各阶段的主要功能编译程序各阶段的主要功能在计算机上如何执行一个高级语言程序？在计算机上如何执行一个高级语言程序？l l把高级语言程序翻译成机器语言程序把高级语言程序翻译成机器语言程序把高级语言程序翻译成机器语言程序把高级语言程序翻译成机器语言程序 l l运行所得的机器语言程序求得计算结果运行所得的机器语言程序求得计算结果运行所得的机器语言程序求得计算结果运行所得的机

7、器语言程序求得计算结果翻译器：翻译器：翻译器：翻译器：能够将一种语言转换成另一种语言的软能够将一种语言转换成另一种语言的软能够将一种语言转换成另一种语言的软能够将一种语言转换成另一种语言的软件，而且后者与前者在逻辑上是等价的。件，而且后者与前者在逻辑上是等价的。件，而且后者与前者在逻辑上是等价的。件，而且后者与前者在逻辑上是等价的。源语言源语言源语言源语言 目标语言目标语言目标语言目标语言n n编译编译 专指由高级语言转换为低级语言专指由高级语言转换为低级语言专指由高级语言转换为低级语言专指由高级语言转换为低级语言 n n解释解释 接受某高级语言的一个语句输入，进行解释并接受某高级语言的一个语

8、句输入，进行解释并接受某高级语言的一个语句输入，进行解释并接受某高级语言的一个语句输入，进行解释并控制计算机执行，马上得到这句的执行结果，控制计算机执行，马上得到这句的执行结果，控制计算机执行，马上得到这句的执行结果，控制计算机执行，马上得到这句的执行结果，然后再接受下一句。然后再接受下一句。然后再接受下一句。然后再接受下一句。编译程序编译程序程序设程序设计语言计语言机器语言机器语言 编译和解释的区别：编译和解释的区别：编译和解释的区别：编译和解释的区别：目标目标目标目标程序程序程序程序源源源源程程程程序序序序编编编编译译译译程程程程序序序序初始数据初始数据初始数据初始数据计计计计算算算算结结

9、结结果果果果源程序源程序源程序源程序解解解解释释释释程程程程序序序序初始数据初始数据初始数据初始数据计计计计算算算算结结结结果果果果特点：特点：1 1 1 1编编编编译译译译器器器器：工工工工作作作作效效效效率率率率高高高高，即即即即时时时时间间间间快快快快、空空空空间间间间省省省省；交交交交互互互互性性性性与动态特性差、可移植性差。大多数与动态特性差、可移植性差。大多数与动态特性差、可移植性差。大多数与动态特性差、可移植性差。大多数PLPLPLPL采用此种方法翻译采用此种方法翻译采用此种方法翻译采用此种方法翻译2 2 2 2解解解解释释释释器器器器：工工工工作作作作效效效效率率率率低低低低，

10、即即即即时时时时间间间间慢慢慢慢、空空空空间间间间费费费费；交交交交互互互互性性性性与与与与动动动动态态态态特特特特性性性性好好好好、可可可可移移移移植植植植性性性性好好好好。早早早早期期期期的的的的BasicBasicBasicBasic和和和和现现现现在在在在的的的的JavaJavaJavaJava等。等。等。等。基本功能基本功能：二者相同二者相同二者相同二者相同所所采采用用的的技技术术：从从从从翻翻翻翻译译译译的的的的角角角角度度度度来来来来讲讲讲讲，两两两两种种种种方方方方式式式式所所所所涉涉涉涉及及及及的原理、方法、技术相似。的原理、方法、技术相似。的原理、方法、技术相似。的原理、方

11、法、技术相似。英译汉与编译的比较英译汉与编译的比较1.1.识别出句子中的一个个单词识别出句子中的一个个单词 2.2.分析句子的语法结构分析句子的语法结构3.3.分析句子的语义分析句子的语义4.4.初步翻译初步翻译5.5.译文修饰译文修饰6.6.写出最后译文写出最后译文1.词法分析词法分析2.2.语法分析语法分析3.3.语义分析语义分析4.4.中间代码生成中间代码生成5.5.优化优化6.6.目标代码生成目标代码生成词法分析器词法分析器语法分析器语法分析器语义分析器语义分析器源程序源程序中间代码生成器中间代码生成器代码优化器代码优化器代码生成器代码生成器目标程序目标程序错误处理错误处理表格管理表格

12、管理 1.1 词法分析词法分析n n任务任务 输入源程序，对构成源程序的字符串进行输入源程序，对构成源程序的字符串进行输入源程序，对构成源程序的字符串进行输入源程序，对构成源程序的字符串进行扫描和分解，识别出一个个的单词。扫描和分解，识别出一个个的单词。扫描和分解，识别出一个个的单词。扫描和分解，识别出一个个的单词。n n单词单词 是高级语言中有实在意义的最小语法单位，是高级语言中有实在意义的最小语法单位，是高级语言中有实在意义的最小语法单位，是高级语言中有实在意义的最小语法单位，它由字符构成。它由字符构成。它由字符构成。它由字符构成。n n识别右边程序中的单词识别右边程序中的单词 基本字：基

13、本字：基本字：基本字：Void,Void,intint,float ,float 标识符标识符标识符标识符:a,b,c,d,x,y,:a,b,c,d,x,y,jisuanjisuan 常数常数常数常数 :50:50 算符算符算符算符 :+,*,=:+,*,=界限符界限符界限符界限符:;,():;,()Void jisuan()int y,c,d;float x,a,b;x=a+b*50;y=（c+d）*(x+b）;n n词法分析依照词法规则，识别出正确的单词法分析依照词法规则，识别出正确的单词，转换成统一规格，备用。词，转换成统一规格，备用。n n转换转换l l对基本字、运算符、界限符的转换对

14、基本字、运算符、界限符的转换对基本字、运算符、界限符的转换对基本字、运算符、界限符的转换 l l标识符的转换标识符的转换标识符的转换标识符的转换 l l常数的转换常数的转换常数的转换常数的转换 l l转换完成后的格式：（转换完成后的格式：（转换完成后的格式：（转换完成后的格式：（单词种别，单词符号的单词种别，单词符号的单词种别，单词符号的单词种别，单词符号的 属性值属性值属性值属性值）n n二元式表示二元式表示 （单词种别，单词符号的属性值）（单词种别，单词符号的属性值）n n描述词法规则的有效工具是描述词法规则的有效工具是正规式正规式和和有限有限自动机自动机。1.2 语法分析语法分析n n任

15、务：任务：根据语言的根据语言的根据语言的根据语言的语法规则语法规则语法规则语法规则，把单词流组成各类，把单词流组成各类，把单词流组成各类，把单词流组成各类语法单位语法单位语法单位语法单位，如：短语、句子、过程、程序，如：短语、句子、过程、程序，如：短语、句子、过程、程序，如：短语、句子、过程、程序n n语法规则：语法规则：语言的规则，又称为文法；规定单语言的规则，又称为文法；规定单语言的规则，又称为文法；规定单语言的规则，又称为文法；规定单词如何构成短语、语句、过程和程序。词如何构成短语、语句、过程和程序。词如何构成短语、语句、过程和程序。词如何构成短语、语句、过程和程序。语法规则通常用语法规

16、则通常用语法规则通常用语法规则通常用上下文无关文法上下文无关文法上下文无关文法上下文无关文法描述。描述。描述。描述。表达式的语法特征表达式的语法特征n n任任任任何何何何一一一一个个个个标标标标识识识识符符符符都都都都是表达式；是表达式；是表达式；是表达式；n n任任任任何何何何一一一一个个个个数数数数都都都都是是是是表表表表达式；达式；达式；达式；n n如如如如果果果果e e e e1 1 1 1和和和和e e e e2 2 2 2都都都都是是是是表表表表达式，那么达式，那么达式，那么达式，那么 e e e e1 1 1 1+e e e e2 2 2 2 e e e e1 1 1 1*e e

17、 e e2 2 2 2 (e e e e1 1 1 1)也都是表达式也都是表达式也都是表达式也都是表达式表达式表达式表达式表达式表达式表达式标识符标识符表达式表达式表达式表达式(initial)标识符标识符(rate)数数(60)*+position :=initial +rate *60;n n语法分析有两种方法：语法分析有两种方法：推导推导推导推导(Derive)(Derive)(Derive)(Derive)和和和和规约规约规约规约(Reduce)(Reduce)(Reduce)(Reduce)n n语法分析过程也可以用一棵倒着的树来表语法分析过程也可以用一棵倒着的树来表示示，这棵树叫做

18、这棵树叫做分析树分析树 赋值语句赋值语句赋值语句赋值语句标识符标识符标识符标识符（positionposition）整数整数整数整数(60)(60)表达式表达式表达式表达式表达式表达式表达式表达式+表达式表达式表达式表达式表达式表达式表达式表达式标识符标识符标识符标识符(rate)(rate)标识符标识符标识符标识符（initialinitial）:=表达式表达式表达式表达式*1.3 语义分析语义分析n n任务任务：检查程序的语义正确性，以保证程序各部检查程序的语义正确性，以保证程序各部检查程序的语义正确性，以保证程序各部检查程序的语义正确性，以保证程序各部分能有意义的结合在一起，为以后的代码

19、生成阶分能有意义的结合在一起，为以后的代码生成阶分能有意义的结合在一起，为以后的代码生成阶分能有意义的结合在一起，为以后的代码生成阶段收集类型信息段收集类型信息段收集类型信息段收集类型信息n n语义分析阶段的重要工作：语义分析阶段的重要工作：语义分析阶段的重要工作：语义分析阶段的重要工作：类型检查类型检查类型检查类型检查语义分析器语义分析器:=+*60id1id2id3:=+*60id1id2id3inttorealposition :=initial +rate *60;词法分析器词法分析器语法分析器语法分析器语义分析器语义分析器源程序源程序中间代码生成器中间代码生成器代码优化器代码优化器代

20、码生成器代码生成器目标程序目标程序出错管理器出错管理器符号表管理器符号表管理器 前三个阶段前三个阶段完成对源程完成对源程序的分析序的分析1.4 中间代码生成中间代码生成n n任务：任务：根据语义规则产生一种介于源语言与目标根据语义规则产生一种介于源语言与目标根据语义规则产生一种介于源语言与目标根据语义规则产生一种介于源语言与目标代码之间的一种中间代码。代码之间的一种中间代码。代码之间的一种中间代码。代码之间的一种中间代码。l l中间代码是不依赖于机器但是又便于生成依赖中间代码是不依赖于机器但是又便于生成依赖中间代码是不依赖于机器但是又便于生成依赖中间代码是不依赖于机器但是又便于生成依赖于机器的

21、目标代码的一种结构简单、含义明确于机器的目标代码的一种结构简单、含义明确于机器的目标代码的一种结构简单、含义明确于机器的目标代码的一种结构简单、含义明确的的的的记号系统记号系统记号系统记号系统n n中间代码形式中间代码形式 逆波兰式、逆波兰式、逆波兰式、逆波兰式、四元式、三元式四元式、三元式四元式、三元式四元式、三元式中间代码生成器中间代码生成器temp1:=inttoreal(60)temp2:=id3*temp1temp3:=id2+temp2id1:=temp3:=+*60id1id2id3inttorealposition :=initial +rate *60;1.5 代码优化代码优

22、化n n任务：任务：对前面产生的中间代码进行加工变换，以对前面产生的中间代码进行加工变换，以对前面产生的中间代码进行加工变换，以对前面产生的中间代码进行加工变换，以期在最后阶段能产生更为高效的目标代码。期在最后阶段能产生更为高效的目标代码。期在最后阶段能产生更为高效的目标代码。期在最后阶段能产生更为高效的目标代码。n n原则：原则：等价变换等价变换等价变换等价变换 n n主要方面：主要方面：公共子表达式的提取、合并已知量、公共子表达式的提取、合并已知量、公共子表达式的提取、合并已知量、公共子表达式的提取、合并已知量、删除无用语句、循环优化等。删除无用语句、循环优化等。删除无用语句、循环优化等。

23、删除无用语句、循环优化等。代码优化器代码优化器temp1:=inttoreal(60)temp2:=id3*temp1temp3:=id2+temp2id1:=temp3temp1:=id3*60.0id1:=id2*temp1例例例例.For(k=1;k,K,100,(9)(2)(j,K,100,(9)(2)(2)(:=,I,M:=,I,M)(3)(*,10,K,T(3)(*,10,K,T1 1)(3)(3)(:=,J,N:=,J,N)(4)(+,I,T(4)(+,I,T1 1,M),M)(4)(4)(j,K,100,(9)j,K,100,(9)(5)(*,10,k,T(5)(*,10,k,

24、T2 2)(5)(5)(+,M,10,M+,M,10,M)(6)(+,J,T(6)(+,J,T2 2,N),N)(6)(6)(+,N,10,N+,N,10,N)(7)(+,K,1,K)(7)(+,K,1,K)(7)(7)(+,K,1,K+,K,1,K)(8)(j,(2)(8)(j,(2)(8)(8)(j,(4)j,(4)(9)(9)(9)(9)1.6 目标代码生成目标代码生成n n任务：任务：把经过优化的中间代码转化成特定把经过优化的中间代码转化成特定把经过优化的中间代码转化成特定把经过优化的中间代码转化成特定 机器机器机器机器上的低级语言代码上的低级语言代码上的低级语言代码上的低级语言代码

25、n n目标代码的形式目标代码的形式 l l绝对指令代码绝对指令代码绝对指令代码绝对指令代码:可立即执行的目标代码。可立即执行的目标代码。可立即执行的目标代码。可立即执行的目标代码。l l汇编指令代码：汇编语言程序，需要通过汇编汇编指令代码：汇编语言程序，需要通过汇编汇编指令代码：汇编语言程序，需要通过汇编汇编指令代码：汇编语言程序，需要通过汇编程序汇编后才能运行。程序汇编后才能运行。程序汇编后才能运行。程序汇编后才能运行。l l可重定位指令代码：先将各目标模块连接起来，可重定位指令代码：先将各目标模块连接起来，可重定位指令代码：先将各目标模块连接起来，可重定位指令代码：先将各目标模块连接起来，

26、确定变量、常数在主存中的位置，装入主存后确定变量、常数在主存中的位置，装入主存后确定变量、常数在主存中的位置，装入主存后确定变量、常数在主存中的位置，装入主存后才能成为可以运行的绝对指令代码。才能成为可以运行的绝对指令代码。才能成为可以运行的绝对指令代码。才能成为可以运行的绝对指令代码。temp1:=id3*60.0id1:=id2*temp1代码生成器代码生成器MOVF id3,R2MULF#60.0,R2MOVF id2,R1ADDF R2,R1MOVF R1,id1词法分析器词法分析器语法分析器语法分析器语义分析器语义分析器源程序源程序中间代码生成器中间代码生成器代码优化器代码优化器代码

27、生成器代码生成器目标程序目标程序出错管理器出错管理器符号表管理器符号表管理器 1.7 符号表管理符号表管理n n表格作用：表格作用：用来记录源程序的各种信息以及编用来记录源程序的各种信息以及编用来记录源程序的各种信息以及编用来记录源程序的各种信息以及编译过程中的各种状况。译过程中的各种状况。译过程中的各种状况。译过程中的各种状况。n n与编译前四阶段有关的表格有：与编译前四阶段有关的表格有：符号表符号表符号表符号表、常数表、标号表、分程序入口表、中间、常数表、标号表、分程序入口表、中间、常数表、标号表、分程序入口表、中间、常数表、标号表、分程序入口表、中间代码表等。代码表等。代码表等。代码表等

28、。符号表：符号表：符号表：符号表：用来登记源程序中的常量名、变量名、用来登记源程序中的常量名、变量名、用来登记源程序中的常量名、变量名、用来登记源程序中的常量名、变量名、数组名、过程名等，记录它们的性质、定义和数组名、过程名等，记录它们的性质、定义和数组名、过程名等，记录它们的性质、定义和数组名、过程名等，记录它们的性质、定义和引用情况。引用情况。引用情况。引用情况。1.8 错误诊断和报告错误诊断和报告n n任务：任务：如果源程序有错误，编译程序应设法发现如果源程序有错误，编译程序应设法发现如果源程序有错误，编译程序应设法发现如果源程序有错误，编译程序应设法发现错误，并报告给用户。错误，并报告

29、给用户。错误，并报告给用户。错误，并报告给用户。n n完成：完成：由专门的出错处理程序来完成由专门的出错处理程序来完成由专门的出错处理程序来完成由专门的出错处理程序来完成 n n错误类型错误类型:l l语法错误语法错误语法错误语法错误:在词法分析和语法分析阶段检测出来。在词法分析和语法分析阶段检测出来。在词法分析和语法分析阶段检测出来。在词法分析和语法分析阶段检测出来。l l语义错误：一般在语义分析阶段检测。语义错误：一般在语义分析阶段检测。语义错误：一般在语义分析阶段检测。语义错误：一般在语义分析阶段检测。1.9 阶段的分组阶段的分组编译前端编译前端：主要指与源语言有关，与目标语言无主要指与

30、源语言有关，与目标语言无主要指与源语言有关，与目标语言无主要指与源语言有关，与目标语言无关的部分，通常包括词法分析、语法分析、语义关的部分，通常包括词法分析、语法分析、语义关的部分，通常包括词法分析、语法分析、语义关的部分，通常包括词法分析、语法分析、语义分析和中间代码生成，与机器无关部分的代码优分析和中间代码生成，与机器无关部分的代码优分析和中间代码生成，与机器无关部分的代码优分析和中间代码生成，与机器无关部分的代码优化化化化编译后端：编译后端：指与目标机器有关的部分。如与机器指与目标机器有关的部分。如与机器指与目标机器有关的部分。如与机器指与目标机器有关的部分。如与机器有关的优化、目标代码

31、生成有关的优化、目标代码生成有关的优化、目标代码生成有关的优化、目标代码生成表表 处处 理理词法分析源源程程序序目目标标程程序序错错 误误 处处 理理语法分析语义分析目标代码生成前 端后 端中间代码优化中间代码生成n n遍：遍：对源程序或源程序的中间结果从头到尾扫描对源程序或源程序的中间结果从头到尾扫描对源程序或源程序的中间结果从头到尾扫描对源程序或源程序的中间结果从头到尾扫描一次，并作有关的加工处理，生成新的中间结果一次，并作有关的加工处理，生成新的中间结果一次，并作有关的加工处理，生成新的中间结果一次，并作有关的加工处理，生成新的中间结果或目标程序。或目标程序。或目标程序。或目标程序。一遍

32、一遍一遍一遍扫扫描描描描：语语法分析法分析法分析法分析扫扫描器描器描器描器语义语义子程子程子程子程序序序序源程序源程序源程序源程序目目目目标标代代代代码码编译编译程序程序程序程序取取取取单词单词类类号号号号内内内内码码归约归约返回返回返回返回注：注：遍与阶段的含义毫无关系。遍与阶段的含义毫无关系。n n要在某机器上为某种语言构造一个编译程要在某机器上为某种语言构造一个编译程序，必须掌握下面三个方面的内容：序，必须掌握下面三个方面的内容：源语言源语言目标语言目标语言编译方法编译方法 本章小结本章小结n n基本概念：基本概念：翻译器、编译器、解释器、源语言、目标语言翻译器、编译器、解释器、源语言、目标语言翻译器、编译器、解释器、源语言、目标语言翻译器、编译器、解释器、源语言、目标语言 前端、后端、遍前端、后端、遍前端、后端、遍前端、后端、遍n n编译过程分哪些阶段编译过程分哪些阶段编译过程分哪些阶段编译过程分哪些阶段n n各个阶段完成的主要功能和采用的主要方法各个阶段完成的主要功能和采用的主要方法各个阶段完成的主要功能和采用的主要方法各个阶段完成的主要功能和采用的主要方法