编译原理NFA转化为DFA的转换算法及实现.doc

课程设计报告书课程设计报告书 设计名称 NFA 转化为 DFA 的转换算法及实现 课程名称 编 译 原 理 学生姓名 专 业 班 别 学 号 指导老师 日 期 2013 年 7 月 5 日 2 目目 录录 目目 录录 2 1 1 前言前言 3 1 1 选题的依据和必要性选题的依据和必要性 3 1 2 课题意义课题意义 3 2 NFANFA 转化为转化为 DFADFA 的算法及实现的算法及实现 3 2 1 基本定义基本定义 3 2 1 2 DFA的概念的概念 4 2 1 3 NFA与与DFA的矩阵表示的矩阵表示 5 2 1 4 NFA向向DFA的转换的思路的转换的思路 6 3 DFA 的化简的化简 6 3 1 化简的理论基础化简的理论基础 6 3 23 2 化简的基本思想化简的基本思想 7 4 4 程序设计程序设计 7 4 14 1 程序分析程序分析 7 4 1 14 1 1 流程图流程图 7 4 1 24 1 2 子集构造法子集构造法 9 4 2 实现代码实现代码 11 3 1 1 前言前言 1 1 选题的依据和必要性选题的依据和必要性 由于很多计算机系统都配有多个高级语言的编译程序 对有些高级语言甚 至配置了几个不同性质的编译程序 从功能上看 一个编译程序就是一个语言 翻译程序 语言翻译程序把源语言书写的程序翻译成目标语言的等价程序 经 过编译程序的设计可以大大提高学生的编程能力 编译程序的工作过程通常是词法分析 语法分析 语义分析 代码生成 代码优化 1 由于现在有很多词法分析程序工具都是基于有穷自动机的 而词 法分析又是语法分析的基础 2 所以我们有必要进行有穷自动机的确定化和最 小化 1 2 课题意义课题意义 编译程序的这些过程的执行先后构成了编译程序的逻辑结构 3 有穷自动机 也称有限自动机 作为一种识别装置 它能准确地识别正规集 即识别正规 文法所定义的语言和正规式所表示的集合 引入有穷自动机这个理论 正是为 词法分析程序的自动构造寻找特殊的方法和工具 4 NFA转化为DFA的理论在词 法构造至整个编译器构造过程中起着至关重要的作用 同时它们被广泛应用于 计算机科学的各个领域 它们与计算机其它学科也有着密切的联系 2 NFANFA转化为转化为DFADFA的算法及实现的算法及实现 编译原理是计算机专业的一门重要专业课 旨在介绍编译程序构造的一般 原理和基本方法 内容包括语言和文法 词法分析 语法分析 语法制导翻译 中间代码生成 存储管理 代码优化和目标代码生成 进行NFA转换为DFA的词 法分析和语法分析 首先要对目标对象有有所了解 这就需要对NFA DFA进一 步了解 2 1 基本定义基本定义 NFA 也称不确定的有穷自动机 是由一个五元式定义的数学模型 特点是 它的不确定性 即在当前状态下 读入同一个字符 可能有多个下一状态 4 DFA 也称确定的有穷自动机 也是由一个五元式定义的数学模型 相对的 特点是它的确定性 即在当前状态下 读入同一个字符 最多有一个后继状态 2 1 1NFA 的概念的概念 NFA nondeterministic finite state automata 即非确定有限自动机 一个非确定的有限自动机 NFA M 是一个五元式 NFA M S S0 F 其中 S 有限状态集 S0 初态集 F 终态集 转换函数 S 2S 2S S 的幂集 S 的子集构成的集合 状态转换图如图2 1 1 1 1 0 1 0 1 图图2 1 1 NFA状态转换图状态转换图 2 1 2 DFA的概念的概念 DFA deterministic finite state automata 即确定有限自动机 一个确 定的有限自动机 DFA M 是一个五元式 M S S0 Z 其中 S 有限状态集 输入字母表 映射函数 也称状态转换函数 Z S P 5 S S s a S S S S a S0 初始状态 S0 S Z 终止状态集 Z S P Z P P aa ba b b a b 图图2 1 2 DFA状态转换图状态转换图 2 1 3 NFA与与DFA的矩阵表示的矩阵表示 一个NFA或者DFA还可以用一个矩阵 5 表示 矩阵也可以说是状态转换表 它的优点是可以快速访问给定的状态在给定的输入字符时能转换到的状态集 矩阵 每个状态一行 每个输入符号和 如果有需要的 各占一列 表的第i 行中与输入符号a对应的表项是一个状态集合 表示NFA或者DFA在状态i输入a 时所能到达的状态集合 DFA的集合唯一 即 i a 6 7 如图2 1 1可用表2 3 1 表示 表表2 3 12 3 1 NFANFA状态转换表状态转换表 输入 状态 01 S P S Z P Z Z P P 如图2 1 2可用表2 3 2表示 表表2 3 22 3 2 DFADFA状态转换表状态转换表 6 输入 状态 ab 012 13 2 213 333 2 1 4 NFA向向DFA的转换的思路的转换的思路 从NFA的矩阵表示中可以看出 表项通常是一状态的集合 而在DFA的矩 阵表示中 表项是一个状态 NFA到相应的DFA的构造的基本思路是 DFA的 每一个状态对应NFA的一组状态DFA使用它的状态记录在NFA读入一个输入符 号后可能达到的所有状态 4 2 2 NFA 和和 DFA 之间的联系之间的联系 在非确定的有限自动机 NFA 中 由于某些状态的转移需从若干个可能的后续 状态中进行选择 故一个 NFA 对符号串的识别就必然是一个试探的过程 这种 不确定性给识别过程带来的反复 无疑会影响到 FA 的工作效率 而 DFA 则是确 定的 将 NFA 转化为 DFA 将大大提高工作效率 因此将 NFA 转化为 DFA 是有其一 定必要的 3 DFA的化简的化简 得到新的DFA之后 并没有完成任务 因为通过NFA转化成DFA不一定是最简 的 也就是说 有多余的状态可以被删除 而我们需要的是得到一个唯一的最 简的DFA 12 也就是说 NFA转化为DFA之后 还需要化简 也就是最小化 3 13 1 化简的理论基础化简的理论基础 DFA的化简是指 寻找一个状态数最少的DFA M 使得L M L M 化简的方法是消去DFA M中的多余状态 或无用状态 合并等价状态 DFA中的多余状态是指这样的状态 从开始状态出发 读入任何输入串都 不能到达的那个状态 或者从这个状态没有通路到达终态 7 两个状态S 和T等价是指 如果从状态S出发能读出某个字W而停于终态 从T出发也能读出同样的字W而停于终态 反之 从T出发能读出同样的字W而 停于终态 从S出发也能读出某个字W而停于终态 3 23 2 化简的基本思想化简的基本思想 化简DFA的基本思想是指导它的状态分成一些互不相交的子集 每一个子 集中的状态都不是等价的 不同子集中的状态可以由某个输入串来区别 最后 将不能区别的每个子集用一个状态来做代表 13 15 这种方法称为 分割法 具 体过程是 1 将M的所有状态分成两个子集 终态集和非终态集 2 考察每一个子集 若发现某子集中的状态不等价 将其划分为两个集合 3 重复第 2 步 继续考察已得到的每一个子集 直到没有任何一个子集 需要继续划分为止 这时DFA的状态被分成若干个互不相交的子集 4 从每个子集中选出一个状态做代表即可得到最简的DFA 4 4 程序设计程序设计 通过本设计所要求达到的目的是 充分理解和掌握NFA DFA以及NFA确定化 过程的相关概念和知识 理解和掌握子集法的相关知识和应用 现在需要编程 16 18 实现对输入NFA转换成DFA输出的功能 4 14 1 程序分析程序分析 4 1 14 1 1 流程图流程图 程序总框图如图4 1所示 8 总模块 NFA 图结构 状态转换表 DFA 图结构 初始化状态 转换矩阵 状态转换操 作 图图4 1 1 程序总框图程序总框图 开始 输入 NFA 初始化 NFA 初步转化为 DFA 结束 重命名化简 9 图图4 1 2 功能图功能图 4 1 24 1 2 子集构造法子集构造法 已证明 非确定的有限自动机与确定的有限自动机从功能上来说是等价的 也就是说 我们能够从 NFA M DFA M 使得 L M L M 为了使得 NFA 确定化 我们首先给出两个定义 定义 1 集合 I 的 闭包 令 I 是一个状态集的子集 定义 closure I 为 1 若 s I 则 s closure I 2 若 s I 则从 s 出发经过任意条 弧能够到达的任何 状态都属于 closure I 状态集 closure I 称为 I 的 闭包 定义 2 令 I 是 NFA M 的状态集的一个子集 a 定义 Ia closure J 其中 J s a J 是从状态子集 I 中的每个状态出发 经过标记为 a 的弧而达到的状态 集合 Ia 是状态子集 其元素为 J 中的状态 加上从 J 中每一个状态出发通过 弧到达的状态 给定如图 2 所示的 NFA 10 b b a a b 0 12 3 4 图 4 1 3 与之等价的 DFA 如图 3 b a b 0 1 2 4 4 3 a 图 4 1 4 11 开始 求开始状态闭包 标记 令它为集合 C 中的唯一成员 集合 C 中存在 尚未被标记子 集 标记 对子集 中的每个输 入字母求 a 子集 将 加入 中 结束 语 是否 图图4 1 5 子集构造法的流程图子集构造法的流程图 这样就完成了从正规表达式 101 0 1 011 到 DFA 的转化 4 2 实现代码实现代码 include include define MAXS 100 using namespace std string NODE 结点集合 string CHANGE 终结符集合 12 int N NFA 边数 struct edge string first string change string last struct chan string ltab string jihe MAXS void kong int a int i for i 0 i a i cout 排序 void paixu string char b for j 0 j a length j for i 0 iNODE find a i 1 b a i a i a i 1 a i 1 b void eclouse char c string for k 0 khe length he b k last eclouse b k last 0 he b 13 void move chan k he ltab length l he jihe m length for i 0 i k i for j 0 jhe jihe m length he jihe m b j last 0 for i 0 i l i for j 0 jhe jihe m length he jihe m b j last 0 输出 void outputfa int len int h chan t int i j m cout I for i 0 i len i cout I CHANGE i cout endl endl for i 0 i h i cout t i ltab m t i ltab length for j 0 j len j kong 8 m m t i jihe j length cout t i jihe j cout endl void main edge b new edge MAXS int i j k m n h x y len bool flag string jh MAXS endnode ednode sta cout 请输入 NFA 各边信息 起点 条件 空为 终点 以 结束 endl 14 for i 0 i b i first if b i first break cin b i change b i last N i for j 0 j N j cout b j first b j change b j last endl for i 0 iNODE length NODE b i first if NODE find b i last NODE length NODE b i last if CHANGE find b i change CHANGE length len CHANGE length cout 结点中属于终态的是 endnode for i 0 iNODE length cout 所输终态不在集合中 错误 endl return cout endnode endnode endl chan t new chan MAXS t 0 ltab b 0 first h 1 eclouse b 0 first 0 t 0 ltab b 求 e clouse cout t 0 ltab endl for i 0 i h i for j 0 j t i ltab length j for m 0 m len m eclouse t i ltab j t i jihe m b 求 e clouse for k 0 k len k cout t i jihe k move t i k b 求 move I a cout t i jihe k endl for j 0 j t i jihe k length j 15 eclouse t i jihe k j t i jihe k b 求 e clouse for j 0 j len j paixu t i jihe j 对集合排序以便比较 for k 0 k h k flag operator t k ltab t i jihe j if flag break if flag cout endl 状态转换矩阵如下 endl outputfa len h t 输出状态转换矩阵 状态重新命名 string d new string h NODE erase cout endl 重命名 endl for i 0 i h i sta t i ltab t i ltab erase t i ltab A i NODE t i ltab cout sta t i ltab endl for j 0 j endnode length j if sta find endnode j sta length d 1 ednode t i ltab for k 0 k h k for m 0 m len m if sta t k jihe m t k jihe m t i ltab for i 0 iednode length d 0 NODE i endnode ednode cout endl DFA 如下 endl outputfa len h t 输出 DFA cout 其中终态为 endnode endl DFA 最小化 16 m 2 sta erase flag 0 for i 0 i m i cout d i d i endl for k 0 k len k cout I CHANGE k endl y m for j 0 j d i length j for n 0 n y n if d n find t NODE find d i j jihe k d n length t NODE find d i j jihe k length 0 i