正则表达式引擎的构建——基于编译原理DFA（龙书第三章）——5 DFA最小化

正则表达式 前端之家
前端之家收集整理的这篇文章主要介绍了正则表达式引擎的构建——基于编译原理DFA（龙书第三章）——5 DFA最小化，前端之家小编觉得挺不错的，现在分享给大家，也给大家做个参考。
分类：C++算法编译原理 2013-07-18 23:39 421人阅读 评论(0) 收藏 举报
正则表达式 编译原理 DFA优化

目录(?)[+]

完整引擎代码在github上，地址为：https://github.com/sun2043430/RegularExpression_Engine.git


DFA最小化的算法原理

“DFA状态最小化算法的工作原理是将一个DFA的状态集合分划成多个组，每个组中的各个状态之间相互不可区分。然后，将每个组中的状态合并成状态最少DFA的一个状态。算法在执行过程中维护了状态集合的一个分划，分划中的每个组内的各个状态不能区分，但是来自不同组的任意两个状态是可区分的。当任意一个组不能再被分解为更小的组时，这个分划就不能再进一步精化，此时我们就得到了状态最少的DFA。”

——《编译原理》例3.38

起始时，该分划包含两个组：接受状态组和非接受状态组。


实例

如图（编译原理 图3-36）

首先我们将ABCDE分划到两个组中{ABCD}和{E}，{E}是接受状态组，且不可被再分割。

{ABCD}是可分割的，所以我们考虑所有可能的转换。

先看转换字符a：

A->a->B

B->a->B

C->a->B

D->a->B

所以ABCD经过a到达的集合是{B}，而{B}属于{ABCD}这一个集合，所以我们说{ABCD}在输入字符为a时是不可分划的。

在来看转换字符b：

A->b->C

B->b->D

C->b->C

D->b->E

到达的集合是{CDE}，其中CD属于{ABCD}分划，E属于{E}分划。

所以我们说{ABCD}在输入字符为b时是不可分划的。按照输入b转换到的组，我们将{ABCD}分划为{ABC}和{D}两个组。同时将{ABCD}从组集合中删除。因为{ABCD}已经分划为{ABC}和{D}。

接下来看{ABC}，先看在字符a上的转换：

A->a->B

B->a->B

C->a->B

因为全部都是到达的B，所以不可分划。

再看在字符b上的转换：

A->b->C

B->b->D

C->b->C

其中C属于{ABC}组，D属于{D}组。所以{ABC}可以分划为{AC}和{B}。

最后看{AC}组，A和C在字符a上都转换到B，在字符b上都转换到C，所以{AC}是不可分划的组。

最后得到的分组情况为：

{AC}，{B}，{D}，{E}。

同一个组中只需要保留一个节点即可（因为同一个组的节点在转换上都是相同的），所以我们直接将C节点去除，保留A节点（因为A节点是开始状态节点）。最终得到的状态最小DFA的转换表为：


代码实现（关键代码）

[cpp] view plain copy print ?
  1. BOOLCDFA::FindRelationNode(list<DFANodeRelation>&lstNodeRelation,
  2. intnIdxFrom,unsignedcharch,int&nMapToIdx)
  3. {
  4. list<DFANodeRelation>::iteratorit=lstNodeRelation.begin();
  5. for(;it!=lstNodeRelation.end();it++)
  6. {
  7. if(it->m_nIdxFrom==nIdxFrom&&it->m_ch==ch)
  8. nMapToIdx=it->m_nIdxTo;
  9. returnTRUE;
  10. }
  11. }
  12. returnFALSE;
  14. intCDFA::FindIdxInListSet(intnMapToIdx,list<set<int>>&lstSet)
  15. inti=0;
  16. for(list<set<int>>::iteratorit=lstSet.begin();it!=lstSet.end();it++,i++)
  17. set<int>&setIdx=*it;
  18. for(set<int>::iteratoritInt=setIdx.begin();itInt!=setIdx.end();itInt++)
  19. if(nMapToIdx==*itInt)
  20. returni;
  21. return-1;
  23. BOOLCDFA::PartitionOneGroup(list<set<int>>&lstSet,set<int>&setOneGroup,85); line-height:18px"> list<DFANodeRelation>&lstNodeRelation,
  24. map<int,87); background-color:inherit; font-weight:bold">int>>&mapPartitionInfo)
  25. BOOLbRet=FALSE;
  26. list<DFANodeRelation>::iteratoritRelation;
  27. set<unsignedchar>setChar;
  28. set<int>setMapToIdx;
  29. try
  30. //collecteachnode'stranslationcharintheset
  31. for(set<int>::iteratorit=setOneGroup.begin();it!=setOneGroup.end();it++)
  32. for(itRelation=lstNodeRelation.begin();itRelation!=lstNodeRelation.end();itRelation++)
  33. if(itRelation->m_nIdxFrom==*it)
  34. setChar.insert(itRelation->m_ch);
  35. //endcollect
  36. for(set<unsignedchar>::iteratorit=setChar.begin();it!=setChar.end();it++)
  37. mapPartitionInfo.clear();
  38. intnMapToIdx=-1;//indicatemaptoadeadstate,therenotranslationforthispairofnode/char
  39. int>::iteratoritNodeId=setOneGroup.begin();itNodeId!=setOneGroup.end();itNodeId++)
  40. if(FindRelationNode(lstNodeRelation,*itNodeId,*it,nMapToIdx))
  41. intnIdx=FindIdxInListSet(nMapToIdx,lstSet);
  42. if(nIdx==-1)
  43. assert(FALSE);
  44. mapPartitionInfo[nIdx].insert(*itNodeId);
  45. else
  46. mapPartitionInfo[-1].insert(*itNodeId);
  47. if(mapPartitionInfo.size()>1)//haddistinguish
  48. break;
  49. catch(...)
  50. gotoExit0;
  51. bRet=TRUE;
  52. Exit0:
  53. returnbRet;
  54. BOOLCDFA::PartitionGroups(list<set< list<set<int>>::iteratorit=lstSet.begin();
  55. int>>mapPartitionInfo;
  56. //usedmaptorecordthenodecantranslatetowhichgroup,
  57. //theint(mapkey)isgroupid.
  58. //theset<int>containthenodeIDthatcantranslatetothegroup.
  59. for(;it!=lstSet.end();)
  60. mapPartitionInfo.clear();
  61. int>&setOneGroup=*it;
  62. CHECK_BOOL(PartitionOneGroup(lstSet,setOneGroup,lstNodeRelation,mapPartitionInfo));
  63. //meansthatcurrentgroupcanpartition
  64. int>>::iteratoritM=mapPartitionInfo.begin();
  65. for(;itM!=mapPartitionInfo.end();itM++)
  66. lstSet.push_back(itM->second);
  67. catch(...)
  68. gotoExit0;
  69. it=lstSet.erase(it);//ifagrouphadpartition,thegroupneeddeleteinthelist
  70. it++;
  71. /**
  72. @briefMinimizeDFA
  73. @paramnSetSizenodecount
  74. @paramlstNodeRelationnoderelationtable
  75. @paramsetAcceptingIdxsetforAcceptingstatusnode'sindex
  76. @paramlstSetforsavetheresult
  77. @returnTRUE,success;otherwisemeansfail.
  78. */
  79. BOOLCDFA::MinimizeDFA(intnNodeCount,87); background-color:inherit; font-weight:bold">int>&setAcceptingIdx,87); background-color:inherit; font-weight:bold">int>>&lstSet
  80. )
  81. int>setUnAccepting;
  82. assert(nNodeCount>=1);
  83. assert(setAcceptingIdx.size()!=0);
  84. assert(lstNodeRelation.size()!=0);
  85. lstSet.clear();
  86. lstSet.push_back(setAcceptingIdx);
  87. //getunAcceptingset
  88. for(inti=0;i<nNodeCount;i++)
  89. if(setAcceptingIdx.find(i)==setAcceptingIdx.end())
  90. setUnAccepting.insert(i);
  91. if(setUnAccepting.size()>0)
  92. lstSet.push_back(setUnAccepting);
  93. CHECK_BOOL(PartitionGroups(lstSet,lstNodeRelation));
  94. returnbRet;
  95. }

完整引擎代码在github上，地址为： https://github.com/sun2043430/RegularExpression_Engine.git

猜你在找的正则表达式相关文章

常用正则表达式-手机号、身份证、邮箱
一、校验数字的表达式 1 数字：^[0-9]*$ 2 n位的数字：^d{n}$ 3 至少n位的数字：^d{n,}$ 4...
JS正则表达式详解
正则表达式非常有用，查找、匹配、处理字符串、替换和转换字符串，输入输出等。下面整理一...
组内正则培训记录
0. 注： 不同语言中的正则表达式实现都会有一些不同。下文中的代码示例除特别说明的外，都...
高级正则表达式技术（Python版）
 正则表达式是从信息中搜索特定的模式的一把瑞士军刀。它们是一个巨大的工具库，其中的...
史上最全最常用的正则表达式
一、校验数字的表达式 数字：^[0-9]*$ n位的数字：^\d{n}$ 至少n位的数字：^\d{n,...
正则表达式工具
正则表达式初步
分享5个可视化的正则表达式编辑工具
　　正则表达式使用单个字符串来描述、匹配一系列符合某个句法规则的字符串。在很多文本编...
分享5个可视化的正则表达式编辑工具
正则表达式使用单个字符串来描述、匹配一系列符合某个句法规则的字符串。在很多文本编辑器...
[知识积累]--正则表达式记忆表
在工作中常常遇到正则表达式问题，有时候又会忘记这则的语法。 下面就分享一份正则表达式记...
算法设计模式多媒体技术正则表达式ElasticsearchFlinkHadoopIDE
受约束摘*day25Java常用类库置信lamda留存持续录入年后正则表达式303.17regularexpre匹多模适20130322基础理论pathmunge涵义reectok需要转义的特资源分享validationex简明魔法里弄形如源码实现完备actionscript