yacc/lex再入門

いやあ、長年使っていたものでも、ちょっと触らないと忘れるものですねえ～。

と、言うことで、メモ

 yaccの起動、lexの起動、Makefile

yacc/lexは残念ながらC++との若干の相性の悪さがあるため、全体はC++で作成 するにしてもyacc/lex部のみはcとします。

まずはMakefile。
ここではyaccソースtest_1_y.yとlexソースtest_1_l.lから実行プログラムtest_1_y を作成し、実行するものとします。簡便化のためmainはyaccソースに埋め込みました。

SHELL = /bin/sh
.SUFFIXES:.o .c .y .l

test_6:test_6_y　　　　　　　　# 実行
	test_6_y < test_6.txt

TEST_6_OBJS= test_6_y.o test_6_l.o
test_6_l.o : test_6_y.h test_6_l.c
test_6_y   :  $(TEST_6_OBJS)
	gcc -o $@ $(TEST_6_OBJS) # リンク

.y.h :
	yacc -d $*.y             # Tokenコード定数ヘッダ吐き出し
	mv y.tab.h $*.h
.y.c :
	yacc $*.y
	mv y.tab.c $*.c          # yacc起動
.l.c :  $*.l
	lex $*.l                 # lex起動
	mv lex.yy.c $*.c

clean :
	rm *.o *_y.c *_l.c

 lexの記述

ここではlexでは英数字による名前トークンと、その他の文字を取得するものとします。 空白は読み飛ばします。

%{
typedef struct str_chain_ {
   struct str_chain_ *next;   
   char              *text;
   } str_chain;
#include "test_6_y.h"   // yacc生成
%}
%%
[ \t\n]*              ; // 空白
[a-zA-Z][a-zA-Z0-9_]* {
                        fprintf(stdout,"\"%s\"\n",yytext);
                        yylval.sval= malloc(strlen(yytext)+1);
                        memcpy(yylval.sval,yytext,strlen(yytext)+1);
                        return NAME;
                      }
.                     {
                        fprintf(stdout,"\"%s\"\n",yytext);
                        return yytext[0];
                      }

lexはトークン定義を%%の後ろに置きます。

トークン定義はトークンの文字パターンの定義の後に{}で囲んで、その パターンに対する処理を書きます。
このとき、yytextにパターンにマッチした文字列が入っています。
戻り値はトークンコードです。
yylvalに値を設定すればyaccでその値を得ることが出来ます。

c言語による記述が必要な場合（通常そうです）%{と%}の間に書きます。

ここでは書いていませんが、%}から%%の間にオプションや補助パターンを 記述できます。

 yaccの記述

次のような構文を考えます。

a : b c d ;
e : f ;
g : h i ;

先頭の名前の後ろに":"があり、名前のリストが続き、";"で終わります。

yacc記述は次のようになります。

%{
#include <stdio.h>
int yywrap()               { return 1; }
void yyerror(const char* s){ fprintf(stderr,"%s\n",s);  } 
int main(char**args)       { yyparse(); }
typedef struct str_chain_ {
   struct str_chain_ *next;   
   char              *text;
   } str_chain; 
%}
%union { char *sval; str_chain* chain; }
%TOKEN <sval>  NAME
%type  <chain> list
%start defs
%%
defs : def
     | defs def
def  : NAME ':' list ';' { fprintf(stdout,"%s :",$1);
                           str_chain*next;
                           str_chain*chn;
                           for(chn=$3;chn;chn=next){
                              fprintf(stdout," %s",chn->text);
                              next= chn->next;
                              free(chn->text);
                              free(chn);
                              }
                           fprintf(stdout,"\n");}
list : /* null */        { $$=0; }
     | list NAME         { $$=(str_chain*)malloc(sizeof(str_chain));
                           $$->next=$1;
                           $$->text=$2; }        

構文パターンの後ろに{}ブロックを置き、そこにプログラムを書きます。

lexからの情報の引き受け、およびyaccの各定義間での情報の引渡しのための union構造を%unionで定義します。
ここではchar*とstr_chain*もつunionを定義しています。

トークンおよび各定義がこのunionのどの値を持つかを%TOKENおよび%typeで 指定します。

プログラムの中では、構文パターンのn番目の要素の値を$nで参照できます。
構文自体の値は$$になります。
このプログラムでは、NAMEのリスト逆順に連結されるようにしています。

%startで構文の入り口を指定します。

これを実際に動かした例を示します。

test_6_y < test_6.txt
"a"
":"
"b"
"c"
"d"
";"
a : d c b
"e"
":"
"f"
";"
e : f
"g"
":"
"h"
"i"
";"
g : i h

 ＃＃＃

2010/6/22:yaccの例を%typeを使う形に修正

 java用の構文解析ツール

java用のsymphonieという強力な構文解析ツールが（仮）公開されています。
これはyacc/lexのようなプログラム生成型のものではなく、 構文定義(BNFを繰り返し定義拡張してあります）と文を 与え、利用者プログラムに順次構文要素を上げる、 構文解析ライブラリです。

yaccと異なり、LR(1)制限はありません。構文定義とプログラムは 完全分離しています。構文定義だけで利用者プログラムを書かなくても 文のチェックを行い構文木をＸＭＬ形式で出力する機能なども持ちます。

• パッケージotsu.symphonieの説明

ライブラリ全体の説明は

• オツライブラリ

にあります。
これを公開しているオツアンドサンズのホームページは

• オツアンドサンズ

です。