上机实验报告

编译原理报告编译原理报告正规式转化为NFA班级：191131班学号：20131002284姓名：李豪强指导老师：刘远兴日期：2015/10/20前期准备摘要题目：正规表达式→NFA问题实习时间：2015/10/12【问题描述】正规表达式→NFA问题的一种描述是：编写一个程序，输入一个正规表达式，输出与该文法等价的有限自动机。【基本要求】=1\*GB3①掌握有限自动机、正规表达式、正规文法之间的转换算法，有些可帮助掌握有限自动机的确定化与最小化，还有些可帮助理解整个词法分析器的构造过程。=2\*GB3②以班为单位，每个班内3-5人为一组，自由组合。选一人为组长，要适当分工，要分工明确。=3\*GB3③需上交：源程序，实验报告。实验报告要交电子档报告，重点写自己那部分的设计思路和实现方法。分工：我们小组具体分工如下：陈渊：负责总体规划，以及系统整合李豪强：负责整个程序架构的设计及软件测试；蔡路：负责伪代码（核心算法）的实现；李涛，陈渊：负责输入输出处理及用户界面设计祝莹倩，樊润宇：数据结构的分析处理；1．需求分析（1）首先要获取用户需要转化的正规式；（2）然后判断用户输入的正确与否，并予以提示；（3）运用正规式转化NFA的算法思想进行词法分析（4）设置初始状态X，终态Y，过程态用数字表示：0123………测试数据：abb输出结果应为：XX-a->0Y00-b->111-b->Y测试数据：(a|b)*abb输出结果应为：XX-~->3Y00-a->111-b->222-b->Y33-~->03-a->33-b->3设计2.1总体设计2.1.1设计思想数据结构***该部分由小组成员樊润宇和祝莹倩同学共同完成***2.2模块设计（重点）程序架构的设计：此次实验的要求是将一个输入的任意合法正规式转换为相应的不确定的有穷自动机（NFA），由教材上所提出的方法可知，在构造有穷自动机的时候，第一步应先将正规式分解为可以直接转换为NFA的正规式，然后将所有的状态经过条件连接得到最终的NFA。所以应设计函数将正规式分解，然后由转换函数得出NFA。过程或函数调用关系图（流程图）2.3函数的功能实现（解释所写函数的作用，写函数的声明原型及其注释。）voiddivide(strings,vector<Node*>*N,intbegin,intend)；//用于将正规式细化voidinsert(strings,vector<Node*>*N,inthead,inttail,charstate[])；//将细化后的正规式转//化为应的NFA状态并将其转换条件一起存储到N中voidDisplay(vector<Node*>N)；//输出NFAvoiddisplay();//输出当前状态以及条件和经此条件所能到达的状态2.4算法设计从正则表达式到NFA的转换方法（核心算法）：****该部分由小组成员蔡路同学完成***3．使用手册（1）数据输入：在输入时对于任何符号都从左到右直接输入(例：不必对于*进行特别的输入处理，直接按键输入即可)功能键用法：“请输入正规式：”后的文本框用于用户输入正规式“转化结果：”后的文本框由于新显示正规式对应的NFA“转化”按钮用于执行将输入文本框中的正规式转化为NFA并在输出文本框中输出结果“关闭”按钮用于关闭对话框。4．测试结果测试数据：abb输出结果应为：XX-a->0Y00-b->111-b->Y屏幕截图：测试数据：(a|b)*abb输出结果应为：XX-~->3Y00-a->111-b->222-b->Y33-~->03-a->33-b->3屏幕截图：5．总结首先，这次上机实验增强了我们团队合作能力，我们小组成员在一起商讨设计思路之后，由组长安排每个人的任务，然后每人完成自己的任务后交由组长整理整合，在这个过程中每人都要参与商讨确定每部分内容应安排在哪部分，这不仅增强了我们的团队合作能力更加深了彼此之间的友情。另外，在此次上机实习中我相信我们都对正规式到NFA的转换有了更加深刻的理解，例如，在转换时可以对正规式有两种处理，一是将正规式从左到右扫描进行类似计算器的操作将正规式转换为后缀式，然后对‘或’、