实验三算符优先算法

1、实验三：算符优先算法一、 实验目的：1使用算符优先算法将输入的正则表达式转化位NFA；2加强对算法优先算法的理解，加强将正则表达式转化为NFA方法的理解；3强化对系统软件综合工程实现能力的训练。二、 实验内容：用 C 语言或者其他的高级语言开发完成将输入的正则表达式转化为NFA的程序。三、 实验要求：编写一个程序，能将输入的正则表达式转化为 NFA，源程序并调试通过。通过测试程序的验收；提交实验报告，报告必须包含以下内容：（1）程序功能描述；（2）程序数据结构描述；（3）函数或模块描述：函数功能、流程图，函数参数含义、返回值描述；（4）函数之间的调用关系描述和程序总体执行流程图；（5）实验总结

2、：你在编程过程中花时多少？多少时间在纸上设计？多少时间上机输入和调试？多少时间在思考问题？遇到了哪些难题？你是怎么克服的？你对你的程序的评价？你的收获有哪些？（6）手写实验报告使用学校要求的实验稿纸，打印实验报告使用B5纸打印。四、 评判标准：输出正确的实验结果；代码清晰，格式良好；提交报告，报告阐述清楚。五、 程序工作说明：程序接受文本文件中输入的正则表达式，生成该正则表达式对应的NFA，在屏幕上显示出这个 NFA。统计并输出该 NFA中的节点个数和边的个数；输入的正则表达式中包含的运算符包括：连接运算符 ”.”,闭包运算符 “*”,逻辑或运算符 “|”,左括号“(“,右括号 “)”。运算符

3、的运算优先级从高到低位(* .|)(4) 输入的正则表达式中的字符限于大写英文字母，小写英文字母，数字09；(5)NFA使用图的邻接链表或者邻接矩阵存储；程序的调试者和执行者保证输入的正则表达式正确，程序不检查正则表达式的正确性。六、结构体和算法流程如果 NFA使用图的邻接链表存储，邻接链表中存储边信息的结构体：struct Arrowint nEndStateID; /箭弧终点的节点状态IDchar chLetter; /箭弧上标注的字符struct Arrow * pNextArrow; /与当前边有相同开始接点的下条箭弧;邻接链表中存储节点信息的结构体：struct Stateint n

4、StateID; /顶点编号，在整个NFA中定点编号是唯一的struct Arrow *pFirstArrow; /当前顶点的连接的第一条箭弧的指针;NFA 中的状态在图中用图的节点表示，NFA 的所有状态保存在邻接链表的节点结点结构体数组中，结构体定义：struct NFAstruct State StateListMAX; /int stateCount; /有效的状态个数int arrowCount; /箭弧的个数表示头结点的数组（就是NFA的状态）;每个输入符号都要生成一个NFA （就是一对开始结束节点和中间连着的箭弧），输入符号生成的NFA 要进栈，输入符号对应的 NFA 的栈结构体

5、：struct stateStackstruct State * pStateListMAX; /栈空间int top; /栈顶，栈顶元素在数组中的下标;正则表达式的运算符栈struct operatorStackchar chOperatorListMAX; /栈空间inttop; /栈顶，栈顶元素在数组中的下标;算符优先算法初始化状态栈；初始化运算符栈；压进入运算符栈；在正则表达式末尾添加 # 运算符；产生一个初始 0号节点读取正则表达式的首符；while( 正则表达式没有结束)if( 当前字符是正则表达式的字符)产生一对新开始和结束节点；在开始节点和结束节点之间拉一条标注为当前字符的箭弧

6、；将开始节点和结束节点压入状态栈；读取下一个字符；elseif( 当前操作符运算优先级别比 栈顶运算符优先级别高)当前操作符压入符号栈；读取下一个字符；else if （当前操作符运算优先级别比栈顶运算符优先级别低）运算符栈的栈顶运算符出栈；if （出栈运算符是连接符）从状态栈中弹出一对开始结束节点A ；从状态栈中弹出一对开始结束节点B ；从 B的结束节点拉一条 指示的箭弧到A 的开始节点；B 的开始节点和 A 的结束节点作为一对开始结束节点入状态栈；else if( 出栈运算符是逻辑或)从状态栈中弹出一对开始结束节点A ；从状态栈中弹出一对开始结束节点B ；生成一对新的开始结束节点C；从 C

7、的开始节点拉一条 指示的箭弧到 A 的开始节点；从 C的开始节点拉一条 指示的箭弧到 B的开始节点；从 A 的结束节点拉一条 指示的箭弧到 C的结束节点；从 B的结束节点拉一条 指示的箭弧到 C的结束节点；C的开始节点和结束节点作为一对节点入状态栈；else if（出栈运算符是闭包运算符）从状态栈中弹出一对开始结束节点A ；生成一对新的开始结束节点C；从 C的开始节点拉一条 指示的箭弧到 A 的开始节点；从 A 的结束节点拉一条 指示的箭弧到 C的结束节点；从 A 的结束节点拉一条 指示的箭弧到 A 的开始节点从 C的开始节点拉一条 指示的箭弧到 C的结束节点C的开始节点和结束节点作为一对开始

8、结束节点入状态栈；else if( 当前操作符运算优先级别比栈顶运算符优先级别相等)if （栈顶运算符是左括号，当前运算符是右括号）左括号出运算符栈；扫描下个字符；else if（栈顶运算符是#，当前运算符是#）正则表达式处理完成，退出循环；从状态栈中弹出一对开始结束节点A ；从 0号节点拉一条 指示的箭弧到A 的开始节点；操作说明：产生一对新开始和结束节点：就是在结构体 struct NFA 的结构体成员 stateCount 的值增加 2，表示结构体中的成员StateList 数组中的有效元素增加2 个，数组的成员是结构体struct State，该结构体有 2个数据成员： nStateI

9、D（表示节点 ID ）和 pFirstArrow （表示这个节点上出发的箭弧链表） ；设置新增的2 个数组成员的StateListstateCount-1 和 StateListstateCount-2 的 nStateID 的值为唯一的状态 ID ，第一条箭弧的指针pFirstArrow赋值为空；在开始节点和结束节点之间拉一条标注为当前字符的箭弧：在结构体 NFA 的成员 StateList 数组中查找到开始节点（找到开始节点对应的下标），该数组元素是个 struct State 类型的结构体，结构体 struct State 中有个指针成员pFirstArrow ，该指针成员指示的链表是所有从这个顶点出发的箭弧，在这个链表中增加一个链表元素（可以用头插法或者尾插法插入） ，表示新增加的边。 该新增的链表元素是个结构体structArrow ，设置该结构体中的箭弧终点的节点状态nEndStateID 的值为结束节点的ID ，箭弧上标注的字符 chLetter 的值为当前字符，箭弧的下一个指针pNextArrow 的值根据头使用插入还是尾插法进行不同的设置；的开始节点和结束节点作为一对开始结束节点入状态栈：C 实际是结构体NFA 中的成员StateList 数组中的2 个数组成员，结构体的str