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

httpd服務的部署、啟動、配置和簡單優化一、部署二、啟動三、配置檔案

配置網頁内容通路

手動安裝Intel network I217-LM網卡的Linux驅動

禁止ubuntu系統彈出報錯界面

Ubuntu Linux下Apache的配置檔案

samba伺服器的功能

【Linux】UDP廣播封包接收速率問題

Linux裝置模型（中）之上層容器

PowerPC平台 Linux移植三