cplab编译原理实验指导.pdf

1 CP LabCP Lab 编译原理实验指导 北京英真时代科技有限公司 ●●●●●●●●●●●●● CP Lab 编译原理实验指导 北京英真时代科技有限公司 2 CP Lab 编译原理实验指导 版本 1.1 北京北京英真时代英真时代科技有限公司科技有限公司 地址: 北京市房山区拱辰大街 98 号 7 层 0825 邮编: 102488 : 010-60357081 : 964515564 邮箱: support@ 网址: CP Lab 编译原理实验指导 北京英真时代科技有限公司 3 目目 录录 CP LAB简介 4 实验 1 实验环境的使用 . 7 实验 2 NFA 到 DFA . 18 实验 3 使用LEX自动生成扫描程序 . 22 实验 4 消除左递归（无替换） . 27 实验 5 消除左递归（有替换） . 31 实验 6 提取左因子 . 36 实验 7 FIRST 集合 . 40 实验 8 FOLLOW 集合 44 实验 9 YACC分析程序生成器 49 实验 10 符号表的构建和使用 . 52 实验 11 三地址码转换为P-代码 . 55 实验 12 GCC编译器案例综合研究 . 59 附录 TINY编译器和TM机 . 67 CP Lab 编译原理实验指导 北京英真时代科技有限公司 4 CPCP LabLab 简介简介 获得人生中的成功需要的专注与坚持不懈多过天才与机会。

——C.W.C.W.WendteWendte 一、一、概述概述 CP Lab 是一款专用于高等院校编译原理实验教学的集成环境，具有可视化程度高、操作简便、扩展性 强等特点CP Lab 主要由两部分组成：  一个功能强大的 IDE 环境  一套精心设计的编译原理实验题目和配套源代码 CP Lab 所提供的 IDE 环境可以在 Windows 操作系统上快速安装、卸载，其用户界面和操作方式与 Microsoft Visual Studio 完全类似，有经验的读者可以迅速掌握其基本用法该 IDE 环境提供的强大功 能可以帮助读者顺利的完成编译原理实验， 主要功能包括对实验源代码的演示功能、 编辑功能、 编译功能、 调试功能和验证功能 CP Lab 提供了一套精心设计的编译原理实验题目和配套源代码实验题目涵盖了从词法分析、语法分 析、语义分析、代码生成等所有重要的编译原理和算法完成这些实验题目后，读者可以学习到通过手工 编码是如何一步步实现一个编译器的，还可以使用 Lex、Yacc 工具完成简单的词法分析程序和语法分析程 序，甚至还可以深入分析一个小型的开源编译器的实现方法所有的源代码文件都使用 C 语言编写，可以 与主流编译原理教材配套使用。

这些源代码以模块化的方式进行组织， 并配有完善的中文注释， 可读性好， 完全符合商业级的编码规范 使用 CP Lab 进行编译原理实验的过程可以参见图 0-1 图图 0 0-1 1：：使用使用 CPCP LabLab 进行进行编译原理编译原理实验实验 CP Lab 编译原理实验指导 北京英真时代科技有限公司 5 二二、、实验题目清单实验题目清单 下面的实验题目适合在学习编译原理课程的过程中逐个完成 序号 概念 实验名称 难度 学时 1 词法分析 实验环境的使用（正则表达式到 NFA） ★★ 2 2 NFA 到 DFA ★★★★ 4 3 使用 Lex 自动生成扫描程序 ★★ 2 4 自顶向下的 语法分析 消除左递归（无替换） ★★★ 2 5 消除左递归（有替换） ★★★★ 4 6 提取左因子 ★★★ 2 7 First 集合 ★★ 2 8 Follow 集合 ★★ 2 9 自底向上的 语法分析 Yacc 分析程序生成器 ★★ 2 10 语义分析 符号表的构建与使用 ★★ 2 11 代码生成 三地址码转换为 P-代码 ★★ 2 12 GCC 编译器案例综合研究 ★★ 2 下面的实验题目适合在学完编译原理课程后，选择一个作为课程设计题目来完成。

序号 课程设计题目要求 1 编写一个程序，可以根据输入的正则表达式生成 NFA，然后将 NFA 转 换为最小化的 DFA，最后使用得到的 DFA 完成字符串匹配 2 参考 Lex 生成 TINY 语言扫描程序的过程，使用 Lex 为 C-Minus 语言生 成一个扫描程序 3 编写一个程序，可以为输入的 BNF 消除左递归或提取左因子，然后根据 BNF 计算出 First 集合和 Follow 集合，从而构造一个 LL(1)分析表，最 终实现一个表驱动的 LL(1)分析算法 4 参考 Yacc 生成 TINY 语言语法分析程序的过程， 使用 Yacc 为 C-Minus 语言生成一个语法分析程序 5 根据表达式的 BNF，使用 Yacc 输出表达式的 Modula-2 转换式 6 编写一个程序，可将输入的三地址码转换为 P-代码，还可将输入的 P-代码转换为三地址码 CP Lab 编译原理实验指导 北京英真时代科技有限公司 6 三三、、开始使用开始使用 读者迅速掌握 CP Lab 的基本使用方法，是顺利完成编译原理实验的重要前提虽然 CP Lab 提供了非 常人性化的操作界面，而且读者只需要掌握很少的几个核心功能，就可以顺利完成实验。

但是，为了达到 “做中学”的目的，在向读者介绍 CP Lab 的核心功能时，不会使用堆砌大量枯燥文字的方法，而是在后面 的“实验 1”中，引导读者在使用 CP Lab 的过程中逐步掌握其基本使用方法，这样达到的效果最好 CP Lab 编译原理实验指导 北京英真时代科技有限公司 7 实验实验 1 实验环境的使用实验环境的使用 实验实验难度难度：：★★ 建议学时：建议学时：2 学时 一、实验目的一、实验目的  熟悉编译原理集成实验环境 CP Lab 的基本使用方法  掌握正则表达式和 NFA 的含义  实现正则表达式到 NFA 的转换 二二、、预备知识预备知识  在这个实验中 NFA 状态结构体使用了类似于二叉树的数据结构，还包括了单链表插入操作以及栈 的一些基本操作如果读者对这一部分知识有遗忘，可以复习一下数据结构中的相关内容  实验中需要把正则表达式转换为 NFA，所以要对正则表达式和 NFA（非确定有穷自动机）有初步 的理解读者可以参考配套的《编译原理》教材，预习这一部分内容 三三、实验内容、实验内容 请读者按照下面的步骤完成实验内容，同时，仔细体会 CP Lab 的基本使用方法。

在本实验题目中， 操作步骤会编写的尽量详细，并会对 CP Lab 的核心功能进行具体说明但是，在后面的实验题目中会尽 量省略这些内容， 而将重点放在实验相关的源代码上 如有必要， 读者可以回到本实验题目中， 参考 CP Lab 的基本使用方法 3 3.1 .1 启动启动 CP LabCP Lab 在安装有 CP Lab 的计算机上，可以使用两种不同的方法来启动 CP Lab：  在桌面上双击“Engintime CP Lab”图标 或者  点击“开始”菜单，在“程序”中的“Engintime CP Lab”中选择“Engintime CP Lab” 3 3.2 .2 用户注册用户注册 CP Lab 每次启动后都会弹出一个“用户信息”对话框在此对话框中填入“学号”和“姓名”后，点 击“确定”按钮完成本次注册 提示提示：：完成注册后，CP Lab 便会开始记录实验数据，这些数据可能会作为实验课的考评依据，所以请 认真填写学号和姓名，并保证学号和姓名的一致性 3 3.3 .3 主主窗口布局窗口布局 CP Lab 的主窗口布局由下面的若干元素组成：  顶部的菜单栏、工具栏  停靠在左侧和底部的各种工具窗口。

 余下的区域用来放置“起始页”和“源代码编辑器”窗口 提示：提示：菜单栏、工具栏和各种工具窗口的位置可以随意拖动如果想恢复窗口的默认布局，选择“窗 口”菜单中的“重置窗口布局”即可 3 3. .4 4 新建新建实验实验项目项目 新建一个实验项目的步骤如下： 1. 在“文件”菜单中选择“新建”，然后单击“项目”，打开“新建项目”对话框 2. 在“新建项目”对话框中，选择项目模板“001 正则表达式到 NFA”注意，其他模板会在后面 CP Lab 编译原理实验指导 北京英真时代科技有限公司 8 的实验题目中使用 3. 在“名称”中输入新项目使用的文件夹名称“lab1” 4. 在“位置”中输入新项目保存在磁盘上的位置“C:\cplab” 5. 点击“确定”按钮 新建完毕后， CP Lab 会自动打开这个新建的项目在“项目管理器”窗口中（如图 1-1 所示） ，根 节点是项目节点，各个子节点是项目包含的文件夹或者文件读者也可以使用“Windows 资源管理器”打 开磁盘上的“C:\cplab\lab1”文件夹，查看项目中包含的源代码文件 提示提示：：右键点击“项目管理器”窗口中的项目节点，选择快捷菜单中的“打开所在的文件夹” ，即可 使用“Windows 资源管理器”打开项目所在的文件夹。

图图 1 1- -1 1：打开项目后的“项目：打开项目后的“项目管理器”窗口管理器”窗口 3 3.5 .5 阅读实验源代码阅读实验源代码 该实验包含了三个头文件“RegexpToNFA.h” 、 “RegexpToPost.h” 、 “NFAFragmentStack.h”和三个 C 源文件“main.c” 、 “RegexpToPost.c” 、 “NFAFragmentStack.c” 下面对这些文件的主要内容、结构和作 用进行说明： main.cmain.c 文件文件 在“项目管理器”窗口中双击“main.c”打开此文件此文件主要包含了以下内容： 1. 在 文 件 的 开 始 位 置 ， 使 用 预 处 理 命 令 包 含 了 RegexpToNFA.h 、 RegexpToPost.h 和 NFAFragmentStack.h 文件 2. 定义了 main 函数在其中实现了栈的初始化然后，调用了 re2post 函数，将正则表达式转换 到解析树的后序序列最后，调用 post2nfa 函数，将解析树的后序序列转换到 NFA 3. 在 main 函数的后面，定义了函数 CreateNFAState 和 MakeNFAFragment，这两个函数分别是用来 创建一个新的 NFA 状态和构造一个新的 Fragment。

接着定义了函数 post2nfa，关于此函数的功 能、参数和返回值，可以参见其注释在这个函数中用‘$’表示空转换，此函数的函数体还不 完整，留给读者完成 RegexpToPostRegexpToPost.c.c 文件文件 在“项目管理器”窗口中双击“RegexpToNFA.c”打开此文件此文件主要包含了以下内容： 1. 在文件的开始位置，使用预处理命令包含了 RegexpToPost.h 文件 2. 定义了 re2post 函数，此函数主要功能是将正则表达式转换成为解析树的后序序列形式 NFAFragmentStackNFAFragmentStack.c.c 文件文件 在“项目管理器”窗口中双击“NFAFragmentStack.c”打开此文件此文件主要包含了以下内容： 1. 在文件的开始位置，使用预处理命令包含了 NFAFragmentStack.。