编译原理Chapt1

1、江西财经大学信息管理学院江西财经大学信息管理学院编译方法编译方法主讲：钱忠胜主讲：钱忠胜 博士博士计算机系计算机系 系统软件课程组系统软件课程组Tel: 079183983891(O)Email: 编译方法第一章第一章 引引 论论江西财经大学信息管理学院江西财经大学信息管理学院n介绍程序设计语言编译程序构造的基本原介绍程序设计语言编译程序构造的基本原理和基本实现技术理和基本实现技术n领悟计算机理论的精髓，从实现的角度重领悟计算机理论的精髓，从实现的角度重新审视软件的开发新审视软件的开发江西财经大学信息管理学院江西财经大学信息管理学院n编译理论与方法编译理论与方法计算机科学与技术中理论和实践相结

2、合的最好计算机科学与技术中理论和实践相结合的最好典范典范 ACM 图灵奖，授予在计算机技术领域作出突出图灵奖，授予在计算机技术领域作出突出贡献的科学家贡献的科学家n自自1966年以来（截止年以来（截止2009年）的所有年）的所有55位图灵奖获位图灵奖获得者中，有近得者中，有近1/3的科学家是因为在程序设计语言和的科学家是因为在程序设计语言和编译方面的成就而获得该项奖励编译方面的成就而获得该项奖励n程序设计语言和编译的发展集中体现了计算机科学程序设计语言和编译的发展集中体现了计算机科学发展的重要成果与精华发展的重要成果与精华n计算机应用能发展到今天，编译技术的发展有着极计算机应用能发展到今天，编

3、译技术的发展有着极其重要的、不可替代的作用其重要的、不可替代的作用江西财经大学信息管理学院江西财经大学信息管理学院n整个整个20世纪世纪50年代，编译程序的编写一直年代，编译程序的编写一直被认为是一个难题，第一个被认为是一个难题，第一个FORTRAN语言语言(1954年年)编译程序整整花了编译程序整整花了18年才得以实年才得以实现。现。江西财经大学信息管理学院江西财经大学信息管理学院源语言源语言程序程序目标语目标语言程序言程序翻译翻译程序程序翻译翻译一、什么是编译程序一、什么是编译程序q翻译程序翻译程序 把某一种语言程序把某一种语言程序( (称为称为源语言程序源语言程序) )等价地转等价地转换

4、成另一种语言程序换成另一种语言程序( (称为称为目标语言程序目标语言程序) )的程序的程序江西财经大学信息管理学院江西财经大学信息管理学院高级语高级语言程序言程序机器语机器语言程序言程序结果结果编译编译程序程序翻译翻译运行运行一、什么是编译程序一、什么是编译程序q编译程序编译程序(compiler)(compiler) 把某一种把某一种高级语言程序高级语言程序等价地转换成另一种等价地转换成另一种低级语低级语言程序言程序( (如汇编语言或机器语言程序如汇编语言或机器语言程序) )的程序的程序诊断编译程序诊断编译程序优化编译程序优化编译程序交叉编译程序交叉编译程序可变目标编译程序可变目标编译程序江

5、西财经大学信息管理学院江西财经大学信息管理学院一、什么是编译程序一、什么是编译程序q解释程序解释程序 把源语言写的源程序作为输入，但不产生目标程序，把源语言写的源程序作为输入，但不产生目标程序，而是边解释边执行源程序本身而是边解释边执行源程序本身源程序源程序结果结果解释解释程序程序解释执行解释执行江西财经大学信息管理学院江西财经大学信息管理学院编译程序编译程序 vs. 解释程序解释程序编译解释江西财经大学信息管理学院江西财经大学信息管理学院江西财经大学信息管理学院江西财经大学信息管理学院n在编译的每个阶段都有可能发现错误，最简单的在编译的每个阶段都有可能发现错误，最简单的处理是：终止编译程序工

6、作，指出错误的地点和处理是：终止编译程序工作，指出错误的地点和类型。类型。n目前有些高级语言的翻译程序同时具有解释和编目前有些高级语言的翻译程序同时具有解释和编译两种功能，在调试时采用解释方式，调试过程译两种功能，在调试时采用解释方式，调试过程中若发现错误，翻译程序立即暂停工作，并用特中若发现错误，翻译程序立即暂停工作，并用特殊记号指示当前错误的位置；当调试完成后，可殊记号指示当前错误的位置；当调试完成后，可利用翻译程序的编译功能，将源程序翻译成机器利用翻译程序的编译功能，将源程序翻译成机器码程序。码程序。n机器码程序通常存放在扩展名为机器码程序通常存放在扩展名为.exe的文件中，的文件中，它

7、可在操作系统环境下脱离翻译程序直接运行。它可在操作系统环境下脱离翻译程序直接运行。江西财经大学信息管理学院江西财经大学信息管理学院二、编译过程二、编译过程n把英文翻译为中文把英文翻译为中文 识别出句子中的一个个单词；识别出句子中的一个个单词；分析句子的语法结构；分析句子的语法结构；根据句子的含义进行初步翻译；根据句子的含义进行初步翻译；对译文进行修饰；对译文进行修饰；写出最后的译文。写出最后的译文。 词法分析词法分析语法分析语法分析中间代码中间代码产生产生优化优化目标代码目标代码产生产生江西财经大学信息管理学院江西财经大学信息管理学院二、编译过程二、编译过程n编译程序的工作一般分为五个阶段编译

8、程序的工作一般分为五个阶段: :词法分析词法分析语法分析语法分析中间代码产生（语义分析）中间代码产生（语义分析）优化优化目标代码产生目标代码产生江西财经大学信息管理学院江西财经大学信息管理学院1.1.词法分析词法分析n任务任务: : 输入源程序，对构成源程序的字输入源程序，对构成源程序的字符串进行扫描和分解，识别出一个个单符串进行扫描和分解，识别出一个个单词符号。词符号。n依循的原则：构词规则依循的原则：构词规则n描述工具：有限自动机描述工具：有限自动机nFOR i := 1 TO 100 DOFOR i := 1 TO 100 DO 保留字保留字 标识符标识符 等符等符 整常数整常数 保留字

9、保留字 整常数整常数 保留字保留字江西财经大学信息管理学院江西财经大学信息管理学院2.2.语法分析语法分析n任务任务: :在词法分析的基础上，根据语言的语在词法分析的基础上，根据语言的语法规则把单词符号串分解成各类语法单位。法规则把单词符号串分解成各类语法单位。n依循的原则：语法规则依循的原则：语法规则n描述工具：上下文无关文法描述工具：上下文无关文法nZ := X + 0.618 Z := X + 0.618 * * Y Y 算术表达式，赋值语句算术表达式，赋值语句江西财经大学信息管理学院江西财经大学信息管理学院3.3.中间代码产生（语义分析）中间代码产生（语义分析）n任务任务: :对各类不

10、同语法范畴按语言的语义对各类不同语法范畴按语言的语义进行初步翻译。进行初步翻译。n依循的原则：语义规则依循的原则：语义规则n中间代码中间代码: :三元式、四元式、语法树、后三元式、四元式、语法树、后缀式等缀式等nZ:=X + 0.618 Z:=X + 0.618 * * Y Y 翻译成四元式为翻译成四元式为(1) (1) * * 0.618 Y T1 0.618 Y T1(2) + X T1 T2(2) + X T1 T2(3) := T2 _ Z(3) := T2 _ Z江西财经大学信息管理学院江西财经大学信息管理学院4.4.优化优化n任务：对于前阶段产生的中间代码进行任务：对于前阶段产生的

11、中间代码进行加工变换，以期在最后阶段产生更高效加工变换，以期在最后阶段产生更高效的目标代码。的目标代码。n依循的原则：程序的等价变换规则依循的原则：程序的等价变换规则FOR K:=1 TO 100 DOFOR K:=1 TO 100 DO BEGIN BEGIN X:=I+1; X:=I+1; M := I + 10 M := I + 10 * * K; K; N := J + 10 N := J + 10 * * K; K; END END江西财经大学信息管理学院江西财经大学信息管理学院中间代码（一）中间代码（一）序号序号 OPROPR OPN1OPN1 OPN2 RESULT OPN2 R

12、ESULT 注释注释(1)(1) :=:=1 1 K K:=1 K K:=1(2)(2) jj100100 K K (10) if (100K) (10) if (100K) goto (10) goto (10)(3)(3) + +I I 1 1 X X X:=I+1 X:=I+1(4)(4) * *1010 K K T1 T1 T1:=10 T1:=10* *K K(5)(5) + +I I T1 T1 M M M:=I+T1 M:=I+T1(6)(6) * *1010 K K T2 T2 T2:=10 T2:=10* *K K(7)(7) + +J J T2 T2 N N N:=J+T2

13、 N:=J+T2(8)(8) + +K K 1 1 K K K:=K+1 K:=K+1(9)(9) j j (2) (2) goto (2) goto (2)(10)(10)400次加法次加法200次乘法次乘法江西财经大学信息管理学院江西财经大学信息管理学院转换后的等价代码（二）转换后的等价代码（二）序号序号 OPROPR OPN1OPN1 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) :=:=J J N N N:=J N:=J(4)(4) :=:=

14、1 1 K K K:=1 K:=1(5)(5) jj100100 K K(10)(10) if (100K) if (100K) goto (10) goto (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) goto (5) goto (5)(10)(10)301次加法次加法江西财经大学信息管理学院江西财经大学信息管理学院5.5.目标代码产生目标代码产生n任务任务: : 把中间

15、代码变换成特定机器上的目把中间代码变换成特定机器上的目标代码。标代码。n依赖于硬件系统结构和机器指令的含义依赖于硬件系统结构和机器指令的含义n目标代码三种形式目标代码三种形式: :绝对指令代码绝对指令代码: : 可直接运行可直接运行 可重新定位指令代码可重新定位指令代码: : 需要连接装配需要连接装配汇编指令代码汇编指令代码: : 需要进行汇编需要进行汇编江西财经大学信息管理学院江西财经大学信息管理学院模块模块Aa模块模块Bb模块模块Cc模块模块Aa模块模块Bb模块模块Cc模块模块Aa模块模块Bb模块模块Cc江西财经大学信息管理学院江西财经大学信息管理学院5.5.目标代码产生目标代码产生江西财

16、经大学信息管理学院江西财经大学信息管理学院三、编译程序结构三、编译程序结构1.1.编译程序总框编译程序总框江西财经大学信息管理学院江西财经大学信息管理学院四元式四元式单词符号单词符号语法单位语法单位四元式四元式目标代码目标代码词法分析器词法分析器语法分析器语法分析器语义分析与中间代码语义分析与中间代码生成器生成器优化段优化段源程序源程序表表格格管管理理出出错错处处理理目标代码生成器目标代码生成器江西财经大学信息管理学院江西财经大学信息管理学院2.2.表格和表格管理表格和表格管理n常见的表格常见的表格: :符号名表，常数表，标号表，符号名表，常数表，标号表，过程引用表。过程引用表。n格式格式:

17、: 名字信息江西财经大学信息管理学院江西财经大学信息管理学院例例: PASCAL: PASCAL程序段：程序段：PROCEDURE INCWAP(MPROCEDURE INCWAP(M，N:INTEGER);N:INTEGER);LABEL START;LABEL START;VARVAR K:INTEGER; K:INTEGER;BEGINBEGINSTART:START: K:=M+1; K:=M+1; M:=N+4; M:=N+4; N:=K; N:=K;END.END.江西财经大学信息管理学院江西财经大学信息管理学院PROCEDURE INCWAP(MPROCEDURE INCWAP(

18、M，N:INTEGER);N:INTEGER);LABEL START;LABEL START;VARVAR K:INTEGER; K:INTEGER;BEGINBEGINSTART:START: K:=M+1; K:=M+1; M:=N+4; M:=N+4; N:=K; N:=K;END.END.江西财经大学信息管理学院江西财经大学信息管理学院PROCEDURE INCWAP(MPROCEDURE INCWAP(M，N:INTEGER);N:INTEGER);LABEL START;LABEL START;VARVAR K:INTEGER; K:INTEGER;BEGINBEGINSTART

19、:START: K:=M+1; K:=M+1; M:=N+4; M:=N+4; N:=K; N:=K;END.END.江西财经大学信息管理学院江西财经大学信息管理学院PROCEDURE INCWAP(MPROCEDURE INCWAP(M，N:INTEGER);N:INTEGER);LABEL START;LABEL START;VARVAR K:INTEGER; K:INTEGER;BEGINBEGINSTART:START: K:=M+1; K:=M+1; M:=N+4; M:=N+4; N:=K; N:=K;END.END.江西财经大学信息管理学院江西财经大学信息管理学院PROCEDUR

20、E INCWAP(MPROCEDURE INCWAP(M，N:INTEGER);N:INTEGER);LABEL START;LABEL START;VARVAR K:INTEGER; K:INTEGER;BEGINBEGINSTART:START: K:=M+1; K:=M+1; M:=N+4; M:=N+4; N:=K; N:=K;END.END.江西财经大学信息管理学院江西财经大学信息管理学院江西财经大学信息管理学院江西财经大学信息管理学院PROCEDURE INCWAP(MPROCEDURE INCWAP(M，N:INTEGER);N:INTEGER);LABEL START;LABE

21、L START;VARVAR K:INTEGER; K:INTEGER;BEGINBEGINSTART:START: K:=M+1; K:=M+1; M:=N+4; M:=N+4; N:=K; N:=K;END.END.江西财经大学信息管理学院江西财经大学信息管理学院3.3.出错处理出错处理n出错处理程序：出错处理程序：发现发现源程序中的源程序中的错误，把错误，把有关错误信息报告给用户有关错误信息报告给用户语法错误语法错误语义错误语义错误 江西财经大学信息管理学院江西财经大学信息管理学院4.4.遍遍(pass)(pass)n所谓所谓 遍遍 ， 就是对源程序或源程序的中间就是对源程序或源程序的中

22、间表示从头到尾扫描一次。表示从头到尾扫描一次。n阶段与遍是不同的概念。一遍可以由若干阶段与遍是不同的概念。一遍可以由若干段组成，一个阶段也可以分若干遍来完成。段组成，一个阶段也可以分若干遍来完成。江西财经大学信息管理学院江西财经大学信息管理学院5.5. 编译前端与后端编译前端与后端n编译前端编译前端：与源语言有关，如词法分析，语：与源语言有关，如词法分析，语法分析，语义分析与中间代码产生，与机器法分析，语义分析与中间代码产生，与机器无关的优化无关的优化n编译后端编译后端：与目标机有关，与目标机有关的：与目标机有关，与目标机有关的优化，目标代码产生优化，目标代码产生优点：减少对内存容量的要求，程

23、序逻辑结构清优点：减少对内存容量的要求，程序逻辑结构清晰晰; ; 优化更充分，有利于移植。优化更充分，有利于移植。不足不足: : 编译程序运行的效率低编译程序运行的效率低源语言源语言中间语言中间语言目标语言目标语言前端前端后端后端江西财经大学信息管理学院江西财经大学信息管理学院四、四、编译程序与程序设计环境编译程序与程序设计环境 n程序设计环境程序设计环境 编辑程序编辑程序 编译程序编译程序连接程序连接程序 调试工具调试工具 n集成化的程序设计环境集成化的程序设计环境 江西财经大学信息管理学院江西财经大学信息管理学院五、编译程序生成五、编译程序生成n以汇编语言和机器语言为工具以汇编语言和机器语

24、言为工具优点优点: : 可以针对具体的机器，充分发挥计可以针对具体的机器，充分发挥计算机的系统功能。生成的程序效率高。算机的系统功能。生成的程序效率高。缺点缺点: : 程序难读、难写、易出错、难维护、程序难读、难写、易出错、难维护、生产的效率低。生产的效率低。江西财经大学信息管理学院江西财经大学信息管理学院五、编译程序生成五、编译程序生成n高级语言书写高级语言书写 S T I S 源程序 T 目标程序 I 实现语言优点优点: : 程序易读、易理解、容易维护、程序易读、易理解、容易维护、生产的效率高。生产的效率高。缺点缺点: : 难以充分发挥计算机的系统功能，难以充分发挥计算机的系统功能，生成的

25、程序效率低。生成的程序效率低。江西财经大学信息管理学院江西财经大学信息管理学院五、编译程序生成五、编译程序生成n高级语言书写高级语言书写利用已有的某种语言的编译程序实现另一语利用已有的某种语言的编译程序实现另一语言的编译程序。言的编译程序。L1语言语言A代码代码P1:A代码代码L2语言语言A代码代码P2: L1语言语言L2语言语言A代码代码P2:A代码代码同一台机器同一台机器不同的语言不同的语言江西财经大学信息管理学院江西财经大学信息管理学院五、编译程序生成五、编译程序生成n 移植方法移植方法把一种机器上的编译程序移植到另一种机器把一种机器上的编译程序移植到另一种机器上。上。L语言语言A代码代

26、码P1:A代码代码L语言语言B代码代码P2: L语言语言L语言语言B代码代码P2:A代码代码L语言语言B代码代码P2: L语言语言L语言语言B代码代码P2:B代码代码同一种语言同一种语言不同的机器不同的机器江西财经大学信息管理学院江西财经大学信息管理学院L1+L2+.+LnL1+L2五、编译程序生成五、编译程序生成n自展技术自展技术L1江西财经大学信息管理学院江西财经大学信息管理学院五、编译程序生成五、编译程序生成n编译程序自动产生编译程序自动产生编译程序编译程序- -编译程序，编译程序书写系统编译程序，编译程序书写系统LEX LEX 词法分析程序产生器词法分析程序产生器YACC YACC 语

27、法分析程序产生器语法分析程序产生器编译程序编译程序自动产生器自动产生器L语言的语法描述语言的语法描述语义描述语义描述目标语言目标语言或机器描述或机器描述L语言的语言的编译程序编译程序江西财经大学信息管理学院江西财经大学信息管理学院六、关于学习编译原理六、关于学习编译原理n 构造编译程序的前提构造编译程序的前提掌握源语言掌握源语言掌握目标语言掌握目标语言掌握编译方法掌握编译方法江西财经大学信息管理学院江西财经大学信息管理学院六、关于学习编译原理六、关于学习编译原理n意义意义学习编译程序构造的原理、方法、技术学习编译程序构造的原理、方法、技术更好地理解高级语言更好地理解高级语言编译的原理和方法有助于构造一些实用的工具编译的原理和方法有助于构造一些实用的工具培养计算思维，提升系统认识能力（在系统的级别上重新认识算法培养计算思维，提升系统认识能力（在系统的级别上重新认识算法和程序）和程序）培养形式化描述能力培养形式化描述能力 提高对计算机系统的总体认识能力提高对计算机系统的总体认识能