woaidongmao

文章均收录自他人博客,但不喜标题前加-[转贴],因其丑陋,见谅!~
随笔 - 1469, 文章 - 0, 评论 - 661, 引用 - 0
数据加载中……

Ragel 状态机简介

从今天开始我把我前一段时间用到的状态机工具Ragel的使用方法做一些总结,希望大家斧正!


(
如果大家对状态机概念有模糊的话,请参考<<编译原理>>一书,基本上有详尽的介绍)

好闲言少叙,言归正传

Ragel
可以从正规表达式生成可执行有限状态机,它可以生成C,C++,Object-C,D,JavaRuby可执行代码

官方网站: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;
};


对应的状态图如下图所示:

clip_image001

 

正则表达式广泛应用于解析器中。它们通常被用来作为黑盒与程序逻辑联系在一起。对正则表达式引擎在执行某些解析工作之后,调用用户自定义行为。加入新的自定义行为,需要重新定义原来的格局,然后粘贴到程序逻辑中。自定义行为越多,正规表达式的优势越小。

Ragel
是一个可以根据用户定义的正则表达式或是由正则表达式生成的状态图来生成健壮的,无依赖的可执行代码,包括CC++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........


 

 

posted on 2008-12-24 15:18 肥仔 阅读(3029) 评论(1)  编辑 收藏 引用 所属分类: 状态机 & 自动机 & 形式语言

评论

# re: Ragel 状态机简介  回复  更多评论   

2009-04-19 19:36 | jans2002

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理