《编译原理(E)》实验指导书计算机软件与工程系 何春梅 -12-28下载后可任意编辑 目 录实验 1 词法程序设计(1) 1实验 2 词法程序设计(2) 3实验 3 语法程序设计(1) 4实验 4 语法程序设计(2) 5实验 5 语法程序设计(3) 6实验 6 中间代码生成 8 下载后可任意编辑实验 1 词法程序设计 ——DFA( 确定的有穷自动机) 的化简一、实验目的与要求经过设计、 编写和调试将确定的有穷自动机的状态数变为最少的 C 程序, 使得学生掌握化简为有穷自动机的过程中的相关概念和方法。DFA 的表现形式能够为表格或图形。二、问题描述每一个正规集都能够由一个状态数最少的 DFA 所识别, 这个DFA 是唯一的( 不考虑同构的情况) 。任意给定的一个 DFA, 根据以下算法设计一个 C 程序, 将该 DFA 化简为与之等价的最简DFA。三、算法( 1) 构造具有两个组的状态集合的初始划分 I: 接受状态组 F 和非接受状态组 Non-F。( 2) 对 I 采纳下面所述的过程来构造新的划分 I-new. For I 中每个组 G do Begin 当且仅当对任意输入符号 a,状态 s 和读入 a 后转换到 I 的同一组中; /*最坏情况下, 一个状态就可能成为一个组*/ 用所有新形成的小组集代替 I-new 中的 G; end( 3) 假如 I-new=I, 令 I-final=I,再执行第( 4) 步, 否则令 I=I=new,重复步骤( 2) 。( 4) 在划分 I-final 的每个状态组中选一个状态作为该组的代表。这些代表构成了化简后的 DFA M＇状态。令 s 是一个代表状态, 而且假设: 在 DFA M 中, 输入为 a 时有从 s 到 t 转换。令t 所在组的代表是 r,那么在 M’中有一个从 s 到 r 的转换, 标记为 a。令包含 s0 的状态组的代表是 M’的开始状态, 并令 M’的接受状态是那些属于 F 的状态所在组的代表。注意,I-final 的每下载后可任意编辑个组或者仅含 F 中的状态, 或者不含 F 中的状态。( 5) 假如 M’含有死状态( 即一个对所有输入符号都有刀自身的转换的非接受状态 d) ,则从 M’中去掉它; 删除从开始状态不可到达的状态; 取消从任何其它状态到死状态的转换。四、 基本要求1、 输入一个 DFA M,输出一个与之等价的最小化的 DFA M’, 上机编程实现。2、 实验报告格式要求书写要点: 概要设计( 总体设计思想) ; 详细设计: 程序主流程、 DFA 的存储格式( 即数据结构) 、 关键函数的流程图; 结果分析( 输入与输出结果、 ...
