编译原理 PPT 第一章.ppt

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

1、第一章第一章 绪论绪论湖南农业大学信息科学技术学院湖南农业大学信息科学技术学院王王 奕奕 teacher_teacher_课程编号：课程编号：20013B320013B3湖南农业大学信息科学技术学院 王 奕课程学时安排课程学时安排:总学时：总学时：64 理论学时：理论学时：52 实验学时：实验学时：12目的目的:掌握编译的基本理论、形式化系统，了解常用的编译技术，了解编译过程及编译系统的构造（结构和机理）。能运用所学技术解决实际问题，能独立编写一个小型编译系统。其其它它应应用用：信息检索系统，模式识别程序，排版、绘图系统和语言结构化编辑器，程序验证器等。湖南农业大学信息科学技术学院 王 奕1.

2、1 翻译程序与编译程序翻译程序与编译程序 计算机只能直接执行用机器语言编写的程序，但是机器语言对计算机依赖性强、直观性差、编写程序工作量大、程序结构也欠清晰。因此人们多数都是用接近自然语言的高级程序设计语言来编写程序，但计算机不能直接接受和执行用高级语言编写的这些程序，需要通过一个翻译程序将它翻译成等价的机器语言程序才能执行。湖南农业大学信息科学技术学院 王 奕源程序源程序 用汇编语言或高级语言编写的程序称为源程序目标程序目标程序 用目标语言所表示的程序目标语言：可以是介于源语言和机器语言之间的“中间语言”，可以是某种机器的机器语言,也可以是某机器的汇编语言.翻译程序翻译程序 将源程序在不改变

3、语义的前提下转换为目标程序的程序称为翻译程序。它是指各种语言的翻译器，包括汇编程序和编译程序，是汇编程序、编译程序以及各种变换程序的总称。湖南农业大学信息科学技术学院 王 奕程序设计语言的翻译方式程序设计语言的翻译方式编译编译 (compiling)(compiling)解释解释 (interpreting)(interpreting)湖南农业大学信息科学技术学院 王 奕程序设计语言的翻译方式程序设计语言的翻译方式 编译编译 (compiling)(compiling)把某种高级语言程序把某种高级语言程序(称为源程序称为源程序)等价地转换成等价地转换成另一种低级语言程序另一种低级语言程序(称为

4、目标程序称为目标程序)的过程。的过程。如把如把C C语言程序编译成某种机器语言语言程序编译成某种机器语言(汇编语言汇编语言)程程序。序。用编译方式翻译的语言：用编译方式翻译的语言：C C，C+C+，FORTRANFORTRAN，PascalPascal和和AdaAda、Visual C/C+Visual C/C+、Delphi Delphi 等。等。编译程序编译程序(compiler)(compiler)实现编译过程的程序实现编译过程的程序(也称编译器也称编译器),),属系统软件范畴。属系统软件范畴。湖南农业大学信息科学技术学院 王 奕源程序的编译和运行源程序的编译和运行n编译或汇编阶段编译或

5、汇编阶段compilen运行阶段运行阶段run输出数据输出数据目标程序目标程序+运行子程序运行子程序输入数据输入数据源程序源程序目标程序目标程序编译程序编译程序或汇编程序或汇编程序 a.pas complie a.exe 湖南农业大学信息科学技术学院 王 奕程序设计语言的翻译方式程序设计语言的翻译方式解释解释(interpreting)(interpreting)一边翻译一边执行，不形成目标代码。一边翻译一边执行，不形成目标代码。如：如：BASICBASIC，LISPLISP，DBASEDBASE、MLML、PrologProlog和和SmalltalkSmalltalk、Visual Bas

6、icVisual Basic、Visual Visual FoxproFoxpro、Power BuilderPower Builder、JavaJava等。等。解释程序解释程序(interpreter)(interpreter)实现解释过程的程序实现解释过程的程序(也称解释器也称解释器),),属系统软件属系统软件范畴。范畴。湖南农业大学信息科学技术学院 王 奕 首先我们会把程序写好，然后储存成文件，接着启首先我们会把程序写好，然后储存成文件，接着启动解释器载入文件，解释器便会逐行读取文件中的程序，动解释器载入文件，解释器便会逐行读取文件中的程序，并且加以执行，执行的过程就称做并且加以执行，执

7、行的过程就称做“解释执行解释执行”。n工作过程工作过程输出数据输出数据解释程序解释程序输入数据输入数据源程序源程序湖南农业大学信息科学技术学院 王 奕“编译编译”部分部分(下图左半边下图左半边)，其过程与一般编译器无异，其过程与一般编译器无异，唯一不同的是一般编译器会将程序编译成唯一不同的是一般编译器会将程序编译成“机器码机器码”可执可执行文件，下图则是将程序编译成行文件，下图则是将程序编译成“P-code”可执行文件，可执行文件，而将来这种而将来这种P-code可执行文件被执行时，会启动解释器来可执行文件被执行时，会启动解释器来解释可执行文件中的解释可执行文件中的P-code。(如如:VB6

8、)pseudo code，意思是“伪码”或“近似码”，表示接近机器码的伪码改良式的解释模式改良式的解释模式湖南农业大学信息科学技术学院 王 奕v编译程序的工作一般分为五个阶段编译程序的工作一般分为五个阶段:词法分析词法分析语法分析语法分析中间代码产生中间代码产生代码优化代码优化目标代码产生目标代码产生 同同时时还还会会伴伴有有表表格格处处理理和和出出错错处处理理。其其中中中中间间代代码码生生成成和和代代码码优优化化不不是是每每个个编编译译程程序必需的序必需的。1.2 编译过程和编译程序的基本结构编译过程和编译程序的基本结构 湖南农业大学信息科学技术学院 王 奕1.1.词法分析词法分析v任务任务

9、:输入源程序，对构成源程序的字符串输入源程序，对构成源程序的字符串进行扫描和分解，识别出一个个单词符号。进行扫描和分解，识别出一个个单词符号。v依循的原则：依循的原则：构词规则构词规则vFOR I :=1 TO 100 DOFOR I :=1 TO 100 DO 保留字保留字 标识符标识符 等符等符 整常数整常数 保留字保留字 整常数整常数 保留字保留字描述词法词法的有效工具是描述词法词法的有效工具是正规式和有限自动机正规式和有限自动机湖南农业大学信息科学技术学院 王 奕2.2.语法分析语法分析v任任务务:在在词词法法分分析析的的基基础础上上，根根据据语语言言的的语语法法规规则则把把单词符号串

10、分解成各类语法单位。单词符号串分解成各类语法单位。v依循的原则：依循的原则：语法规则语法规则vZ:=X+0.618*Y Z:=X+0.618*Y 算术表达式，赋值语句算术表达式，赋值语句湖南农业大学信息科学技术学院 王 奕3.3.中间代码产生中间代码产生v任任务务:对对各各类类不不同同语语法法范范畴畴按按语语言言的的语语义义进进行初步翻译。行初步翻译。v依循的原则：依循的原则：语义规则语义规则v语法规则的表示：语法规则的表示：BNFBNFv中间代码中间代码:三元式，四元式，树形结构等三元式，四元式，树形结构等vZ:=X+0.618*Y Z:=X+0.618*Y 翻译成四元式为翻译成四元式为(1

11、)*0.618 Y T1(1)*0.618 Y T1(2)+X T1 T2(2)+X T1 T2(3):=T2 _ Z(3):=T2 _ Z湖南农业大学信息科学技术学院 王 奕4.4.优化优化v任任务务：对对于于前前阶阶段段产产生生的的中中间间代代码码进进行行加加工工变变换，以期在最后阶段产生更高效的目标代码。换，以期在最后阶段产生更高效的目标代码。v依循的原则：依循的原则：程序的等价变换规则程序的等价变换规则FOR K:=1 TO 100 DOFOR K:=1 TO 100 DO BEGIN BEGIN X:=I+1;X:=I+1;M:=I+10*K;M:=I+10*K;N:=J+10*K;

12、N:=J+10*K;K:=K+1 K:=K+1 END END湖南农业大学信息科学技术学院 王 奕中间代码（一）中间代码（一）序号序号 OPROPROPN1OPN1 OPN2 RESULT OPN2 RESULT 注释注释(1)(1):=:=1 1 K K K:=1 K:=1(2)(2)jj100100 K K (10)if(100K)(10)if(100K)gotogoto(10)(10)(3)(3)+I I 1 1 X X X:=I+1 X:=I+1(4)(4)*1010 K K T1 T1 T1:=10*K T1:=10*K(5)(5)+I I T1 T1 M M M:=I+T1M:=I

13、+T1(6)(6)*1010 K K T2 T2 T2:=10*K T2:=10*K(7)(7)+J J T2 T2 N N N:=J+T2 N:=J+T2(8)(8)+K K 1 1 K K K:=K+1K:=K+1(9)(9)j j (2)(2)gotogoto(2)(2)(10)(10)湖南农业大学信息科学技术学院 王 奕转换后的等价代码（二）转换后的等价代码（二）序号序号 OPROPROPN1OPN1 OPN2OPN2 RESULT RESULT注释注释(1)(1)+I I 1 1 X X X:=I+1 X:=I+1(2)(2):=:=I I M M M:=I M:=I(3)(3):=

14、:=J J N N N:=J N:=J(4)(4):=:=1 1 K K K:=1 K:=1(5)(5)jj100100 K K(10)(10)if(100K)if(100K)gotogoto(10)(10)(6)(6)+M M 10 10 M M M:=M+10 M:=M+10(7)(7)+N N 10 10 N N N:=N+10 N:=N+10(8)(8)+K K 1 1 K K K:=K+1 K:=K+1(9)(9)j j(5)(5)gotogoto(5)(5)(10)(10)湖南农业大学信息科学技术学院 王 奕5.5.目标代码产生目标代码产生v任任务务:把把中中间间代代码码变变换换成

15、成特特定定机机器器上上的的目目标标代码。代码。v依赖于硬件系统结构和机器指令的含义依赖于硬件系统结构和机器指令的含义v目标代码三种形式目标代码三种形式:绝对指令代码绝对指令代码:可直接运行可直接运行 可重新定位指令代码可重新定位指令代码:连接装配，连接装配，汇编指令代码汇编指令代码:需要进行汇编需要进行汇编湖南农业大学信息科学技术学院 王 奕5.5.目标代码产生目标代码产生v例例:b=a+2 MOV a,R1ADD#2,R1MOV R1,b 0001 01 00 00000000*0011 01 10 00000010 0100 01 00 00000100*L=00001111 0001 0

16、1 00 000011110011 01 10 000000100100 01 00 00010011 湖南农业大学信息科学技术学院 王 奕词法分析器词法分析器语法分析器语法分析器中间代码生成器中间代码生成器优化段优化段源程序源程序单词符号单词符号语法单位语法单位四元式四元式表表格格管管理理出出错错处处理理目标代码生成器目标代码生成器四元式四元式目标代码目标代码1.1.编译程序总框编译程序总框湖南农业大学信息科学技术学院 王 奕2.2.表格和表格管理表格和表格管理v常常见见的的表表格格:符符号号名名表表，常常数数表表，标标号号表表，入口名表，过程引用表。入口名表，过程引用表。其其它它还还有有：

17、循循环环特特征征表表、等等价价名名表表、公公用用链链表、格式表、中间代码表等。表、格式表、中间代码表等。v格式格式:NAME(名字名字)INFORMATION(信息信息)湖南农业大学信息科学技术学院 王 奕3.3.出错处理出错处理v任务：如果源程序有错，编译程序应发现错任务：如果源程序有错，编译程序应发现错误并报告给用户。误并报告给用户。v完成：由专门的出错处理程序来完成。完成：由专门的出错处理程序来完成。v错误类型：错误类型：语法错误：在词法或语法分析阶段检测语法错误：在词法或语法分析阶段检测 语义错误：在语义分析阶段检测语义错误：在语义分析阶段检测 for(i=1,i=k,i+)湖南农业大

18、学信息科学技术学院 王 奕4.4.编译程序的逻辑结构：遍编译程序的逻辑结构：遍(pass)(pass)v概概念念：所所谓谓“遍遍”，就就是是对对源源程程序序或或源源程程序序的的中中间间表表示示从从头头到到尾尾扫扫描描一一次次,并并转转换换成成另另一一紧邻的等价物的全过程。紧邻的等价物的全过程。v阶阶段段与与遍遍是是不不同同的的概概念念。一一遍遍可可以以由由若若干干段段组组成，一个阶段也可以分若干遍来完成。成，一个阶段也可以分若干遍来完成。五个基本阶段五个基本阶段：是将源程序翻译为目标程序在逻辑上要完成的：是将源程序翻译为目标程序在逻辑上要完成的 工作。工作。遍遍：是指完成上述：是指完成上述5个基本阶段的工作，要经过几次扫描处理。个基本阶段的工作，要经过几次扫描处理。要注意遍与基本阶段的区别要注意遍与基本阶段的区别