Jet 筆記本: 10月 2009

這是翻譯 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 -- ? 待續

Jet 筆記本

2009年10月27日星期二

Ragel 簡介

Ragel基本使用

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

建立詞法分析器

追蹤者

網誌存檔

關於我自己

2009年10月27日 星期二

Ragel 簡介

Ragel基本使用

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

建立詞法分析器

追蹤者

網誌存檔

關於我自己

2009年10月27日星期二