编译程序的设计与实现.pdf

发布时间：2022-06-09 发布人：admin 分类：说明书资料大小：3.02M 资料格式：pdf 举报版权申诉

wolegequya-4091458-4744300845404403843.pdf-第1页.png

第1页 / 共301页

wolegequya-4091458-4744300845404403843.pdf-第2页.png

第2页 / 共301页

wolegequya-4091458-4744300845404403843.pdf-第3页.png

第3页 / 共301页

wolegequya-4091458-4744300845404403843.pdf-第4页.png

第4页 / 共301页

wolegequya-4091458-4744300845404403843.pdf-第5页.png

第5页 / 共301页

wolegequya-4091458-4744300845404403843.pdf-第6页.png

第6页 / 共301页

wolegequya-4091458-4744300845404403843.pdf-第7页.png

第7页 / 共301页

wolegequya-4091458-4744300845404403843.pdf-第8页.png

第8页 / 共301页

前言

1．1 高级程序设计语言的实现

1．2 编译程序的组成

1．3 编译程序的实现

1．4 其他相关程序

2．1 SNL语言的特点

2．2 SNL语言的词法

2．2．1 语言的字符表

2．2．2 单词的巴科斯范式

2．3 SNL语言的语法

2．3．1 语法的非形式说明

2．3．2 语法的形式定义

2．4 SNL语言的语义

3．1 SNL编译程序功能结构

3．2 SNL编译器的开发环境

3．3 SNL编译器程序包

3．4 SNL编译器的主程序说明

4．1 词法分析简介

4．1．1 单词的分类

4．1．2 单词的Token表示

4．1．3 词法分析程序和语法分析程序的接口

4．2 DFA的构造和实现

4．2．1 状态转换图

4．2．2 状态转换图的实现

4．3 词法分析程序的实现

4．3．1 词法分析程序的输入输出

4．3．2 实现词法分析器的注意事项

4．3．3 词法分析程序的实现框图

4．4 词法分析程序的自动生成器

4．4．1 LEX/FLEX简介

4．4．2 LEX运行与应用过程

4．4．3 LEX源程序结构

4．4．4 应用LEX构造词法分析程序

5．1 语法分析概述

5．1．1 上下文无关文法

5．1．2 语法分析方法的分类

5．1．3 三个重要集合

5．1．4 SNL 语言的Predict集

5．2 语法分析程序的实现

5．2．1 语法分析程序的输入与输出

5．2．2 语法树节点的数据结构

5．3 递归下降法的实现

5．3．1 递归下降法基本原理

5．3．2 递归下降法应满足的条件

5．3．3 递归下降法的语法分析程序框图

5．4 LL(1)语法分析方法的实现

5．4．1 LL(1)语法分析方法的基本原理

5．4．2 SNL语言的LL(1)语法分析概述

5．4．3 LL(1)语法分析程序框图

5．5 语法分析程序的自动生成器

5．5．1 YACC/Bison

5．5．2 ACCENT

6．1 语义分析概述

6．2 符号表管理

6．2．1 符号表的内容

6．2．2 符号表的组织

6．2．3 符号表的操作

6．2．4 符号表的实现

6．3 语义分析实现

6．3．1 输入输出

6．3．2 算法框图

7．1 中间代码简介

7．1．1 中间代码的表示形式

7．1．2 中间代码的生成方法

7．2 SNL的中间语言

7．3 SNL的中间代码生成

7．3．1 输入输出

7．3．2 中间代码的构造方法

7．3．3 从语法树生成四元式

7．3．4 相关的应用函数

7．3．5 中间代码生成程序说明

8．1 中间代码优化简介

8．1．1 优化种类介绍

8．1．2 基本块的划分

8．2 常量表达式优化

8．2．1 常量表达式优化的原理

8．2．2 常量表达式节省的实现

8．3 公共表达式节省方法

8．3．1 公共表达式优化原理

8．3．2 公共表达式节省的实现

8．4 循环不变式外提

8．4．1 循环不变式外提的原理

8．4．2 循环外提的实现

9．1 虚拟目标机TM

9．1．1 TM的寄存器和存储器

9．1．2 TM的地址模式和指令集

9．2 编译程序中运行时存储空间管理

9．2．1 存储空间结构

9．2．2 过程活动记录

9．2．3 动态链

9．3 语法树到目标代码的生成

9．3．1 原理

9．3．2 框图

9．4 四元式到目标代码的生成

9．4．1 原理

9．4．2 四元式到目标代码生成中的关键问题

9．4．3 程序框图

10．1 解释程序

10．2 虚拟目标机TM的可执行命令

10．3 解释程序的实现

10．3．1 解释程序的实现框图

11．1 语言的扩充和实现

11．2 实现方法的扩充

11．3 应用自动生成工具

11．4 实现语言

12．1 SNLC概述

12．1．1 SNLC的特色

12．1．2 SNLC的运行环境

12．1．3 SNLC的安装和卸载

12．1．4 SNLC的启动和退出

12．2 SNLC的使用

12．2．1 SNL文件的操作

12．2．2 SNL程序的词法分析

12．2．3 SNL程序的语法分析

12．2．4 SNL程序的语义分析

12．2．5 SNL程序的中间代码生成

12．2．6 SNL程序的优化

12．2．7 SNL程序的目标代码生成

12．2．8 SNL程序的虚拟执行

12．3有关问题的说明

12．3．1 SNLC的维护和出错处理

12．3．2 SNLC的帮助功能

编译程序的设计与实现刘磊金英张晶张荷花单郸编著吉林大学计算机科学与技术学院 2004 年 2 月

简介编译程序是计算机系统不可缺少的部分，是程序设计者的必备工具。学习并掌握编译程序的构造原理和实现技术，能够增强对程序设计语言的理解，提高程序设计、尤其是大型软件的设计能力。本教材以一个简单的具有嵌套过程定义的过程式语言 SNL 作为教学语言，详细介绍了该语言编译程序的设计和实现方法，并且对已经实现的编译程序的源代码分阶段进行了详细的分析，尤其是对编译器程序的组成、实现算法、所用数据结构以及各功能部分所采用的编译技术都作了详细的介绍，并配有相应的框图说明。学生在学习《编译原理》课程的同时，可以配合本教材中编译实例的分析，进一步理解和掌握编译器程序的构造原理和实现方法。此外，通过对本教材中所提供的编译程序源代码的阅读和改进，可以大大地提高程序设计能力。本教材是一本难得的编译程序实例分析和教学辅导教材。 1

目录前言................................................................................................................................. 1 第一章编译原理概述 1．1 高级程序设计语言的实现................................................................................. 1 1．2 编译程序的组成................................................................................................. 2 1．3 编译程序的实现................................................................................................. 4 1．4 其他相关程序..................................................................................................... 5 第二章 SNL 语言介绍 2．1 SNL语言的特点 ................................................................................................. 6 2．2 SNL语言的词法 ................................................................................................. 6 2．2．1 语言的字符表.................................................................................. 6 2．2．2 单词的巴科斯范式.......................................................................... 6 2．3 SNL语言的语法 ................................................................................................. 7 2．3．1 语法的非形式说明.......................................................................... 7 2．3．2 语法的形式定义.............................................................................. 8 2．4 SNL语言的语义 ............................................................................................... 13 第三章 SNL 语言的编译程序简介 3．1 SNL编译程序功能结构 ................................................................................... 14 3．2 SNL编译器的开发环境 ................................................................................... 16 3．3 SNL编译器程序包 ........................................................................................... 16 3．4 SNL编译器的主程序说明 ............................................................................... 25 第四章 SNL 语言的词法分析 4．1 词法分析简介................................................................................................... 31 4．1．1 单词的分类.................................................................................... 31 4．1．2 单词的Token表示.......................................................................... 32 4．1．3 词法分析程序和语法分析程序的接口 ........................................ 32 4．2 DFA的构造和实现 ........................................................................................... 33 4．2．1 状态转换图.................................................................................... 33 4．2．2 状态转换图的实现........................................................................ 36 4．3 词法分析程序的实现....................................................................................... 38 2

4．3．1 词法分析程序的输入输出............................................................ 38 4．3．2 实现词法分析器的注意事项 ........................................................ 39 4．3．3 词法分析程序的实现框图............................................................ 40 4．4 词法分析程序的自动生成器........................................................................... 44 4．4．1 LEX/FLEX简介 .............................................................................. 44 4．4．2 LEX运行与应用过程 ..................................................................... 44 4．4．3 LEX源程序结构 ............................................................................. 45 4．4．4 应用LEX构造词法分析程序 ........................................................ 47 第五章 SNL 语言的语法分析 5．1 语法分析概述................................................................................................... 52 5．1．1 上下文无关文法............................................................................. 52 5．1．2 语法分析方法的分类..................................................................... 54 5．1．3 三个重要集合................................................................................. 54 5．1．4 SNL 语言的Predict集 .................................................................... 55 5．2 语法分析程序的实现....................................................................................... 57 5．2．1 语法分析程序的输入与输出 ......................................................... 57 5．2．2 语法树节点的数据结构 ................................................................. 58 5．3 递归下降法的实现........................................................................................... 63 5．3．1 递归下降法基本原理..................................................................... 63 5．3．2 递归下降法应满足的条件 ............................................................. 63 5．3．3 递归下降法的语法分析程序框图 ................................................. 64 5．4 LL(1)语法分析方法的实现 ........................................................................... 107 5．4．1 LL(1)语法分析方法的基本原理.................................................. 107 5．4．2 SNL语言的LL(1)语法分析概述.................................................. 108 5．4．3 LL(1)语法分析程序框图 ............................................................. 108 5．5 语法分析程序的自动生成器......................................................................... 143 5．5．1 YACC/Bison.................................................................................. 143 5．5．2 ACCENT....................................................................................... 148 第六章符号表管理与语义分析 6．1 语义分析概述................................................................................................... 154 6．2 符号表管理..................................................................................................... 154 6．2．1 符号表的内容.............................................................................. 155 6．2．2 符号表的组织.............................................................................. 159 6．2．3 符号表的操作.............................................................................. 161 6．2．4 符号表的实现.............................................................................. 161 6．3 语义分析实现................................................................................................. 163 6．3．1 输入输出....................................................................................... 164 3

6．3．2 算法框图....................................................................................... 164 第七章中间代码生成 7．1 中间代码简介................................................................................................. 177 7．1．1 中间代码的表示形式................................................................... 178 7．1．2 中间代码的生成方法................................................................... 179 7．2 SNL的中间语言 ............................................................................................. 179 7．3 SNL的中间代码生成 ..................................................................................... 182 7．3．1 输入输出....................................................................................... 182 7．3．2 中间代码的构造方法................................................................... 182 7．3．3 从语法树生成四元式................................................................... 186 7．3．4 相关的应用函数........................................................................... 187 7．3．5 中间代码生成程序说明 ............................................................... 189 第八章中间代码优化 8．1 中间代码优化简介......................................................................................... 199 8．1．1 优化种类介绍............................................................................... 199 8．1．2 基本块的划分............................................................................... 200 8．2 常量表达式优化............................................................................................. 201 8．2．1 常量表达式优化的原理 ............................................................... 201 8．2．2 常量表达式节省的实现 ............................................................... 202 8．3 公共表达式节省方法..................................................................................... 207 8．3．1 公共表达式优化原理................................................................... 207 8．3．2 公共表达式节省的实现 ............................................................... 209 8．4 循环不变式外提............................................................................................. 216 8．4．1 循环不变式外提的原理 ............................................................... 217 8．4．2 循环外提的实现........................................................................... 220 第九章 SNL 语言的目标代码生成 9．1 虚拟目标机TM............................................................................................... 226 9．1．1 TM的寄存器和存储器................................................................. 226 9．1．2 TM的地址模式和指令集............................................................. 227 9．2 编译程序中运行时存储空间管理................................................................. 228 9．2．1 存储空间结构............................................................................... 228 9．2．2 过程活动记录............................................................................... 229 9．2．3 动态链........................................................................................... 231 9．3 语法树到目标代码的生成............................................................................. 232 9．3．1 原理............................................................................................... 232 4

9．3．2 框图............................................................................................... 236 9．4 四元式到目标代码的生成............................................................................. 246 9．4．1 原理............................................................................................... 246 9．4．2 四元式到目标代码生成中的关键问题 ....................................... 251 9．4．3 程序框图....................................................................................... 252 第十章虚拟目标代码的解释程序 10．1 解释程序....................................................................................................... 264 10．2 虚拟目标机TM的可执行命令..................................................................... 264 10．3 解释程序的实现........................................................................................... 265 10．3．1 解释程序的实现框图................................................................. 265 第十一章总结 11．1 语言的扩充和实现......................................................................................... 274 11．2 实现方法的扩充............................................................................................. 274 11．3 应用自动生成工具......................................................................................... 274 11．4 实现语言......................................................................................................... 275 第十二章 SNLC(SNL Compiler)软件使用指南 12．1 SNLC概述........................................................................................................ 276 12．1．1 SNLC的特色.................................................................................. 276 12．1．2 SNLC的运行环境.......................................................................... 276 12．1．3 SNLC的安装和卸载...................................................................... 276 12．1．4 SNLC的启动和退出...................................................................... 279 12．2 SNLC的使用.................................................................................................... 279 12．2．1 SNL文件的操作 ............................................................................ 280 12．2．2 SNL程序的词法分析 .................................................................... 281 12．2．3 SNL程序的语法分析 .................................................................... 281 12．2．4 SNL程序的语义分析 .................................................................... 282 12．2．5 SNL程序的中间代码生成 ............................................................ 283 12．2．6 SNL程序的优化 ............................................................................ 285 12．2．7 SNL程序的目标代码生成 ............................................................ 287 12．2．8 SNL程序的虚拟执行 .................................................................... 288 12．3 有关问题的说明.............................................................................................. 291 12．3．1 SNLC的维护和出错处理.............................................................. 291 12．3．2 SNLC的帮助功能.......................................................................... 291 参考文献………………………………………………………………………………..292 5

前言前言编译原理课程是计算机科学与技术专业最为重要的专业课之一，掌握编译方法和技术是每一个优秀计算机软件专业人员的必备素质。对于计算机专业的学生来说，也许将来只有少部分人从事专业开发编译程序、维护编译程序的工作，但学好这门课程是十分重要的，体现在： 1．学好编译课程可以加深对程序设计语言的理解，因为设计一个编译程序，需要准确认识程序语言的语法和语义，了解目标机及目标代码的结构，这些知识对于学习新的程序设计语言是非常有帮助的。 2．因为编译程序本身是一个十分庞大而复杂的系统软件，涉及到许多复杂的数据结构和实现算法，若能系统全面的掌握编译技术，必将大大提高程序设计能力，特别是开发大型软件的能力。 3．编译技术可以应用于许多实际的软件开发工作中，如软件开发平台、软件自动生成、模式匹配等许多方面。 4．编译课程的学习可以培养学生的抽象思维能力，掌握形式化描述技术，这种思想和方法可能对今后从事的软件开发工作产生深远的影响。 5．编译程序是一种元级程序，即它处理的对象就是程序，因此学习编译原理和实现技术，对于我们掌握元级程序设计方法十分有帮助。许多学过编译原理课程的同学都会感到有些困惑：首先觉得编译课程难度较大，不易掌握；其次虽然掌握了编译的各个阶段的技术，但缺乏对编译程序的总体理解，各部分之间难以衔接。针对这种情况，我们编写了本教材。本教材设计了简单的具有嵌套过程的程序设计语言 SNL(Small Nested Language)。该语言具有标准数据类型和结构数据类型，可以嵌套定义过程，过程的参数可以分为值参和变参两种形式，控制语句和 PASCAL 语言基本相同，因此除指针类型外，SNL 语言具备了过程式语言的基本特征，以它作实例语言，构造其编译程序，使得绝大多数编译技术可以在该编译程序中得以体现。本教材介绍了 SNL 语言的编译程序的实现方法，并且对 SNL 编译程序的源代码分阶段进行了详细的分析，尤其是对编译程序的组成、数据结构、所用算法以及各功能部分所采用的编译技术都作了详细介绍，并配有框图说明。学生在学习《编译原理》课程的同时，可以通过本教材中编译实例的分析，进一步理解和掌握编译器程序的构造原理和实现方法，同时，通过对本教材中提供的编译程序源代码的阅读和改进，可以大大地提高程序设计能力。本书分为十二章，具体每章的主要内容如下：第一章：简单介绍一下编译程序的构造原理；第二章：介绍本教材使用的类 PASCAL 高级程序设计语言 SNL；第三章：介绍 SNL 编译程序的总体结构和程序的组成； 1

第四章～第九章：分别介绍了 SNL 编译程序的词法分析、语法分析、语义分析、中间代码生成、中间代码优化和目标代码生成部分的实现原理、具体的程序说明以及源程序清单；第十章：介绍了 SNL 编译程序的虚拟目标代码的解释程序的实现方法；第十一章：总结了前面介绍的 SNL 编译程序，并指出了可以改进的方面和一些其它的应用实例；前言第十二章：介绍了 SNL 编译器系统 SNLC(Small Nested Language’s Compiler)的简明使用手册，以方便读者更好地使用 SNL 的编译器系统。本书是作者根据多年教学实践经验总结而成，已在计算机科学与技术专业本科生教学中使用多次，效果良好。北京工业大学计算机学院蒋宗礼教授认真审阅了本书的全部初稿，并提出了很多中肯的修改意见，吉林大学计算机学院金成植教授在本书的成书过程中也给予了多方面的指导。此外，吉林大学计算机学院软件自动化实验室的教师、博士生和研究生的帮助和建议也对本书的出版起了积极的作用。在此，作者向所有对本书编写工作给予支持和帮助的人表示衷心的感谢。由于编者水平有限，时间匆忙，肯定会有不少缺点和不足，敬请读者多提宝贵意见，以便在适当的时间再作修订补充。 2

分享到：

赞收藏

资料库

编译程序的设计与实现.pdf

相关推荐

课程资源

热门标签

最新资料