程序设计语言编译程序构造的基本原理和基本实现技术

1、 编译原理第一章第一章 引引 论论n本课程介绍程序设计语言编译程序构造的本课程介绍程序设计语言编译程序构造的基本原理和基本实现技术基本原理和基本实现技术. .源语言源语言程序程序目标语目标语言程序言程序翻译翻译程序程序翻译翻译一一. 什么是编译程序什么是编译程序q翻译程序翻译程序 把某一种语言程序把某一种语言程序( (称为称为源语言程序源语言程序) )等价地转等价地转换成另一种语言程序换成另一种语言程序( (称为称为目标语言程序目标语言程序) )的程序的程序高级语高级语言程序言程序机器语机器语言程序言程序结果结果编译编译程序程序翻译翻译运行运行一一. 什么是编译程序什么是编译程序q编译程序编译

2、程序(compiler)(compiler) 把某一种把某一种高级语言程序高级语言程序等价地转换成另一种等价地转换成另一种低级语低级语言程序言程序( (如汇编语言或机器语言程序如汇编语言或机器语言程序) )的程序的程序诊断编译程序诊断编译程序优化编译程序优化编译程序交叉编译程序交叉编译程序可变目标编译程序可变目标编译程序一一. 什么是编译程序什么是编译程序q解释程序解释程序 把源语言写的源程序作为输入，但不产生目标程序，把源语言写的源程序作为输入，但不产生目标程序，而是边解释边执行源程序本身而是边解释边执行源程序本身源程序源程序结果结果解释解释程序程序解释执行解释执行二二. . 编译过程编译过

3、程n把英文翻译为中文把英文翻译为中文 识别出句子中的一个个单词；识别出句子中的一个个单词；分析句子的语法结构；分析句子的语法结构；根据句子的含义进行初步翻译；根据句子的含义进行初步翻译；对译文进行修饰；对译文进行修饰；写出最后的译文。写出最后的译文。 词法分析词法分析语法分析语法分析中间代码中间代码产生产生优化优化目标代码目标代码产生产生二二. . 编译过程编译过程n编译程序的工作一般分为五个阶段编译程序的工作一般分为五个阶段: :词法分析词法分析语法分析语法分析中间代码产生中间代码产生优化优化目标代码产生目标代码产生1. 1. 词法分析词法分析n任务任务: : 输入源程序，对构成源程序的字输

4、入源程序，对构成源程序的字符串进行扫描和分解，识别出一个个单符串进行扫描和分解，识别出一个个单词符号。词符号。n依循的原则：构词规则依循的原则：构词规则n描述工具：有限自动机描述工具：有限自动机nFOR I := 1 TO 100 DOFOR I := 1 TO 100 DO 保留字保留字 标识符标识符 等符等符 整常数整常数 保留字保留字 整常数整常数 保留字保留字2. 2. 语法分析语法分析n任务任务: :在词法分析的基础上，根据语言的语在词法分析的基础上，根据语言的语法规则把单词符号串分解成各类语法单位。法规则把单词符号串分解成各类语法单位。n依循的原则：语法规则依循的原则：语法规则n描

5、述工具：上下文无关文法描述工具：上下文无关文法nZ := X + 0.618 Z := X + 0.618 * * Y Y 算术表达式，赋值语句算术表达式，赋值语句3. 3. 中间代码产生中间代码产生n任务任务: :对各类不同语法范畴按语言的语义对各类不同语法范畴按语言的语义进行初步翻译。进行初步翻译。n依循的原则：语义规则依循的原则：语义规则n中间代码中间代码: :三元式，四元式，树形结构等三元式，四元式，树形结构等nZ:=X + 0.618 Z:=X + 0.618 * * Y Y 翻译成四元式为翻译成四元式为(1) (1) * * 0.618 Y T1 0.618 Y T1(2) + X

6、 T1 T2(2) + X T1 T2(3) := T2 _ Z(3) := T2 _ Z4. 4. 优化优化n任务：对于前阶段产生的中间代码进行任务：对于前阶段产生的中间代码进行加工变换，以期在最后阶段产生更高效加工变换，以期在最后阶段产生更高效的目标代码。的目标代码。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;

7、END END中间代码（一）中间代码（一）序号序号 OPROPR OPN1OPN1 OPN2 RESULT OPN2 RESULT 注释注释(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

8、K K T2 T2 T2:=10 T2:=10* *K 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+1 K:=K+1(9)(9) j j (2) (2) goto (2) goto (2)(10)(10)转换后的等价代码（二）转换后的等价代码（二）序号序号 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:

9、=J N:=J(4)(4) :=:=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)5. 5. 目标代码产生目标代码产生n任务任务: : 把中间代码变换成特定机器上的目把

10、中间代码变换成特定机器上的目标代码。标代码。n依赖于硬件系统结构和机器指令的含义依赖于硬件系统结构和机器指令的含义n目标代码三种形式目标代码三种形式: :绝对指令代码绝对指令代码: : 可直接运行可直接运行 可重新定位指令代码可重新定位指令代码: : 需要连接装配需要连接装配汇编指令代码汇编指令代码: : 需要进行汇编需要进行汇编三三. . 编译程序结构编译程序结构n编译程序总框编译程序总框中间代码中间代码单词符号单词符号语法单位语法单位中间代码中间代码目标代码目标代码词法分析器词法分析器语法分析器语法分析器语义分析与中间代码语义分析与中间代码生成器生成器优化段优化段源程序源程序表表格格管管理

11、理出出错错处处理理目标代码生成器目标代码生成器2. 2. 表格和表格管理表格和表格管理n常见的表格常见的表格: :符号名表，常数表，标号表，符号名表，常数表，标号表，入口名表，过程引用表。入口名表，过程引用表。n格式格式: : 名字信息例例: 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

12、; 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.表 0.1 符号名表 SNTNAMEINFORMATIONM形式参数，整型，值参数N形式参数，整型，值参数K整型，变量表 0.2 常数表 CT值(VALUE)(1)1(2)

13、4PROCEDURE 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.表 0.3 入口名表 ENTNAMEINFORMATION(1)INCWAP 二目子程序,入口四元式:1PROCEDURE INCWAP(MPROCEDURE INCWAP(M，N:INTEGER);N:INTEGER);LAB

14、EL 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. 表 0.4 标号表 LTNAME INFORMATION(1)START 四元式:(4)PROCEDURE INCWAP(MPROCEDURE INCWAP(M，N:INTEGER);N:INTEGER);LABEL START;LABEL START;VARVAR K:INTEGER; K:INTEGER;BEGINBEGINSTART:START

15、: K:=M+1; K:=M+1; M:=N+4; M:=N+4; N:=K; N:=K;END.END.表 0.1 符号名表 SNTNAMEINFORMATIONM形式参数，整型，值参数N形式参数，整型，值参数K整型，变量表 0.2 常数表 CT值(VALUE)(1)1(2)4表 0.3 入口名表 ENTNAMEINFORMATION(1)INCWAP 二目子程序,入口四元式:1 表 0.4 标号表 LTNAME INFORMATION(1)START 四元式:(4) 表 0.5 四元式表 QTOPROPN1OPN2RESULT(1)link(2)parINCWAP1M(3)parINCWA

16、P2N(4)+M1K(5)+N4M(6):=KN(7) returnPROCEDURE 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.3. 3. 出错处理出错处理n出错处理程序：出错处理程序：发现发现源程序中的源程序中的错误，把错误，把有关错误信息报告给用户有关错误信息报告给用户语法错误语法错误

17、语义错误语义错误 4. 4. 遍遍(pass)(pass)n所谓所谓“遍遍”， 就是对源程序或源程序的中就是对源程序或源程序的中间表示从头到尾扫描一次间表示从头到尾扫描一次, ,从外存输入从外存输入, ,处处理后结果输出到外存。理后结果输出到外存。n阶段与遍是不同的概念。一遍可以由若干阶段与遍是不同的概念。一遍可以由若干段组成，一个阶段也可以分若干遍来完成。段组成，一个阶段也可以分若干遍来完成。5. 编译前端与后端编译前端与后端n编译前端编译前端：与源语言有关，如词法分析，：与源语言有关，如词法分析，语法分析，语义分析与中间代码产生，语法分析，语义分析与中间代码产生，与机器无关的优化与机器无关

18、的优化n编译后端编译后端：与目标机有关，与目标机有：与目标机有关，与目标机有关的优化，目标代码产生关的优化，目标代码产生源语言源语言中间语言中间语言目标语言目标语言前端前端后端后端四四. .编译程序与程序设计环境编译程序与程序设计环境 n程序设计环境程序设计环境 编辑程序编辑程序 编译程序编译程序连接程序连接程序 调试工具调试工具 n集成化的程序设计环境集成化的程序设计环境 五五. .编译程序生成编译程序生成n以汇编语言和机器语言为工具以汇编语言和机器语言为工具优点优点: : 可以针对具体的机器，充分发挥计可以针对具体的机器，充分发挥计算机的系统功能。生成的程序效率高。算机的系统功能。生成的程

19、序效率高。缺点缺点: : 程序难读、难写、易出错、难维护、程序难读、难写、易出错、难维护、生产的效率低。生产的效率低。五五. .编译程序生成编译程序生成n高级语言书写高级语言书写 S T I S 源程序 T 目标程序 I 实现语言优点优点: : 程序易读、易理解、容易维护、程序易读、易理解、容易维护、生产的效率高。生产的效率高。缺点缺点: : 难以充分发挥计算机的系统功能，难以充分发挥计算机的系统功能，生成的程序效率低。生成的程序效率低。五五. .编译程序生成编译程序生成n高级语言书写高级语言书写利用已有的某种语言的编译程序实现另一语利用已有的某种语言的编译程序实现另一语言的编译程序。言的编译

20、程序。L1语言语言A代码代码P1:A代码代码L2语言语言A代码代码P2: L1语言语言L2语言语言A代码代码P2:A代码代码五五. .编译程序生成编译程序生成n 移植方法移植方法把一种机器上的编译程序移植到另一种机器把一种机器上的编译程序移植到另一种机器上。上。L语言语言A代码代码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 语法分析程序产生器语法分析程序产