编译原理实验教程

本书结合对现代编译器设计理论的详细研究，精心设计了若干个实验，每个实验都使用C语言编写完成，并配有大量的练习，使读者可以将注意力集中到编程上，真正做到“以源代码为核心”。 

本书结合对现代编译器设计理论的详细研究，精心设计了若干个实验，每个实验都使用C语言编写完成，并配有大量的练习，使读者可以将注意力集中到编程上，真正做到“以源代码为核心”。读者可以亲自动手完成这些实验，在实践的过程中循序渐进地学习编译原理的理论知识，进而加深对编译原理的理解，掌握理论知识在实际中的应用情况，从而将理论知识统一起来。本书还完整描述了一个可运行的小规模语言编译器(包括源代码)。
全书包含12个实验，是一本真正能够引导读者动手实践的书。本书可作为高等院校“编译原理”课程的实践教材，也可作为各类程序开发者、爱好者的阅读参考书。

目录

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

纸上得来终觉浅，绝知此事要躬行。——陆游

本书特点众所周知，编译原理是计算机知识领域中一个核心的组成部分，也是高校计算机科学专业学生的重要基础课。同时，编译原理也是一门实践性很强的课程。本书通过引导读者动手进行相应的实验，进而达到使读者深刻理解编译原理的目的。本书非常适合于编译原理的初学者使用，能够帮助初学者进行高质量的编译系统实验。本书精心设计了若干个实验题目，使读者可以逐步地接触到一个实际编译系统的源代码。本书还配置了一个集成度很高的实验环境——CP Lab，在这个集成实验环境中，读者可以非常轻松地编辑、编译和调试源代码，从而读者可以将有限的精力放在学习编译原理上，而不是如何构建实验环境，或者使用各种工具上。本书会一步一步地带动读者通过动手实践的方式来分析和编写可以实际工作的源代码，进而理解编译原理。现代编译系统已经变得越来越复杂，虽然本书中的编译系统是专为教学而设计，相对于一些商用编译系统已经非常简化，但是相信本书的很多读者都是次接触到这样规模的源代码。本书在编写时充分考虑到了这个问题，并做了一些有益的尝试。为了方便读者理解，编译系统的源代码进行了很多简化，各个模块间的耦合性被设计得尽量小，这样读者在学*个模块时就更容易集中精力。在本书的各个实验之间也会存在一些交叉的或者重复的内容，有时还会提示读者回到之前的实验学习相关的内容，这种“螺旋式”的学习方法可以帮助读者从整体上理解编译原理。本书另外一个着重点就是要让读者真正动手实践。只有通过亲身实践学习到的知识才能够真正被掌握，而那些仅仅从书本上得到的知识更容易被忘记。本书为了让读者在动手实践的过程中达到“做中学”的目的，精心设计了12个配套实验，可以覆盖编译原理知识领域中所有重要的模块和知识点。本书配套的实验按照“由易到难，循序渐进”的原则进行设计。前面的若干个实验以“验证型”练习为主，后面的若干个实验会添加适当的“设计型”和“综合型”练习。在单个实验内容的安排上，一般会首先带领读者阅读并调试相关模块的源代码，并结合相应的编译原理进行分析。待读者对源代码和系统原理熟悉后，再安排读者对已有代码进行适当改写，或者编写新的代码。在每个实验的后还会提编译原理实验教程前言供一些“思考与练习”的题目，感兴趣的读者可以完成这些题目，从而进一步提高动手实践能力和创新能力。此外，考虑到在实际工作中，如果一位刚参加工作的程序员参与到一个项目的开发中，项目负责人一定会让他首先阅读项目已有的代码，并在已有代码的基础上进行一些小的修改，待他工作一段时间后，对项目有较深入的理解，才能在项目中添加一些复杂的、创新的功能。读者按照本书提供的实验进行实践的过程，与上述过程是完全一致的，这也是本书实验设计的目的之一。研究表明，图示具有直观、简洁、易于说明事物的客观现状或事件的发展过程的特点。在对某一事物或事件进行描述时, 图示往往比文字更容易被读者理解和接受。所以，本书不遗余力地使用各种图示或者表格，力求将枯燥、复杂的编译原理，以更直观的方式展现在读者的面前。而且，本书在适当的地方会从源代码中引用一些关键的代码片段，并结合编译原理对这些代码片段进行详细讲解，让读者有一种身临其境的真实感。阅读源代码的建议接下来为读者阅读源代码提供一些有益的建议，希望能够帮助读者更顺利地阅读源代码。首先，读者应该明确阅读源代码的目的，或者说通过阅读源代码，读者能够学到哪些有用的知识，对读者参加实际工作会有哪些帮助。重要的目的当然是理解编译系统的原理，源代码能够帮助读者将书本上枯燥的理论实例化。虽然读者亲自动手开发一个商业编译系统的可能性很小，但是编译系统所使用的许多思想在计算机科学的各个领域有广泛的适用性，学习系统的内部设计理念对于算法设计和实现、构建虚拟环境、网络管理等其他多个领域也非常有用。而且，源代码是精心编写的高质量源代码，无论是代码的组织结构还是代码的编写风格，都是按照商业级的规格来完成的，这些在读者的实际工作中都会有很大的借鉴意义。此外，本书由于篇幅的限制，不可能涉及系统的所有内容，幸好源代码就是完全、准确的文档，读者通过学习源代码，能够获得几倍于本书内容的知识。其次，读者在开始阅读源代码之前，还应该完成一些准备工作。源代码主要使用C语言编写，定义较多的数据结构，并尽量使用常用的、简单的算法来操作这些数据结构，所以读者需要有比较扎实的C语言程序设计、数据结构和算法的相关知识。在阅读源代码时应该使用一些正确的方法，从而达到事半功倍的效果。已经有专门的书籍详细介绍阅读源代码的方法，本书由于篇幅的限制，在这里只能为读者列举一些快速而有效的方法。 应该首先搞清楚源代码的组织方式，例如都包含哪些源代码文件，这些源代码文件是如何组织在不同的文件夹中的。这对于读者快速地了解结构有很大帮助。 重视数据结构。要搞清楚数据结构中各个域的意义，以及使用这些数据结构定义了哪些重要的变量（特别是全局变量）。系统的大部分函数都是在操作由这些数据结构所定义的变量，要搞清楚函数对这些变量进行的操作会产生怎样的结果。 分析函数的层次和调用关系。要特别注意哪些函数是全局函数，哪些函数是模块内部使用的函数。 本书对于特别简单或者特别复杂的函数会一语带过，读者也可以在搞清楚这些函数功能的基础上暂时跳过它们，从而将有限的时间和精力用于学习本书详细介绍的重要函数。 重视阅读源代码文件中的注释，必要的情况下可以根据自己的理解添加一些注释。 使用工具提高阅读源代码的效率。 每当阅读完一部分源代码后，应该认真思考一下，大胆地提出一些问题，例如“为什么要这样编写？可以不可以用别的方法来编写？”也可以试着向别人介绍自己正在阅读的源代码，或者将自己的心得发布到互联网上。以某种方式表达自己思想的过程，其实就是重新梳理自己知识的过程，这样能够让读者的知识更加系统化，并且有可能发现被忽略掉的细节。 读者除了可以完成本书配套的实验之外，还可以自己设计一些小实验，例如进行一些修改或者添加一些功能来验证读者的想法。参与讨论读者可以使用下面的链接登录本书配套的论坛。论坛中有和读者一样对编译原理感兴趣的网友，有本书的编者，还有CP Lab的开发者。读者在这里提出的问题可以获得及时准确的解答，提出的意见和建议也可以在本书的下一版中获得虚心的接纳。如果本书有勘误信息或者更新的章节内容，也会在时间发布到论坛上。可以说，有一个高效的团队在为本书的读者服务，读者在使用本书学习的过程中可以获得持续的支持。http://www.engintime.com/forum/本书由哈尔滨工程大学刘刚、北京英真时代科技有限公司赵鹏翀编著，参编人员包括北京英真时代科技有限公司刘建成等。全书由刘刚进行统稿。本书在撰写过程中参阅了大量的文献及资料，特此对这些作者表示诚挚的敬意。编译技术的发展日新月异，新的技术也不断出现。由于时间仓促及作者视野的限制，书中难免出现疏漏及不当之处，敬请广大读者批评指正。
编者2017年1月

评论

实验5实验5消除左递归(有替换)实验难度: ★★★★☆ 建议学时: 4学时一、 实验目的 了解在上下文无关文法中的左递归的概念。 掌握直接左递归、一般左递归的消除算法。二、 预备知识 在这个实验中用到了单链表插入和删除操作。如果读者对这一部分知识有遗忘，可以复习一下数据结构中的相关内容。 理解指针的指针的概念和用法。在这个实验中，指针的指针被用来确定单链表插入和删除的位置，以及用来完成插入和删除的具体操作。 理解左递归和右递归的含义以及左递归的各种形式，如简单直接左递归、普遍的直接左递归、一般的左递归。三、 实验内容〖*2〗3.1准备实验按照下面的步骤准备实验: (1) 启动CP Lab。(2) 在“文件”菜单中选择“新建”|“项目”，打开“新建项目”对话框。(3) 使用模板“005 消除左递归(有替换)”新建一个项目。3.2阅读实验源代码1. RemoveLeftRecursion.h文件(参见源代码清单51)此文件主要定义了与文法相关的数据结构，这些数据结构定义了文法的单链表存储形式。其中，Rule结构体用于定义文法的名称和文法链表；RuleSymbol结构体用于定义文法产生式中的终结符和非终结符。具体内容可参见表5|1和表5|2。表5|1Rule的域说明RuleName文法的名称pFirstSymbol指向文法的个Select的个SymbolpNextRule指向下一条文法编译原理实验教程实验5消除左递归(有替换)表5|2RuleSymbol的域说明pNextSymbol指向下一个SymbolpOther指向下一个SelectisToken是否为终结符。1表示终结符，0表示非终结符TokenName终结符的名称。isToken为1时这个域有效pRule指向Symbol对应的Rule。isToken为0时这个域有效下面是一个简单文法，并使用图5|1和5|2说明了该文法的存储结构: A->Aa|aBB->bB图51Rule和RuleSymbol结构体图例图52简单文法的存储结构

2. main.c文件(参见源代码清单52)此文件定义了main函数。在main函数中首先调用InitRules函数初始化了文法，然后调用PrintRule函数打印消除左递归之前的文法，接着调用RemoveLeftRecursion函数对文法消除左递归，后再次调用PrintRule函数打印消除左递归之后的文法。在main函数的后面定义了一系列函数，有关这些函数的具体内容参见表5|3。关于这些函数的参数和返回值，可以参见其注释。表5|3函数名功 能 说 明SymbolNeedReplace判断当前 Rule 中的一个 Symbol 是否需要被替换。如果 Symbol 是一个非终结符，且 Symbol 对应的Rule 在当前 Rule 之前，就需要被替换。此函数的函数体还不完整，留给读者完成CopySymbol复制一个Symbol。此函数的函数体还不完整，留给读者完成CopySelect复制一个Select。在此函数中可以调用CopySymbol函数，将Select中的Symbol逐个进行复制。此函数的函数体还不完整，留给读者完成ReplaceSelect替换一个 Select的个 Symbol提示:  在调用此函数之前，已经调用了SymbolNeedReplace函数，确保Select的个Symbol需要被替换 Select的个Symbol是一个非终结符，该Symbol对应的Rule就是用于替换该Symbol模板。 当需要复制Select时，可以调用CopySelect函数。此函数的函数体还不完整，留给读者完成FreeSelect释放一个 Select 的内存。此函数的函数体还不完整，留给读者完成RuleHasLeftRecursion判断一条Rule是否存在左递归提示:  只要一条Rule中的一个Select存在左递归，那么这条Rule就存在左递归 如果一个Select的个符号（非终结符）对应的就是此条文法，这个Select就存在左递归此函数的函数体还不完整，留给读者完成AddSymbolToSelect将一个 Symbol 添加到 Select 的末尾。此函数的函数体还不完整，留给读者完成AddSelectToRule将一个 Select 加入到文法末尾，当 Select 为 NULL 时就将一个ε终结符加入到文法末尾。在本程序中ε可以用 $ 来代替。此函数的函数体还不完整，留给读者完成RemoveLeftRecursion对文法消除左递归提示:  在本函数中包含了替换算法，从而可以处理间接左递归的情况。而且由于替换后还可能需要替换，所以设置了一个标识isChange，并初始化为0，每当发生替换之后就将该标识赋值为1，并将此标识作为循环条件，直到没有替换发生时，才能结束替换 在本函数中使用指针的指针pSelectPtr来确定符号在单链表中插入和删除的位置，在进入下一次循环之前应为pSelectPtr设置正确的值 在每处理完一条文法后，会将文法链表的游标指向新文法，这样在继续执行for循环的移动游标操作后，就会跳过这条新文法，从而继续对后面的文法进行消除左递归操作（新文法不包含左递归，所以并不需要对这条文法进行处理）此函数的函数体还不完整，留给读者完成续表函数名功 能 说 明InitRules使用给定的数据初始化文法链表CreateRule创建一个新的RuleCreateSymbo创建一个新的 SymbolFindRule根据RuleName在文法链表中查找名字相同的文法PrintRule输出文法。此函数的函数体还不完整，留给读者完成源代码清单51: RemoveLeftRecursion.h文件#ifndef _REMOVELEFTRECURSION_H_#define _REMOVELEFTRECURSION_H_////在此处包含C 标准库头文件//#include////在此处包含其他头文件//////在此处定义数据结构//#define MAX_STR_LENGTH 64struct _Rule;typedef struct _RuleSymbol{struct _RuleSymbolpNextSymbol;  //指向下一个Symbolstruct _RuleSymbolpOther; //指向下一个Selectint isToken; //是否为终结符。1表示终结符,0表示非终结符char TokenName[MAX_STR_LENGTH]; //终结符的名称。isToken 为1 时这个域有效struct _RulepRule;//指向Symbol 对应的Rule。isToken 为0 时这个域有效}RuleSymbol;typedef struct _Rule{char RuleName[MAX_STR_LENGTH];//文法的名称struct _RuleSymbolpFirstSymbol; //指向文法的个Select 的个Symbolstruct _RulepNextRule;  //指向下一条文法}Rule;////在此处声明函数//RuleInitRules();RuleCreateRule(const charpRuleName);RuleSymbolCreateSymbol();RuleFindRule(RulepHead, const charRuleName);int RuleHasLeftRecursion(RulepRule);void AddSymbolToSelect(RuleSymbolpSelect, RuleSymbolpNewSymbol);void AddSelectToRule(RulepRule, RuleSymbolpNewSelect);RuleSymbolCopySymbol(const RuleSymbolpSymbolTemplate);RuleSymbolCopySelect(const RuleSymbolpSelectTemplate);void FreeSelect(RuleSymbolpSelect);RuleSymbolReplaceSelect(const RuleSymbolpSelectTemplate);void RemoveLeftRecursion(RulepHead);void PrintRule(RulepHead);////在此处声明全局变量//extern const charVoidSymbol;extern const charPostfix;#endif/_REMOVELEFTRECURSION_H_ /源代码清单52: main.c文件#include “RemoveLeftRecursion.h”const charVoidSymbol=”$”;//”ε”const charPostfix=”‘”;int main(int argc, charargv[]){////调用InitRules函数初始化文法//RulepHead=InitRules();////输出消除左递归之前的文法//printf(“Before Remove Left Recursion:\n”);PrintRule(pHead);////调用RemoveLeftRecursion 函数消除文法中的左递归//RemoveLeftRecursion(pHead);////输出消除左递归之后的文法//printf(“\nAfter Remove Left Recursion:\n”);PrintRule(pHead);return 0;}/功能: 判断当前Rule 中的一个Symbol 是否需要被替换。如果Symbol 是一个非终结符,且Symbol 对应的Rule 在当前Rule 之前,就需要被替换。参数: pCurRule–当前Rule 的指针。pSymbol–Symbol 指针。返回值: 需要替换返回1。不需要替换返回0。/int SymbolNeedReplace(const RulepCurRule, const RuleSymbolpSymbol){////TODO: 在此添加代码//}/功能: 复制一个Symbol。参数: pSymbolTemplate–需要被复制的Symbol 指针。返回值: 复制获得的新Symbol 的指针。/RuleSymbolCopySymbol(const RuleSymbolpSymbolTemplate){////TODO: 在此处添加代码//}/功能: 复制一个Select。参数: pSelectTemplate–需要被复制的Select 指针。返回值: 复制获得的新Select 的指针。/RuleSymbolCopySelect(const RuleSymbolpSelectTemplate){////TODO: 在此处添加代码//}/功能: 替换一个Select 的个Symbol。参数: pSelectTemplate–需要被替换的Select 指针。返回值: 替换后获得的新Select 的指针。注意,替换后可能会有一个新的Select,也可能会有多个Select 链接在一起。/RuleSymbolReplaceSelect(const RuleSymbolpSelectTemplate){////TODO: 在此处添加代码//}/功能: 释放一个Select 的内存。参数: pSelect–需要释放的Select 的指针。/void FreeSelect(RuleSymbolpSelect){////TODO: 在此处添加代码//}/功能: 判断一条Rule 是否存在左递归。参数: prRule–Rule 指针。返回值: 存在返回1。不存在返回0。/int RuleHasLeftRecursion(RulepRule){////TODO: 在此处添加代码//}/功能: 将一个Symbol 添加到Select 的末尾。参数: pSelect–Select 指针。pNewSymbol–Symbol 指针。/void AddSymbolToSelect(RuleSymbolpSelect, RuleSymbolpNewSymbol){////TODO: 在此处添加代码//}/功能: 将一个Select加入到文法末尾,当Select为NULL时就将一个ε终结符加入到文法末尾。参数: pRule–文法指针。pNewSelect–Select 指针。/void AddSelectToRule(RulepRule, RuleSymbolpNewSelect){////TODO: 在此处添加代码//}/功能: 消除左递归。参数: pHead–文法链表的头指针。/void RemoveLeftRecursion(RulepHead){RulepRule;//Rule 游标RuleSymbolpSelect; //Select 游标RulepNewRule;  //Rule 指针int isChange;//Rule 是否被替换的标记RuleSymbol pSelectPrePtr; //Symbol 指针的指针////TODO: 在此处添加代码//}/功能: 使用给定的数据初始化文法链表。返回值: Rule指针。/typedef struct _SYMBOL{int isToken;char Name[MAX_STR_LENGTH];}SYMBOL;