自己总结的词法分析器flex的源码及算法分析
需积分: 45 127 浏览量
2018-10-18
20:50:19
上传
评论
收藏 1.34MB DOCX 举报
一． 概念
正则表达式
使用 来解析输入文件，将输入文件的规则区中的正则表达式转换为 图
典型的 状态图可见下面的示例
到 的计算过程：
从 图中得到每个对应 状态的 状态集合 （每次转换一步）
求 的 闭包，得到一个新的 状态集合
根据 求出一个对应的 状态，对应的节点集合为
重复步骤 ，直至所有的转换都已完成（已无新的 状态集合），整个构造过程是动态
的， 状态集合是动态计算得到，一旦有新的 状态集合求出，对应的 状态也对
应增加
等价类
等价类（）指的是将输入字符根据规则需要分类，例如下面的例子 总数为
；而 等价类（）则是用于模型机的（），是一种更抽象
的分类，如下面的例子 总数为
转换表和转换算法
转换矩阵
根据上面 计算结果以及所有的等价类，求出从一个 状态转换到另一 状态的转
换矩阵，两个转换状态的转换边（转换条件）为
状态集合和转换矩阵可见下面的示例
和 !
和 ! 用于减少转换表项的空间，及加速查找和转换过程；
两种表项均为双向链表
和 ! 表项可见下面的示例
剩余11页未读，继续阅读
资源评论
