目次


Lexとyaccでコードをビルドする 第1回: 導入

Lex、yacc、flexそしてbisonと出会う

Comments

ほとんどの人にとっては、lexやyaccが何をするものなのか知る必要はありません。時には何かダウンロードしたものをコンパイルするためにインストールしておく必要がありますが、ほとんどの場合、インストールしたものはそのまま動作します。稀にREADMEファイルが「shift/reduce」競合を参照することがあるくらいでしょう。ただし、こうしたツールはUnixツールボックスの一部として相変わらず貴重なものであり、少し慣れておくと非常に役に立つものです。

Lexとyaccはほとんど常に一組のように言われますが、実際には、別々に使用するものです。些末ながら非常に楽しいプログラムが幾つか、全てlexで書かれています(参考文献)。一方lexではなくyaccを使ったプログラムは稀です。

この記事全体を通して、「lex」や「yacc」と言う場合には、これらユーティリティのGNU版であるflexやbisonも含めるものとして使います。ここで提供するコードは、主要なバージョン、例えばMKS yaccなどの全てで動作するはずです。どれもみな同じ家族の一員なのです!

この記事は2回の構成です。最初の記事ではlexとyaccをより一般的な言葉で紹介し、これらが何を行うものか、それをどのように行うかを解説します。2回目では、これらを使った実際のアプリケーションを説明します。

Lexやyaccとは何か、両者を一緒にするのはなぜか?

Lexとyaccは対となったツールです。lexはファイルを何セットかの「トークン」に(大まかに例えて言うと単語のようなレベルにまで)分解します。yaccは何セットかのトークンをまとめて高位レベルの構造体(例えて言うと文のように)に組み立てます。yaccはlexの出力を相手にするように作られていますが、皆さんが自分でその隙間を埋めるような独自のコードを書くこともできます。同様にlexの出力は大部分、何らかのパーサーに送られるように作られています。

Lexとyaccは、適切に構造化されたフォーマットを持つファイルを読むためのものです。例えば、多くのプログラミング言語で書かれたコードをlexとyaccを使って読むことができます。また多くのデータ・ファイルも、lexとyaccを使って読むに十分なほどの予測可能なフォーマットを持っています。かなり単純で一般的な文法を構文解析するためにlexとyaccを使うこともできます。自然言語は対象外ですが、大部分のコンピューター・プログラミング言語は対象範囲内です。

Lexとyaccはプログラム構築のためのツールです。lexとyaccからの出力自体がコードであり、これをコンパイラーに渡す必要があります。通常、lexやyaccが生成するコードを使うためには、さらにユーザー・コードを追加します。ほとんどコード追加が必要ない単純なプログラムもあれば、非常に大きく複雑なプログラムの小さな一部としてパーサーを使用するものもあります。

ではそうしたプログラムをもっと詳しく見てみましょう。

Lex: A lexical analyzer generator(字句解析プログラム生成器)

字句解析プログラムはSFドラマに出てくるような携帯型の小道具ではなく、認識できる断片にまで入力を分解するプログラムです。例えば単純な字句解析プログラムであれば、入力中の語数を数えるかもしれません。lexは仕様ファイルを読み込んで、仕様に対応する字句解析プログラムをCコードで生成します。

一番分かりやすい説明は例を見ることでしょう。下記はflexのmanページからとった単純なlexプログラムです。

リスト1. lexを使って語数を数える
int num_lines = 0, num_chars = 0;
%%
\n      ++num_lines; ++num_chars;
.       ++num_chars;
%%
main() {
	yylex();
	printf("# of lines = %d, # of chars = %d\n", num_lines, num_chars);
}

このプログラムには、%%マーカーで分けられた3つのセクションがあります。最初と最後のセクションは、おなじみの単純なCコードです。真ん中が面白いセクションで、一連のルールから成っており、これをlexが字句解析プログラムに変換します。そしてそれぞれのルールは正規表現と、その正規表現が一致した時に実行されるコードから成っています。一致しないテキストはどれも、単純に標準出力にコピーされます。ですからある言語をプログラムで構文解析する場合であれば、可能性のある全ての入力を字句解析プログラムが確実に捉えるようにしておくことが重要です。そうしないと、取り残されたものが(どんなものであっても)まるでメッセージであるかのように、ユーザーに対して表示されてしまいます。

実のところ、リスト1のコードは完全なプログラムなのです。これをlexを介してコンパイルし、その結果を実行すると、そうするのだろうと思える通りのことをするのです。

この場合では、何が起こるかは非常に簡単に見ることができます。改行は常に最初のルールに一致します。それ以外の文字はどれも2番目のルールに一致します。lexはそれぞれのルールを順に試し、一連の入力のうち、最も長いもので一致を調べます。もし何かがどのルールにも全く一致しない場合には、lexは単純にそれを標準出力にコピーします。ただしこの振る舞いは多くの場合、望ましいものではありません。簡単な解決方法としては、何にでも一致するような最後のルールを追加して、(怠惰な人であれば)全く何もしないか、あるいは何らかの診断を出力させます。lexは、例え後の方にあるものでも長い一致を優先することに注意して下さい。ですから次のようなルールがあったとして「uuu」を入力すると、lexは最初の2文字を使って最初に2番目のルールとの一致を調べ、次に最初のルールでの一致を調べます。

u { printf("You!\n"); }
uu { printf("W!\n"); }

ただし、何かが2つのルールのどちらかに一致する場合には、lex仕様の中での順番が、どちらのルールを使うかを決めることになります。一部のバージョンのlexでは、そのルールに一致するものがない場合に警告を出します。

Lexが便利な上に面白いのは、もっと複雑なルールも処理できることです。例えば、あるC識別子を認識するルールは次のようなものになります。

[a-zA-Z_][0-9a-zA-Z_]* { return IDENTIFIER; }

ここで使われている構文は、おなじみの正規表現構文です。ただし幾つかの拡張もあります。その一つは共通パターンに名前をつけられることです。上に挙げたlexプログラムの最初のセクションで、最初の%%の前で次のようなものに名前を定義することができます。

DIGIT [0-9]
ALPHA [a-zA-Z]
ALNUM [0-9a-zA-Z]
IDENT [0-9a-zA-Z_]

こうしておくと、ルールのセクションでこれらの名前を大括弧に入れることで、これらを逆参照できるようになります。

({ALPHA}|_){IDENT}*{ return IDENTIFIER; }

それぞれのルールには対応したコードがあり、正規表現に一致した時にこのコードが実行されます。このコードは必要などんな必要な処理も行い、またオプションとして値を戻します。パーサーがlexの出力を使用している場合には、この値が使用されます。例えば行を数えるような単純なプログラムでは、パーサーは特に必要ありません。ところが新しい言語でのコードを解釈するためにパーサーを使用している場合には、どのようなトークンを見つけたかをパーサーに伝えるために、何かをパーサーに戻す必要があります。共有のインクルード・ファイルの中で単にenumまたは一連の#define疑似命令を使うこともできますし、あるいはyaccに事前定義した値のリストを生成させることもできるのです。

Lexはデフォルトで標準入力から読み取ります。他のファイルを読み取るようにすることも簡単にできますが、例えばバッファーから読み取るのは少し難しくなります。このために完全に標準化された方法はありません。一番移植性が高いのは、一時ファイルを開いてそこにデータを書き込み、その一時ファイルを字句解析プログラムに渡す方法です。このためのサンプル・コードの一部は以下のようなものです。

リスト2. メモリー・バッファーを字句解析プログラムに渡す
int
doparse(char *s) {
        char buf[15];
        int fd;
        if (!s) {
                return 0;
        }
        strcpy(buf, "/tmp/lex.XXXXX");
        fd = mkstemp(buf);
        if (fd < 0) {
                fprintf(stderr, "couldn't create temporary file: %s\n",
                        strerror(errno));
                return 0;
        }
        unlink(buf);
        write(fd, s, strlen(s));
        lseek(fd, 0, SEEK_SET);
        yyin = fdopen(fd, "r");
        yylex();
	fclose(yyin);
}

このコードは注意深く一時ファイルをリンク解除し、自動的にクリーンアップするように、既に除去されてオープンになっている状態にします。もっと注意深いプログラマーであれば、あるいは読者のために限られたスペースでサンプルコードを書く人でなければ、ユーザーがTMPDIRを選択する意味合いも検討するかも知れません。

yacc: yet another compiler compiler

さて、入力をトークンの流れとして分解しました。今度は高位レベルのパターンを認識する方法が何か必要です。ここがyaccの出番です。yaccを使うことで、トークンで何をしたいかを記述できるようになるのです。yaccの文法はたいてい下記のようなものになります。

リスト3. 単純なyacc文法
value:
		  VARIABLE
		| NUMBER
expression:
		  value '+' value
		| value '-' value

これは、表現が幾つかの形式(例えば変数、プラス記号、それに数字もあり得ます)のうち、どれでも良いことを意味しています。パイプ文字(| )は他にとり得るものを表します。字句解析プログラムが生成するシンボルは終了記号(terminals)またはトークン(tokens)と呼ばれます。また、これらから組み立てられるものは非終了記号(non-terminals)と呼ばれます。ですからこの例ではNUMBERは終了記号で、字句解析プログラムはこの結果を生成します。対照的にvalueは非終了記号で、終了記号から組み立てることによってのみ、これが作られます。

Yaccファイルはlexファイルと同様、セクションが%%マーカーで区切られています。またlexファイルと同様、yaccファイルには3つのセクションがありますが、最後のセクションはオプションで、生成されるファイルに取り込まれる単純なCコードのみを含んでいます。

Yaccはトークンのパターンを認識することができます。例えば上の例のように、ある表現が、値とプラスまたはマイナス記号、そしてもう一つの値から成ることを認識することができます。また、動作を起こすこともできます。例えば{}の対で囲まれた何ブロックかのコードがあると、パーサーが表現の中でそこに達した時にそのコードが実行されます。例えば次のようなものを書くことができます。

expression:
value '+' value { printf("Matched a '+' expression.\n"); }

Yaccファイルの最初のセクションは、パーサーが操作、生成するオブジェクトを定義します。このセクションが空の場合もありますが、ほとんどの場合は少なくとも幾つかの%token疑似命令を含んでいます。こうした疑似命令は字句解析プログラムが戻すトークンの定義に使用します。yaccを-dオプションで実行すると、定数を定義するヘッダー・ファイルを生成します。ですから下記を使用する先ほどのlexの例、

({ALPHA}|_){IDENT}* { return IDENTIFIER; }

この例には、次のような行を含んだ対応yacc文法があるかも知れません。

%token IDENTIFIER

Yaccは次のような行を含んだ(デフォルトでy.tab.hと呼ばれる)ヘッダー・ファイルを作ります。

#define IDENTIFIER 257

こうした数字は、有効な文字の範囲外でしょう。ですから字句解析プログラムは個々の文字をそのまま、あるいはこれらの定義された値を使った特別なトークンを戻します。これはあるシステムから別のシステムにコードを移植する場合に問題になります。一般的に、生成されたコードを移植するよりも、新しいプラットフォームでlexとyaccを再実行した方が無難です。

yaccが生成するパーサーはデフォルトとして、ファイルのルール・セクションで最初に見つけたルールを構文解析しようとする時に開始します。これを変更するには%startで別のルールを規定すれば良いのですが、たいていの場合は、最も優先度の高いルールをセクションの先頭に置く方がより賢明だと言えます。

トークン、タイプ、そして値、まあ何と素晴らしい!

次は表現のコンポーネントをどう扱うかという問題です。一般的な方法としては、yaccが操作するオブジェクトを含むようにデータ・タイプを定義します。このデータ・タイプはC unionオブジェクトで、yaccファイルの最初のセクションで%unionを使って宣言されます。トークンを定義する時にはタイプを規定することができます。例えば、お遊びのプログラミング言語であれば、次のようにすることができます。

リスト4. 最低限の%union宣言
%union {
	long	value;
}
%token <value>	NUMBER
%type <value>	expression

パーサーが字句解析プログラムが戻すNUMBERトークンを受け取る時には常に、グローバル変数yylvalvalueという名前のメンバーは意味を持つ値で満たされているもの、と想定できることを、このリストは示しています。もちろん字句解析プログラムは何らかの方法でこれを処理できる必要があります。

リスト5. 字句解析プログラムがyylvalを使えるようにする
[0-9]+	{
		yylval.value = strtol(yytext, 0, 10);
		return NUMBER;
	}

Yaccでは表現のコンポーネントをシンボル名で呼ぶことができます。非終了記号を構文解析する時には、その中に入っているコンポーネントには$1$2などと名前がつけられます。非終了記号が高位レベルのパーサーに渡す値は$$と呼ばれます。例えば、

リスト6. yaccの変数を使う
expression:
	NUMBER '+' NUMBER { $$ = $1 + $3; }

文字通りのプラス記号は$2 であり、何も意味のある値は持っていないのですが、やはり場所を占めていることに注意して下さい。「戻り」やその他のものを規定する必要はなく、ただ単に魔法の名前、$$に割り当てます。%type宣言は、expression非終了記号がこのUnionのvalueメンバーも使うことを規定しています。

場合によると、%union宣言に複数のタイプのオブジェクトがあると便利です。この時点では、%type宣言と%token宣言で宣言するタイプは、実際に使うものとなっているように確認する必要があります。例えば整数値とポインター値の両方を持つ%union宣言があり、そのポインター値を使おうとトークンを宣言し、ところが字句解析プログラムは整数値を入てしまう・・・というようなことになると、悪いことが起こります。

当然ながら、これでも最後の問題を解決することはできません。つまり最初の非終了記号表現には戻るところがどこにも無いので、非終了記号が生成する値を何とかする必要があります。このための一つの方法としては、必要のある作業全てを進みながら確実に行う、というものです。もう一つは(例えばアイテムのリンク・リストなど)単一の巨大なオブジェクトを構築し、それに対して開始ルールの最後にあるグローバル変数へのポインターを割り当てる、という方法です。ですから例えば上記の表現パーサーを汎用の電卓に組み込むような場合、単にパーサーだけを書いたとすると、非常に注意深く表現を構文解析した後、表現に対して何もしなかった、というプログラムが手元に残ることになります。これは学術的には興味深く、なにがしか美的感覚に訴えるところがあるかも知れませんが、あまり実用的なものではありません。

基本的な紹介はしましたので、自分で好きな時にlexとyaccを適当に少しいじる、例えば構文解析対象の表現を使って何らかのことを実際にするような単純な電卓を作る、という程度はできるようになったはずです。少しいじっていると気がつくことの一つは、lexとyaccはトラブルシューティングが難しいという点でしょう。次回の記事ではトラブルシューティングの手法を見て行きます。また実世界の作業に使えるような、もっと大きくて強力なパーサーも構築する予定です。


ダウンロード可能なリソース


関連トピック

  • 第2回 (US)ではlexとyaccの具体的なアプリケーションとして、単純な電卓の例とeメールのメッセージを構文解析するプログラムの構築方法を紹介します。
  • この記事で使用しているサンプルコードがPeterのWebサイトに置かれています。
  • The Lex & Yacc Pageには興味深い歴史的な参考資料が幾つかあり、またlexとyaccに関する非常に良い説明資料もあります。
  • LexとyaccのGNU版はflexbisonです。GNUではどれもそうですが、様々なフォーマットでの完全なユーザー・マニュアルを含めて、素晴らしい資料が付属しています。
  • John Levine著のlex & yacc, 2nd Edition (1992年O'Reilly & Associates刊)は現在でも決定版と言うことができます。
  • Yacc...そしてLexをよみがえらせる(developerWorks, 2000年11月)では、誰もが大好きな字句解析プログラム+パーサーのコンビの背景について、もう少し入門的な説明をしています。また例として、語数をカウントするプログラムを紹介しています。
  • Using SDL, Part 4: lex and yacc(developerWorks, 2000年5月)ではPirates Ho!というゲームを書く中で、このゲームのための設定ファイル・パーサーをlexとyaccを使って作り上げる方法を説明しています。
  • developerWorksのLinuxゾーンにはLinux開発者のための記事が他にも豊富に用意されています。
  • Developer BookstoreのLinuxセクションでLinux関連の技術書が値引きして購入できます。

コメント

コメントを登録するにはサインインあるいは登録してください。

static.content.url=http://www.ibm.com/developerworks/js/artrating/
SITE_ID=60
Zone=Linux
ArticleID=228936
ArticleTitle=Lexとyaccでコードをビルドする 第1回: 導入
publish-date=08112004