使用MPLex实现语法高亮显示的功能代码解释
在前面的文章使用MPLex实现语法高亮显示的功能里面，贴了一个实现语法高亮显示的代码，是采用类似于编译器自动状态机的方法来判断代码里面每个单词的类型。
有限自动状态机是表示有限个状态以及在这些状态之间的转移和动作等行为的数学模型。状态之间只有一个转移的动作。 MPLex或者说相关软件（例如flex）通过分析用户给定的词法文件，自动生成相应的有限自动机，将自动机的状态保存在一个表里面。
#include <iostream>
#include <string>
using namespace std;
enum TokenType
{
BOOM_ERROR = -1, // 啊哈，出错了
NUMBER = 1,
IDENTIFIER = 2,
IF = 4
};
int DFA_Table[][37] = {
// 0 1 2 3 4 5 6 7 8 9 a b c d e f g h i j k l m n o p q r s t u v w x y z !
{1,1,1,1,1,1,1,1,1,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,-1}, // s0 -- 起始状态
{1,1,1,1,1,1,1,1,1,1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1}, // s1 -- 到这里说明是数字
{3,3,3,3,3,3,3,3,3,3,2,2,2,2,2,4,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,-1}, // s2 -- 变量
{2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,-1},
{2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,-1} // s4 -- 这是IF
};
//
// Match:
// 给定一个字符串str，判断这个字符串的类型
//
// 例子:
// if, 返回IF
// 数字,返回NUMBER
// 变量,返回IDENTIFIER
//
TokenType Match(string str)
{
int state = 0;
for (string::iterator iter = str.begin();
iter != str.end();
++iter )
{
char c = *iter;
int index = 0;
if ( c >= '0' && c <= '9' )
{
index = c - '0';
}
else if (c >= 'a' && c <= 'z')
{
index = c - 'a' + 10; // a列在DFA_Table中的索引值
}
else
{
index = 36; // !列在DFA_Table中的索引值，到这里说明不匹配了
}
state = DFA_Table[state][index];
if (state == BOOM_ERROR)
break;
}
return (TokenType)state;
}
int g_line = 0;
void Print(TokenType type)
{
switch (type)
{
case BOOM_ERROR:
cout << ++g_line << ": BOOM_ERROR\n" <<>
break;
case IF:
cout << ++g_line << ": IF\n" <<>
break;
case NUMBER:
cout << ++g_line << ": NUMBER\n" <<>
break;
case IDENTIFIER:
cout << ++g_line << ": IDENTIFIER\n" <<>
break;
default:
cout << ++g_line << ": Error\n" <<>
break;
}
}
int main()
{
Print(Match("if"));
Print(Match("iff"));
Print(Match("if0"));
Print(Match("0if"));
Print(Match("i0f"));
Print(Match("ia"));
Print(Match("01"));
Print(Match("123"));
Print(Match("1f"));
Print(Match("abcd"));
Print(Match("ab"));
Print(Match("a"));
Print(Match("0"));
Print(Match("i"));
Print(Match("_"));
return 0;
}
例子1：一个简单的DFA表驱动匹配程序
上面的例子里，字符串的匹配或者说是分类是通过有限自动机来完成的，有限自动机在代码里面的表示就是那个二维数组 DFA_Table。DFA_Table的每一行(DFA_Table[i])表示有限自动机的状态，而列表示从当前状态可以执行的状态转换（Transfer）。例如在匹配的时候，程序先从DFA_Table[0]，也就是起始状态开始，如果第一个字符串是i，则根据DFA_Table[0]['i']指定的转换规则跳转到下一个状态（State）去，这里下一个状态是2，也就是DFA_Table的第三行，再根据str的下一个字符来确定要转换的状态。匹配过程一直循环到字符串被全部处理掉，这时程序判断当前的状态是不是一个可以接受的状态（Acceptable State），也就是说这个状态是否在TokenType中定义，如果状态在TokenType中定义，那好，我们给出的字符串匹配成功，否则……BOOM。
我在Match函数的for循环中用了if判断来根据当前的字符选择正确的索引，其实如果你不嫌麻烦的话，你的Match函数中的for循环可以简化成这样：
for (string::iterator iter = str.begin();
iter != str.end();
++iter )
{
state = DFA_Table[state][*iter];
}
前提是愿意把DFA_Table扩展成一个127 * 5的二维表格。
知道了有限自动机是如何匹配代码里的关键字以后，接下来要做的就是生成保存有限自动机里面的状态的状态表了。生成状态表的工作就由MPLex来完成了，因为手工写实在是太复杂了。下面这个词法定义文件就是告诉MPLex有哪些元素需要进行特殊处理，例如将注释、字符串、数字和关键字与其他普通代码文本区分开来。
%namespace Coder.LexScanner
%x COMMENT
White0 [ \t\r\f\v]
White {White0}|\n
CmntStart \/\*
CmntEnd \*\/
ABStar [^\*\n]*
%%
\'[^\'\n]{0,3}\'
\"[^\"\n]*\"
\/\/\n
\'[^\'\n]*\n
\**
\**
[^\n]*\**
if
while
do
abstract
as
base
bool
break
byte
case
catch
char
checked
class
const
continue
decimal
default
delegate
double
else
enum
event
explicit
extern
false
finally
fixed
float
for
foreach
goto
implicit
in
int
interface
internal
is
lock
long
namespace
new
null
object
operator
out
override
params
private
protected
public
readonly
ref
return
sbyte
sealed
short
sizeof
stackalloc
static
string
struct
switch
this
throw
true
try
typeof
uint
ulong
unchecked
unsafe
ushort
using
virtual
volatile
void
[0-9]+
[a-zA-Z_][a-zA-Z0-9_]*
+
\n
.
%%
Scanner.lex文件
上面代码里面的TokenType枚举需要在另外的C#文件里面定义：
using System;
namespace Coder.LexScanner
然后使用命令根据词法文件生成词法匹配的C#代码：
Mplex.exe scanner.lex
最后为了判断生成的C#代码是否有用，我写了一个小程序调用词法匹配函数测试了一下：
using System;
using Coder.LexScanner;
public class TestClass
实际上，Visual Studio的代码高亮显示功能也是通过Mplex和Mppg实现，这样做的好处是，新的编程语言可以以插件的形式加入到Visual Studio里面来，而Visual Studio照样能够在编辑新编程语言的程序时，实现高亮显示以及其他，例如变量和函数定义查找、智能提示框之类的功能。