编译原理 词法分析 RE NFA DFA MDFA
所有的算法实现:https://github.com/SZFHH/compiler
效果
以下所有的图片来自网易云课堂 华保健老师的编译原理
RE->NFA Thompson算法
具体实现中先把正则表达式变成了一棵正则树,这部分是由递归下降算法完成的。然后再由正则树转换成NFA。
NFA->DFA 子集构造算法
DFA中的每个点包含了NFA中的n个点,这n个点组成一个set。从set中的每个点出发,沿着eps边能到达的所有点组成新的set,这个操作为eps_closure。从set中的每个点出发,沿着某个字符边能到的所有点组成新的set,这个操作为delta。初始集合为eps_closure(n0),n0为NFA的起始结点。通过delta和eps_closure操作就能不断得到新的DFA结点(set),最多为2^n个,把没有出现过的结点加入worklist,如果worklist为空,循环结束。
eps_closure可以用DFS或者BFS。delta只走一次,eps_closure沿着eps边走到不能走为止。
DFA->MDFA Hopcrpft算法
从DFA得到的图可能是可以合并的,如下图。
q1,q2,q3,可以合并为一个accept结点,并且连接一条自环b,c。
Hopcrpft算法的思想是先把所有点按accept和非accpet分为两堆,然后对每一堆,按每个字符进行分割。这样就可以把每一堆分成很多个小堆,重复这个过程,直到没有新的堆出现。
分割的具体操作:假设有堆A和B,当前以字符c对A进行分割,如果A中的结点na和B中的结点nb以c相连,那就把堆A分成{na}和A\{na}。
驱动代码
上述代码满足最长匹配原则。