 |
Lemonパーザジェネレータ チュートリアル
→元記事
by Mike Chirico, in Tutorials - Sat, Aug 14th 2004 00:00 PDT
translated by Shin-ya TSUBAKI - Sunday, August 29th 2004 17:00 GMT
LemonはDr. Richard Hippにより書かれた, コンパクトでスレッドセー
フ, 十分テストされたパーザジェネレータです. flexのようなスキャナーとあ
わせてパーザジェネレータを使うことで, 書くコードの量が少なくなるのでと
ても便利です. パーザ用の文法を書くだけでいいのです.
著作権に関する注意: freshmeat.netにある読者投稿記事の
著作権および責任はすべてその著者に帰属するものとします; 再掲
載については著者に直接連絡をとってください.
Example 1: はじめよう
Lemonを使ったコーディングと, ゼロからのコーディングを比較しましょう.
例えば, 標準的なC++デ
スクトップ計算機と以下のファイルを比較しましょう. 以下にあるのはパー
ザが使う文法を含む文法ファイルです. "example1.y"は非常に単純な計算機の
文法ファイルの例です.
example1.y
1 %token_type {int}
2
3 %left PLUS MINUS.
4 %left DIVIDE TIMES.
5
6 %include {
7 #include <iostream>
8 #include "example1.h"
9 }
10
11 %syntax_error {
12 std::cout << "Syntax error!" << std::endl;
13 }
14
15 program ::= expr(A). { std::cout << "Result=" << A << std::endl; }
16
17 expr(A) ::= expr(B) MINUS expr(C). { A = B - C; }
18 expr(A) ::= expr(B) PLUS expr(C). { A = B + C; }
19 expr(A) ::= expr(B) TIMES expr(C). { A = B * C; }
20 expr(A) ::= expr(B) DIVIDE expr(C). {
21 if(C != 0){
22 A = B / C;
23 }else{
24 std::cout << "divide by zero" << std::endl;
25 }
26 } /* end of DIVIDE */
27 expr(A) ::= INTEGER(B). { A = B; }
このように, このファイルはたった27行(ただし空行は除く)です. 生コードを
書き換えるよりも文法を変更するほうが容易であることが分かります.
パーザジェネレータ(lemon.cとlempar.c)は文法ファイル"example1.y"を読み
込み, パーザファイル"example1.c"を生成します. このとき, さらに2つのファ
イルが生成されます. 1つはトークンが定義されている"example1.h"であり,
もう1つは"example1.y"に示された文法の状態遷移を詳細に示した
"example1.out"です.
手順に沿って進んでいきましょう. まずレモンのソースコード(ここから入手できます)
のコンパイルです. まずlemon.cをコンパイルしましょう:
$ gcc -o lemon lemon.c
これでパーザジェネレータlemonができました. これを使って文
法ファイル"example1.y"を処理しましょう.
$ ./lemon example1.y
これによりexample1.c, example1.h, example1.outが作成されます. では
lempar.cはどうでしょうか? "example1.c"と"lemper.c"を比べると, 同じコー
ドがたくさん含まれていることに気がつくでしょう. "lemper.c"はテンプレー
トファイルです. もし必要があればこのコードを修正しましょう. すべての修
正は"example1.c"に(コメントも含めて)継承されます.
しかし"example1.c"は完全ではありません. main関数とトークンの入っている
ファイル"main_part"の内容を追加しましょう. "main_part"はドライバと呼ば
れています.
main_part
1 int main()
2 {
3 void* pParser = ParseAlloc (malloc);
4 /* First input:
5 15 / 5
6 */
7 Parse (pParser, INTEGER, 15);
8 Parse (pParser, DIVIDE, 0);
9 Parse (pParser, INTEGER, 5);
10 Parse (pParser, 0, 0);
11 /* Second input:
12 50 + 125
13 */
14 Parse (pParser, INTEGER, 50);
15 Parse (pParser, PLUS, 0);
16 Parse (pParser, INTEGER, 125);
17 Parse (pParser, 0, 0);
18 /* Third input:
19 50 * 125 + 125
20 */
21 Parse (pParser, INTEGER, 50);
22 Parse (pParser, TIMES, 0);
23 Parse (pParser, INTEGER, 125);
24 Parse (pParser, PLUS, 0);
25 Parse (pParser, INTEGER, 125);
26 Parse (pParser, 0, 0);
27 ParseFree(pParser, free );
28 }
このmain_partは何をしているのでしょうか? まず3行目でパーザを初期化しま
す. pParserは7行目から始まる"Parse"関数を呼びだすたびに, 必ず最初に実
行されます. 15/5もしくは15割る5という表現が7から10行目で実行されます.
最初に整数15が送られ, 次に識別子DIVIDEが送られます. DIVIDEには引数が必
要ないので第3引数に0をとっています. 最後に10行目の"Parse(pParser, 0,
0);"で第2引数に0を渡すことで, この表現の入力が終了したことを通知します.
("example4.y"で, 文法がNEWLINEによって処理されていること, そして
"Parse(pParser,0,...);"が文法ファイルの末尾にのみ書かれていることに注
意しましょう.)
"main_part"を"example1.c"に追加します. ダウンロードできる例題に含まれ
るMakefileを参照するとよいでしょう. 追加するには以下のようにします:
$ cat main_part >> example1.c
それではexample1.cをコンパイルしましょう.
$ g++ -o ex1 example1.c
では"ex1"を実行してみましょう. まず15/5の結果である3, 50+125の結果175,
そして50*125+125の結果6375が得られます. 最後の結果では掛け算TIMESが足
し算PLUSよりも高位の優先度をもっていることの確認です.
$ ./ex1
Result=3
Result=175
Result=6375
それでは文法ファイル(example1.y)を詳細に見てみることにしましょう. なぜ
TIMESはPLUSよりも優先度が高いのでしょうか? 3行目と4行目で演算PLUS,
MINUS, DIVIDE, TIMESの優先度を決めています.
3 %left PLUS MINUS.
4 %left DIVIDE TIMES.
先に書いてあるものほど低い優先度となります. これはとても重要なことです.
PLUSとMINUSはDIVIDEとTIMESよりも低い優先度となる理由は, PLUSとMINUSが3
行目に, そしてDIVIDEとTIMESが4行目に書いてあるからなのです. 例えば, も
し指数(EXP)を加えるならば, EXPはTIMESやDIVIDEよりもさらに高位の優先度
を持っている演算子なのですから, 4行目よりも下に書くことになるわけです.
整数ではなく実数である15.5や5.2を入力したい場合はどうしたらよいでしょ
うか? 実はとても簡単です. これらのトークンが今のところ整数なのは,
"example1.y"にあるこのの行のためなのです:
1 %token_type {int}
doubleにしたいのであれば, 1行目を次のように変更しましょう:
%token_type {double}
"example1.y"の下のほうを見てみましょう. 6行目には"include"指示がありま
す. "example1.y"のinclude文はCステートメントをすべて通します. これらは
パーズファイル"example1.c"の先頭に挿入されます. これは宣言やヘッダに必
要な処理なのです.
...
6 %include {
7 #include <iostream>
8 #include "example1.h"
9 }
...
"example1.h"は"$ ./lemon example1.y"により生成されること
に注意しましょう. ここにトークンが定義されていて, すべてのトークンに1
から順に番号がつけられているのです. なぜ0からでなく1から始まるのでしょ
うか? なぜなら0はParse関数に割当てられているからです. "Parse (pParser,
0, 0);"で第2引数を0にすると入力の終了を意味することを思い出してくださ
い.
example1.h (註: これは生成されたファイルです; このファイルにコードを追
加しないでください):
#define PLUS 1
#define MINUS 2
#define DIVIDE 3
#define TIMES 4
#define INTEGER 5
Example 2: トークン型や構造を自作する
"example2.y"では"example1.y"とは違い, トークン型を構造体として定義して
います. 特に, このトークン型はファイル"ex2def.h"に定義されています. 自
分独自の構造を定義することで, 意味解析, つまり生成規則の右側のコードに
自由度が与えられるのです.
expr(A) ::= expr(B) TIMES expr(C). { A.value = B.value * C.value;
A.n = B.n+1 + C.n+1;
}
"example2.y"
のtoken_typeはTokenとして6行目に定義されています.
6 %token_type {Token}
この構造体Tokenは"ex2def.h"の中で以下のように定義されています:
ex2def.h
struct Token {
const char *z;
int value;
unsigned n;
};
特記: "const char *z"はこの例では使われていませんが, この構造を残して
おきました. なぜなら計算機の次の論理的なステップとして, 表現を変数に割
当てたいからです. 例えば, 変数1=2+5のように, 変数1にシンボル表の特定の
値をもたせたいのです. この文献を参照しましょう.
繰り返しますが, include指示の変更, つまり"ex2def.h"の追加に注意しましょ
う. これはToken構造体の定義です.
example2.y
1 #include {
2 #include <iostream>
3 #include "ex2def.h"
4 #include "example2.h"
5 }
6 %token_type {Token}
7 %default_type {Token}
8 %type expr {Token}
9 %type NUM {Token}
10
11 %left PLUS MINUS.
12 %left DIVIDE TIMES.
13
14
15 %syntax_error {
16 std::cout << "Syntax error!" << std::endl;
17 }
18
19 program ::= expr(A). {
20 std::cout << "Result.value=" << A.value << std::endl;
21 std::cout << "Result.n=" << A.n << std::endl;
22 }
23 expr(A) ::= expr(B) MINUS expr(C). { A.value = B.value - C.value;
24 A.n = B.n+1 + C.n+1;
25 }
26 expr(A) ::= expr(B) PLUS expr(C). { A.value = B.value + C.value;
27 A.n = B.n+1 + C.n+1;
28 }
29 expr(A) ::= expr(B) TIMES expr(C). { A.value = B.value * C.value;
30 A.n = B.n+1 + C.n+1;
31 }
32 expr(A) ::= expr(B) DIVIDE expr(C). {
33 if(C.value != 0){
34 A.value = B.value / C.value;
35 A.n = B.n+1 + C.n+1;
36 }else{
37 std::cout << "divide by zero" << std::endl;
38 }
39 } /* end of DIVIDE */
40 expr(A) ::= NUM(B). { A.value = B.value; A.n = B.n+1; }
以下で見るように, 23-25行目に注目すると, Token構造体Aは"A.value"と
"A.n"を伴っています. ".value"は表現の値を, そして".n"は代入回数を表し
ています:
23 expr(A) ::= expr(B) MINUS expr(C). { A.value = B.value - C.value;
24 A.n = B.n+1 + C.n+1;
25 }
これは"shift"と"reduce"の好例となっています. "shift"はトークンがスタッ
クからプッシュされた回数を表しています. "reduce"は表現ルールがマッチし
た回数を表しています. マッチするたびに展開(reduce)されます.
lemonが実行されるたびに, 3つのファイルが作られることを思
い出してください. 3つのファイルとは*.c, *.h, *.outでした. この".out"ファ
イルには文法の各ステップが, シフトと還元に沿って記載されています. 簡単
にまとめたければ, lemonに"-s"オプションをつけて実行してみるとよいでしょ
う:
$ ./lemon -s example2.y
Parser statistics: 6 terminals, 3 nonterminals, 6 rules
11 states, 0 parser table entries, 0 conflicts
前の例でもあったように, "main_part2"というドライバが"example2.c"に追加
されます:
$ cat main_part2 >> example2.c
これで"example2.c"をコンパイル・実行できます:
$ g++ -o ex2 example2.c
$ ./ex2
Result.value=17
Result.n=4
Result.value=-9
Result.n=4
Result.value=78
Result.n=10
Example 3: トークンデストラクタの機能
bisonとlemonを協働させることのメリットは, 端末以外に使われるメモリを解
放できることにあります. 好きな関数を呼び出すことができるのです.
"expr"が非端末の例です. 非端末でプログラムが呼び出される
と, token_destructorが呼ばれます.
example3.y
1 %include {
2 #include <iostream>
3 #include "ex3def.h"
4 #include "example3.h"
5 void token_destructor(Token t)
6 {
7 std::cout << "In token_destructor t.value= " << t.value << std::endl;
8 std::cout << "In token_destructor t.n= " << t.n << std::endl;
9 }
10 }
11 %token_type {Token}
12 %default_type {Token}
13 %token_destructor { token_destructor($$); }
...
13行目のtoken_destructorは関数
"token_destructor($$);"です. 関数
"token_destructor"は5行目から9行目で定義されています. こ
の簡単な例では, メモリは全く確保されていませんので, free
を呼び出す必要がありません. 何が起こるのかを知りたければ, std::coutに
行われる出力を見てみるとよいでしょう.
プログラムをコンパイルしたら, 以下のようにして実行します. 出力には説明
の都合上, 行番号が付与されている点に注意しましょう.
$ ./ex3
1 t0.value=4 PLUS t1.value=13
2 In token_destructor t.value= 4
3 In token_destructor t.n= 0
4 Result.value=17
5 Result.n=4
6 parsing complete!
...
表現が還元された後, デストラクタが呼ばれます. しかし, token.value=4の
時にしか呼ばれません. これは何故でしょうか? その答えを知るために,
"main_part3"を見てみることにしましょう.
main_part3
1 int main()
2 {
3 void* pParser = ParseAlloc (malloc);
4 struct Token t0,t1;
5 struct Token mToken;
6 t0.value=4;
7 t0.n=0;
8 t1.value=13;
9 t1.n=0;
10 std::cout << " t0.value=4 PLUS t1.value=13 " << std::endl;
11 Parse (pParser, NUM, t0);
12 Parse (pParser, PLUS, t0);
13 Parse (pParser, NUM, t1);
14 Parse (pParser, 0, t0);
15 std::cout << " t0.value=4 DIVIDE t1.value=13 " << std::endl;
16 Parse (pParser, NUM, t0);
17 Parse (pParser, DIVIDE, t0);
18 Parse (pParser, NUM, t1);
19 Parse (pParser, 0, t1);
...
14行目で第3引数にt0を渡すことで, 文法を終了させます. 第3
引数は定義されたデストラクタ関数"token_destructor(..."に
"$$"として渡されます. "Parse"が2回目に呼ばれ
たときには未定義になっていますから, 表現を終了させるためにトークンを渡
し終わった後にデストラクタ関数を呼び出す必要があります. つまり,
"Parse (pParser, 0, t0);"の直後に再度"Parse
(pParser, 0, t0);"を呼び出す必要はないのです.
19行目のtoken_destructorが呼ばれると,
t1.value=13が返されます. "main_part3"の19行目を見れば, 第
2引数に0を, 第3引数にt1を指定して
Parseが呼ばれていることが分かるでしょう.
プログラムの出力の続きです:
7
8
9 t1.value=13 PLUS t0.value=4
10 In token_destructor t.value= 13
11 In token_destructor t.n= 0
12 Result.value=17
13 Result.n=4
14 parsing complete!
14行目では第3引数にt0を, 19行目にはt1が渡さ
れています. これは特に問題とはなりません. 1つの変数はトークンの値を保
持します. 例えば, main_part3は値4と14を以下のようにToken
t0に保持しています:
...
struct Token t0;
t0.value=4;
t0.n=0;
Parse (pParser, NUM, t0);
Parse (pParser, PLUS, t0);
t0.value=13;
t0.n=0;
Parse (pParser, NUM, t0);
Parse (pParser, 0, t0);
...
Example 4: NEWLINEによる文法の終了
これまでの3つの例では, Parse(pParse,0..が表現の入力の終了
を知らせるために呼ばれていました. これは面倒です. 代わりに, 表現が還元
できなくなったときに文法を決定させることができます.
"example4.y"には以下の行が含まれています:
example4.y
1 %include {
2 #include <iostream>
3 #include "ex4def.h"
4 #include "example4.h"
...
23
24 %syntax_error {
25 std::cout << "Syntax error!" << std::endl;
26 }
27
28 /* This is to terminate with a new line */
29 main ::= in.
30 in ::= .
31 in ::= in state NEWLINE.
32 state ::= expr(A). {
33 std::cout << "Result.value=" << A.value << std::end
34 std::cout << "Result.n=" << A.n << std::endl;
35 }
36 expr(A) ::= expr(B) MINUS expr(C). { A.value = B.value - C.value;
37 A.n = B.n+1 + C.n+1;
38 }
...
29-35行目に注目しましょう. "main"と"in"が定
義されています(29-31行目). あなたがBisonユーザなら非端末のmainを定義
する必要はありませんが, lemonでは現在定義する必要があります.
"example4.y"にこのような修正をすることで, "main_part4"はトークン
NEWLINEを渡すことで表現を終了させることができるようになります.
main_part4のセクションです:
main_part4
1 int main()
2 {
3 void* pParser = ParseAlloc (malloc);
4 struct Token t0,t1;
5 struct Token mToken;
6 t0.value=4;
7 t0.n=0;
8 t1.value=13;
9 t1.n=0;
10 std::cout << std::endl <<" t0.value=4 PLUS t1.value=13 " << std::endl << std::endl;
11 Parse (pParser, NUM, t0);
12 Parse (pParser, PLUS, t0);
13 Parse (pParser, NUM, t1);
14 Parse (pParser, NEWLINE, t1);
15 std::cout << std::endl <<" t0.value=4 TIMES t1.value=13 " << std::endl << std::endl;
14行目でトークンNEWLINEが渡されています. NEWLINEはここでは整数6として
"example4.h"で定義されています.
では"ex4"の出力を見てみましょう. 行番号は説明のために付与されています:
$ ./ex4
1 t0.value=4 PLUS t1.value=13
2
3 In token_destructor t.value= 4
4 In token_destructor t.n= 0
5 Result.value=17
6 Result.n=4
7
8 t0.value=4 TIMES t1.value=13
9
10 In token_destructor t.value= 4
11 In token_destructor t.n= 0
12 Result.value=52
13 Result.n=4
14 parsing complete!
5行目に結果が表示されています. もちろんParse (pParser, 0,
t0);は不要です. Parse( pParse, NEWLINE, t0);が機能
していることが分かるでしょう.
Example 5: トークナイザとしてflexを使う
次の例では端末から直接入力を受け取ります. flexを使って適切なトークンを
見付けるスキャナーを生成しましょう.
まず, flexプログラム"lexer.l"を見てみましょう. 行番号は説明のためにつ
いています:
lexer.l
1 %{
2 #include "lexglobal.h"
3 #include "example5.h"
4 #include <string.h>
5 #include <math.h>
6 int line = 1, col = 1;
7 %}
8 %%
9 [0-9]+|[0-9]*\.[0-9]+ { col += (int) strlen(yytext);
10 yylval.dval = atof(yytext);
11 return NUM; }
12 [ \t] { col += (int) strlen(yytext); } /* ignore but count white space */
13 [A-Za-z][A-Za-z0-9]* { /* ignore but needed for variables */
14 return 0;
15 }
16 "+" { return PLUS; }
17 "-" { return MINUS; }
18 "*" { return TIMES; }
19 "/" { return DIVIDE; }
20 \n { col = 0; ++line; return NEWLINE; }
21 . { col += (int) strlen(yytext); return yytext[0]; }
22 %%
23 /**
24 * reset the line and column count
25 *
26 *
27 */
28 void reset_lexer(void)
29 {
30 line = 1;
31 col = 1;
32 }
33 /**
34 * yyerror() is invoked when the lexer or the parser encounter
35 * an error. The error message is passed via *s
36 *
37 *
38 */
39 void yyerror(char *s)
40 {
41 printf("error: %s at line: %d col: %d\n",s,line,col);
42 }
43 int yywrap(void)
44 {
45 return 1;
46 }
flexのフォーマットは基本的にはルールを左側に, 実行するCコードを右側に
書くというものです. 9行目を見てみましょう.
"[0-9]+|[0-9]*\.[0-9]+"は3, .3, 0.3, 23.4のいずれにもマッ
チし, NUMを返します. ではNUMの値はいくつになるのでしょう? これは
3行目でインクルードしている, lemonパーザにより生成される"example5.h"を
見ると分かります. 10行目にyylval.dvalが
浮動小数に変換された後に"yytext"に代入されています.
yylvalの構造は2行目の"lexglobal.h"で定義されています.
行番号をつけて"lexglobal.h"を載せておきます:
lexglobal.h
1 #ifndef YYSTYPE
2 typedef union {
3 double dval;
4 struct symtab *symp;
5 } yystype;
6 # define YYSTYPE yystype
7 # define YYSTYPE_IS_TRIVIAL 1
8 #endif
9 /* extern YYSTYPE yylval; */
10 YYSTYPE yylval;
yystypeはdvalとsymtabのユニオン
です. symtabはこの例では使われていませんが, 計算機に値を
渡したいときに使うことができます. flexとbisonを用いた完全な計算機の例
は参考文献の3番を参照してください.
再びlexer.l
の9-11行目を見てみましょう:
...
9 [0-9]+|[0-9]*\.[0-9]+ { col += (int) strlen(yytext);
10 yylval.dval = atof(yytext);
11 return NUM; }
...
トークンNUMの型と値が決まります. 入力されたものが数字であることを知る
と同時に, その値も知る必要があります.
これとは違い, PLUS, MINUS, TIME, DIVIDEの場合は, 特定の識別子が見付かっ
たかどうかだけを知ればいいのです. よって, lexer.lでは16-19行目でトーク
ンの値を返しています.
16 "+" { return PLUS; }
17 "-" { return MINUS; }
18 "*" { return TIMES; }
19 "/" { return DIVIDE; }
20 \n { col = 0; ++line; return NEWLINE; }
21 . { col += (int) strlen(yytext); return yytext[0]; }
22 %%
20行目はNEWLINEです. 使われていませんが, 行番号は変数
"line"に保持されています. またcolはカラム数
を保持しています. これらはデバッグの時に役立つでしょう.
ドライバmain_part5にはもっと多くのコードが書かれています. 低レベルread
文がstdinに使われます. これはソケットディスクリプタからの入力に容易に
変更できます. よって, もしTCPソケットからの入力をスキャンするWebスクラッ
ピングプログラムが欲しいなら, 33行目の"fileno(stdin)"をソ
ケットディスクリプタにすればよいのです.
main_part5
1 #include <stdio.h>
2 #include <unistd.h>
3 #include <sys/types.h>
4 #include <sys/stat.h>
5 #include <fcntl.h>
6 #include <stdlib.h>
7 #define BUFS 1024
8 /**
9 * We have to declare these here - they're not in any header files
10 * we can include. yyparse() is declared with an empty argument list
11 * so that it is compatible with the generated C code from bison.
12 *
13 */
14 extern FILE *yyin;
15 typedef struct yy_buffer_state *YY_BUFFER_STATE;
16 extern "C" {
17 int yylex( void );
18 YY_BUFFER_STATE yy_scan_string( const char * );
19 void yy_delete_buffer( YY_BUFFER_STATE );
20 }
21 int main(int argc,char** argv)
22 {
23 int n;
24 int yv;
25 char buf[BUFS+1];
26 void* pParser = ParseAlloc (malloc);
27 struct Token t0,t1;
28 struct Token mToken;
29 t0.n=0;
30 t0.value=0;
31 std::cout << "Enter an expression like 3+5 <return>" << std::endl;
32 std::cout << " Terminate with ^D" << std::endl;
33 while ( ( n=read(fileno(stdin), buf, BUFS )) > 0)
34 {
35 buf[n]='\0';
36 yy_scan_string(buf);
37 // on EOF yylex will return 0
38 while( (yv=yylex()) != 0)
39 {
40 std::cout << " yylex() " << yv << " yylval.dval " << yylval.dval << std::endl;
41 t0.value=yylval.dval;
42 Parse (pParser, yv, t0);
43 }
44 }
45 Parse (pParser, 0, t0);
46 ParseFree(pParser, free );
47 }
"lexer.l"によりflexでC++コードはなくCコードが生成されるので, 16行目の'
extern "C"'は必要です.
$ flex lexer.l
詳細はflexマニュアル(参考文献7)を参照してください.
"flex++"であればC++コードが生成されます. しかし, 複雑になっ
た場合にはCコードのほうが高速です. "main_part5"は複雑なC++プログラムで
すが, これで全く問題ありません.
パーザは"Parse(pParser,0,.."で第2引数に0が入力されれば必
ず終了します. flexへの入力がなくなった場合, 必ずゼロを返します.
よって, 38行目以降ではゼロによりwhileループが終了します.
また, 33行目でread文により入力されます. これはソケットか
らの入力でよく使われる手です. 入力が遅れるからです.
もし初期読み込み(33行目の最初の読み込み)に失敗すると, flexはゼロを返す
ことができません. よって, 45行目の第2引数にゼロが指定されているのです.
...
33 while ( ( n=read(fileno(stdin), buf, BUFS )) > 0)
...
38 while( (yv=yylex()) != 0)
39 {
40 std::cout << " yylex() " << yv << " yylval.dval " << yylval.dval << std::endl;
41 t0.value=yylval.dval;
42 Parse (pParser, yv, t0);
43 }
...
45 Parse (pParser, 0, t0);
46 ParseFree(pParser, free );
まとめ
lemonは速く, 完全にパブリックドメインであり, SQLiteで十分にテストされ
た, スレッドセーフなパーザジェネレータです. パーザジェネレータはゼロか
ら完全なプログラムを書く時間の数分の一の時間で複雑な動作をする再利用可
能なコードを書くための助けになります. 文法ファイルは様々な用途にあわせ
て修正できます.
私はlemon.cに関して何ら問題ありませんでしたが, -Wall -Wフラグをつけた
ときに符号つき/なし整数に関する以下のような警告が出ました:
[chirico@third-fl-71 lemon_examples]$ gcc -Wall -W -O2 -s -pipe lemon.c
lemon.c: In function `resolve_conflict':
lemon.c:973: warning: unused parameter `errsym'
lemon.c: In function `main':
lemon.c:1342: warning: unused parameter `argc'
lemon.c: At top level:
lemon.c:2308: warning: return type defaults to `int'
lemon.c: In function `preprocess_input':
lemon.c:2334: warning: comparison between signed and unsigned
lemon.c:2352: warning: control reaches end of non-void function
lemon.c:2311: warning: `start' might be used uninitialized in this function
lemon.c:2313: warning: `start_lineno' might be used uninitialized in this function
lemon.c: In function `Parse':
lemon.c:2393: warning: comparison between signed and unsigned
lemon.c: In function `tplt_open':
lemon.c:2904: warning: implicit declaration of function `access'
lemon.c: In function `append_str':
lemon.c:3019: warning: comparison between signed and unsigned
lemon.c:3011: warning: unused variable `i'
lemon.c: In function `translate_code':
lemon.c:3109: warning: control reaches end of non-void function
これではparse.cに既存のコードを追加したときに不便です. 現在修正中です.
修正が近々完了することを期待しています. よって, ここで使っている
lemon.cは作者のサイトからあなたが取得できるものと同じバージョンだと思
います. よって, パッチを当てるのも容易だと思います.
lemonやbisonのようなパーザが多機能すぎる時があります. これらは強力なツー
ルです. あなたがC++プログラマでインラインパージングだけが必要なのであ
れば, spiritライブラリという手もあります. 参考文献の9番を参照しましょ
う.
この記事の例題
パーザ自身を含めた例題すべてをここからダウンロードできます.
参考文献
- ゼロからデスクトップ計算機を書いた例
- flexとbisonパーザの例
- lemonパーザジェネレータのページ
- SQLiteのページ
- パーザ用語集
- パーザの良い手引き
- GNU flexマニュアル
- GNU bisonマニュアル
- spiritパーザ
- C Flex字句解析ツールとともにC++ Bisonパーザを使おう
- Lex-YACCハウツー
Author's bio:
Mike Chirico, a father of
triplets (all girls) lives outside of Philadelphia, PA, USA. He has
worked with Linux since 1996, has a Masters in Computer Science and
Mathematics from Villanova University, and has worked in
computer-related jobs from Wall Street to the University of
Pennsylvania. His hero is Paul Erdos, a brilliant number theorist who
was known for his open collaboration with others. Mike's notes page is
souptonuts.
T-Shirts and Fame!
We're eager to find people interested in writing articles on
software-related topics. We're flexible on length, style, and
topic, so long as you know what you're talking about and back up
your opinions with facts. Anyone who writes an article gets a
t-shirt from ThinkGeek
in addition to 15 minutes of fame. If you think you'd like to try
your hand at it, let jeff.covey@freshmeat.net
know what you'd like to write about.
[add comment]
|
|
