2009年10月27日 星期二

Ragel 簡介

這是翻譯 http://jp.rubyist.net/magazine/?0023-Ragel 的筆記, 根據 ragle 6.5修訂範例

前言

Ragel 是 Adrian Thurston 提出的狀態機編譯器。

使用Ragel,你可以簡單的製作一個詞法分析的分析器和編譯器。 Ragel還支持多種語言輸出,目前可以生成C / C + + / Objective-C/D/Java/Ruby的源代碼。

狀態機簡單的說是一種狀態轉換圖。 根據輸入值, 狀態機將進到入指定狀態。可以確定狀態轉換最後的輸入,並且可以知道這種輸入是否正確的。
狀態機是的各種用途。
  • 作為一個編譯器詞法分析。
  • 用來確定數據是否正確的格式。
  • 替代正則表達式。
  • 用於設計Web應用程序畫面轉換。
  • 各種跟狀態變遷有關的設計, 例如網路協定處理, 自動販賣機設計...

Ragel,Ragel用戶指南請點擊這裡

Windows可執行文件請點擊這裡

此外,Ragel,可產生視化狀態圖,建議您安裝 Graphviz

Ragel基本使用

要知道如何使用Ragel,讓我們創建第一個簡單的例子。
為了描述狀態機,第一次嘗試生成Ragel狀態圖語法的定義。
請參閱list-1。這是一個辨認整數和小數範例。
list-1 ex1.rl:辨認整數和小數的文法
1: %%{
2:
3:  ## 狀態機名稱
4:   machine ex1;
5:
6:  ## 文法定義
7:   main := ('+' | '-')? [0-9]+ ('.' [0-9]+)? ;
8:
9: }%%

要點如下。
  • 第1,9行:Ragel狀態機是指從"%%{"到"}%%"之間。 如果只有一個行,你可以在第一列“%%”之 後寫Ragel敘述句。
  • 您需要為狀態機命名。 這個名字,在Ruby和C代碼生成的情況下,成為變量名稱前綴。
  • 第7行:從“main:=” 到 “;”是定義文法在這裡,寫一個模式語法。
    • "('+' |'-')?"表示,即使是一個或是沒有的正負符號。
    • “[0-9] +”表示數字,最少出現一次, 可以重複出現。
    • “('.' [0-9 ]+)?", 小數點, 然後至少一個的數字顯示。 在 “?” 意指整個是可省略的。
    • “#”是一個註釋行開頭。
如果你看看語法,您會發現非常類似於正則表達式。事實上,Ragel上寫的,良好的語言和語法,是一個正則表達式和正則表達式的能力(概念)相同
list-2 編譯它,產生狀態圖的圖形文件
### Ragel 編譯
c:> ragel -Vp ex1.rl > ex1.dot
### Graphviz 圖檔產生 (dot.exe 在 Graphviz目錄內)
c:> dot -Tpng ex1.dot > ex1.png
你這樣做,圖- 1 -像圖像生成。 以下はその説明です。下面是他們的解釋。
  • “○”和“◎”代表狀態。 “◎”是接受狀態,如果輸入值有匹配的語法在結束時的輸入狀態(輸入==接受)的手段。
  • 箭頭代表狀態遷移。箭頭上的字符串代表的轉換發生條件。
fig-1. ex.rl創建的狀態圖

從這一狀態圖中,可以看到下面。
  • 有5個狀態
  • 最初狀態是1
  • 接受狀態是4 & 5
這樣,Ragel可以輕鬆地創建使用狀態圖。
... 中略 日文基礎太差, 看不懂原文 這是筆記, 不用全部翻譯.....



Ragel允許你為個別Ragel狀態表示式命名。
list-3. ex2.rl
%%{

## 狀態機名稱
machine ex2;

## 表示式命名
sign = '+' | '-';
d    = [0-9];

## 文法定義
main := sign? d+ ('.' d+)? ;

}%%

當您生成這個定義的狀態轉換圖,跟fig-1是完全一樣的。
Ragel此外,還有下列預定義的別名。 欲了解更多信息參閱Ragel用戶指南,第2.3節的基本機
any 任意文字符

ascii ASCII碼, 字符代碼以及介於0和127。

alpha 字母。 與“[A-Za-z]”相同。

digit 數字 與 “[0-9]”相同。

alnum 文數字 與 “[0-9A-Za-z]" 相同。

xdigit 十六進制字符。與 “[0-9A-Fa-f]" 相同。

space 空白文字。 "[\t\v\f\n\r ]"相同。


C代碼生成 (原文是Ruby, 懂C的人還是比較多)


Ragel可自動生成狀態代碼要做到這一點,寫下面的源代碼。
%% write data;
生成一個狀態機所需的靜態數據。
%% write init;
初始化狀態機必須變數。
%% write exec;
運行狀態機實作。
list-4 ex3.rl 讀取浮點數範例, 使用C



%%{

## 狀態機名稱
machine ex3;

## 表示式命名
sign = '+' | '-';

## action 定義
##
action on_sign { /* 正負號辨認 */
/* 「fc」是現在scan到的文字
Ragel
*/
sign_char = fc;
#if DEBUG
printf( "*** on_sign: sign_char=%c\n", sign_char);
#endif
}
action on_int { /* 整數辨認 */
ch = fc;
#if DEBUG
printf( "*** on_integer: ch=%c", ch);
#endif
val = val * 10 + (ch - '0');
}
action on_float { /*小數部份 */
ch = fc;
#if DEBUG
printf( "*** on_float: ch=%c", ch);
#endif
e = 0.1 * e;
val += e * (ch - '0');
}

## main 文法定義。
main := sign? @on_sign digit+ @on_int ('.' digit+)? @on_float ;

}%%


#define DEBUG 0
/* 產生必要的狀態機資料 */
%% write data;

float scan( char *input )
{
char *p = input; /* Ragel 的目前文字指標 */
char *pe = input + strlen( p ); /* Ragel 的終點文字指標 */
int cs; /* Ragel 的目前狀態編號 */
int fc; /* Ragel 的目前文字 == *p */
int ch;
float e = 1.0;
float val = 0;
char sign_char = 0;


/* Ragel 初始化 */
%% write init;

/* Ragel 狀態機展開 */
%% write exec;

/* 檢查最終狀態 */
    if(  cs &lt ex3_first_final )
    {
      printf(  "** syntax error (p=%p, data[p]='%c')" , p, *p );
    }
     printf(  "cs=%d, fl=%d",  cs, ex3_first_final);
    /*## return 解析 result */
    return( sign_char == '-' ? -val : val);
}


main(int argc, char *argv[])
{
char line[100];
float val;

  while( gets(line) )
  {
    val = scan(line);
    printf( "val=%f\nOK.\n", val);
  }
}




用Ragel編譯此代碼,生成C源代碼, 用C編譯器產生執行檔, (list-5)。
list-5. 編譯和運行
C:> ragel -C ex3.rl     # 從ex3.rl生成 ex3.c
C:> wcl386 ex3.c
C:> ex3
-123
val=-123
OK.
3.14
val=3.14
OK.
123daa!
** syntax error (p=3, data[p]='d') 

Ragel此外,還有一些變數來指定更先進的和詳細的行動。 欲了解更多信息參閱Ragel用戶指南,第3章用戶操作請點擊這裡。

建立詞法分析器

當您建立一個編譯器詞法分析(掃描)經常使用狀態機來實作。 因此,Ragel提供簡便的詞法分析的功能。
Ragel使用此功能,在定義語法“| *”和“* |”用來描述模式匹配的動作了。 具體來說,像list-6這樣寫。
list-6. Ragel的詞法分析文法
%%{
 main := |*
    pattern1 =>  { action1 };
    pattern2 =>  { action2 };
    pattern3 =>  { action3 };
 *|;
}%%


因為模式匹配, 採用最長匹配方法, 所以需要做匹配失敗時回溯(backtrack). 需要一些變數來記錄這些變化 如下。
ts
匹配起始位置的標記。
te
匹配結束位置的標記。
act
代表最後成功的模式。用於回溯。
實際例子請參見list7。 在這個例子,認得整數和小數,以及識別字符作為token。 空白字符就跳過。
list-7. ex4.rl: 字句解析列表7。ex4.rl:詞法分析
%%{

## 狀態機名稱
machine ex4;

##  定義
sign = '+' | '-';

## 文法定義
main := |*

 ## 空白
 space+ ;  ## do nothing

 ## 整數
 sign? digit+ => {   
   memcpy( tokenstr, ts, te-ts);
   tokenstr[te-ts]=0;
   printf( "INT %s ", tokenstr);
   fbreak;       /* 狀態遷移中止 */
 };

 ## 小數
 sign? digit+ '.' digit+ => {   
   memcpy( tokenstr, ts, te-ts);
   tokenstr[te-ts]=0;
   printf( "FLOAT %s ", tokenstr);
   fbreak;       /* 狀態遷移中止 */
 };

 ## 識別子
 [a-zA-Z_] [a-zA-Z0-9_]* => {   
   memcpy( tokenstr, ts, te-ts);
   tokenstr[te-ts]=0;
   printf( "IDENT %s ", tokenstr);
   fbreak;       /* 狀態遷移中止 */
 };

*|;

}%%


#include 
#include 

#define DEBUG 1

/* 產生必要的狀態機資料 */
 %% write data;


scan_all( char *input)
{
     int cs, act;
     char *ts, *te = 0;
     char *p = input,
          *pe = input + strlen(input),
    *eof = 0; /* 用 |* ... *| 必須有此變數 */
     int done = 0;

     char tokenstr[100];

/*
 ## Ragel 初始化
 ##  (Ragel 變數
 ##      p ||= 0              # 現在位置 (pointer)
 ##      pe ||= data.length   # 終止位置 (end pointer)
 ##      cs = ex4_start       # 現在狀態 (current state)
 ##      ts = nil             # Token開始位置 (token start)
 ##      te = nil             # Token終了位置 (token end)
 ##      act = 0              #
 ##   )
*/
 %% write init;
 

 while( ! done )
     {
   token = 0;
       tokenstr[0] = 0;
  /* Check if this is the end of line. */
  if ( p >= pe ) {
   eof = pe;   /* must for flush last token out! */
   done = 1;
  }
   /* 狀態機展開  */
   %% write exec;

  /* 終結狀態檢查 */
   if( cs < cs="%d," p="%c,">
讓Ragel編譯它和運行。被承認為一個標記或標識符整數和小數的空間可以被忽略,你可以看到有一個錯誤符號(list-8)。
list-8. 編譯和運行
C:> ragel -C ex4.rl
C:> wcl386 ex4.c
C:> ex4
123  -3.14   foo
** token=:INT, str="123"
** token=:FLOAT, str="-3.14"
** token=:IDENT, str="foo"
OK.
func(123)
** token=:IDENT, str="func"
** syntax error (cs=0, p=4, data[p]='(') 
Ragel更多有關詞法分析,Ragel用戶指南,第6.3節掃描儀 ,請參閱。
-- 下面整理中--
JSON -- ? 待續


沒有留言:

張貼留言

追蹤者