编译原理习题

1、编译原理课题组编译原理课题组编译原理 2022年年5月月6日日 编 译 原 理课程组高级语言汇编语言SOURCE PROGRAMAssemble PROGRAM？翻译程序？翻译程序？TRANSLATER 为什么要学习编译原理n程序设计语言是计算机软件专业的重要核心程序设计语言是计算机软件专业的重要核心n学习编程的历程：学习编程的历程：C C语言汇编语言数据结构语言汇编语言数据结构 2022年年5月月6日日 编 译 原 理课程组为什么要学习编译原理n必修主干课程必修主干课程，操作系统和编译系统构成程序，操作系统和编译系统构成程序设计者与计算机之间的基本界面。设计者与计算机之间的基本界面。n通过学

2、习该课程，掌握编译的基本理论、常用通过学习该课程，掌握编译的基本理论、常用的编译技术，了解编译过程及编译系统结构和的编译技术，了解编译过程及编译系统结构和机理。能运用所学技术解决实际问题，能机理。能运用所学技术解决实际问题，能独立独立编写一个小型编译系统编写一个小型编译系统。n此外，通过学习编译原理可以更好地理解程序此外，通过学习编译原理可以更好地理解程序语言的内部机制语言的内部机制, ,从而更好地理解和运用程序从而更好地理解和运用程序设计语言。能运用编译程序构造的原理和技术设计语言。能运用编译程序构造的原理和技术完成完成相关软件工具的设计和开发相关软件工具的设计和开发工作。工作。 2022年

3、年5月月6日日 编 译 原 理课程组为什么要学习编译原理n计算机软件学科计算机软件学科理论与实践相结合理论与实践相结合的典范。的典范。n在学习过程中既要注重该领域在理论上取得在学习过程中既要注重该领域在理论上取得的完美结论，也要注重这些理论在实际中的的完美结论，也要注重这些理论在实际中的应用。应用。 2022年年5月月6日日 编 译 原 理课程组先修课程n要求先学习以下课程要求先学习以下课程1.程序设计语言程序设计语言2.算法与数据结构算法与数据结构：栈分配、堆分配、静态分配等各种：栈分配、堆分配、静态分配等各种存储分配方式。线性表、二叉查找树、哈希表等多种存储分配方式。线性表、二叉查找树、哈

4、希表等多种数据结构。数据结构。 3.离散数学离散数学：集合论与数理逻辑是进一步学习形式语言：集合论与数理逻辑是进一步学习形式语言与自动机理论的数学基础。与自动机理论的数学基础。 n最好学习过或同时学习以下课程最好学习过或同时学习以下课程1.软件工程软件工程：掌握大型程序设计以及工程化的软件生产：掌握大型程序设计以及工程化的软件生产方法。方法。2.形式语言与自动机形式语言与自动机：相当于本课程中词法分析与语法：相当于本课程中词法分析与语法分析的理论基础。分析的理论基础。 2022年年5月月6日日 编 译 原 理课程组n陈火旺陈火旺 刘春林等，刘春林等，程序设计语言编译原理程序设计语言编译原理，国

5、防工业出版社国防工业出版社教材教材参考书参考书 李建中译，李建中译，编译原理编译原理（龙书）（龙书），机械工业出版社，机械工业出版社 李冬梅，施海虎，李冬梅，施海虎，编译原理编译原理，人民邮电出版社，人民邮电出版社 吕映芝，张素琴等，吕映芝，张素琴等，编译原理编译原理，清华大学出版社，清华大学出版社 2022年年5月月6日日 编 译 原 理课程组 平时（平时（30%30%） 无故旷课：无故旷课： 一本教材，一本教材，认真听课认真听课：以讲义为主，板书为：以讲义为主，板书为辅辅-做适当的笔记做适当的笔记 认真完成课堂和课后认真完成课堂和课后作业作业 完成要求的完成要求的课外实验课外实验内容内容

6、期末（期末（70%70%）: :开卷笔试开卷笔试课程特点：理论性强，算法复杂课程特点：理论性强，算法复杂编译原理课题组编译原理课题组第一章第一章 引引 论论n本课程介绍程序设计语言编译程序构造的本课程介绍程序设计语言编译程序构造的基本原理和基本实现技术基本原理和基本实现技术. .编译原理课题组编译原理课题组第一章第一章 引引 论论n编译理论与方法编译理论与方法计算机科学与技术中理论和实践相结合的最好计算机科学与技术中理论和实践相结合的最好典范典范 ACM 图灵奖，授予在计算机技术领域作出突出图灵奖，授予在计算机技术领域作出突出贡献的科学家贡献的科学家n程序设计语言、编译理论与方法约占程序设计语

7、言、编译理论与方法约占1/3编译原理课题组编译原理课题组源语言源语言程序程序目标语目标语言程序言程序翻译翻译程序程序翻译翻译一一. 什么是编译程序什么是编译程序q翻译程序翻译程序 把某一种语言程序把某一种语言程序( (称为称为源语言程序源语言程序) )等价地转等价地转换成另一种语言程序换成另一种语言程序( (称为称为目标语言程序目标语言程序) )的程序的程序编译原理课题组编译原理课题组高级语高级语言程序言程序机器语机器语言程序言程序结果结果编译编译程序程序翻译翻译运行运行一一. 什么是编译程序什么是编译程序q编译程序编译程序(compiler)(compiler) 把某一种把某一种高级语言程序

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

9、译解释编译原理课题组编译原理课题组二二. . 编译过程编译过程n把英文翻译为中文把英文翻译为中文 识别出句子中的一个个单词；识别出句子中的一个个单词；分析句子的语法结构；分析句子的语法结构；根据句子的含义进行初步翻译；根据句子的含义进行初步翻译；对译文进行修饰；对译文进行修饰；写出最后的译文。写出最后的译文。 词法分析词法分析语法分析语法分析中间代码中间代码产生产生优化优化目标代码目标代码产生产生编译原理课题组编译原理课题组二二. . 编译过程编译过程n编译程序的工作一般分为五个阶段编译程序的工作一般分为五个阶段: :词法分析词法分析语法分析语法分析中间代码产生中间代码产生优化优化目标代码产生

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

11、的基础上，根据语言的语法规则把单词符号串分解成各类语法单位。法规则把单词符号串分解成各类语法单位。n依循的原则：语法规则依循的原则：语法规则n描述工具：上下文无关文法描述工具：上下文无关文法nZ := X + 0.618 Z := X + 0.618 * * Y Y 算术表达式，赋值语句算术表达式，赋值语句编译原理课题组编译原理课题组3. 3. 中间代码产生中间代码产生n任务任务: :对各类不同语法范畴按语言的语义对各类不同语法范畴按语言的语义进行初步翻译。进行初步翻译。n依循的原则：语义规则依循的原则：语义规则n中间代码中间代码: :三元式，四元式，树形结构等三元式，四元式，树形结构等nZ:

12、=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任务：对于前阶段产生的中间代码进行任务：对于前阶段产生的中间代码进行加工变换，以期在最后阶段产生更高效加工变换，以期在最后阶段产生更高效的目标代码。的目标代码。n依循的原则：程序的等价变换规则依循的原则：程序的等价变换规则FOR K:=1 TO 100 DOFOR K:=1 TO 100

13、 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 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

14、 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 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)编译原理课题组编译原理课题组转换后的等价代码（二）转换后的等价代码（二）序号序

15、号 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) :=:=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

16、 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任务任务: : 把中间代码变换成特定机器上的目把中间代码变换成特定机器上的目标代码。标代码。n依赖于硬件系统结构和机器指令的含义依赖于硬件系统结构和机器指令的含义n目标代码三种形式目标代码三种形式: :绝对指令代码绝对指令代码: : 可直接运行可直接运行 可重新定位指令代码可重新定位指令代码: : 需要连接装配需要连接装配汇编指令代码汇编指令代码: : 需要进行

17、汇编需要进行汇编编译原理课题组编译原理课题组模块模块Aa模块模块Bb模块模块Cc模块模块Aa模块模块Bb模块模块Cc模块模块Aa模块模块D模块模块Cc编译原理课题组编译原理课题组5. 5. 目标代码产生目标代码产生n例例: 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 01 00 000011110011 01 10 000000100100 01 00 00010011 编译原理课题组编译原理课题组三三. . 编

18、译程序结构编译程序结构n编译程序总框编译程序总框编译原理课题组编译原理课题组四元式四元式单词符号单词符号语法单位语法单位四元式四元式目标代码目标代码词法分析器词法分析器语法分析器语法分析器语义分析与中间代码语义分析与中间代码生成器生成器优化段优化段源程序源程序表表格格管管理理出出错错处处理理目标代码生成器目标代码生成器编译原理课题组编译原理课题组2. 2. 表格和表格管理表格和表格管理n常见的表格常见的表格: :符号名表，常数表，标号表，符号名表，常数表，标号表，入口名表，过程引用表。入口名表，过程引用表。n格式格式: : 名字信息编译原理课题组编译原理课题组例例: PASCAL: PASCA

19、L程序段：程序段：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(M，N:INTEGER);N:INTEGER);LABEL START;LABEL START;VARVAR K:

20、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)4PROCEDURE INCWAP(MPROCEDURE INCWAP(M，N:INTEGER);N:INTEGER);LABEL START;LABEL START;VARVAR K:INTEGER; K:INT

21、EGER;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);LABEL START;LABEL START;VARVAR K:INTEGER; K:INTEGER;BEGINBEGINSTART:START: K:=M+1; K:=M+1; M:=N+

22、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: K:=M+1; K:=M+1; M:=N+4; M:=N+4; N:=K; N:=K;END.END.编译原理课题组编译原理课题组表 0.1 符号名表 S

23、NTNAMEINFORMATIONM形式参数，整型，值参数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)parINCWAP2N(4)+M1K(5)+N4M(6):=KN(7) returnPROCEDURE INCWAP(

24、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出错处理程序：出错处理程序：发现发现源程序中的源程序中的错误，把错误，把有关错误信息报告给用户有关错误信息报告给用户语法错误语法错误语义错误语义错误 编译原理课题组编译原理课题组4. 4. 遍遍(pass)

25、(pass)n所谓所谓 遍遍 ， 就是对源程序或源程序的中间就是对源程序或源程序的中间表示从头到尾扫描一次。表示从头到尾扫描一次。n阶段与遍是不同的概念。一遍可以由若干阶段与遍是不同的概念。一遍可以由若干段组成，一个阶段也可以分若干遍来完成。段组成，一个阶段也可以分若干遍来完成。编译原理课题组编译原理课题组5. 编译前端与后端编译前端与后端n编译前端编译前端：与源语言有关，如词法分析，语：与源语言有关，如词法分析，语法分析，语义分析与中间代码产生，与机器法分析，语义分析与中间代码产生，与机器无关的优化无关的优化n编译后端编译后端：与目标机有关，与目标机有关的：与目标机有关，与目标机有关的优化，

26、目标代码产生优化，目标代码产生优点：减少对内存容量的要求，程序逻辑结构清优点：减少对内存容量的要求，程序逻辑结构清晰晰; ; 优化更充分，有利于移植。优化更充分，有利于移植。不足不足: : 编译程序运行的效率低编译程序运行的效率低源语言源语言中间语言中间语言目标语言目标语言前端前端后端后端编译原理课题组编译原理课题组JAVA语言语言操作系统平台操作系统平台Java虚拟机虚拟机(解释器解释器)Java编译器编译器Java源程序源程序(.java)Java虚拟机代码虚拟机代码(.class)解释执行解释执行编译原理课题组编译原理课题组四四. .编译程序与程序设计环境编译程序与程序设计环境 n程序设

27、计环境程序设计环境 编辑程序编辑程序 编译程序编译程序连接程序连接程序 调试工具调试工具 n集成化的程序设计环境集成化的程序设计环境 编译原理课题组编译原理课题组.NET Framework与VS.NETOperating SystemCommon Language RuntimeADO.NET: Data and XMLASP.NET: Web Services & Web FormsWindowsFormsCommon Language SpecificationVisual Studio.NETVBC+C#JScript编译原理课题组编译原理课题组五五. .编译程序生成编译程序生

28、成n以汇编语言和机器语言为工具以汇编语言和机器语言为工具优点优点: : 可以针对具体的机器，充分发挥计可以针对具体的机器，充分发挥计算机的系统功能。生成的程序效率高。算机的系统功能。生成的程序效率高。缺点缺点: : 程序难读、难写、易出错、难维护、程序难读、难写、易出错、难维护、生产的效率低。生产的效率低。编译原理课题组编译原理课题组五五. .编译程序生成编译程序生成n高级语言书写高级语言书写 S T I S 源程序 T 目标程序 I 实现语言优点优点: : 程序易读、易理解、容易维护、程序易读、易理解、容易维护、生产的效率高。生产的效率高。缺点缺点: : 难以充分发挥计算机的系统功能，难以充

29、分发挥计算机的系统功能，生成的程序效率低。生成的程序效率低。编译原理课题组编译原理课题组五五. .编译程序生成编译程序生成n高级语言书写高级语言书写利用已有的某种语言的编译程序实现另一语利用已有的某种语言的编译程序实现另一语言的编译程序。言的编译程序。L1语言语言A代码代码P1:A代码代码L2语言语言A代码代码P2: L1语言语言L2语言语言A代码代码P2:A代码代码编译原理课题组编译原理课题组五五. .编译程序生成编译程序生成n 移植方法移植方法把一种机器上的编译程序移植到另一种机器把一种机器上的编译程序移植到另一种机器上。上。L语言语言A代码代码P1:A代码代码L语言语言B代码代码P2:

30、L语言语言L语言语言B代码代码P2:A代码代码L语言语言B代码代码P2: L语言语言L语言语言B代码代码P2:B代码代码编译原理课题组编译原理课题组L1+L2+.+LnL1+L2五五. .编译程序生成编译程序生成n自展技术自展技术L1编译原理课题组编译原理课题组五五. .编译程序生成编译程序生成n编译程序自动产生编译程序自动产生编译程序编译程序- -编译程序，编译程序书写系统编译程序，编译程序书写系统LEX LEX 词法分析程序产生器词法分析程序产生器YACC YACC 语法分析程序产生器语法分析程序产生器编译程序编译程序自动产生器自动产生器L语言的语法描述语言的语法描述语义描述语义描述目标语

31、言目标语言或机器描述或机器描述L语言的语言的编译程序编译程序编译原理课题组编译原理课题组六六. . 关于学习编译原理关于学习编译原理n 构造编译程序的前提构造编译程序的前提: :掌握源语言掌握源语言掌握目标语言掌握目标语言掌握编译方法掌握编译方法编译原理课题组编译原理课题组六六. . 关于学习编译原理关于学习编译原理n意义意义: :学习编译程序构造原理，技术学习编译程序构造原理，技术更好地理解高级语言更好地理解高级语言编译的原理和方法有助于构造一些实用的编译的原理和方法有助于构造一些实用的工具工具编译原理课题组编译原理课题组六六. . 关于学习编译原理关于学习编译原理n 课程特点课程特点: :理解性理解性技术性技术性n 考核：考核：作业及上机实习：作业及上机实习：30%30%笔试：笔试：70%70% 内容内容1 1 什么是编译程序什么是编译程序2 2 编译过程和编译程序的结构编译过程和编译程序的结构3 3 为什么要学习编译程序为什么要学习编译程序 重点重点对编译程序的功能和结构做一综述对编译程序的功能和结构做一综述 难点难点了解编译程序各个成分在编译阶段的逻辑了解编译程序各个成分在编译阶段的逻辑关系以及他们怎样作为一个整体完成编译关系以及他们怎样作为一个整体