编译原理-词法分析05-正则表达式到DFA-01

时间:2022-06-01 17:57:19

编译原理-词法分析05-正则表达式到DFA

要经历 正则表达式 --> NFA --> DFA 的过程。

0. 术语

Thompson构造Thompson Construction

利用ε-转换将正则表达式的机器片段“粘在一起”以构成与整个正则表达式相对应的机器。

ε-闭包ε-closure

可由ε-转换从某状态或某些状态达到的所有状态集合。

子集构造subset construction

通过ε-闭包将NFA构造为DFA的一种方法过程。

1. Thompson构造的基本表示

基本正则表达式

对于空转换

编译原理-词法分析05-正则表达式到DFA-01

符号a的转换

编译原理-词法分析05-正则表达式到DFA-01

并置

编译原理-词法分析05-正则表达式到DFA-01

选择

编译原理-词法分析05-正则表达式到DFA-01

重复

编译原理-词法分析05-正则表达式到DFA-01

2. 示例

(ε|a*b)

编译原理-词法分析05-正则表达式到DFA-01

3. NFA2DFA——子集构造算法

input:NFA N

output:DFA D

计算字母表 ∑
计算NFA的开始状态的ε-闭包,作为 D 的初始状态,且未被标记。
while (在 D 中存在未被标记的状态 T)
{
  取出T,为 T 加上标记 //出栈
for (在∑中的每个字符a) //遍历字母表
{
states = move (T,a) // 从T经过字母a转换的状态集合
U = ϵ-closure(states) //计算states的闭包
if (U 不在 D 中) {
将 U 加入 D 中,且未被标记 //新增一个状态,且转为的字符为a
}
T[a]=U //记录转换
}
}

ref: http://www.cnblogs.com/cyjb/p/LexerDfa.html

同样可以使用表驱动来完成构造过程。

NFA的状态集合 DFA上的状态 a b c