flex中dfa和nfa

有限自动机的数学模型由五个部分组成: ? 1. 有穷状态集 States ? 2. 输入字符集 Input symbols ? 3. 转移函数 Transitions ? 4. 起始状态 Start state ? 5. 接受状态 Accepting states 一个状态机由起始状态,通过接受输入一系列字符来实现状态迁移,最终到达接受状态. 一. 在flex中一个nfa机器由一个连续的nfa状态数组来表示. ?? firstst?? ?:? nfa机器的第一个状态. ?? lastst?? ?:? nfa机器的最后一个状态. ?? finalst?? ?:? nfa机器的逻辑最后一个状态 ?? transchar?? ?:? nfa状态的转换字符 ?? trans1?? ?:? nfa状态接受tranchar后到达的状态 ?? trans2?? ?:? nfa状态通过epsilon可到达的状态 ?? accptnum?? ?:? nfa状态对应的规则号 ?? assoc_rule?? :? nfa状态关联的规则号 ?? state_type?? :? nfa状态的类型 函数说明: mkstate ?? ?: 生成一个nfa状态,输入为该状态的转换字符,返回状态号 mkxtion?? ??? ?: 由一个状态转换到另一个状态. ? 例子: 让状态1接受'a'到达状态2 : ? ?? ?state1 = mkstate('a'); ? ?? ?state2 = mkstate(SYM_EPSILON); ?? ?mkxtion(state1,state2); ? 注: 只有epsilon(由SYM_EPSILON转换字符生成的状态)状态能迁移到两个状态,也就是说trans2是专门给epsilon状态使用的. link_machine?? ?: 连接两个nfa机器,与mkxtion的区别:前者是状态机连接,mkxtion是状态之间连接. 一个状态机包含一些列的状态. ? 描述:? 1)把第一个状态的最后一个状态与第二个状态机的状态相连,第一个状态机成为新的状态机. ?? ?2)把第二个状态机的逻辑最后一个状态赋值给新的状态机 ?? ?3)重新选择物理第一个和最后一个状态赋值给新的状态机 ?? ?4)返回新的状态机 mkbranch : 生成一个新的机器,分支到两个状态机. 新生成一个epsilon状态. trans1->状态1,trans2到状态2. dupmachine : 复制一个状态机. 从状态机的物理第一个状态到物理最后一个状态一一拷贝属性. 被拷贝的状态机要求是连续的. mkposcl?? ?: 自环一个状态机,也就是把状态的逻辑最后一个状态与状态机首状态相连接,可无限循环. 正则表达式中 + 与之等价. mkopt?? ?: 使一个状态变成可选的. 正则表达式中 ? 与之等价. ?? 描述:? 生成两个epsilon状态e1,e2.?? e1->e2,e1->m,m->e2. 这样机器m就变成可选了. mkclos? : 使一个机器变成闭包. 先让状态机自环,然后在使其变成可选的. 正则表达式中 * 与之等价. 也就是说正则表达式的 a* = (a+)? mkor?? ?: 使两个状态机变成或关系(a|b). 生成两个epsilon状态. e1->a,e1->b,a->e2,b->e2. mkrep?? ?: 重复生成lb~ub个状态,并连接起来. 正则表达式为? machine{lb,ub} 二. 在flex中dfa的表示 ? dhash?? ??? ?: dfa状态中包含所有nfa状态号之和 ? dfasiz?? ?: dfa状态中包含nfa状态的个数 ? dss?? ??? ?: dfa状态中包含nfa状态的集合(数组,长度为dfasiz) ? dfaacc?? ?: dfa的接受状态 nfa传dfa的方法: ? 1. nfa状态机起始状态,在flex中就是scset和scbol. ? 2. 使用epsclosure函数找出所有nfa通过epsilon可到达的状态. ? 3. 使用snstods把上述的nfa集合生成一个新的dfa状态或者返回相同的旧的dfa状态 ? 4. 扫描dfa状态集中的每一个的状态,使用sympartition区分出dfa的转换字符 ? 5. 使用symfollowset收集dfa状态的相应输出字符的nfa状态集合 ? 6. 在使用epsclosure函数找出上述集合中所有nfa通过epsilon可到达的状态. ? 7. 使用snstods把上述的nfa集合生成一个新的dfa状态或者返回相同的旧的dfa状态 ? 8. 使用dfa状态和输出字符集以及输出状态集生成表格. ???? base为相应dfa状态的字符集起始 ???? nxt为字符集转换表 ???? chk为检查表 ???? def为默认转换表,即输入字符不在字符集转换表中时,dfa如何转. ?? 9. 重复步骤4. ?