《编译原理》实验指导书-最终版

编译方法编译方法 实验指导书 柴本成 赵晨 编写 浙江万里学院 2010 01 目 录 实验一 有限自动机的构造与实现 1 实验二 词法分析器的设计 3 实验三 语法分析 递归下降分析器 5 实验四 LL 1 文法预测分析表的实现 6 附 录 9 附录一 实验结果的提交与检查 9 附录二 实验报告参考格式 9 附录三 Visual C 上机环境简介 10 附录四 参考程序 13 实验一实验一 有限自动机的构造与实现有限自动机的构造与实现 一 实验目的实验目的 1 正确理解正规式和正规集以及有限自动机的定义 2 熟练掌握用状态转换图表示有限自动机的方法 二 实验预习提示实验预习提示 1 正规表达式就是一种形式化的表示法 它可以表示单词符号的结构 从而精确地 定义单词符号集 正规表达式简称为正规式正规式 它表示的集合即为正规集正规集 2 状态转换图是一张当输入不同内容时选择不同分析路径的有向图 一个状态转换 图可用于识别一定的字符串 3 有限自动机 FA 是更一般化的状态转换图 可用来识别正规集 分为 DFA 和 NFA 两种 三 实验内容实验内容 构造识别如下字符串的状态转换图 并将其编程实现 1 识别标识符 以字母开始由字母和数字构成的字符串 要求长度不超过 10 参考程序 include include 字符串处理的头文件 判断一个字符是不是字母 bool Isletter char ch if ch a return false 判断一个字符串是不是标识符 bool IsId char str if Isletter str 0 return false int l strlen str 计算字符串的长度 for int i 1 i l i if Isletter str i IsDigit str i continue 如果是字母或数字就继续循环 elsereturn false 否则 返回不是字符串 return true void main char str 1abc 初始化字符串 也可键盘输入 if IsId str cout accept endl else cout not accept endl 2 识别实数 要求正负号可有可无 长度不超过 20 不要求识别用科学记数法表示的 实数 3 选做 识别实数 包含科学计数法 四 实验要求实验要求 1 编程语言可用 C C 中任意一种 2 自行设计测试数据对程序进行测试 对输入的字符串 以 作为结束符 如果能 识别 则显示 接受 否则 显示 不接受 3 书写实验报告 实验报告的格式可参见附录 实验报告参考格式 实验二实验二 词法分析器的设计词法分析器的设计 一 实验目的实验目的 通过设计编制调试一个具体的词法分析程序 加深对词法分析原理的理解 并掌握在 对程序设计语言源程序进行扫描过程中将其分解为各类单词的词法分析方法 编制一个读单词过程 从输入的源程序中 识别出各个具有独立意义的单词 即基本 保留字 标识符 常数 运算符 分隔符五大类 并依次输出各个单词的内部编码及单词 符号自身值 遇到错误时可显示 Error 然后跳过错误部分继续显示 二 实验预习提示实验预习提示 1 词法分析器的功能和输出格式 词法分析器的功能是输入源程序 输出单词符号 词法分析器的单词符号常常表 示成以下的二元式 单词种别码 单词符号的属性值 本实验中 采用的是一类符号 一种别码的方式 2 单词的 BNF 表示 3 超前搜索 方法 词法分析时 常常会用到超前搜索方法 如当前待分析字符串为 a 当前字 符为 此时 分析器到底是将其分析为大于关系运算符还是大于等于关系运算符呢 显然 只有知道下一个字符是什么才能下结论 于是分析器读入下一个字符 这时 可知应将 解释为大于运算符 但此时 超前读了一个字符 所以要回退一个字符 词法分析器才能正常运行 在分析标识符 无符号整数等时也有类似情况 三 实验过程和指导三 实验过程和指导 一 准备 1 阅读课本有关章节 花一周时间明确语言的语法 写出基本保留字 标识符 常数 运算符 分隔符和程序例 2 初步编制好程序 3 准备好多组测试数据 二 上课上机 将源代码拷贝到机上调试 发现错误 再修改完善 第二次上机调试通过 三 程序要求 程序输入 输出示例 如源程序为 C 语言 输入如下一段 main int a b a 10 b a 20 要求输出如右图 具体要求如下 1 识别保留字 if int for while do return break continue 等 2 其他的都识别为标识符 3 常数为无符号整形数 4 运算符包括 TA A TA A e T FB B FB B e F E F i 2 根据预测分析表 判断该文法是否为 LL 1 文法 三 实验过程和指导三 实验过程和指导 对给定的无左递归和无回溯的上下文无关文法 按以下步骤执行 1 1 构造 First 集合 对文法中的每一个非终结符 X 构造 FIRST X 其方法是连续使用下述规则 直到 每个集合的 FIRST 不再增大为止 注 对终结符 a 而言 FIRST a a 因而无 需构造 1 若有产生式 X a 且 a VT 则把 a 加入到 FIRST X 中 若存在 X 则将 也加入到 FIRST X 中 2 若有 X Y 且 Y VN 则将 FIRST Y 中的所有非 元素 记为 都加入到 FIRST X 中 若有 X Y1Y2 Yk 且 Y1 Yi 1 都是非终结符 而 Y1 Yi 1 的候选式都有 存在 则把 FIRST Yj 的所有非 元素都加入到 FIRST X 中 j 1 2 i 特别是当 Y1 Yk 均含有 产生式时 应把 也 加到 FIRST X 中 2 2 构造 FOLLOW 集合 对文法 G S 的每个非终结符 A 构造 FOLLOW A 的方法是连续使用下述规则 直到 每个 FOLLOW 不再增大为止 1 对文法开始符号 S 置 于 FOLLOW S 中 由语句括号 S 中的 S 得到 2 若有 A B 可为空 则将 FIRST 加入到 FOLLOW B 中 3 若有 A B 或 A B 且 即 FIRST 则把 FOLLOW A 加到 FOLLOW B 中 此处的 也可为空 3 3 构造预测分析表 M 1 对文法 G S 的每个产生式 A 执行以下 2 3 步 2 对每个终结符 a FIRST A 把 A 加入到 M A a 中 其中 为含有首字 符 a 的候选式或为惟一的候选式 3 若 FIRST A 则对任何属于 FOLLOW A 的终结符 b 将 A 加入到 M A b 中 4 把所有无定义的 M A a 标记为 出错 4 4 判断该文法是否为 LL 1 文法 若预测分析表 M 无多重定义 则该文法为 LL 1 文法 否则 该文法不是 LL 1 文 法 四 实验提示四 实验提示 1 为了简化实验过程 我们这里假定要分析的文法都是无左递归的 即我们编程序 时无需考虑文法是否左递归了 下面给出文法结构体和文法符号集合的程序定义 define MAX GRAM LEN 255 文法符号的最大长度 define MAX ELE NUM 40 文法符号的最大个数 define MAX GRAM ELE NUM 300 所有文法符号的个数 定义文法结构体 typedef struct char mSetence MAX GRAM LEN grammerElement grammerElement GrammerSet MAX GRAM ELE NUM 定义文法符号的结构体 typedef struct int len char ele MAX ELE NUM simpleGroup simpleGroup groupFirst MAX ELE NUM First集 simpleGroup groupFollow MAX ELE NUM Follow集 int grammerNum 文法符号个数 char VTSet MAX ELE NUM 终结符 char VNSet MAX ELE NUM 非终结符 int VNProduceZ MAX ELE NUM 产生式 int vtSetLen 终结符的个数 int vnSetLen 非终结符的个数 char startedSign 开始符号 2 为了便于分析程序 在实验中要求把分析的文法保存在一个文本文件中 同时输 出的结果也保存在一个文本文件中 3 3 在附录中 我们给出了求First集的参考程序 大家可以参考该程序 并在此基础 上写出求Follow集以及构造分析表的程序 附附 录录 附录一附录一 实验结果的提交与检查实验结果的提交与检查 1 提交实验结果提交实验结果 每个实验的结果包括两项 实验报告和程序源代码 实验报告中请写明姓名 班号 学号 Email 等个人信息 以便遇到问题时老师 可以及时与你联系 实验报告的格式可参见 实验报告参考格式 也可自行拟定报告的格式 但要求 实验报告中至少包含如下内容 实验题目及内容 所用的状态转换图 主要数据结构 的设计 重要算法的流程 关键的代码段及注释 所用的测试数据及测试结果 以及 实验中遇到的问题和解决方法 请把实验的结果放入一个目录中 并将上述所有的文件打包成 rar 文件 文件名 为 自己的学号 rar 例如 01001 zip 通过 ftp 或 Email 提交 2 检查方式与评分标准检查方式与评分标准 在大家提交实验后 我们将对提交的程序进行测试 评分的主要标准是实验报告 以及程序输出与标准输出相符合的程度 附录二附录二 实验报告参考格式实验报告参考格式 以实验二 词法分析器的设计为例 实验报告格式如下 一 实验目的与任务一 实验目的与任务 编制一个读单词过程 从输入的源程序中 识别出各个具有独立意义的单词 即基本 保留字 标识符 常数 运算符 分隔符五大类 并依次输出各个单词的内部编码及单词 符号自身值 遇到错误时可显示 Error 然后跳过错误部分继续显示 二 实验步骤二 实验步骤 1 仔细阅读实验要求和书上的相关内容 写出基本保留字 标识符 常数 运算符 分 隔符和要测试的程序例 在这里写出基本保留字 标识符 常数 运算符 分隔符和要测试的程序实例 2 程序的功能描述 在这里描述你的程序的功能 3 程序的模块描述 在这里写出 重要的全局变量及其用途 主要函数的定义 功能 参数与返回值的含 义 4 关键程序代码 在这里写出 实验中关键的程序代码 不用把所有代码都写上 三 实验总结三 实验总结 可以从以下几个方面来总结 你在编程过程中花时多少 时间是怎么分配的 多少时 间在思考问题 遇到了哪些难题 你是怎么克服的 你对你的程序的评价 你的收获有哪 些 附录三附录三 Visual C 上机环境简介上机环境简介 上机实验环境亦可选择 Microsoft Visual C 以下简称 VC VC 是美国微软公司生 产的基于其 Windows 系统的软件开发工具 它具有使用灵活 并与 32 位 Windows 内核 使 用于 Windows 2000 Windows XP 高度兼容的特点 从而被 Windows 程序员们广泛使用 同时 VC 同样可以加工处理 C 语言程序 与标准的 ANSI C 语言兼容 VC 提供了一种控制 台操作方式 初学者使用它应该从这里开始 下面我们将对使用 VC 编写简单的控制台程序 作一个最初步的介绍 一 控制台程序简介一 控制台程序简介 Win32 控制台程序 Win32 Console Application 是一类 Windows 程序 它不使用复杂 的图形用户界面 程序与用户交互时通过一个标准的正文窗口 通过几个标准的输入输出 流 I O Streams 进行 它们分别是 stdin 标准输入 stdout 标准输出 以及 stderr 标准错误输出 这些流都是 ANSI C 语言标准库提供的 通过 printf 等函数 可以访问这些流 一个最简单的控制台程序如下 hello c include 包含使用标准输入输出的头文件声明 int main 主函数 printf Hello World n 向标准输出 stdout 输出一个字符串 return 0 主函数返回 该程序的运行结果如图 3 4 所示 图 3 4 控制台程序运行结果 图中显示的黑色窗口称为控制台窗口 程序的输入 输出均在这个窗口中进行 二 使用二 使用 VCVC 编写控制台程序编写控制台程序 很简单 只需要按照下面几个步骤进行 1 打开 MSVC 集成开发环境 双击桌面或 开始 菜单中的 Microsoft Visual C 6 0 不久将看到 VC 的编辑窗口 如图 3 5 图 3 5 VC 启动界面 2 选择菜单 File New 在弹出的对话框中 1 单击上方的选项卡 File 2 选择 C Source File 3 在 File name 一栏中填写文件名例如 hello c 4 在 Location 一栏中填写你想把文件存放的位置 目录 然后按 OK 见 图 3 6 注意 第 3 步中一定写明扩展名 c 不要用 cpp 那样 VC 将按 C 的方式编译 C 与 C 有一些的不兼容性 第 4 步中指定你自己的目录 不要使用系统的缺省目录或者随便放在根目录或者其 他的目录下 图 3 6 应用程序向导主界面 3 在右侧的窗口中键入程序的内容 然后点击图标存盘 进入 VC 编辑界面 如 图 3 7 图 3 7 VC 编辑界面 4 试编译 点击图标 或者选择菜单 Build Build 启动程序加工 这样 系统将连续进行编译和连接操作 另一种更稳妥的方式是先做编译 检查无误后 再做连接 这时 VC 将弹出一个对话窗口 说明这个命令需要一个工程 Project 问 是否创建一个默认的工程 点击 Yes 如图 3 8 所示 图 3 8 是否创建一个工程 5 编辑器中编译窗口开始显示编译的结果 如果显示 hello exe 0 error s 0 warning s 则表示编译已经通过 6 点击快捷工具栏上的红色的感叹号 或者选择菜单 Build Execute 或按 Ctrl F5 查看运行结果 VC 将自动打开一个显示结果的窗口 如上图 3 4 所示 三 如何调试程序三 如何调试程序 利用 VC 编写程序 还需要学会如何调试程序 我们都会发现 在编写较长的程序时 能够一次成功而不含有任何错误决非易事 当然 鼓励同学们以此为目标 进行长期大量 的练习 对于程序中的错误 VC 提供了易用且有效的调试手段 在工具栏上单击鼠标右 键 在弹出的菜单中对 Debug 项打勾 发现如图 3 9 所示的许多按钮 其中 较常用的 工具有 单步跟踪进入子函数 Step Into 单步跟踪跳过子函数 Step Over 运行至 当前函数的末尾 Step Out 以及观察变量的值 Watch 等 这些 VC 中常用的调试功能 详见有关参考文献 图 3 9 VC 调试工具条 附录四附录四 参考程序参考程序 1 词法分析器的设计 参考程序 cifa fenxi chengxu include include stdlib h include define N 100 定义要分析的标识符或常数的最大个数 define M 20 标识符的长度 char sourceFile 1 txt 定义进行词法分析的源文件 char key 8 if else for while do return break continue 关键字 char border 6 界符定义 char arithmetic 4 算术运算符定义 char relation 6 关系运算符定义 char consts N 常数定义 char label N 标识符 int constnum 0 labelnum 0 constnum 常数个数 labelnum 标识符个数 判断一个字符是不是字母 int Isletter char ch if ch a return 0 判断单词符号类型 int search char searchchar int wordtype int i 0 switch wordtype case 1 for i 0 i 7 i if strcmp key i searchchar 0 返回具体的关键字 return i 1 case 2 for i 0 i 5 i if strcmp border i searchchar 0 返回具体的界符 return i 1 return 0 case 3 for i 0 i 3 i if strcmp arithmetic i searchchar 0 返回具体的算术运算符 return i 1 return 0 case 4 for i 0 i 5 i if strcmp relation i searchchar 0 返回具体的关系运算符 return i 1 return 0 case 5 for i 0 i constnum i if strcmp consts i searchchar 0 返回具体的整型常数 return i 1 consts i 1 char malloc sizeof searchchar strcpy consts i 1 searchchar constnum return i case 6 for i 0 i labelnum i if label i NULL if strcmp label i searchchar 0 返回标识符 return i 1 label i 1 char malloc sizeof searchchar strcpy label i 1 searchchar labelnum return i return 1 标识符或关键字 char alphaprocess char buffer FILE fp int atype int i 1 char alphatp M while Isletter buffer IsDigit buffer alphatp i buffer buffer fgetc fp alphatp i 1 0 if atype search alphatp 1 输出关键字 printf s 1 d n alphatp atype 1 else atype search alphatp 6 输出标识符 printf s 6 d n alphatp atype 1 return buffer 常数处理 char digitprocess char buffer FILE fp int i 1 char digittp M int dtype while IsDigit buffer digittp i buffer buffer fgetc fp digittp i 1 0 dtype search digittp 5 输出整型常数 printf s 5 d n digittp dtype 1 return buffer 其它处理 运算符 界符等 char otherprocess char buffer FILE fp int i 1 char othertp M int otype otypetp othertp 0 buffer othertp 1 0 if otype search othertp 3 printf s 3 d n othertp otype 1 buffer fgetc fp goto out if otype search othertp 4 buffer fgetc fp othertp 1 buffer othertp 2 0 if otypetp search othertp 4 printf s 4 d n othertp otypetp 1 goto out else othertp 1 0 printf s 4 d n othertp otype 1 goto out if buffer buffer fgetc fp if buffer printf 2 2 n buffer fgetc fp goto out else if otype search othertp 2 printf s 2 d n othertp otype 1 buffer fgetc fp goto out if buffer n buffer fgetc fp out return buffer void main int i FILE fp 文件指针 指向要分析的源程序 char cbuffer 保存最新读入的字符 for i 0 i N i label i NULL 初始化标识符 consts i NULL 初始化常数 if fp fopen sourceFile rb NULL 判断源文件是否存在 printf 文件 s不存在 sourceFile else cbuffer fgetc fp 读入字符 while cbuffer EOF 如果文件没有结束 就一直循环 if Isletter cbuffer 若为字母 cbuffer alphaprocess cbuffer fp else if IsDigit cbuffer 若为数字 cbuffer digitprocess cbuffer fp else cbuffer otherprocess cbuffer fp printf over n getchar 2 LL 1 文法预测分析表的实现 参考程序 程序说明 grammer txt 用于输入相应的文法 第一行字母表示起始字符 include include include define MAX GRAM LEN 255 文法符号的最大长度 define MAX ELE NUM 40 文法符号的最大个数 define MAX GRAM ELE NUM 300 所有文法符号的个数 文件指针 FILE grammerFile char grammerFileName grammer txt 输入文法文件 FILE testFile char testFileName outputData txt 输出文件 文法结构体 typedef struct char mSetence MAX GRAM LEN grammerElement grammerElement GrammerSet MAX GRAM ELE NUM typedef struct int len char ele MAX ELE NUM simpleGroup simpleGroup groupFirst MAX ELE NUM First集 simpleGroup groupFollow MAX ELE NUM Follow集 int grammerNum 文法符号个数 char VTSet MAX ELE NUM 终结符 char VNSet MAX ELE NUM 非终结符 int VNProduceZ MAX ELE NUM 产生式 int vtSetLen int vnSetLen char startedSign 开始符号 voidreadInGrammer void cal first set 计算First集 void main 首先读入文法文件 if grammerFile fopen grammerFileName rb NULL printf open file grammerFile error n return if testFile fopen testFileName wb NULL printf open file testFile error n return readInGrammer 计算First集 Follow集 cal first set GrammerSet cal follow set GrammerSet fclose grammerFile fclose testFile getchar 从文件中读入文法 void readInGrammer char tmpChar char tmpStr MAX GRAM LEN int tmpIndex int vtIndex vnIndex int i j tmpIndex 0 vtIndex 0 vnIndex 0 fscanf grammerFile c r n while feof grammerFile if fscanf grammerFile c s r n GrammerSet tmpIndex mSetence 0 tmpChar GrammerSet tmpIndex mSetence 1 0 strcat GrammerSet tmpIndex mSetence tmpStr tmpIndex for i 0 i 65j vtIndex j if tmpStr i VTSet j break if j vtIndex 新的文法符号 VTSet vtIndex tmpStr i vtIndex i VTSet vtIndex 0 VNSet vnIndex 0 vtSetLen vtIndex vnSetLen vnIndex grammerNum tmpIndex 计算First集合 void cal first set int i j k int relationMatrix int matrixSize int vnIndex int rowIndex colIndex matrixSize vnSetLen vtSetLen relationMatrix int malloc sizeof int matrixSize for i 0 i matrixSize i relationMatrix i int malloc sizeof int matrixSize if relationMatrix NULL printf in cal first set mem apply failure n return for i 0 i matrix