FA-Finite Automata 有限自动机的实现思路
秒大刀 2007-03-23
最近在做一个对代码进行分析的简单工具，功能非常简单，对源代码文件进行分析，得到文件中的代码行数、注释行数和文件的总行数。我把它命名为代码计数器，也即对代码中的最基本特征进行统计，当然这个工具以后可以进行各种各样的扩充。
其中一个最基本的功能就是要对C#或者C++中的注释进行识别并统计。我画的FA如下所示：
学过编译原理的都知道手工实现这个FA的识别代码并不是一件很复杂的事情，一堆的if-else、for、while、swith就不信做不出来。这样的实现是没有问题的，但有没有其他的方法呢？
我试着考虑用面向对象的状态机转移去实现，即将每一个状态都抽象成一个State的对象，然后根据不同的条件这些状态在相互切换，并在切换的过程中触发特定的事件。然我这个小工具的需求就这么一点点，好像不值得，而且出来后的速度很难把握。Shift!
看着那些FA箭头指来指去，我觉得它怎么有点像goto呢？为什么不能用goto去实现这个识别过程呢？有了点子，做事就很快了。（为了尽量避免我绞尽脑汁给那么多的状态起英文名字，我只是简单的把它们进行编号，下面的代码也正好和状态的编号对应）
while (true)
{
State_1:
if (file.EndOfFile)
goto EndOfFile;
char c1 = file.GetChar();
if (c1 == '/')
goto State_2;
else if (char.IsWhiteSpace(c1))
goto State_1;
else
goto State_8;
State_2:
if (file.EndOfFile)
goto EndOfFile;
char c2 = file.GetChar();
if (c2 == '/')
goto State_3;
else if (c2 == '*')
goto State_5;
else
goto State_8;
State_3:
if (file.EndOfFile)
goto EndOfFile;
char c3 = file.GetChar();
if (c3 == '\n')
goto State_4;
else
goto State_3;
State_4:
count_remark++;
goto State_1;
State_5:
if (file.EndOfFile)
goto EndOfFile;
char c5 = file.GetChar();
if (c5 == '*')
goto State_6;
else
goto State_5;
State_6:
if (file.EndOfFile)
goto EndOfFile;
char c6 = file.GetChar();
if (c6 == '/')
goto State_7;
else
goto State_5;
State_7:
count_remark++;
goto State_1;
State_8:
if (file.EndOfFile)
goto EndOfFile;
char c8 = file.GetChar();
if (c8 == '/')
goto State_9;
else if (c8 == '\n')
goto State_10;
else
goto State_8;
State_9:
file.BackChar('/');
count_code++;
goto State_1;
State_10:
count_code++;
goto State_1;
}
EndOfFile:
return GetResult();
}
也许上面的代码很糟糕，但你可以发现它和前面的FA图有出人意料的相似，甚至可以用工具直接转过来。这也就是我所要说的，只要你得到了FA就用goto实现识别，也许会有一些弊端，但迅速的实现会让你充满自信，而且这种代码相对而言也有较好的可读性。
用goto实现FA：直观，编码迅速简单
Goto有它的用处，请不要无情批判。凡事得客观点，做人得厚道点。
评论