C#词法分析器之构造NFA详解
有了上一节中得到的正则表达式，那么就可以用来构造NFA了。NFA可以很容易的从正则表达式转换而来，也有助于理解正则表达式表示的模式。
一、NFA的表示方法在这里，一个NFA至少具有两个状态：首状态和尾状态，如图1所示，正则表达式$t$对应的NFA是N(t)，它的首状态是$H$，尾状态是$T$。图中仅仅画出了首尾两个状态，其它的状态和状态间的转移都没有表示出来，这是因为在下面介绍的递归算法中，仅需要知道NFA的首尾状态，其它的信息并不需要关心。
namespaceCyjb.Compiler.Lexer{
classNfa{
//获取或设置NFA的首状态。
NfaStateHeadState{get;set;}
//获取或设置NFA的尾状态。
NfaStateTailState{get;set;}
//在当前NFA中创建一个新状态。
NfaStateNewState(){}
}
}
NFA的状态中，必要的属性只有三个：符号索引、状态转移和状态类型。只有接受状态的符号索引才有意义，它表示当前的接受状态对应的是哪个正则表达式，对于其它状态，都会被设为-1。
状态转移表示如何从当前状态转移到下一状态，虽然NFA的定义中，每个节点都可能包含多个ϵ 转移和多个字符转移（就是边上标有字符的转移）。但在这里，字符转移至多有一个，这是由之后给出的NFA构造算法的特点所决定的。
状态类型则是为了支持向前看符号而定义的，它可能是Normal、TrailingHead和Trailing三个枚举值之一，这个属性将在处理向前看符号的部分详细说明。
下面是NfaState类的定义：
namespaceCyjb.Compiler.Lexer{
classNfaState{
//获取包含当前状态的NFA。
NfaNfa;
//获取当前状态的索引。
intIndex;
//获取或设置当前状态的符号索引。
intSymbolIndex;
//获取或设置当前状态的类型。
NfaStateTypeStateType;
//获取字符类的转移对应的字符类列表。
ISet<int>CharClassTransition;
//获取字符类转移的目标状态。
NfaStateCharClassTarget;
//获取ϵ转移的集合。
IList<NfaState>EpsilonTransitions;
//添加一个到特定状态的转移。
voidAdd(NfaStatestate,charch);
//添加一个到特定状态的转移。
voidAdd(NfaStatestate,stringcharClass);
//添加一个到特定状态的ε转移。
voidAdd(NfaStatestate);
}
}
我在NfaState类中额外定义的两个属性Nfa和Index单纯是为了方便状态的使用。$\epsilon$转移直接被定义为一个列表，而字符转移则被定义为两个属性：CharClassTarget和CharClassTransition，CharClassTarget表示目标状态，CharClassTransition表示字符类，字符类会在下面详细解释。
NfaState类中还定义了三个Add方法，分别是用来添加单个字符的转移、字符类的转移和$\epsilon$转移的。
二、从正则表达式构造NFA
这里使用的递归算法是McMaughton-Yamada-Thompson算法（或者叫做Thompson构造法），它比Glushkov构造法更加简单易懂。
2.1基本规则
- 对于正则表达式$\epsilon$，构造如图2(a)的NFA。对于包含单个字符$a$的正则表达式$\bf{a}$，构造如图2(b)的NFA。
上面的第一个基本规则在这里其实是用不到的，因为在正则表达式的定义中，并没有定义$\epsilon$。第二个规则则在表示字符类的正则表达式CharClassExp类中使用，代码如下：
voidBuildNfa(Nfanfa){
nfa.HeadState=nfa.NewState();
nfa.TailState=nfa.NewState();
//添加一个字符类转移。
nfa.HeadState.Add(nfa.TailState,charClass);
}
2.2归纳规则
有了上面的两个基本规则，下面介绍的归纳规则就可以构造出更复杂的NFA。
假设正则表达式s 和t 的NFA分别为N(s) 和N(t)。
1.对于r=s|t，构造如图3的NFA，添加一个新的首状态H 和新的尾状态T，然后从H 到N(s) 和N(t) 的首状态各有一个ϵ 转移，从H 到N(s) 和N(t) 的尾状态各有一个ϵ 转移到新的尾状态T。很显然，到了H 后，可以选择是匹配N(s) 或者是N(t)，并最终一定到达T。
这里必须要注意的是，$N(s)$和$N(t)$中的状态不能够相互影响，也不能存在任何转移，否则可能会导致识别的结果不是预期的。
AlternationExp类中的代码如下：
voidBuildNfa(Nfanfa){
NfaStatehead=nfa.NewState();
NfaStatetail=nfa.NewState();
left.BuildNfa(nfa);
head.Add(nfa.HeadState);
nfa.TailState.Add(tail);
right.BuildNfa(nfa);
head.Add(nfa.HeadState);
nfa.TailState.Add(tail);
nfa.HeadState=head;
nfa.TailState=tail;
}
2.对于$r=st$，构造如图4的NFA，将$N(s)$的首状态作为$N(r)$的首状态，$N(t)$的尾状态作为$N(r)$的尾状态，并在$N(s)$的尾状态和$N(t)$的首状态间添加一条$\epsilon$转移。
ConcatenationExp类中的代码如下：
voidBuildNfa(Nfanfa){
left.BuildNfa(nfa);
NfaStatehead=nfa.HeadState;
NfaStatetail=nfa.TailState;
right.BuildNfa(nfa);
tail.Add(nfa.HeadState);
nfa.HeadState=head;
}
LiteralExp也可以看成是多个CharClassExp连接而成，所以可以多次应用这个规则来构造相应的NFA。
3.对于$r=s*$，构造如图5的NFA，添加一个新的首状态$H$和新的尾状态$T$，然后添加四条$\epsilon$转移。不过这里的正则表达式定义中，并没有显式定义$r*$，因此下面给出RepeatExp对应的规则。
4.对于$r=s\{m,n\}$，构造如图6的NFA，添加一个新的首状态$H$和新的尾状态$T$，然后创建$n$个$N(s)$并连接起来，并从第$m-1$个$N(s)$开始，都添加一条尾状态到$T$的$\epsilon$转移（如果$m=0$，就添加从$H$到$T$的$\epsilon$转移）。这样就保证了至少会经过$m$个$N(s)$，至多会经过$n$个$N(s)$。
不过如果$n=\infty$，就需要构造如图7的NFA，这时只需要创建$m$个$N(s)$，并在最后一个$N(s)$的首尾状态之间添加一个类似于$s*$的$\epsilon$转移，就可以实现无上限的匹配了。如果此时再有$m=0$，情况就与$s*$相同了。
综合上面的两个规则，得到了RepeatExp类的构造方法：
voidBuildNfa(Nfanfa){
NfaStatehead=nfa.NewState();
NfaStatetail=nfa.NewState();
NfaStatelastHead=head;
//如果没有上限，则需要特殊处理。
inttimes=maxTimes==int.MaxValue?minTimes:maxTimes;
if(times==0){
//至少要构造一次。
times=1;
}
for(inti=0;i<times;i++){
innerExp.BuildNfa(nfa);
lastHead.Add(nfa.HeadState);
if(i>=minTimes){
//添加到最终的尾状态的转移。
lastHead.Add(tail);
}
lastHead=nfa.TailState;
}
//为最后一个节点添加转移。
lastHead.Add(tail);
//无上限的情况。
if(maxTimes==int.MaxValue){
//在尾部添加一个无限循环。
nfa.TailState.Add(nfa.HeadState);
}
nfa.HeadState=head;
nfa.TailState=tail;
}
5.对于$r=s/t$这种向前看符号，情况要特殊一些，这里仅仅是将$N(s)$和$N(t)$连接起来（同规则2）。因为匹配向前看符号时，如果$t$匹配成功，那么需要进行回溯，来找到$s$的结尾（这才是真正匹配的内容），所以需要将$N(s)$的尾状态标记为TrailingHead类型，并将$N(T)$的尾状态标记为Trailing类型。标记之后的处理，会在下节转换为DFA时说明。
2.3正则表达式构造NFA的示例
这里给出一个例子，来直观的看到一个正则表达式(a|b)*baa是如何构造出对应的NFA的，下面详细的列出了每一个步骤。
最后得到的NFA就如上图所示，总共需要14个状态，在NFA中可以很明显的区分出正则表达式的每个部分。这里构造的NFA并不是最简的，因此与上一节《C#词法分析器（三）正则表达式》中的NFA不同。不过NFA只是为了构造DFA的必要存在，不用费工夫化简它。
三、划分字符类
现在虽然得到了NFA，但这个NFA还是有些细节问题需要处理。例如，对于正则表达式[a-z]z，构造得到的NFA应该是什么样的？因为一条转移只能对应一个字符，所以一个可能的情形如图9所示。
前两个状态间总共需要26个转移，后两个状态间需要1个转移。如果正则表达式的字符范围再广些呢，比如Unicode范围？添加6万多条转移，显然无论是时间还是空间都是不能承受的。所以，就需要利用字符类来减少需要的转移个数。
字符类指的是字符的等价类，意思是一个字符类对应的所有字符，它们的状态转移完全是相同的。或者说，对自动机来说，完全没有必要区分一个字符类中的字符——因为它们总是指向相同的状态。
就像上面的正则表达式[a-z]z来说，字符a-y完全没有必要区分，因为它们总是指向相同的状态。而字符z需要单独拿出来作为一个字符类，因为在状态1和2之间的转移使得字符z和其它字符区分开来了。因此，现在就得到了两个字符类，第一个字符类对应字符a-y，第二个字符类对应字符z，现在得到的NFA如图10所示。
使用字符类之后，需要的转移个数一下就降到了3个，所以在处理比较大的字母表时，字符类是必须的，它即能加快处理速度，又能降低内存消耗。
而字符类的划分，就是将Unicode字符划分到不同的字符类中的过程。我目前采用的算法是一个在线算法，即每当添加一个新的转移时，就会检查当前的字符类，判断是否需要对现有字符类进行划分，同时得到转移对应的字符类。字符类的表示是使用一个ISet<int>，因为一个转移可能对应于多个字符类。
输入：新添加的转移$t$
输出：新添加的转移对应的字符类$cc_t$
foreach(每个现有的字符类$CC$){
$cc_1=\left\{c|c\int\&c\inCC\right\}$
if($cc_1=\emptyset$){continue;}
$cc_2=\left\{c|c\inCC\&c\notint\right\}$
将$CC$划分为$cc_1$和$cc_2$
$cc_t=cc_1\cupcc_t$
$t=\left\{c|c\int\&c\notinCC\right\}$
if($t=\emptyset$){break;}
}
这里需要注意的是，每当一个现有的字符类$CC$被划分为两个子字符类$cc_1$和$cc_2$，之前的所有包含$CC$的转移对应的字符类都需要更新为$cc_1$和$cc_2$，以包含新添加的子字符类。
我在CharClass类中实现了该算法，其中充分利用了CharSet类集合操作效率高的特点。
ViewCode
HashSet<int>GetCharClass(stringcharClass){
intcnt=charClassList.Count;
HashSet<int>result=newHashSet<int>();
CharSetset=GetCharClassSet(charClass);
if(set.Count==0){
//不包含任何字符类。
returnresult;
}
CharSetsetClone=newCharSet(set);
for(inti=0;i<cnt&&set.Count>0;i++){
CharSetcc=charClassList[i];
set.ExceptWith(cc);
if(set.Count==setClone.Count){
//当前字符类与set没有重叠。
continue;
}
//得到当前字符类与set重叠的部分。
setClone.ExceptWith(set);
if(setClone.Count==cc.Count){
//完全被当前字符类包含，直接添加。
result.Add(i);
}else{
//从当前的字符类中剔除被分割的部分。
cc.ExceptWith(setClone);
//更新字符类。
intnewCC=charClassList.Count;
result.Add(newCC);
charClassList.Add(setClone);
//更新旧的字符类......
}
//重新复制set。
setClone=newCharSet(set);
}
returnresult;
}
四、多条正则表达式、限定符和上下文
通过上面的算法，已经可以实现将单个正则表达式转换为相应的NFA了，如果有多条正则表达式，也非常简单，只要如图11那样添加一个新的首节点，和多条到每个正则表达式的首状态的$\epsilon$转移。最后得到的NFA具有一个起始状态和$n$个接受状态。
对于行尾限定符，可以直接看成预定义的向前看符号，r\$可以看成r/\n或r/\r?\n（这样可以支持Windows换行和Unix换行），事实上也是这么做的。
对于行首限定符，仅当在行首时才会匹配这条正则表达式，可以考虑把这样的正则表达式单独拿出来——当从行首开始匹配时，就使用行首限定的正则表达式进行匹配；从其它位置开始匹配时，就使用其它的正则表达式进行匹配。
当然，即使是从行首开始匹配，非行首限定的正则表达式也是可以匹配的，所以就将所有正则表达式分为两个集合，一个包含所有的正则表达式，用于从行首匹配是使用；另一个只包含非行首限定的正则表达式，用于从其它位置开始匹配时使用。然后，再为这两个集合分别构造出相应的NFA。
对于我的词法分析器，还会支持上下文。可以为每个正则表达式指定一个或多个上下文，这个正则表达式就会只在给定的上下文环境中生效。利用上下文机制，就可以更精细的控制字符串的匹配情况，还可能构造出更强大的词法分析器，例如可以在匹配字符串的同时处理字符串内的转义字符。
上下文的实现与上面行首限定符的思想相同，就是为将每个上下文对应的正则表达式分为一组，并分别构造NFA。如果某个正则表达式属于多个上下文，就会将它复制并分到多个组中。
假设现在定义了$N$个上下文，那么加上行首限定符，总共需要将正则表达式分为$2N$个集合，并为每个集合分别构造NFA。这样不可避免的会有一些内存浪费，但字符串匹配速度会非常快，而且可以通过压缩的办法一定程度上减少内存的浪费。如果通过为每个状态维护特定的信息来实现上下文和行首限定符的话，虽然NFA变小了，但存储每个状态的信息也会消耗额外的内存，在匹配时还会出现很多回溯的情况（回溯是性能杀手），效果可能并不好。
虽然需要构造$2N$个NFA，但其实只需要构造一个具有$2N$个起始状态的NFA即可，每个起始状态对应于一个上下文的（非）行首限定正则表达式集合，这样做是为了保证这$2N$个NFA使用的字符类是同一个，否则后面处理起来会非常麻烦。
现在，正则表达式对应的NFA就构造好了，下一篇文章中，我就会介绍如何将NFA转换为等价的DFA。
相关文章
- 完美解决C#中拖动splitContainer分割线时显示虚线问题
- [C#.NET 拾遗补漏]10：理解 volatile 关键字（去除 Release 版本反向优化）
- 应用c#读取带cookie的http数据详解编程语言
- C#后台调用前台javascript的五种方法小结
- C#短时间内产生大量不重复的随机数
- C#.net中的类型转换详细介绍
- 浅谈C#中Process类的使用详解
- 解决C#程序只允许运行一个实例的几种方法详解
- 深入C#内存管理以及优化的方法详解
- 解决C#获取鼠标相对当前窗口坐标的实现方法
- 深入Unix时间戳与C#DateTime时间类型互换的详解
- C#中的cookie编程简单实例与说明
- c#winform读取xml文件创建菜单的代码
- C#异常处理详解
- C#中FormClosing与FormClosed的区别详细解析
- C#中跨线程访问控件问题解决方案分享
- linux操作系统安装MONO执行C#程序的详解步骤
- c#继承与多态使用示例
- C#事件访问器详解
- C#中的多线程多参数传递详解
- c#序列化详解示例
- c#线程同步使用详解示例
- c#批量上传图片到服务器示例分享
- c#实现metro文件压缩解压示例
- c#实现pdf的另存为功能
- C#中Equality和Identity浅析
- C#的File类实现文件操作实例详解