DFA在编译过程中起到了分析语法的作用，同理，敏感词过滤和正则表达式同样可以使用DFA实现
实际使用中，正则表达式可以通过：正则->NFA->DFA->最简DFA
希望使用DFA能够解决H248的digitMap匹配原则；
正则->NFA
这部分有三个替换原则如下：
- 规则一，r=ab（就是a&b），状态转换如下：i(起始状态)->(a)->k(中间状态)->(b)->j(结束状态)
- 规则二，r=a|b，转换状态如下:i（起始状态）->(a)->j(结束状态)；第二条路：i（起始状态）->(b)->j(结束状态)
- 规则三，r=a*（通配符）转换状态如下：i(起始状态)->(只要能达到下一个状态即可的路径)->k(中间状态)->(只要是能达到下一个状态即可的路径)->j(结束状态)
- 这个分解过程要持续进行到只剩下epsilon和单纯的字符
（对于digitmap来说就是分解到剩下x*#0-9和epsilon这几种情况）
NFA->DFA
子集构造法：使用一个表格构造子集；
第一行第一列的内容记作I；从起点开始，经过任意ε（包含经过0个），可以到达的结点的集合；
- 第一行第二列的内容记作Ia；表示，从该集合开始，经过一个a可以到达的节点的集合；所谓经过一个a的意思是 只能经过一个a，经过2个a的不算，经过的ε不算，epsilon随便经过，经过几个都可以
- 第一行第三列的内容记作Ib；表示，从该集合的起点开始，只经过一个b可以达到的节点的结合；同样，要求是经过且只经过一个b，对epsilon不做限制，限制b和epsilon之外的一切的路径；
- ……如果nfa经过简化之后包含有更多的路径，则继续向下写；
此时状态表如下
| i | ia | ib |
|---|---|---|
| 从起点出发，经过epsilon得到的子集，记作子集A | 以子集A中的元素为起点，分析a边推出的子集；记作子集B | 以子集A中的元素为起点，分析b边推出的子集；记作子集C |
| 子集B | 以子集B中的元素为起点，分析a边推出的子集…假设这里是状态B | 以子集B中的元素为起点，分析b边推出的子集；假设为子集D |
| etc…. | ….. | …… |
- 这样不断分析下去，子集的数量总是有限的，当再也找不出新的子集写到第一列中被分析，那么所有的子就完全被列出了；
然后可以构建DFA：从第一行开始一行一行的进行构建；从第一行可以构建出子集A经过a可以到达子集B，子集A经过b可以到达子集C；就这样一行一行的写出来
DFA的简化
假设当前存在ABCDE几个子集，进行切分，切分的规则如下
I，I发出的边数相同
- I，I发出的边相同
- 对应相同的边连接的状态属于同一个等价类
对于包含终态的子集来讲，第一步就会把这些包含终态的子集切分出来；然后对余下的子集的集合进行切分
DigitMap的构建
Q1.是否同时存在复数个DigitMap规则？
应当是存在的；as follow
//1. 规则1：本地电话匹配[2-8]xxxxxxx//2. 规则2：特殊服务号码10xxS.|11[02479]|11[13568]Sx.|12[026789]|121xx|12[3-5]Sx.|168xxxxx|1[79]xSx.|18xSx|200|201|20[2-9]xSx|400xS.|444S.|600x|800xxxxxxx|9xxxxSx.
如果一个号码拨入，依次进行match；以上面的例子来讲，如果1的匹配级别高于2的匹配级别，则使用规则1；否则使用规则2；
Q2.如何划分状态？
As follow
//1. 规则1：本地电话匹配[2-8]xxxxxxx//2. 规则2：特殊服务号码10xxS.|11[02479]|11[13568]Sx.|12[026789]|121xx|12[3-5]Sx.|168xxxxx|1[79]xSx.|18xSx|200|201|20[2-9]xSx|400xS.|444S.|600x|800xxxxxxx|9xxxxSx.
如果现在要针对规则1生成DFA应当如何实现？？
若有收获，就点个赞吧
0 人点赞
