Lexとyaccでコードをビルドする 第2回: 開発とトラブルシューティング

実際に何かを作る

2回シリーズ第2回目の今回は、もう少し進んだlex/yacc開発を取り上げ、また基本的なトラブルシューティング手法を紹介します。プログラムが皆さんの目の前でeメールのヘッダーを構文解析するのです! 面白いエラー・メッセージを出すのです! コンピューターが実際に何かを計算するのです!

Peter Seebach, Author, Freelance

Peter SeebachPeter Seebachは健全とは思えないほどエミュレーターでOSを走らせていますが、それを楽しいことだと思っています。エミュレーターのエミュレーターのエミュレーターは走らせたことはありませんが、そのうちにするかも知れません。



2004年 8月 24日

第1回の記事を基にして、この記事ではlexとyaccを使った具体的なアプリケーションを幾つか取り上げ、見落としがちな落とし穴について説明します。ここで取り上げる例、単純な電卓とeメールのメッセージを構文解析するプログラムは非常に単純なものです。

Lexのみのコード

Lexを使えば、パーサーに対してトークンのシーケンスを生成することができますが、単純な入力操作もlexを使って行うことができます。lexのみを使って、単純な英語の文を風変わりな言葉に変換するためプログラムが幾つか書かれています。おそらく最も有名なものはインターネットで広く配布されている古典的なSwedish Chef翻訳でしょう。こうしたプログラムはちょっとしたパターンを認識して、即座にそのパターンに対応するのです。良くできた字句解析プログラムを見ると、トークン化プログラム(tokenizer)をどのように書けば良いかが分かります。Swedish Chefプログラムへのリンクは参考文献にあります(ソースもありますので、どのように動作するのかが具体的に分かります)。

当然ですが、大部分の単純なプログラミングのプロジェクトでは、非常に単純な字句解析プログラムで済ませることができます。文脈を知らなくても確実にトークンを認識するように、言語設計にちょっとした注意を組み込んでおけば、字句解析を大幅に単純化できます。当然ですが、全ての言語がそれに適しているわけではありません。例えば、特別な文字が他の文字を修飾するCのストリング定数をlexで扱うのは楽ではありません。


お遊びの例:電卓

下記の例は1ページほどのyaccと半ページほどのlexコードで書けるプログラムです。これを見ると、幾つか面白いことが分かります。それに、時には、まあ、便利です。

単純な電卓のための字句解析プログラム
%{
#include "calc.h"
#include "y.tab.h"
%}
NUMBER  [0-9]+
OP	[+-/*]
%%
{NUMBER}	{ yylval.value = strtol(yytext, 0, 10); return NUMBER; }
({OP}|\n)	{ return yytext[0]; }
.		{ ; }

このプログラムでしていることは、数字や演算子、改行などの突き合わせだけです。数字には特別なトークンNUMBERが戻ります。他は全て単純な文字として戻ります。一致しない文字は黙って無視されます。

リスト2. 単純な電卓用のパーサー
%{
#include <stdio.h>
#include "calc.h"
%}
%union {
	long value;
}
%type <value> expression add_expr mul_expr
%token <value> NUMBER
%%
input:
	  expression
	| input expression
expression:
	  expression '\n' { printf("%ld\n", $1); }
	| expression '+' add_expr { $$ = $1 + $3; }
	| expression '-' add_expr { $$ = $1 - $3; }
	| add_expr { $$ = $1; }
add_expr:
	  add_expr '*' mul_expr { $$ = $1 * $3; }
	| add_expr '/' mul_expr { $$ = $1 / $3; }
	| mul_expr { $$ = $1; }
mul_expr:
	  NUMBER { $$ = $1; }

このパーサーは、yaccに競合を解決させる上で、明示的に%prec宣言を使うことなく優先順位や結合順序を扱うための一つの方法を示しています。バインドの緩い演算子が、バインドのきつい演算子を使った表現をオペランドとして使う場合には、優先順位は自動的に処理されます。これは、例えばC標準での、正式な文法の定義方法です。

注意して欲しいのですが、ある表現の後に改行がある場合には、その表現の値は単純に出力されます。長期間の保存は必要なく、どの変数も変更はされません。即席のデスクトップ電卓にはこれで充分です。

左再帰(left recursion)の使い方にも注意してください。yaccは左再帰を好みます。「input」のルールを次のように書くのは全く正しいのです。

input:expression
| expression input

ただしこれを行うと、書かれた各表現が、パーサーで別レイヤーの再帰を引き起こします。元々書かれている通り、次の表現を構文解析する必要があるまで、各表現はinputオブジェクトにまで削減されます。左再帰はより効率的であり、大きな入力セットに対しては、唯一の現実的なオプションかも知れません。


具体的な例:eメールを構文解析する

課題として考えられるのは、eメール・メッセージを含むファイルを読み込み、そのヘッダーや内容を抽出することです。ヘッダーを読むためのルールは非常に複雑で、一部に対しては開始状態を使った方が現実的になることから、これは面白い例ということができます。メッセージのどこにあるのかを検索する作業の一部は字句解析プログラムが実際に行いますが、相変わらずパーサーが全体を把握するのです。

このサンプル・プログラムは個々のメッセージ、あるいはBerkeleyの「mbox」フォーマットを読むことができます。また「From」で始まる行をメッセージの区切り記号としてとして使います。これは変更することもできますが、これでも充分間に合います。

これをサポートするコードはごく単純です。「sz」タイプは便宜上のコードであり、ストリングが大きくなった時に行われるストリングの再割り付け作業を隠すストリング・ライブラリーです。この構造はごく最低限のものであり、あまりうまく汎用化されてはいませんが、それはコードを小さく、読みやすくするためです。実際のコードはもう少し汎用になります。

文法は大部分きわめて単純です。ファイルは一つまたは複数のメッセージからできています。各メッセージの後でルールが削減されるように左再帰が使われます。メッセージはヘッダーと空の行、そして本体から成り立っています。本体は簡単に読むことができるものであり、何行もの行が入っています。本体には明示的な終了記号が無いことに注意してください。その代わり「メッセージ本体ではないもの」はまず、次のオブジェクトらしきものの初めに一致する必要があります。読み返したり先に進んだりするうちに、それがヘッダーの一部に違いないと分かるようになります。本体ではLINEトークンのみが起こりうるので、次に現れてくる別のトークンはヘッダーの一部、あるいは構文エラーであろうということになります。特別な場合として(yaccでは文法で述べておらず暗黙的ですが)、0トークンは、もうトークンが無いこと、そして構文解析を終了することを意味します。開始ルール(この場合はfile)は無事削減され、構文解析は成功したと見なすことができます。

ヘッダー・プログラムは極限まで複雑というほどではありませんが、かなり複雑です。ヘッダーはheaderlineまたはFROMLINEトークンで開始します。逆にheaderline非終了記号(non-terminal)にはヘッダー名、ヘッダー本体、それにオプションとして継続要素が必要です。ここでも再度、継続行は効率的になるように、左再帰を使って処理されます。理論的に言うとこの文法は、複数の「From」行を持つヘッダーを受け付けてしまうことに注意してください。これを修正することもできますが、これを心配する理由も特に見あたりません。

この例での字句解析プログラムは電卓の場合よりも、はるかに複雑です。これは開始状態を使用しており、この機能によって字句解析プログラムは、ある時にだけ一部のルールを突き合わせることができるようになります。字句解析プログラムが使用する2つの状態にはBODYHEADERという名前が付いています。HEADER状態はメッセージ・ヘッダー全体を構文解析するためではなく、与えられた名前/値の対の、値部分を構文解析する時に使います。LINEパターンの一突き合わせにHEADERルールとBODYルールがあるのは、字句解析プログラムが(行全体を戻し始める前に)ヘッダー名や継続要素を確実に識別させるようにするためです。単に行全体を戻してしまうと、パーサーはその行をどうすべきか判定するために、行の解析をしなければならなくなります。

これは、空の行によってヘッダーと本体が分離されているということを、字句解析プログラムとパーサーの両方が知っている必要があることを意味します。同様に、字句解析プログラムは継続要素の構造についても知っている必要があります。パーサーが知っているのは、ヘッダーに追加すべきテキストを時々受け取ることがある、ということだけです。

このプログラムでは、パーサーはグローバル変数を使って、構文解析するメッセージのリストを追跡します。こうしてテストプログラムはメッセージのリストにアクセスするのです。yyparse()への呼び出しは単に成功か失敗かを示す結果を戻すだけで、その呼び出しでは作られたオブジェクトは戻しません(構文解析が成功した場合の戻り値はゼロ、失敗した場合はゼロ以外です)。


一般的な問題のトラブルシューティング

Lexとyaccは、あまり複雑でないファイル・フォーマットであれば、非常にうまく構文解析を行います。最大の制約は、yaccの先読みが一つのトークンに制限されていることです。これはつまり、yaccが次に行うべき動作を判断するために2つのトークンを先読みする必要がある時には、下記の文法は構文解析することができない、という意味になります。

リスト3. yacc文法としてのUncle Shelby's ABZ
a_f:
	  'a' 'b' 'c' 'd' 'e' 'f' { printf("alphabet\n"); }
	| 'a' 'b' 'z' 'd' 'e' 'f' { printf("Silverstein\n"); }

(注)Uncle Shelby's ABZについては参考文献を見てください

この場合では、yaccが何かをしなければならなくまでには、yaccは普通のアルファベットとUncle Shelby's ABZのどちらのアルファベットを構文解析しているかを知ることができます。ところが次のようなルールを書いてしまうと、うまく動作しません。

リスト4. 構文解析不可能な文法
a_f:
	  'a' { printf("alphabet\n"); } 'b' 'c' 'd' 'e' 'f'
	| 'a' { printf("Silverstein\n"); } 'b' 'z' 'd' 'e' 'f'

この場合では、2つのうちどちらにするかの判断に使えるトークンとしては文字「b」のみですが、この場合どちらのルールでもbで、同じです。この文法は曖昧で、yaccは何が起きているかを判断することができません。

ただし、yaccは一文字先読みすることができます。ですから、

リスト5. 構文解析可能な文法
a_f:
	  'a' 'b' { printf("alphabet\n"); } 'c' 'd' 'e' 'f'
	| 'a' 'b' { printf("Silverstein\n"); } 'z' 'd' 'e' 'f'

これならば大丈夫です。「c」または「z」のどちらかを見れば、yaccはどちらのルールを使うべきかを充分に判断できます。あまり複雑でないファイル・フォーマットを扱うには、通常はこの程度でも充分柔軟です。

競合の解決

たいていの人はやがてshift/reduce競合またはreduce/reduce競合に突き当たります。shift/reduce競合の方が問題は小さいのですが、reduce/reduce競合は一般的により深刻です。shift/reduce競合で一番よく知られている例は、Cでの「ぶら下がりelse」の曖昧さです。

次のようなyacc文法を考えてみてください。

リスト6. ぶら下がりelse
statement	  if '(' condition ')' statement
         	| if '(' condition ')' statement else statement
		| printf '(' string ')' ';'

これは、ちょっと単純化されているかも知れませんが、実際のC文法にかなり似ています。では条件ステートメントが、別の条件ステートメントの中にネストしている場合に、これがどうなるかを考えてみてください。

リスト7. ネスト化した条件
if (a)
if (b)
printf("a and b\n");
else
printf("???\n");

elseトークンは内側のifif (b))に付いているのでしょうか、それとも外側のifに付いているのでしょうか。どちらにしても、if/else構造体が一つあり、単純なifが一つあります。これはshift/reduce競合と言われます。yaccはelseトークンを見ると、(if (b)からセミコロンまでの)シーケンスを削減してステートメントにしてしまうか(既にprintf行全体をステートメントにまで削減しています)、あるいはelseトークンをそのシーケンスにシフトしてしまい、長くしたパターンの初めの方とします。実際yaccの解釈は次のようになります。

リスト8. 解決されたぶら下がりelse
if (a)
	if (b)
		printf("a and b\n");
	else
		printf("a and not-b\n");

デフォルトの振る舞いとしては削減よりもシフトが優先しており、多くの場合はこの方が好都合です。別のパターンの優先順位を設定することによって、この振る舞いを強制することができます。別のオプションとしては、この曖昧さを排除するような自分の文法を設計することです。例えばperlの場合、ifステートメントがオプションでない時には、elseが内側のifステートメントの一部なのか、外側のifステートメントの一部なのかが分かりやすいように、本体の回りを大括弧で囲みます。

字句解析プログラムでもよく問題が起きます。一般的な問題は、長すぎるようなテキストとの一致を調べるようなルールを作ってしまうことです。さらに困るのは、lexは見つけられる限り長い一致を見つけようとするので、まるで不適切なルールで一致検出が行われてしまう場合です。これに対処するには開始状態が大いに役に立ちます。もっと強力なツールは排他状態で、これを使えば排他状態に一致するルールのみが突き合わせされるようになります(全てのバージョンのlexでこれをサポートしているわけではありませんが、最近のものであれば、どれでも使用できるはずです)。

自分が使っているlexのバージョンに排他状態が無い場合には、全てのルールを状態で修飾し、その状態間で切り換えることができます。デフォルトとして使いたい状態をBEGINで始めるのに%{...%}ブロックを使うと、そのブロックは他の全状態が排他的であるかのように動作します。


複数のパーサーと字句解析プログラム

かつては一つのプログラム内で複数のパーサーを使うためには、lexやyaccが生成するファイルを、充分時間をかけて注意深く調整することが必要でした。幸いなことにこれは修正されています。lexもyaccも最近のバージョンでは、生成されたコードでのシンボル名に対して使うプレフィックスを規定することができます。その通りにやってみれば良いのです。その方が簡単です。flexではこのオプションは-Pprefixであり、最近のyaccではたいていの場合、-p prefixです。デフォルトで用意されているlexやyaccがこれをサポートしていない場合でも、まず確実にflexやbisonを使うように設定することができます。


今後は・・

Lexやyaccについてさらに学ぶためには、お遊びプログラムを幾つか書いてみるのが一番です。サンプル・プログラムはインターネットにたくさんあります。ちょっと検索してみれば、いろいろ素晴らしいものが見つかるはずです。この記事の最後に挙げたリンクも役に立つと思います。

字句解析プログラムと構文解析プログラムには、できうる限り別々のテスト・プログラムを書くようにします。問題が見つかった時には、どこが悪いかを知ることが重要です。問題が、トークンが悪いせいなのか、文法が間違っているためなのかを知ることがまず第一歩です。適切なyyerrorルーチンを書くように少し努力すれば、大いに役に立ちます。文法が複雑になればなるほど、エラーが起きた時に明確で意味のある診断を下すことがより重要になってきます。

参考文献

  • このシリーズ第1回ではlexやyacc、flex、bisonを紹介しています。この記事を読む前に読んでください。
  • PeterのWebサイトに、この記事で使用しているサンプル・コードがポストされています。
  • The Lex & Yacc Page、またはその副題「The asteroid to kill this dinosaur is still in orbit(この恐竜を殺すためのアステロイドはまだ軌道を回っている)」には、歴史的な幾つかの参考文献や、lexやyaccに関する非常に良いドキュメンテーションが置かれています。
  • LexとyaccのGNU版はflexbisonです。GNUではどれもそうですが、様々なフォーマットでの完全なユーザー・マニュアルを含めて、素晴らしい資料が付属しています。
  • John Levine著のlex & yacc, 2nd Edition (1992年O'Reilly & Associates刊)は現在でも決定版と言うことができます。
  • Lexやyaccでの競合の解決方法についての説明の他、トラブルシューティングにも使われている「ABZ」文法の起源は、Shel Silverstein著によるUncle Shelby's ABZ's(1961年Simon and Schuster刊)です。
  • Chef/Jive/ValSpeak/PigはSwedish ChefやValley Girl、Jive、Pig Latin等を話す翻訳サイトで、純lexコードで書かれています。「lex and yacc are fun」と入力すると「lex und yecc ere-a foon」が出力されます(The Muppet ShowによるSwedish Chefがデフォルトです)。
  • ANSI C yacc grammarはまあまあ完全なC89文法で、yaccで書かれています。これに対応する字句解析プログラムを書いてみてください。自分独自のCコンパイラーも書いてみてください。ちょっと一仕事必要なだけです・・。
  • 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関連の技術書が値引きして購入できます。
  • Linux上で実行する、より抜きのdeveloperWorks Subscription製品の無料の試用版をダウンロードして下さい。developerWorksのSpeed-start your Linux appセクションからWebSphere Studio Site DeveloperやWebSphere SDK for Web services、WebSphere Application Server、DB2 Universal Database Personal Developers Edition、Tivoli Access ManagerそれにLotus Domino Serverが入手できます。もっと手早くしたければ、ハウ・ツー記事や技術サポートが製品毎に集められていますので、ご自由に入手して下さい。

コメント

developerWorks: サイン・イン

必須フィールドは(*)で示されます。


IBM ID が必要ですか?
IBM IDをお忘れですか?


パスワードをお忘れですか?
パスワードの変更

「送信する」をクリックすることにより、お客様は developerWorks のご使用条件に同意したことになります。 ご使用条件を読む

 


お客様が developerWorks に初めてサインインすると、お客様のプロフィールが作成されます。会社名を非表示とする選択を行わない限り、プロフィール内の情報(名前、国/地域や会社名)は公開され、投稿するコンテンツと一緒に表示されますが、いつでもこれらの情報を更新できます。

送信されたすべての情報は安全です。

ディスプレイ・ネームを選択してください



developerWorks に初めてサインインするとプロフィールが作成されますので、その際にディスプレイ・ネームを選択する必要があります。ディスプレイ・ネームは、お客様が developerWorks に投稿するコンテンツと一緒に表示されます。

ディスプレイ・ネームは、3文字から31文字の範囲で指定し、かつ developerWorks コミュニティーでユニークである必要があります。また、プライバシー上の理由でお客様の電子メール・アドレスは使用しないでください。

必須フィールドは(*)で示されます。

3文字から31文字の範囲で指定し

「送信する」をクリックすることにより、お客様は developerWorks のご使用条件に同意したことになります。 ご使用条件を読む

 


送信されたすべての情報は安全です。


static.content.url=http://www.ibm.com/developerworks/js/artrating/
SITE_ID=60
Zone=Linux
ArticleID=228937
ArticleTitle=Lexとyaccでコードをビルドする 第2回: 開発とトラブルシューティング
publish-date=08242004