Jet 筆記本: 2009

2009年11月8日星期日

Lemon Parser user guide 筆記

Lemon Parser 是 LALR 文法. LALR 的好處是產生的狀態表比較小.
目前Lemon 是sqlite 的一部份.
sqlite 廣泛用於各種軟體. 例如 firefox browser
user guide 原文在此.
http://www.hwaci.com/sw/lemon/lemon.html

Lemon 跟 yacc/bison 的差異
1. Lemon parser 是 Token scanner 取得 token 時, 叫parser 處理得到的token. 而 yacc/bison 是 parser 需要一個token時叫 Token scanner解析文句.
2. Lemon 是比 yacc/bison 較新地設計, 它具有可重入, 多線程安全的優點. 簡單說, yacc/bison用全域變數儲存一些狀態, 而lemon 則否.
3.

Lemon parser 命令列
Lemon 輸入文法檔 .y
Lemon 輸出
1. parser C code (.c file)
2. header file 內含終端符號及對映的整數. (.h file)
3. 狀態表. (.out file)

Lemon 的command line switch
-m 不產生 header file (no .h file)
-q 不產生 state report (no .out file)
-? command line help
-b 簡易 state report (brief .out)
-c 取消 state table 壓縮, debug 文法錯誤較容易
-g 去除註解, 及action routine. 把純文法檔輸出到 stdout
-s Summary

Lemon parser 介面
使用Lemon parser, 需要知道幾個function
1. 建立指標 void *pParser = ParseAlloc( malloc );
使用Lemon 的函式都得依靠這個指標. malloc 就是 C的記憶體資源配置函式.

2. 當不再使用 Lemon parser 時, 用ParseFree(pParser, free); 解除資源配置.
free 是記憶體資源釋放函式.
pParser 是由 ParseAlloc() 建立的指標.

3. 每當 toekn scanner 解析出一個toekn時, 叫用Lemon parser函式如下,
Parse(pParser, hTokenID, sTokenData, pArg);
pParser 是由 ParseAlloc() 建立的指標.
hTokenID 是一個整數對到文法的終端符號, (lemon 產生之.h file)
sTokenData 終端符號的原始字串, 或是終端符號的值
pArg 程式員自定之資料結構, Lemon 會不作修改, 直接傳給action routine.
使用 %extra_argument 來定義

一個典型的 Lemon parser 運用如下(這個簡化的例子移除錯誤處理的部份)
01 ParseTree *ParseFile(const char *zFilename){
02 Tokenizer *pTokenizer;
03 void *pParser;
04 Token sToken;
05 int hTokenId;
06 ParserState sState;
07
08 pTokenizer = TokenizerCreate(zFilename);
09 pParser = ParseAlloc( malloc );
10 InitParserState(&sState);
11 while( GetNextToken(pTokenizer, &hTokenId, &sToken) ){
12 Parse(pParser, hTokenId, sToken, &sState);
13 }
14 Parse(pParser, 0, sToken, &sState);
15 ParseFree(pParser, free );
16 TokenizerFree(pTokenizer);
17 return sState.treeRoot;
18 }

請注意第 14行, 執行ParseFree()之前要先叫用Parse(pParser, 0, sToken, &sState); 是為讓Lemon Parser 結束所有狀態處理. 這是必要的程序.

4. Lemon Parser的除錯. 使用下列函式開啟除錯
ParseTrace(FILE *stream, char *zPrefix);
Lemon 將狀態表的變遷輸出到 stream, 若 stream==NULL, 就結束除錯
Lemon 會在每一則訊息前加 zPrefix

Lemon parser 的文法檔
1. 終端符號使用大寫字母開始, 一般是全部字母大寫.
終端符號表示已經完成, 不再有新的狀態變化.

2. 非終端符號使用小寫字母開始, 一般是全部字母小寫
非終端符號表示需要文法來轉變. 讓它最後到達終端符號

3. 每一條文法規則都是由非終端符號轉變成非終端符號及終端符號的串列.
規則的型式是非終端符號 ::= 非終端符號及終端符號串列.
用 "::=" 表示串列開始
用 "." 句點表示串列結束
::= 右邊的串列可以是空的.
例如 expr 是非終端符號
PLUS, TIMES, LPAREN,RPAREN,VALUE是終端符號
expr ::= expr PLUS expr.
expr ::= expr TIMES expr.
expr ::= LPAREN expr RPAREN.
expr ::= VALUE.

4. 跟yacc/bison 一樣, 在文法規則完成時, 可以立即執行一action routine.
例如
expr ::= expr PLUS expr. { printf("Doing an addition...\n"); }

5. 跟yacc/bison 一樣, Lemon可以把文法裏的符號用到C動作程式. 但是規則不一樣.
在yacc/bison 人們這樣寫.
expr -> expr PLUS expr { $$ = $1 + $2; };
在Lemon 是像這樣,
expr(A) ::= expr(B) PLUS expr(C). { A = B+C; }
Lemon 會去檢查文法規則跟後面的C動作程式是否有匹配. yacc/bison並不會如此檢查.

Precedence Rules優先規則
優先順序指定可以簡化文法規則處理含糊的語法.
%left, %right, %nonassoc 指定終端符號的結合優先順序, 最先出現的, 有最低的優先順序, 越後面, 優先順序越高.在同一行的優先順序一樣例如：
%left AND.
%left OR.
%nonassoc EQ NE GT GE LT LE.
%left PLUS MINUS.
%left TIMES DIVIDE MOD.
%right EXP NOT.
如果看到
a AND b OR c.
Lemon 會像這樣處理
a AND (b OR c).

如果看到 a AND b AND c 會這樣的解析 (a AND b) AND c
如果看到 a EXP b EXP c 會這樣的解析 a EXP (b EXP c)
如果看到 a EQ b EQ c 會產生一個錯誤

通常優先順序適用於到多數的文法規則, 如果在某一規則想用暫時更改. 可以在規則後使用方括符號. 放在規則結束後, C動作程式前. 例如
expr = MINUS expr. [NOT] 告訴Lemon 這裏MINUS 的優先等級跟 "NOT"一樣.

Lemon 是LALR parser, 所以使用 %left 會比使用 %right 更有效率, 且節省堆疊空間.

Lemon文法的指令

%left , %right , %nonassoc
定義結合優先順序

%include { C code }
直接包括一段 C code

%extra_argument
定義 Parse(pParser, hTokenID, sTokenData, pArg); 的 pArg 資料型態
eg. %extra_argument { Mystrcut *pABC}

%name
修改 Lemon Parser 介面函式的名稱, 如此可以一個文法檔包含數個不同Parser.
eg. %name Abcde
Lemon Parser 函式名變成
AbcdeAlloc(), AbcdeFree(), AbcdeTrace(), 和 Abcde().

%parse_accept
定義parser 成功時的動作
eg. %parse_accept { printf("parsing complete!\n"); }

%parse_failure
定義parser 失敗時的動作
eg. %parse_failure {
fprintf(stderr,"Giving up. Parser is hopelessly lost...\n"); }

%syntax_error
語法錯誤時, 如果有定義這個指令, 就首先用此指令
然後Lemon會嘗試從堆疊移除發生錯誤的非終端規則, 然後從這非終端符號的其他規則重新處理. 若是這過程堆疊被歸零, 就叫用 %parse_failure

%stack_overflow
堆疊溢出的處理.
eg. %stack_overflow {
fprintf(stderr,"Giving up. Parser stack overflow\n"); }
Lemon 是LALR, 使用左邊遞迴, 會使用較少堆疊空間.

list ::= list ATOM. #good
list ::=.

list ::= ATOM list. #bad!
list ::=.

%stack_size
增加堆疊空間, 預設值是100
eg. %stack_size 2000

%start_symbol
Lemon 預設從第一個非終端符號的規則開始處理, 使用這個指令, 可以改變初始的第一個規則.
eg. %start_symbol prog

%type
定義某個非終端符號的資料結構
eg. %type expr {Expr*}

%token_type
定義終端符號的資料結構, 所有終端符號的資料結構都一樣. 用於 Parse()的第3個參數. 預設資料結構是"int".
eg. %token_type {Token*}

%token_prefix
為終端符號加字首, 例如Lemon 產生的 header file 如下
#define AND 1
#define MINUS 2
#define OR 3
#define PLUS 4

使用%token_prefix TOKEN_ 之後
#define TOKEN_AND 1
#define TOKEN_MINUS 2
#define TOKEN_OR 3
#define TOKEN_PLUS 4

%destructor
非終端符號的解構.
每當非終端符號從堆疊彈出時, 可以叫用解構的C動作.
有這些情形會用到 %destructor
1. 運行ParseFree()
2. 因為錯誤處理, 從堆疊彈出
3. 當一個規則消除非終端符號, 而沒有C動作程序

eg.
%type nt {void*}
%destructor nt { free($$); }
nt(A) ::= ID NUM. { A = malloc( 100 ); }
這個例子, 當 nt 成為 ID NUM 時, 配置100 byte 空間, 當nt 從堆疊彈出時, 將其釋放. $$ 代表由malloc得到的指標.
如果當一個規則消除非終端符號, 而有C動作程序, 則由該動作程序負責相關解構動作. 而不會執行 %destructor

%token_destructor
動作原理跟 %destructor一樣, 但是只針對終端符號.

透過謹慎的 %token_destructor & %destructor設計可以減少記憶體資源洩
漏.

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 -- ? 待續

Jet 筆記本

2009年11月8日星期日

Lemon Parser user guide 筆記

2009年10月27日星期二

Ragel 簡介

Ragel基本使用

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

建立詞法分析器

追蹤者

網誌存檔

關於我自己

2009年11月8日 星期日

Lemon Parser user guide 筆記

2009年10月27日 星期二

Ragel 簡介

Ragel基本使用

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

建立詞法分析器

追蹤者

網誌存檔

關於我自己

2009年11月8日星期日

2009年10月27日星期二