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設計可以減少記憶體資源洩
漏.