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