词法分析核心算法(1)正规式》NFA_第1页
词法分析核心算法(1)正规式》NFA_第2页
词法分析核心算法(1)正规式》NFA_第3页
词法分析核心算法(1)正规式》NFA_第4页
全文预览已结束

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

1、正规式转换为不确定的有穷自动机的算法.目的与要求：通过设计、编写和调试将正规式转换为不确定的有穷自动机的程序， 掌握转换过程中的相关概念和方法，NFA的表现形式可以是图标或 者图形。.问题描述：任意给定一个正规式r （包括链接、或、闭包运算），根据如下算法， 设计一个程序，生成与该正规式等价的NFAN.算法：首先，分析给定的正规式r,将其分解成最基本的子表达式，使用下 面的规那么（1）和规那么（2）为r中的每个基本符号（8或字母表中的 符号）构造NFA。如果符号a在r中出现屡次，那么要为它的每次出现 构造一个NFA。然后，使用规那么（3）逐步地组合前面构造的NFA,直到获得整个正 规式的NFA

2、为止。基本规那么如下：（1）对于,构造如下列图所示的NFA,它识别储;(2)对于汇中的每个符号a,构造如下列图所示的NFA,它识别a； a (3)如果N(s)和N(t)分别是正规式s和t的NFA,那么：1对正规式s It,构造合成的NFAN(s I t),结果如下列图所示：加入x和y节点，从x弓|弧到N(s)和N(t)的开始状态，从N(s)和 N(t)的接受状态引8弧到y节点;2对正规式st,构造合成的NFAN(st),结果如下列图所示：CD Ms) 1 0 N(t)(Q)N(s)的开始状态成为合成后的NFA的开始状态，N(t)的接受状态 成为合成后的NFA的接受状态，N(s)的接受状态和N(

3、t)的开始状 态合并；3对于正规式s*,构造合成的NFAN(s*),如下列图所示：4对于括号括起来的正规式，使用N(s)本身作为他的NFA.基本要求：(1)输入一个正规式r;(2)输出与正规式r等价的NFA(可以是表格形式或图形形式)。测试数据：输入正规式:r=(a I b)*(aa I bb)(a I b)*.实现提示：NFA的表示可以是图形或者表格形式，状态之间的变换也可以 直接表示为每两个状态一组，表示为“起始状态 输入字符 到达状态”，如“a”表示在状态下读入输入字符a, 变换到状态。(2)实现时的数据结构的定义：1用字符串存储正规式；2用结构体链表存放状态转换图struct NFA int from;int to;char varch; 表而正态fh)m到达状,态to,经过多符varch3中间过程使用堆栈结合正规式算符优先关系表来完成正规式的优先关系表：a*1()#aerrerr*1(err#err将#压入堆栈，并从左到右扫描输入符号串，遇到下一个优先性低 的运算符那么出栈并构造NFA;遇到下一个优先性高的运算符那么入 栈。为了方便处理，将*运算符改为前缀，如：r=(a I b)*(aa I bb)(a I b)*=r=* (a I b) (aea I beb) *(a I b)注意：处理过程中，当前运算符作用域的处理。如：* (a I

人人文库> 全部分类> 办公材料 > 办公文档

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论