從今天開始我把我前一段時間用到的狀態機工具Ragel的使用方法做一些總結,希望大家斧正!
(如果大家對狀態機概念有模糊的話,請參考<<編譯原理>>一書,基本上有詳盡的介紹)
好閑言少敘,言歸正傳
Ragel可以從正規表達式生成可執行有限狀態機,它可以生成C,C++,Object-C,D,Java和Ruby可執行代碼
官方網站:http://www.cs.queensu.ca/home/thurston/ragel/
第一回
Ragel是一個可以生成協議處理代碼的工具.
先舉個例子，簡簡單單的幾行代碼,實現的功能為將一個數字字符串轉換成整數：
[Copy to clipboard] [ - ]
CODE:
int atoi( char *str )
{
char *p = str;
int cs, val = 0;
bool neg = false;
%%{ //Ragel 的關鍵字,用于聲明狀態機代碼段的開始
action see_neg {
neg = true;
}
action add_digit {
val = val * 10 + (fc - '0');
}
main :=
( '-'@see_neg | '+' )? ( digit @add_digit )+
'\n' @{ fbreak; };
# Initialize and execute.
write init; //狀態機關鍵字,這個會再接下來的內容中介紹
write exec noend; //同上
}%% //狀態機代碼段結束標記
if ( neg )
val = -1 * val;
if ( cs < atoi_first_final )
cerr << "atoi: there was an error" << endl;
return val;
};
比c里面那500多行實現的atoi函數更加高效
上面這段代碼，生成的C語言代碼如下:
[Copy to clipboard] [ - ]
CODE:
int atoi( char *str )
{
char *p = str;
int cs, val = 0;
bool neg = false;
#line 27 "atoi.c"
{
cs = atoi_start;
}
#line 31 "atoi.c"
{
switch ( cs )
{
case 1:
switch( (*p) ) {
case 43: goto st2;
case 45: goto tr2;
}
if ( 48 <= (*p) && (*p) <= 57 )
goto tr3;
goto st0;
st0:
goto _out0;
tr2:
#line 23 "atoi.rl"
{
neg = true;
}
goto st2;
st2:
p += 1;
case 2:
#line 52 "atoi.c"
if ( 48 <= (*p) && (*p) <= 57 )
goto tr3;
goto st0;
tr3:
#line 27 "atoi.rl"
{
val = val * 10 + ((*p) - '0');
}
goto st3;
st3:
p += 1;
case 3:
#line 63 "atoi.c"
if ( (*p) == 10 )
goto tr4;
if ( 48 <= (*p) && (*p) <= 57 )
goto tr3;
goto st0;
tr4:
#line 33 "atoi.rl"
{ goto _out4; }
goto st4;
st4:
p += 1;
case 4:
#line 74 "atoi.c"
goto st0;
}
_out0: cs = 0; goto _out;
_out4: cs = 4; goto _out;
_out: {}
}
#line 38 "atoi.rl"
if ( neg )
val = -1 * val;
if ( cs < atoi_first_final )
cerr << "atoi: there was an error" << endl;
return val;
};
對應的狀態圖如下圖所示:
| 正則表達式廣泛應用于解析器中。它們通常被用來作為“黑盒”與程序邏輯聯系在一起。對正則表達式引擎在執行某些解析工作之后，調用用戶自定義行為。加入新的自定義行為，需要重新定義原來的格局，然后粘貼到程序邏輯中。自定義行為越多，正規表達式的優勢越小。
Ragel是一個可以根據用戶定義的正則表達式或是由正則表達式生成的狀態圖來生成健壯的，無依賴的可執行代碼，包括C，C++，Object-C, Java, Ruby 等等. 可以靈活控制已經生成狀態機的變動，利用已經嵌入自定義行為的模式重構掃描器
Ragel基于任何正規語言能被轉化為有限狀態自動機的原理
基本的使用步驟如下:
首先,根據你的業務流程邏輯與需要,按照ragel提供的語法與關鍵字編寫.rl文件
1． 編寫.rl文件, 如下所示： [Copy to clipboard] [ - ] CODE: /*
* to parse a string started with “table” or “div”
*/
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
%%{
#狀態機的名字(必須有一個名字而且必須符合命名規則,和變通的變量聲明一樣)
machine par_str;
write data;
}%%
//函數聲明,用于在用戶自定義行為中調用,用到了參數的傳遞,此函數也可以是類成員函數
void printtable(int len)
{
printf("there is a table,length is:%d\n",len);
}
//另外一個函數,功能同上,只是參數傳遞用的是引用傳遞
void printdiv(char *p)
{
printf("%s\n",(*p));
}
//主處理函數
void par_str( char *str,int len )
{
char *p = str, *pe = str + strlen( str );
int cs; //狀態機關鍵字,用于說明當明狀態,以整型值標識(current status的縮寫)
//狀態機自定義行為塊
%%{
#調用自定義函數
action see_table {
printtable(len);
}
#invoke prindiv function to show the table information, as same as above
action see_div {
printdiv(p);
}
#正則表達式聲明,用于在狀態機初始化時,按照此規則匹配目標
main :=
([t][a][b][l][e]@see_table) ([d][i][v]@see_div)+'\n';
# 初始化
write init;
write exec;
}%%
if ( cs < par_str_first_final )
fprintf( stderr, "par_str: there was an error\n" );
};
#define BUFSIZE 1024
//主函數,用于測試生成的狀態機
int main()
{
char buf[BUFSIZE];
while ( fgets( buf, sizeof(buf), stdin ) != 0 )
{
par_str(buf,10);
}
return 0;
}
接下來,用ragel命令生成目的語言文件
CODE: ragel -o test.cpp test.rl
用代碼生成工具,直接生成可執行代碼
CODE: rlcodegen -o hello.cpp test.cpp
最后編寫對此代碼的Makefile,make........
|
| |