Ragel：强大的可嵌入动作的状态机生成器

大家好，欢迎来到IT知识分享网。

开篇

回忆一下我们平常是怎么使用正则表达式的，先搜索一下对应语言的正则匹配的API接口，它们通常需要接收一个subject和一个pattern，即待匹配的字符串和模式串。使用这些API时只需要把subject和pattern交给它们，然后就等待着返回匹配结果就行了，最后将匹配出来的结果用到我们自己的程序逻辑中。对于每天专注于编写业务代码的程序员们来说，这样如黑匣子般使用正则表达式也就够了，但是如果你对正则匹配引擎的工作原理有所了解的话，那我们今天介绍的Ragel能帮你更大地发掘正则表达式的能力，让你能够在正则匹配的过程中也能做很多事情，而不是只能简单的等待API返回结果。

要理解Ragel的能力，需要首先理解正则匹配的基石 — 有限状态自动机，Ragel的核心就是基于此，所以我们先从有限状态自动机开始。

有限状态自动机

有限状态自动机（finite-state machine，FSM or finite-state automaton，FSA），后文统一用FSM来代表，是表示有限个状态以及在这些状态之间的转移和动作等行为的数学计算模型。FSM是在自动机理论和计算理论中研究的一类自动机，算是比较简单的自动机，更复杂的自动机还有下推自动机、线性有界自动机等等。

• age >= 45
• int age = 40
• 2+3*5

为了简化，这三个语句中我们只考虑四类Token，分别是标识符(Id)、数字字面量（IntLiteral）、>(GT)、>=(GE)。用正则文法表示如下：

Id : [a-zA-Z_]([a-zA-Z_] | [0-9])* IntLiteral: [0-9]+ GT : '>' GE : '>=' 

上图中的圆圈有单线的也有双线的。双线的意思是这个状态已经是一个合法的 Token 了，单线的意思是这个状态还是临时状态。按照这 5 种状态迁移过程，你很容易写出程序。

词法分析的过程就是识别 Token 的过程，也是是 FSM 状态迁移的过程。其中，FSAM分为确定的有限自动机（DFA）和非确定的有限自动机（NFA）。

DFA 的特点是，在任何一个状态，我们基于输入的字符串，都能做一个确定的转换，比如我们上面的那个例子。

NFA 的特点是，它存在某些状态，针对某些输入，不能做一个确定的转换，这又细分成两种情况：

• 对于一个输入，它有两个状态可以转换。
• 存在ε转换（空转换）。也就是没有任何输入的情况下，也可以从一个状态迁移到另一个状态。

在图中状态1的节点输入 b 时，这个状态是有两条路径可以选择的，所以这个有限自动机是一个 NFA。

上面这个 NFA 还有引入ε转换的画法，它们是等价的。实际上，下面这个加入了ε转换的等价NFA 可以更方便的通过写程序，分析对应的正则表达式来自动生成出来。

NFA 算法的特点是因为存在多条可能的路径，所以运行过程中需要试探和回溯，遍历所有可能路径。在比较极端的情况下，回溯次数会非常多，性能会变得非常慢。特别是当处理类似 s* 这样的语句时，因为 s 可以重复 0 到无穷次，所以在匹配字符串时，可能需要尝试很多次。

因为NFA 的运行可能导致大量的回溯，所以能否将 NFA 转换成 DFA，让字符串的匹配过程更简单呢？如果能的话，那整个过程都可以自动化，从正则表达式到 NFA，再从 NFA 到 DFA。确实有这样的算法，那就是子集构造法。但是由NFA生产的DFA也有缺点，DFA 可能有很多个状态。

假设原来 NFA 的状态有 n 个，那么把它们组合成不同的集合，可能的集合总数是 2 的 n 次方个。比如NFA有 13 个状态，最坏的情况下，生成的 DFA 可能有 2 的 13 次方，也就是 8192 个状态，会占据更多的内存空间。而且生成这个 DFA 本身也需要消耗一定的计算时间。

当然了，这种最坏的状态很少发生，所以也要具体情况具体对待。

Ragel

好的，了解了有限状态自动机的知识之后，我们就可以进入正题，开始学习Ragel了。

首先，Rage为何物。Ragel是一个软件工具，它允许将用户的操作代码嵌入到正则表达式的对应状态机的状态转换中，当从状态n到状态m的转换发生时，状态机会执行用户操作代码。它从自己定义的高级语法中编译出可执行的、嵌入了用户操作代码的状态机程序代码，生成的代码可以是C、C、++、Object-C、D、Go、Java和Ruby。

也就是说，Ragel最大的作用就是可以在FSM的状态转换中嵌入使用者的代码，这些代码可以读取当前状态等等信息，在状态机运行过程中就可以根据当前运行情况执行自定义逻辑，而不是只能在正则表达式的状态机运行完毕后才能执行自定义逻辑。

在状态机的状态转换中嵌入自定义代码有什么用处呢，最大的好处是我们可以直接使用一个完整的正则表达式来处理文本或字符流。而不再需要将它分解成多个子表达式，然后再和我们自己的逻辑粘贴组合起来，避免在运行时来回切换正则匹配引擎和我们的代码。

一个简单的例子

下面我们举个简单的例子来说明如何使用Ragel在正则表达式中嵌入操作代码。

首先，Ragel自己定义了一个状态机语法，Ragel编译程序读取Ragle状态机定义文件(通常扩展名为.rl)。当它在状态机定义文件中看到一个Ragel语法单元时，会生成相应代码来替换这个语法单元。Ragel定义了很多语法单元，比如：

• 一个Ragel代码块以%%{开始，以}%%结束；
• 单行的Ragel语句以%%开始；
• machine FSMName语句用于定义一个FSM的名字；
• include FSMName “inputfile.rl”可以导入其它文件的状态机定义；
• …
  下面是一个Ragel状态机定义文件，实现了将数字字符串转换为数字整数的功能：
  

/* * Convert a string to an integer. */ #include <stdlib.h> #include <string.h> #include <stdio.h> // 定义了一个Ragel代码块，其中声明了状态机的名字为atoi，编译后生成的目前代码会替换此处的代码块 %%{ 
    machine atoi; // 定义了该FSM的名字(没有定义名字会沿用上一个定义了名字的状态机) write data; // 在该位置生成该状态机的一些静态变量数据，通常是状态和转换的集合数组 }%% // 将数字字符串转换为数字整数的函数 long long atoi( char *str ) { 
    // Ragel状态机要求必须定义的变量： // p: 指向输入字符buffer； // pe: 要处理的字符buffer的长度； // cs：当前所处状态 char *p = str, *pe = str + strlen( str ); int cs; // 下面定义用户自定义变量  long long val = 0; // 最终的整数值 bool neg = false; // 是否为负数 // 继续定义atoi状态机  %%{ 
    // 定义一个动作，可以在后续通过动作名字来引用。 // 该动作将neg变量标记为true，即标记数字为负数 action see_neg { 
    neg = true; } // 定义一个动作，将状态机消费的字符累加成数字 action add_digit { 
    val = val * 10 + (fc - '0'); } // main := 语句用于实例化该状态机，该语句会生成:=后面定义语句的状态机。 // '-'@see_neg代表在遇到'-'后执行动作see_neg，即标记数字为负数。 // digit @add_digit代表遇到数字字符时执行动作add_digit。 main := ( '-'@see_neg | '+' )? ( digit @add_digit )+ '\n'; # 生成状态机初始化和执行代码. write init; // write init语句用于在该位置生成状态机初始化代码，在状态机执行前被执行 write exec; // write exec语句用于在该位置生成状态机执行的代码 }%% // 状态机定义结束 // 下面的是用户自定义逻辑代码 if ( neg ) val = -1 * val; if ( cs < atoi_first_final ) fprintf( stderr, "atoi: there was an error\n" ); return val; }; #define BUFSIZE 1024 int main() { 
    char buf[BUFSIZE]; while ( fgets( buf, sizeof(buf), stdin ) != 0 ) { 
    long long value = atoi( buf ); printf( "%lld\n", value ); } return 0; } 

接下来我们可以执行Ragel命令来根据该状态机定义文件生成代码和可视化的状态转换图：

// -C代表生成C语言代码，-V代表生成可视化状态转换图，-T0代表生成表驱动的状态机 ./ragel -C -V -T0 aoti.rl 

可见aoti状态机一共4个状态，状态1为初始状态，状态4带双圈代表最终接受状态。我们来解释下各个状态转换边：

• 45/see_neg：代表初始时遇到字符’-‘（ascii码为45）转移到状态2，同时执行动作see_neg；
• 43：代表初始时遇到字符’+’转移到状态2；
• 48…57/add_digit：代表遇到数字字符转移到状态3，同时执行动作add_digit；
• 10：代表遇到字符’\n’，转移到结束状态4；

我们再来看看ragel生成的状态机代码：

#line 1 "aoti.rl" /* * Convert a string to an integer. */ #include <stdlib.h> #include <string.h> #include <stdio.h> #line 13 "aoti.c" static const char _atoi_actions[] = { 
    0, 1, 0, 1, 1 }; static const char _atoi_key_offsets[] = { 
    0, 0, 4, 6, 9, 12, 14 }; static const char _atoi_trans_keys[] = { 
    43, 45, 48, 57, 48, 57, 10, 48, 57, 10, 48, 57, 48, 57, 0 }; static const char _atoi_single_lengths[] = { 
    0, 2, 0, 1, 1, 0, 0 }; static const char _atoi_range_lengths[] = { 
    0, 1, 1, 1, 1, 1, 0 }; static const char _atoi_index_offsets[] = { 
    0, 0, 4, 6, 9, 12, 14 }; static const char _atoi_indicies[] = { 
    0, 2, 3, 1, 3, 1, 4, 5, 1, 4, 5, 1, 3, 1, 1, 0 }; static const char _atoi_trans_targs[] = { 
    2, 0, 5, 3, 6, 4 }; static const char _atoi_trans_actions[] = { 
    0, 0, 1, 3, 0, 3 }; static const int atoi_start = 1; static const int atoi_first_final = 6; static const int atoi_error = 0; static const int atoi_en_main = 1; #line 12 "aoti.rl" long long atoi( char *str ) { 
    char *p = str, *pe = str + strlen( str ); int cs; long long val = 0; bool neg = false; #line 70 "aoti.c" { 
    cs = atoi_start; } #line 75 "aoti.c" { 
    int _klen; unsigned int _trans; const char *_acts; unsigned int _nacts; const char *_keys; if ( p == pe ) goto _test_eof; if ( cs == 0 ) goto _out; _resume: _keys = _atoi_trans_keys + _atoi_key_offsets[cs]; _trans = _atoi_index_offsets[cs]; _klen = _atoi_single_lengths[cs]; if ( _klen > 0 ) { 
    const char *_lower = _keys; const char *_mid; const char *_upper = _keys + _klen - 1; while (1) { 
    if ( _upper < _lower ) break; _mid = _lower + ((_upper-_lower) >> 1); if ( (*p) < *_mid ) _upper = _mid - 1; else if ( (*p) > *_mid ) _lower = _mid + 1; else { 
    _trans += (unsigned int)(_mid - _keys); goto _match; } } _keys += _klen; _trans += _klen; } _klen = _atoi_range_lengths[cs]; if ( _klen > 0 ) { 
    const char *_lower = _keys; const char *_mid; const char *_upper = _keys + (_klen<<1) - 2; while (1) { 
    if ( _upper < _lower ) break; _mid = _lower + (((_upper-_lower) >> 1) & ~1); if ( (*p) < _mid[0] ) _upper = _mid - 2; else if ( (*p) > _mid[1] ) _lower = _mid + 2; else { 
    _trans += (unsigned int)((_mid - _keys)>>1); goto _match; } } _trans += _klen; } _match: _trans = _atoi_indicies[_trans]; cs = _atoi_trans_targs[_trans]; if ( _atoi_trans_actions[_trans] == 0 ) goto _again; _acts = _atoi_actions + _atoi_trans_actions[_trans]; _nacts = (unsigned int) *_acts++; while ( _nacts-- > 0 ) { 
    switch ( *_acts++ ) { 
    case 0: #line 22 "aoti.rl" { 
    neg = true; } break; case 1: #line 26 "aoti.rl" { 
    val = val * 10 + ((*p) - '0'); } break; #line 161 "aoti.c" } } _again: if ( cs == 0 ) goto _out; if ( ++p != pe ) goto _resume; _test_eof: { 
   } _out: { 
   } } #line 37 "aoti.rl" if ( neg ) val = -1 * val; if ( cs < atoi_first_final ) fprintf( stderr, "atoi: there was an error\n" ); return val; }; #define BUFSIZE 1024 int main() { 
    char buf[BUFSIZE]; while ( fgets( buf, sizeof(buf), stdin ) != 0 ) { 
    long long value = atoi( buf ); printf( "%lld\n", value ); } return 0; } 

可以看到生成的代码部分都用#line标识出来了，这个文件可以直接编译运行，非常方便。

总结

Ragel的语法中定义了许多的语句和操作符，可以组合起来实现非常复杂的功能，比如linux awk的字符串处理能力等。如果你有类似的需求，比如在正则匹配过程中要执行很多特定的动作，Ragel是个值得深挖的项目。而且Ragel为了保证生成的状态机的性能，会将正则表达式全部编译为DFA，不会产生NFA的回溯问题。

这篇文章限于篇幅我们只讲了一个aoti的简单例子，如果有兴趣可以研究下Ragel的一些复杂的例子，它们就存放在Ragel源码中的example目录下，进而尝试自己实用Ragel构造一些状态机。

参考资料

1. http://www.colm.net/open-source/ragel/