本书结合对现代编译器设计理论的详细研究,精心设计了若干个实验,每个实验都使用C语言编写完成,并配有大量的练习,使读者可以将注意力集中到编程上,真正做到以源代码为核心。读者可以亲自动手完成这些实验,在实践的过程中循序渐进地学习编译原理的理论知识,进而加深对编译原理的理解,掌握理论知识在实际中的应用情况,从而将理论知识统一起来。本书还完整描述了一个可运行的小规模语言编译器(包括源代码)。
全书包含12个实验,是一本真正能够引导读者动手实践的书。本书可作为高等院校编译原理课程的实践教材,也可作为各类程序开发者、爱好者的阅读参考书。
本书结合对现代编译器设计理论的详细研究,精心设计了若干个实验,每个实验都使用C语言编写完成,并配有大量的练习,使读者可以将注意力集中到编程上,真正做到以源代码为核心。
纸上得来终觉浅,绝知此事要躬行。陆游
本书特点众所周知,编译原理是计算机知识领域中一个核心的组成部分,也是高校计算机科学专业学生的重要基础课。同时,编译原理也是一门实践性很强的课程。本书通过引导读者动手进行相应的实验,进而达到使读者深刻理解编译原理的目的。本书非常适合于编译原理的初学者使用,能够帮助初学者进行高质量的编译系统实验。本书精心设计了若干个实验题目,使读者可以逐步地接触到一个实际编译系统的源代码。本书还配置了一个集成度很高的实验环境CP Lab,在这个集成实验环境中,读者可以非常轻松地编辑、编译和调试源代码,从而读者可以将有限的精力放在学习编译原理上,而不是如何构建实验环境,或者使用各种工具上。本书会一步一步地带动读者通过动手实践的方式来分析和编写可以实际工作的源代码,进而理解编译原理。现代编译系统已经变得越来越复杂,虽然本书中的编译系统是专为教学而设计,相对于一些商用编译系统已经非常简化,但是相信本书的很多读者都是第一次接触到这样规模的源代码。本书在编写时充分考虑到了这个问题,并做了一些有益的尝试。为了方便读者理解,编译系统的源代码进行了很多简化,各个模块间的耦合性被设计得尽量小,这样读者在学习某个模块时就更容易集中精力。在本书的各个实验之间也会存在一些交叉的或者重复的内容,有时还会提示读者回到之前的实验学习相关的内容,这种螺旋式的学习方法可以帮助读者从整体上理解编译原理。本书另外一个着重点就是要让读者真正动手实践。只有通过亲身实践学习到的知识才能够真正被掌握,而那些仅仅从书本上得到的知识更容易被忘记。本书为了让读者在动手实践的过程中达到做中学的目的,精心设计了12个配套实验,可以覆盖编译原理知识领域中所有重要的模块和知识点。本书配套的实验按照由易到难,循序渐进的原则进行设计。前面的若干个实验以验证型练习为主,后面的若干个实验会添加适当的设计型和综合型练习。在单个实验内容的安排上,一般会首先带领读者阅读并调试相关模块的源代码,并结合相应的编译原理进行分析。待读者对源代码和系统原理熟悉后,再安排读者对已有代码进行适当改写,或者编写新的代码。在每个实验的最后还会提编译原理实验教程前言供一些思考与练习的题目,感兴趣的读者可以完成这些题目,从而进一步提高动手实践能力和创新能力。此外,考虑到在实际工作中,如果一位刚参加工作的程序员参与到一个项目的开发中,项目负责人一定会让他首先阅读项目已有的代码,并在已有代码的基础上进行一些小的修改,待他工作一段时间后,对项目有较深入的理解,才能在项目中添加一些复杂的、创新的功能。读者按照本书提供的实验进行实践的过程,与上述过程是完全一致的,这也是本书实验设计的目的之一。研究表明,图示具有直观、简洁、易于说明事物的客观现状或事件的发展过程的特点。在对某一事物或事件进行描述时, 图示往往比文字更容易被读者理解和接受。所以,本书不遗余力地使用各种图示或者表格,力求将枯燥、复杂的编译原理,以更直观的方式展现在读者的面前。而且,本书在适当的地方会从源代码中引用一些关键的代码片段,并结合编译原理对这些代码片段进行详细讲解,让读者有一种身临其境的真实感。阅读源代码的建议接下来为读者阅读源代码提供一些有益的建议,希望能够帮助读者更顺利地阅读源代码。首先,读者应该明确阅读源代码的目的,或者说通过阅读源代码,读者能够学到哪些有用的知识,对读者参加实际工作会有哪些帮助。最重要的目的当然是理解编译系统的原理,源代码能够帮助读者将书本上枯燥的理论实例化。虽然读者亲自动手开发一个商业编译系统的可能性很小,但是编译系统所使用的许多思想在计算机科学的各个领域有广泛的适用性,学习系统的内部设计理念对于算法设计和实现、构建虚拟环境、网络管理等其他多个领域也非常有用。而且,源代码是精心编写的高质量源代码,无论是代码的组织结构还是代码的编写风格,都是按照商业级的规格来完成的,这些在读者的实际工作中都会有很大的借鉴意义。此外,本书由于篇幅的限制,不可能涉及系统的所有内容,幸好源代码就是最完全、最准确的文档,读者通过学习源代码,能够获得几倍于本书内容的知识。其次,读者在开始阅读源代码之前,还应该完成一些准备工作。源代码主要使用C语言编写,定义较多的数据结构,并尽量使用常用的、简单的算法来操作这些数据结构,所以读者需要有比较扎实的C语言程序设计、数据结构和算法的相关知识。在阅读源代码时应该使用一些正确的方法,从而达到事半功倍的效果。已经有专门的书籍详细介绍阅读源代码的方法,本书由于篇幅的限制,在这里只能为读者列举一些快速而有效的方法。 应该首先搞清楚源代码的组织方式,例如都包含哪些源代码文件,这些源代码文件是如何组织在不同的文件夹中的。这对于读者快速地了解结构有很大帮助。 重视数据结构。要搞清楚数据结构中各个域的意义,以及使用这些数据结构定义了哪些重要的变量(特别是全局变量)。系统的大部分函数都是在操作由这些数据结构所定义的变量,要搞清楚函数对这些变量进行的操作会产生怎样的结果。 分析函数的层次和调用关系。要特别注意哪些函数是全局函数,哪些函数是模块内部使用的函数。 本书对于特别简单或者特别复杂的函数会一语带过,读者也可以在搞清楚这些函数功能的基础上暂时跳过它们,从而将有限的时间和精力用于学习本书详细介绍的重要函数。 重视阅读源代码文件中的注释,必要的情况下可以根据自己的理解添加一些注释。 使用工具提高阅读源代码的效率。 每当阅读完一部分源代码后,应该认真思考一下,大胆地提出一些问题,例如为什么要这样编写?可以不可以用别的方法来编写?也可以试着向别人介绍自己正在阅读的源代码,或者将自己的心得发布到互联网上。以某种方式表达自己思想的过程,其实就是重新梳理自己知识的过程,这样能够让读者的知识更加系统化,并且有可能发现被忽略掉的细节。 读者除了可以完成本书配套的实验之外,还可以自己设计一些小实验,例如进行一些修改或者添加一些功能来验证读者的想法。参与讨论读者可以使用下面的链接登录本书配套的论坛。论坛中有和读者一样对编译原理感兴趣的网友,有本书的编者,还有CP Lab的开发者。读者在这里提出的问题可以获得及时准确的解答,提出的意见和建议也可以在本书的下一版中获得虚心的接纳。如果本书有勘误信息或者更新的章节内容,也会在第一时间发布到论坛上。可以说,有一个高效的团队在为本书的读者服务,读者在使用本书学习的过程中可以获得持续的支持。http://www.engintime.com/forum/本书由哈尔滨工程大学刘刚、北京英真时代科技有限公司赵鹏翀编著,参编人员包括北京英真时代科技有限公司刘建成等。全书由刘刚进行统稿。本书在撰写过程中参阅了大量的文献及资料,特此对这些作者表示诚挚的敬意。编译技术的发展日新月异,新的技术也不断出现。由于时间仓促及作者视野的限制,书中难免出现疏漏及不当之处,敬请广大读者批评指正。
编者2017年1月
目录
CP Lab简介1
实验1实验环境的使用3
实验2NFA到DFA26
实验3使用Lex自动生成扫描程序48
实验4消除左递归(无替换)62
实验5消除左递归(有替换)74
实验6提取左因子89
实验7First集合104
实验8Follow集合117
实验9Yacc分析程序生成器132
实验10符号表的构建和使用137
实验11三地址码转换为P\|代码146
实验12GCC编译器案例综合研究156
附录ATINY编译器和TM机167
参考文献225第1章数据结构课程设计概述1
1.1数据结构简介1
1.2课程设计目标和特点2
1.3编写说明3
1.4课程设计实例的标准格式4
第2章线性表的应用6
2.1存储结构与基本运算的算法6
2.2集合的交、并运算15
2.3学生成绩管理18
2.4多项式求导25
2.5约瑟夫环问题30
2.6数据库管理系统34
第3章栈的应用58
3.1存储结构与基本运算的算法58
3.2括号匹配63
3.3汉诺塔问题66
3.4算术表达式求值69
3.5马踏棋盘76
第4章队列的应用82
4.1存储结构与基本运算的算法82
4.2看病排队候诊问题88
4.3数制的转换91
4.4停车场管理99
4.5基数排序107
第5章串的应用114
5.1存储结构与基本运算的算法114
5.2KMP算法118
5.3最长公共子串121
5.4大整数计算器123
编译原理实验教程目录第6章多维数组和广义表的应用130
6.1存储结构与基本运算的算法130
6.2魔方阵139
6.3稀疏矩阵的加法运算143
6.4本科生导师制问题151
第7章树状结构的应用169
7.1存储结构与基本运算的算法169
7.2线索二叉树的创建与遍历172
7.3由遍历确定二叉树175
7.4电文的编码和译码177
7.5家族关系查询系统183
第8章图状结构的应用201
8.1存储结构与基本运算的算法201
8.2地铁建设问题209
8.3安排教学计划214
8.4校园导航218
附录A课程设计实例软件包224
参考文献227