Linux使用ragel进行文本快速解析

1、前言
2、相关知识
- 2.1、简介
- - 2.1.1 Ragel 优势
  - 2.1.2 Ragel 特性
- 2.2 状态机（mechine）概念
- 2.3 动作（action）的概念
- - 2.4 流程设计
3、案例实践
- 3.1 源码分析
- 3.2 编译
4、结论
- - 参考文章：

1、前言

在项目中我们经常涉及一些文本解析处理的场景，大部分场景是进行简单解析且数据量不大，但本文要讨论的是某些特定场景下，需要高性能解析大量文本的处理，如百万级每秒的日志解析。翻看Intel 的 hyperscan 依赖，发现有一款解析引擎Ragel，特性非常棒，可以拉出来进行实践。

当我们对文本（协议）进行解析的时候，有许多工具、语言可以进行选择。需求考虑一种实用、高效的可编程语言，但又要避免乏味、语义晦涩的写法。在这些工具像Lex、Re2C，或者sed、awk、perl脚本中，我们会发现有一个共同点：他们都是使用正则表达式匹配引擎，结合特定的程序处理逻辑来实现的。

经过大家的经验累积，我们得出一种结论：正则表达式可以清晰描述处理流程，而状态机可以可靠、快速地执行该流程。所以引入Ragel的编程哲学：开发者使用易理解的正则表达式来设计流程，然后生成高效的状态机代码给机器运行。

2、相关知识

以下通过 Ragel 官方手册[^2] 我们进行一部分的翻译理解，来逐步掌握这个工具。

Ragel 是一款代码生成器，他对常规的语言进行编译，生成有限状态机（FSM）代码。Ragel支持生成C、C++、ASM。Ragel 的状态机不仅可以使用正则表达式识别字节序列，而且可以在匹配过程中执行相关操作。Ragel生成相关的嵌入代码将使用内联操作，并不会破坏原语言的语法结构。

Ragel的核心语言包括正则表达式运算符、动作（action）嵌入运算符。用户的正则表达式将被编译为确定的状态机，并且执行指定的动作。编程的核心在于理解正则表达式和确定性有限状态机的关系。

2.1、简介

2.1.1 Ragel 优势

实现健壮的协议；
解析数据格式；
编程语言的语法分析；
验证用户输入；

2.1.2 Ragel 特性

结合常规代码、状态图表、扫描器就能构建FSM；
支持在FSM任意位置插入执行的动作；
使用防御性操作控制流程不确定性；
使用Hopcroft算法实现最小自动机；
支持Graphviz软件对FSM可视化；
使用单字节、双字节、字长的字母表；
在非依赖情况下生成C、C++、ASM(GNU, x86_64, System V ABI) 代码；
可选使用表、控制流去驱动状态机；

2.2 状态机（mechine）概念

Ragel 对于字符串的解析，是用一种结合正则表达式的机器语言来描述，可表现为内嵌的状态机语言规范。这种机器语言通过扫描输入的字符串，匹配状态机的特定状态进行处理，当扫描结束的时候，处理也随之完成。这种有限状态机语言可以由数行代码完成，使用标识符 %%{ 开始、使用 }%% 结束，也可以使用 %% 开始的一行进行实现。

下面看一个简单例子，该例子判断输入字符串中是否含有’foo’或’bar’字符：

#include <string.h>
#include <stdio.h>
%%{
machine foo;
main :=
	( ’foo’ | ’bar’ )
	0 @{ res = 1; };
}%%
%% write data;

int main( int argc, char **argv )
{
	int cs, res = 0;
	if ( argc > 1 ) {
		char *p = argv[1];
		char *pe = p + strlen(p) + 1;
		%% write init;
		%% write exec;
	}
	printf("result = %i\n", res );
	return 0;
}

Ragel语法的文件为rl后缀命名，内部expression支持正则表达式的语法:

命名：machine fsm_name；

定义： = ;

实例化： = ;

引用：include FsmName “inputfile.rl”;

引用：import “inputfile.h”;

2.3 动作（action）的概念

Ragel 允许自定义动作嵌入到正则表达式对应的状态机动作之中，随着FSM的状态迁移，自定义动作随之执行。与正则表达式一样，action 动作操作符是可以任意组合的。由于动作可以嵌入组成，用户可以完全自由地定义动作。

action ActionName {
	/* Code an action here. */
    count += 1;
}

动作的触发是在配合 FSM 状态迁移进行，按照动作大类区分有：

>开始状态

< 除了开始状态的其他状态

$ 任意状态下

% 结束状态

@ 除了结束状态的任意状态

<> 中间状态（除了开始状态和结束状态）

按动作小类区分有：

~ （to）迁移其他状态时的动作

* （from）从其他状态迁移过来时的动作

/ （eof）EOF时的动作

! （err）发生错误时的动作

^ （lerr）本地错误时的动作

下面列举一个例子来表示如何处理错误，在解析失败时时进行信息提示，并跳转到错误处理，当错误处理完成后，继续进入主线处理。

action cmd_err {
    printf( "command error\n" );
    fhold; fgoto line;
}
action from_err {
    printf( "from error\n" );
    fhold; fgoto line;
}
action to_err {
    printf( "to error\n" );
    fhold; fgoto line;
}

line := [^\n]* ’\n’ @{ fgoto main; };

main := (
    (
        ’from’ @err(cmd_err)
            ( ws+ address ws+ date ’\n’ ) $err(from_err) |
        ’to’ @err(cmd_err)
            ( ws+ address ’\n’ ) $err(to_err)
    )
)*;

2.4 流程设计

从前面几个小节讲，Ragel 提供了灵活的设计方法，但随着任意动作嵌入的灵活多变，需要控制正则表达式中的非确定性。

如果正则表达式不明确，则除了预期部分之外的解析器的子组件可能变得不可控。这意味着解析过程中action可能执行了当前子集无关的动作，从而给程序员带来问题。基于正则表达式引擎并用于识别任务的工具通常可以按预期运行，而不管是否存在歧义。

对于脚本语言的用户来说，编写非常模糊的正则表达式并且通常无关紧要是很常见的。只要识别出其中一个潜在匹配，就可以存在任意数量的其他匹配。在一些解析系统中，运行时引擎可以采用用于解决模糊的策略，例如总是追求最长可能的匹配并丢弃其他匹配。在Ragel中，没有正则表达式运行时引擎，只是一个简单的状态机执行模型。

所以显然，当我们执行动作并面对各种匹配的可能性时，在机器构造级别控制非确定性是非常重要的。

3、案例实践

3.1 源码分析

ragel_atoi.rl 提供了一个读取字符串转换成整数的例子

#include <stdlib.h>
#include <stdio.h>

%%{
    machine atoi;
    write data;
}%%

long long ragel_atoi(char *str)
{
    char *p = str, *pe = str + strlen(str);
    int cs;
    long long val = 0;
    bool neg = false;

    %%{
        action see_neg {
            neg = true;
        }   

        action add_digit { 
            val = val * 10 + (fc - '0');
        }   

        main := ( '-'@see_neg | '+' )? ( digit @add_digit )+ '\n';

        # Initialize and execute.
        write init;
        write exec;
    }%%

    if ( neg )
        val = -1 * val;

    if ( cs < atoi_first_final )
        fprintf( stderr, "atoi: there was an error\n" );

    return val;
};

int main(int argc, char *argv[])
{
    char buf[SIZE_LINE_NORMAL];

    while (fgets(buf, sizeof(buf), stdin) != 0) {
        long long value = ragel_atoi(buf);
        printf("%lld\n", value);
    }
    return 0;
}

main函数循环获取输入数据，子函数 ragel_atoi 进行字符串处理，核心语句为：

main := ( '-'@see_neg | '+' )? ( digit @add_digit )+ '\n';

action see_neg 处理首字符-/+ 正数、负数的动作，

action add_digit 则进行后续数字的扫描，进行十进制累加。

最后字符串读取到’\n’，表示结束，则退出子函数。

3.2 编译

类似于protoc命令，通过执行ragel，将rl文件转换为c语言代码：

ragel -G2 ragel_atoi.rl
gcc -o ragel_atoi ragel_atoi.c

我们可以看一下转换后"晦涩难懂"而又"效率至上"的代码：

#line 1 "ragel_atoi.rl"

#include "common.h"


#line 8 "ragel_atoi.c"
static const int atoi_start = 1;
static const int atoi_first_final = 4;
static const int atoi_error = 0;

static const int atoi_en_main = 1;


#line 7 "ragel_atoi.rl"


long long ragel_atoi(char *str)
{
    char *p = str, *pe = str + strlen(str);
    int cs;
    long long val = 0;
    bool neg = false;

    
#line 27 "ragel_atoi.c"
        {
        cs = atoi_start;
        }

#line 32 "ragel_atoi.c"
        {
        if ( p == pe )
                goto _test_eof;
        switch ( cs )
        {
case 1:
        switch( (*p) ) {
                case 43: goto st2;
                case 45: goto tr2;
        }
        if ( 48 <= (*p) && (*p) <= 57 )
                goto tr3;
        goto st0;
st0:
cs = 0;
        goto _out;
tr2:
#line 17 "ragel_atoi.rl"
        {
            neg = true;
        }
        goto st2;
st2:
        if ( ++p == pe )
                goto _test_eof2;
case 2:
#line 59 "ragel_atoi.c"
        if ( 48 <= (*p) && (*p) <= 57 )
                goto tr3;
        goto st0;
tr3:
#line 21 "ragel_atoi.rl"
        { 
            val = val * 10 + ((*p) - '0');
        }
        goto st3;
st3:
        if ( ++p == pe )
                goto _test_eof3;
case 3:
#line 73 "ragel_atoi.c"
        if ( (*p) == 10 )
                goto st4;
        if ( 48 <= (*p) && (*p) <= 57 )
                goto tr3;
        goto st0;
st4:
        if ( ++p == pe )
                goto _test_eof4;
case 4:
        goto st0;
        }
        _test_eof2: cs = 2; goto _test_eof; 
        _test_eof3: cs = 3; goto _test_eof; 
        _test_eof4: cs = 4; goto _test_eof; 

        _test_eof: {}
        _out: {}
        }

#line 30 "ragel_atoi.rl"


    if ( neg )
        val = -1 * val;

    if ( cs < atoi_first_final )
        fprintf( stderr, "atoi: there was an error\n" );

    return val;
};

int main(int argc, char *argv[])
{
        char buf[SIZE_LINE_NORMAL];

        while (fgets(buf, sizeof(buf), stdin) != 0) {
                long long value = ragel_atoi(buf);
                printf("%lld\n", value);
        }
        return 0;
}

4、结论

Ragel 体现了一种代码生成代码的特点，字符串的处理中，正则表达式是人类自然语言最好的提醒，同时又能通过转换成高效的计算机语言，Ragel作为中间工具将两者完美的结合起来了。

参考文章：

[0] Ragel官方文档, http://www.colm.net/files/ragel/ragel-guide-6.10.pdf

[1] Hyperscan简介, https://www.sdnlab.com/18773.html

Linux使用ragel进行文本快速解析（上）1、前言2、相关知识3、案例实践4、结论

Linux使用ragel进行文本快速解析

1、前言

2、相关知识

2.1、简介

2.1.1 Ragel 优势

2.1.2 Ragel 特性

2.2 状态机（mechine）概念

2.3 动作（action）的概念

2.4 流程设计

3、案例实践

3.1 源码分析

3.2 编译

4、结论

参考文章：

继续阅读

Apache (You don't have permission to access / on this server.）

debian9升级4.9.0内核到4.19.2内核过程

centOS7 配置 vsftpd 虚拟用户及权限Vsftpd配置虚拟用户及权限

linux-svn卸载与安装

vsftp虚拟多用户多权限一键部署脚本

Ubuntu14.04 LTS下安装mongodb

Nginx服务优化（1）——隐藏版本号、修改用户与组、网页缓存时间、日志切割、连接超时一、隐藏版本号二、修改用户与组三、配置Nginx网页缓存时间四、实现Nginx日志分割五、配置Nginx实现连接超时六、补充关于时间日期的命令

httpd服务的部署、启动、配置和简单优化一、部署二、启动三、配置文件

配置网页内容访问

手动安装Intel network I217-LM网卡的Linux驱动

禁止ubuntu系统弹出报错界面

Ubuntu Linux下Apache的配置文件

samba服务器的功能

【Linux】UDP广播报文接收速率问题

Linux设备模型（中）之上层容器

PowerPC平台 Linux移植三