Lex and YACC primer/HOWTO PowerDNS BV (bert hubert ) v0.8 $Date: 2002/07/22 14:02:09 $ 大西 大樹 (daiki onishi ) v0.8j 2003/02/08 本ドキュメントは Lex と YACC の基本的な使い方について記述します ______________________________________________________________________ 目次 1. イントロダクション 1.1 本ドキュメントに含まれないもの 1.2 ダウンロード 1.3 ライセンスについて 2. Lex と YACC でできること 2.1 それぞれのプログラムのやっていること 3. Lex 3.1 正規表現でのマッチ 3.2 C のようなシンタックスをもつもう少し高度な例 3.3 おさらい 4. YACC 4.1 単純な温度調節器 4.1.1 YACC ファイルの全文 4.1.2 温度調節器のコンパイルと起動 4.2 引数を扱えるように拡張した、温度調節器 4.3 設定ファイルの構文解析 5. C++ での構文解析器の作成 6. Lex と YACC の内部動作 6.1 トークンの値 6.2 再帰 - '善(right=右）は悪' 6.3 より高度な yylval - %union 7. デバッグ 7.1 ステートマシン 7.2 コンフリクト: 'shift/reduce', 'reduce/reduce' 8. 関連情報 9. 謝辞 ______________________________________________________________________ 1. イントロダクション ようこそ、高貴なる読者のみなさん Unix 環境で、ある程度プログラミング経験を積まれている方なら、Lex & YACC、もしくは GNU/Linux ユーザの間で Flex & Bison として知られてい る、神秘的なプログラムをご存知のことと思います。Flex とは、Vern Paxon による Lex 実装であり、Bison とは GNU 版 YACC です。以下、断りのない限 りこれらを Lex & YACC と呼ぶことにします - Flex & Bison は、Lex & YACC と上位互換にあるので、本ドキュメントのサンプルもそのまま動作します。 これらのプログラムは、非常に利用価値の高いものです。しかし、C コンパイ ラの man ページがそうであるように、言語仕様はもとより使い方についてす ら満足な記述がありません。YACC は Lex と組み合わせて使うと、高い効果が 得られるのですが、Bison の man ページには Lex で生成されたコードと Bison のプログラムを協調動作させる方法についての記述がありません。 1.1. 本ドキュメントに含まれないもの Lex & YACC については、いくつか良書があります。深く知りたいのであれ ば、是非読むことをお勧めします。本ドキュメントに書かれているより、ずっ とたくさんの情報が得られるはずです。巻末の '関連情報' の章をご覧くださ い。ここでは、読者が簡単なプログラムを組める程度に、Lex & YACC の基本 的な使い方を解説することに内容をとどめます。 Flex と BISON に付属してくるドキュメントも良いのですが、チュートリアル がありません。この HOWTO の足りない部分を補完する分には有用ですが。こ れに関しても、巻末の関連情報の章をご覧ください。 筆者は YACC/Lex のエキスパートではありません。このドキュメントを書き始 めた頃でも、ちょうど二日の経験しかありませんでした。筆者の願いは、この 二日間を皆さんにとって、少しでも楽なものにしてあげたいということに尽き ます。 ここに例示される、YACC と Lex のコーディングスタイルが常に最も適切であ るとは限りません。コード例はシンプルにするよう努めましたが、より良い書 き方があるかもしれません。お気づきの点があれば是非、お教えください。 1.2. ダウンロード 例示されているコードは、すべて machine readable な形式でダウンロードで きます。詳細は ホームページ をご覧ください。 1.3. ライセンスについて Copyright (c) 2001 by bert hubert. この著作物の配布に関しては Open Publication License, vX.Y またはそれ以降で定められている規約と条件に準 拠します（最新版は http://www.opencontent.org/openpub/ で入手可能で す）。 2. Lex と YACC でできること これらのプログラムを正しく利用すると、簡単に複雑な言語の構文解析ができ るようになります。特に設定ファイルを読み込みたい時や、自分または他人が 発案した言語用のコンパイラを書きたい時などに、非常に助けとなります。 このドキュメントでは、わずかな手助けにしかならないかもしれませんが、そ れでも、今後手作業で構文解析器 (Parser) を書いてみようとは思わなくなる はずです - Lex & YACCとはそのような作業をしてくれるツールです。 2.1. それぞれのプログラムのやっていること これらのプログラムは、組み合わせて使うとすばらしいものですが、それぞれ は違った目的の上に作られています。次章ではそれぞれがやっていることを説 明します。 3. Lex Lex プログラムは '字句解析器 (Lexer)' と呼ばれるものを生成します。これ は入力に文字列ストリームをとる関数で、キーにマッチする文字列群を見つけ た時に、ある決まった動作をさせることができます。以下はその簡単な例で す。 %{ #include %} %% stop printf("Stop command received\n"); start printf("Start command received\n"); %% %{ と %} の組で括られる最初のセクションは、出力プログラムでは直接イン クルードされます。これは、stdio.h で定義されている printf が、後で必要 となるためです。 セクションは '%%' で区切られ、二つ目のセクションの第一行は 'stop' キー で始まることになります。入力で 'stop' キーが発現した時は、残り行 ( printf() 呼び出し) が実行されます。 "stop" に加えて、ここでは "start" というほとんど同じ動作をするものも定 義しました。 上記のコードセクションを '%%' で閉じます。 Example 1 をコンパイルするには以下のようにします。 lex example1.l cc lex.yy.c -o example1 -ll 注意 - lex の代わりに flex を使用している方は、コンパイルスクリプト の'- ll' を '-lfl' に置き換える必要があるかもしれません。RedHat 6.x やSuSE では 'flex' を 'lex' として起動しているかもしれませんが、この変 更が必要です! 以上により、'example1' というファイルが生成されたと思います。実行する と、キーボードからの入力待ちになります。定義済みのキー ( 即ち、'stop' や 'start') 以外のものを入力すると、それがそのまま出力されます。'stop' を入力すると、'Stop command received' が出力されます。 EOF (^D) でプログラムを終了させることができます。 main() 関数も定義されていないのに、どうやってプログラムが動いたのか不 思議に思われたかもしれません。これは、-ll コマンドでコンパイル時にリン クした libl (liblex) が、main() 関数の定義を含んでいたからです。 3.1. 正規表現でのマッチ 上記の例は、それ自身ではあまり使えるものではありませんでした。次の例も それほど利用価値のあるものではないのですが、後々重宝することになる、 Lex での正規表現の使い方を例示しています。 Example 2: %{ #include %} %% [0123456789]+ printf("NUMBER\n"); [a-zA-Z][a-zA-Z0-9]* printf("WORD\n"); %% この Lex ファイルでは WORD と NUMBER という、二種類のマッチ（トーク ン）を記述しています。正規表現と聞くとびくついてしまう人もいるかもしれ ませんが、ちょっと勉強すればすぐに理解できるようになるものです。NUMBER に対するマッチを見てみましょう。 [0123456789]+ これは、0123456789 のどれか一文字を含む文字、または文字列が存在すると いう意味です。以下のような簡略表記もできます。 [0-9]+ WORD マッチはもう少し複雑になります。 [a-zA-Z][a-zA-Z0-9]* 前半部分は、'a' から 'z' または 'A' から 'Z' の間の文字列、つまりアル ファベットのどれかという意味です。アルファベットの後には、アルファベッ トもしくはアラビア数字がゼロ個以上続きます。アスタリスクを使っているの は何故でしょう？ '+' というのは一個以上のマッチを表しますが、WORD は、 前半部分で既にマッチした一文字のみという可能性もあります。その場合に は、後半部分でのマッチがゼロになってしまうので、'*' とする必要があるの です。 このようにして、多くのプログラミング言語が要求するような、最初の文字が アルファベットで 始まらなくては *ならず*、その後はアラビア数字を含んで も良いというような、変数名の規則に似せたものを作ることができました。つ まり、'temperature1' は良いですが、'1temperature' はだめということにな ります。 Example 1 でやったように、Example 2 をコンパイルしてみてください。それ から以下の例のようにテキストを入力してみてください。 $ ./example2 foo WORD bar WORD 123 NUMBER bar123 WORD 123bar NUMBER WORD 出力のホワイトスペースがどこから来たのか、不思議に思われたかもしれませ ん。理由は簡単です。これらは、もともと入力に含まれていたものですが、 マッチしないためそのまま出力となって現れたというだけの話です。 Flex の man ページには、使われている正規表現について詳しく載っていま す。また、perl の正規表現の man ページ (perlre) を便利だと感じられる方 々もたくさんいます - もっとも Flex の正規表現の実装は、perl ほど完全で はありませんが。 "[0-9]*" のように、長さゼロのマッチは行わないように注意してください。 字句解析器が混乱してしまい、空文字列とのマッチを繰り返すようなことにな ります。 3.2. C のようなシンタックスをもつもう少し高度な例 以下のような設定ファイルを構文解析したいとします。 logging { category lame-servers { null; }; category cname { null; }; }; zone "." { type hint; file "/etc/bind/db.root"; }; このファイル内にはいくつものカテゴリ（トークン）があるのがわかります。 o "zone" や "type" などの WORD o "/etc/bind/db.root" などの FILENAME o ファイルネームを括っている QUOTE o { を表す OBRACE o } を表す EBRACE o ; を表す SEMICOLON 対応する Lex ファイルは Example 3 のようになります。 %{ #include %} %% [a-zA-Z][a-zA-Z0-9]* printf("WORD "); [a-zA-Z0-9\/.-]+ printf("FILENAME "); \" printf("QUOTE "); \{ printf("OBRACE "); \} printf("EBRACE "); ; printf("SEMICOLON "); \n printf("\n"); [ \t]+ /* ホワイトスペースは無視 */; %% プログラムに設定ファイルを入力すると、この Lex ファイルから （example3.compile を使って)以下のような出力が得られます。 WORD OBRACE WORD FILENAME OBRACE WORD SEMICOLON EBRACE SEMICOLON WORD WORD OBRACE WORD SEMICOLON EBRACE SEMICOLON EBRACE SEMICOLON WORD QUOTE FILENAME QUOTE OBRACE WORD WORD SEMICOLON WORD QUOTE FILENAME QUOTE SEMICOLON EBRACE SEMICOLON 設定ファイルと見比べると、適切に 'トークン化' されたのがわかります。 ファイルの各々の部分で、正規表現によるマッチがとられ、トークンに変換さ れています。 これが、YACC を活用するために必要なことなのです。 3.3. おさらい Lex は任意の入力から、それぞれの部分が何であるか決定することができる、 ということがわかりました。これを 'トークン化する' といいます。 4. YACC YACC は、ある値をもつトークンから構成される、入力ストリームの構文解析 をすることができます。このことは、Lex に対する YACC の関係を、はっきり と示しています。YACC はそもそも '入力ストリーム' というものが何である かを理解しておらず、トークン化された入力を必要とします。ご自身で字句解 析プログラムを書かれても良いですが、ここではそれは Lex に譲ることにし ます。 文法と構文解析器について、補足しておきます。YACC は、登場したての頃は コンパイラへの入力ファイル - つまりプログラム- の構文解析に使われてい ました。コンピュータ向けのプログラミング言語で書かれたプログラムは、通 常曖昧なところは *なく*、意味も一つに限られています。従って、YACC は曖 昧さを許容できず、shift/reduce や reduce/reduce コンフリクトなどの警告 やエラーを出します。曖昧さと YACC 特有の "問題点" については、'コンフ リクト' の章をご覧ください。 4.1. 単純な温度調節器 単純な言語を使って制御できる温度調節器があるとします。この温度調節器を 使ったやりとりは以下のようになります。 heat on Heater on! heat off Heater off! target temperature 22 New temperature set! 認識しなくてはならないトークンは、heat, on/off(STATE), target, temperature, NUMBER です。 この字句解析器を Lex で作ると (Example 4) %{ #include #include "y.tab.h" %} %% [0-9]+ return NUMBER; heat return TOKHEAT; on|off return STATE; target return TOKTARGET; temperature return TOKTEMPERATURE; \n /* 改行は無視 */; [ \t]+ /* ホワイトスペースは無視 */; %% 二つ大きな違いがあります。一つ目は 'y.tab.h' をインクルードしているこ とです。二つ目は、print 出力するのをやめてトークン名を返すようにしてい るということです。これは、Lex の出力を全て YACC に入力しようとしている からで、スクリーンに表示する意味がないからです。y.tab.h ではトークンの 定義がされています。 y.tab.h はどこから出て来たのでしょう？これは、後で作ることになる文法 ファイルから YACC が生成したものです。言語と同様、文法も非常に単純に なっています。 commands: /* empty */ | commands command ; command: heat_switch | target_set ; heat_switch: TOKHEAT STATE { printf("\tHeat turned on or off\n"); } ; target_set: TOKTARGET TOKTEMPERATURE NUMBER { printf("\tTemperature set\n"); } ; 先頭の部分を、ここでは 'root' と呼ぶことにします。これは 'commands' と いうものが定義されていて、それが個別の 'command' から構成されていると いうことを示しています。コマンドがさらにコマンドを含んでいることから、 この規則は再帰的であると言えます。これはまた、構文解析器が連続するコマ ンドを一つずつ還元できるようになった、ということも意味しています。再帰 については、'Lex と YACC の内部動作' の章に重要な記述があります。 その次は、コマンドを定義する規則です。ここでは、'heat_switch' と 'target_set' という二種類のみサポートします。これは | 記号で表され、' コマンドが heat_switch または target_set から成る' ことを示していま す。 heat_switch は、単に 'heat' という単語を指す HEAT トークンに、状態 (Lex ファイルで 'on' や 'off' として定義済み）を付加したものです。 target_set はもう少し複雑で、これは TARGET トークン ('target' という単 語)、TEMPERATURE トークン ('temperature' という単語) そして数字から構 成されています。 4.1.1. YACC ファイルの全文 前のセクションでは、YACC の文法部分だけでしたが、もう少し解説しておく ことがあります。以下は省略したヘッダの部分です。 %{ #include #include void yyerror(const char *str) { fprintf(stderr,"error: %s\n",str); } int yywrap() { return 1; } main() { yyparse(); } %} %token NUMBER TOKHEAT STATE TOKTARGET TOKTEMPERATURE yyerror() 関数はエラーが見つかった時に、YACC から呼ばれます。ここでは 単に与えられたメッセージを出力しますが、もう少し賢いこともできます。巻 末の'関連書籍'の章をご覧ください。 yywrap() 関数は、連続して他のファイルから読み続けるのに使われます。 EOF で呼ばれ、もう一つのファイルをオープンした後 0 を返します。または 1 を返して、もう読むべきファイルはないということを通知します。詳しく は' Lex と YACC の内部動作'の章をご覧ください。 それから main() 関数がありますが、これはプログラムを起動するという以外 のことは何もしていません。 最終行は、単に使用するトークンを定義しているだけです。これらは YACC を -d オプションで実行した時に自動生成される y.tab.h から得られます。 4.1.2. 温度調節器のコンパイルと起動 lex example4.l yacc -d example4.y cc lex.yy.c y.tab.c -o example4 いくつか以前と違う点があります。YACC を使って文法ファイルをコンパイル することで、y.tab.c と y.tab.h を生成しています。それから普通に Lex を 呼び出しています。コンパイルする時は -ll フラグを外してください。ここ ではmain() 関数を定義しているので、libl で提供されるものを使う必要があ りません。 注意 - コンパイラが 'yylval' が見つからないというエラーを出す場合は、 example4.l の #include の直後に、以下を記述してください。 extern YYSTYPE yylval; これについては 'Lex と YACC の内部動作' の章に説明されています。 以下は、簡単な動作例です。 $ ./example4 heat on Heat turned on or off heat off Heat turned on or off target temperature 10 Temperature set target humidity 20 error: parse error $ 本当にやりたかったこととは多少ずれていますが、無理のない学習曲線を辿る という意味でも、ここでかっこいいコードやテクニックをいっぺんに紹介する のは避けています。 4.2. 引数を扱えるように拡張した、温度調節器 ここまでで、温度調節器のコマンドを正しく構文解析することができるように なっただけでなく、エラーの通知処理も適切に行えるようになりました。しか し、（Temperature set というような）曖昧な言い回しからも想像がつくよう に、プログラムは何をすべきか理解しておらず、ユーザから入力された値も受 け取っていません。 新規の設定温度値を読み込む機能を追加してみましょう。これをするために は、字句解析器でどのように NUMBER に対するマッチがなされて、YACC で読 めるような整数値に変換されるのかを知る必要があります。 Lex では、ターゲットにマッチするものがあった時、'yytext' という文字列 にマッチしたテキストを格納します。一方YACC では、数値のマッチは' yylval' 変数の値を読むことで得られます。Example 5 はその実装です。 %{ #include #include "y.tab.h" %} %% [0-9]+ yylval=atoi(yytext); return NUMBER; heat return TOKHEAT; on|off yylval=!strcmp(yytext,"on"); return STATE; target return TOKTARGET; temperature return TOKTEMPERATURE; \n /* 改行は無視 */; [ \t]+ /* ホワイトスペースは無視 */; %% ご覧の通り、yytext を引数として atoi() を実行し、結果を YACC が理解で きる yylval に格納しています。STATE についてもほとんど同様の処理を行っ ており、'on' にマッチする文字列があれば yylval に 1 を格納しています。 Lex では 'on' と 'off' のようなマッチは別々にすると、高速なコードが生 成されるということは覚えておいてください。ここではちょっと複雑な規則と 動作をお見せしたくて、一緒にしています。 さて、これには YACC ではどう対応すれば良いのでしょうか。Lex の 'yylval' は YACC では別の名前で参照されます。新規の設定温度値を記述す る規則を見てみましょう。 target_set: TOKTARGET TOKTEMPERATURE NUMBER { printf("\tTemperature set to %d\n",$3); } ; コマンド定義の三番目 (即ち、NUMBER) の値にアクセスするには、$3 を使い ます。yylval の値は、yylex() から戻ってくる度にバッファの最後尾に追加 されて行き、$ コンストラクトでアクセスできるようになります。 もう少し詳しく説明するために、新しい 'heat_switch' の規則を見てみま しょう。 heat_switch: TOKHEAT STATE { if($2) printf("\tHeat turned on\n"); else printf("\tHeat turned off\n"); } ; example5 を試してみてください。入力が適切な形で出力されるはずです。 4.3. 設定ファイルの構文解析 以前に触れた設定ファイルの一部を、もう一度見てみましょう。 zone "." { type hint; file "/etc/bind/db.root"; }; このファイル用の字句解析器は既に作りました。あとは YACC の文法ファイル を作り、字句解析器の戻り値を YACC が理解できるような形式に修正するだけ です。 Example 6 の 字句解析器から以下のことがわかります。 %{ #include #include "y.tab.h" %} %% zone return ZONETOK; file return FILETOK; [a-zA-Z][a-zA-Z0-9]* yylval=strdup(yytext); return WORD; [a-zA-Z0-9\/.-]+ yylval=strdup(yytext); return FILENAME; \" return QUOTE; \{ return OBRACE; \} return EBRACE; ; return SEMICOLON; \n /* EOLを無視 */; [ \t]+ /* ホワイトスペースを無視 */; %% 注意深く見てみると、yylval が違うことに気づいたでしょう! 整数値である ことすら期待していませんし、実際 char * であると仮定しています。問題を 簡単にするために、メモリを浪費するのも構わず strdup を実行してみます。 ひとつのファイルを一度だけパースして終了、というような一般的な用途にお いては、これで問題ないということを覚えておいてください。 ここではファイル名やゾーン名のような名前を最も頻繁に扱うので、それらを 文字列として格納したいとします。データの複数の型の扱い方については後述 します。 YACC に新しい型の yylval を教えてやるには、YACC の文法ファイルの先頭に 以下を追加します。 #define YYSTYPE char * 文法自体は更に複雑なものになっています。理解しやすいように分割してみま す。 commands: | commands command SEMICOLON ; command: zone_set ; zone_set: ZONETOK quotedname zonecontent { printf("Complete zone for '%s' found\n",$2); } ; これは、上述の再帰的な 'root' を含む導入部分です。コマンドが ; で終端 されて（そして区切られて）いることに留意してください。ここでは 'zone_set' という、コマンドのみ定義します。このコマンドは ZONE トーク ン（ 'zone' という単語）と、それに続く引用符で括られた名前、それに 'zonecontent' から成ります。まずはとっかかり易い zonecontent ですが - zonecontent: OBRACE zonestatements EBRACE これは { で表される OBRACE で始まります。それから zonestatements、そし て } で表される EBRACE と続きます。 quotedname: QUOTE FILENAME QUOTE { $$=$2; } このセクションは 'quotedname' を定義しています。QUOTE に挟まれた FILENAME という意味ですが、ちょっと特殊なのは、quotedname というトーク ンの値が FILENAME の値に等しいということです。つまり、quotedname は ファイル名から引用符を除いたものであるという意味です。 これは魔法の '$$=$2' コマンドがやってくれることで、自身の値は自身の二 番目の部位の値であるということを指します。他の文法規則でも参照されてい る quotedname に $ コンストラクトでアクセスすると、ここで $$=$2 として 設定した値が得られます。 注意 - この文法では、ゾーンファイル名に '.' か '/' かが含まれていない とうまく行きません。 zonestatements: | zonestatements zonestatement SEMICOLON ; zonestatement: statements | FILETOK quotedname { printf("A zonefile name '%s' was encountered\n", $2); } ; これは、'zone' ブロック内のあらゆる種類の文に対応できるように一般化し た文です。ここでも再帰性が認められます。 block: OBRACE zonestatements EBRACE SEMICOLON ; statements: | statements statement ; statement: WORD | block | quotedname これはブロックと、'文' の中に出現する '文' を定義しています。 実行されると、出力は以下のようになります。 $ ./example6 zone "." { type hint; file "/etc/bind/db.root"; type hint; }; A zonefile name '/etc/bind/db.root' was encountered Complete zone for '.' found 5. C++ での構文解析器の作成 Lex と YACC は C++ が登場する以前からありますが、C++ で構文解析器を作 成することも可能です。Flex には C++ の 字句解析器を生成するオプション もありますが、YACC の方にそれを直接扱う方法がないので、ここでは使用し ません。 筆者が C++ の構文解析器を作る際に好んで使う方法は、Lex に普通の C ファ イルの字句解析器を出力させて、YACC に C++ の構文解析器を生成させるやり 方です。アプリケーションをリンクした時に、この方法だと問題がある場合が あります。C++ では明示的に extern "C" 宣言しない限り、デフォルトでは C の関数を見つけられないからです。 これを回避するためには、YACC で以下のような C ヘッダを作ってください。 extern "C" { int yyparse(void); int yylex(void); int yywrap() { return 1; } } yydebug を宣言もしくは、変更したい場合はここで以下のように行ってくださ い。 extern int yydebug; main() { yydebug=1; yyparse(); } これは、C++ の '定義は一度' 規則のために必要で、yydebug の多重定義を防 ぎます。 加えて、C++ では型チェックがより厳しいので、YYSTYPE の #define を Lex ファイルに追記しないとだめかもしれません。 コンパイルするには、以下のようにしてください。 lex bindconfig2.l yacc --verbose --debug -d bindconfig2.y -o bindconfig2.cc cc -c lex.yy.c -o lex.yy.o c++ lex.yy.o bindconfig2.cc -o bindconfig2 -o 指定があるので、y.tab.h は bindconfig2.cc.h という名前になっている ことにも留意してください。 まとめ - 字句解析器のコンパイルは、わざわざ C++ でやろうとしないで C でやること。構文解析器は C++ で作り、C 関数を呼び出したい時は extern "C" 文でコンパイラに宣言すること。 6. Lex と YACC の内部動作 上述の YACC ファイルでは、yyparse() を呼び出す main() 関数を自作しまし た。yyparse() 関数は YACC が自動生成してくれ、y.tab.c というファイルに なりました。 yyparse() は、連続して入力されるべきトークンとその値の組を、yylex() か ら読み込みます。この関数は読者が自作されても構いませんが、Lex に作らせ ることもできます。ここでは、Lex にやらせることにします。 Lex が作成した yylex() は、yyin という FILE * 型ファイルポインタから文 字列を読み込みます。yyin はセットしない限り、デフォルトでは標準入力に なります。出力は yyout になり、これもセットされていなければ、デフォル トで標準出力となります。また、ファイルの最後で呼ばれる yywrap() 関数内 の yyin も変更でき、別のファイルをオープンしてパースし続けるようにする こともできます。 この場合は、0 を戻り値として返すようにしてください。パースを終了させた い時は、1 を返すようにしてください。 yylex() は呼ばれる度に、トークン種別を表す整数値を返します。これは YACC が、いままでにどんなトークンを読み込んだか見分けるのに使われま す。トークンは随意、値を持つ場合があり、その場合は yylval に値が格納さ れます。 デフォルトでは、yylval は int 型ですが、YACC ファイルで再度 YYSTYPE を #define することで、オーバーライドすることができます。 字句解析器は、yylval にアクセスできる必要があります。そのためには、 yylval が字句解析器のスコープに対して、外部参照変数として宣言されてい る必要があります。オリジナルの YACC は、これを自動的にしてくれないの で、以下を字句解析器の #include 直後に、記述する必要がありま す。 extern YYSTYPE yylval; 近年広く使われている Bison では、これを自動的にやってくれます。 6.1. トークンの値 上述したように、yylex() は出現したトークン種別を返す必要があり、値を yylval に格納する必要があります。これらのトークンが、%token コマンドで 定義されている場合、各々には 256 から始まる数字の id が振られていま す。 このことから、全アスキー文字をトークンとすることも可能です。例えば、電 卓を作る場合など、これまでの経験を生かすと、以下のように字句解析器を書 けることになるでしょうか。 [0-9]+ yylval=atoi(yytext); return NUMBER; [ \n]+ /* eat whitespace */; - return MINUS; \* return MULT; \+ return PLUS; ... YACC 文法には、以下を含むことになります： exp: NUMBER | exp PLUS exp | exp MINUS exp | exp MULT exp これは無駄に複雑なだけです。数値を表すトークン id を、文字列を使って簡 略表記すると、字句解析器は以下のように書き直せます: [0-9]+ yylval=atoi(yytext); return NUMBER; [ \n]+ /* eat whitespace */; . return (int) yytext[0]; 最後のドットは、マッチしなかった文字全てを表します。 一方、YACC文法は exp: NUMBER | exp '+' exp | exp '-' exp | exp '*' exp 随分わかりやすく、また短くなりました。アスキー文字を表すトークンをヘッ ダの %token で宣言する必要もなく、そのままで使えています。 このコンストラクトのもうひとつ優れたところは、入力したものはなんでも Lex がマッチをとってくれるようになった、ということです - こうすること で、マッチしない入力を標準出力へ吐き出すという、デフォルト動作を回避し ています。例えば、電卓にユーザが ^ を入力すると、標準出力へそのまま表 示される代わりに構文解析エラーを出力するようになります。 6.2. 再帰 - '善(right=右）は悪' 再帰は、YACC ではきわめて重要です。これなくしては、独立するコマンドや 文の連続からファイルが構成されている、ということが言えなくなります。つ まり、YACC にとって最も重要なのは一番目の規則、即ち、'%start' シンボル で指定した、起点を示す規則のみということになります。 YACC における再帰には、2つのタイプ - 右と左 - があります。左再帰はほと んどの場合に使うべきもので、以下のようなものです。 commands: /* empty */ | commands command これは、コマンドが空である、もしくは複数のコマンドの後に、あるコマンド が続くという意味です。YACC の動作からすると、これは（前方から）個々の コマンド群を簡単に切り分けて、還元できるということを意味します。 これを右再帰と比べてみると、紛らわしいですが見た目は良くなります。 commands: /* empty */ | command commands しかし、これは処理としては高くつきます。%start 規則として使われた場 合、YACC はファイル中の全コマンドをスタックに保持しなくてはならず、メ モリを大量に消費します。このことから、ファイル全部というような長文の構 文解析をする際は、左再帰を使用してください。時には右再帰の使用が避けら れないような状況もあるかもしれませんが、文があまりにも長すぎる場合を除 いては、左再帰以外を使う必要はないでしょう。 コマンドを終端して（ゆえに区切って）いるものがあるような場合には、右再 帰を使うと自然な感じになりますが、処理が高くつくことにはかわりありませ ん。 commands: /* empty */ | command SEMICOLON commands このコードは、正しくは左再帰を使って書きます（これも筆者がでっちあげた 訳ではありません）。 commands: /* empty */ | commands command SEMICOLON この HOWTO の以前のバージョンでも、間違えて右再帰を使っていましたが、 Markus Triska が親切にも指摘してくれました。 6.3. より高度な yylval - %union ここまででは、yylval の *型そのもの* を定義する必要がありました。しか し、これがいつも適当であるとは限りません。複数のデータ型を扱えなくては ならないこともあるかも知れないからです。仮想温度調節器の例に戻って、制 御するべきヒーターを選びたいとしたら、以下のようになります。 heater mainbuiling Selected 'mainbuilding' heater target temperature 23 'mainbuilding' heater target temperature now 23 ポイントは yylval が共用体になって、文字列と整数の両方を保持することが できる、ということです - 同時に一緒ではありませんが。 以前、YACC に対して yylval の型を、YYSTYPE として定義していたのを思い 出してください。これは、YACC の %union 文という、より簡単な方法で、共 用体として定義することもできたのではないでしょうか。 Example 4 に基づいて、Example 7 の YACC 文法を書いてみます。まずはその 導入部分 - %token TOKHEATER TOKHEAT TOKTARGET TOKTEMPERATURE %union { int number; char *string; } %token STATE %token NUMBER %token WORD 数字と文字列のみを含む、共用体を定義します。それから拡張された %token シンタックスで、YACC に共用体のどの部分に、それぞれのトークンがアクセ スすべきか指示しています。 この場合、以前やったように STATE トークンに int 型を割り当てます。同様 に、温度を読み取るための NUMBER トークンも割り当てます。 新しいのは WORD トークンで、文字列であると宣言されています。 字句解析プログラムのファイルも、多少変更があります。 %{ #include #include #include "y.tab.h" %} %% [0-9]+ yylval.number=atoi(yytext); return NUMBER; heater return TOKHEATER; heat return TOKHEAT; on|off yylval.number=!strcmp(yytext,"on"); return STATE; target return TOKTARGET; temperature return TOKTEMPERATURE; [a-z0-9]+ yylval.string=strdup(yytext);return WORD; \n /* 改行は無視 */; [ \t]+ /* ホワイトスペースは無視 */; %% お気づきになったように、もう yylval そのものには直接アクセスしておら ず、アクセスしたい部分を示すのに、サフィックスを付加しています。YACC には以下のような魔法があるので、YACC 文法ではこれは不要です。 heater_select: TOKHEATER WORD { printf("\tSelected heater '%s'\n",$2); heater=$2; } ; 前述の %token 宣言のおかげで、YACC は自動的に共用体から '文字列' メン バを読み取ってくれています。また、ここでは後で、コマンドの送り先になっ ているヒーターをユーザに通知するのに使われる、$2 のコピーも格納してい ます。 target_set: TOKTARGET TOKTEMPERATURE NUMBER { printf("\tHeater '%s' temperature set to %d\n",heater,$3); } ; 詳細は example7.y を参照ください。 7. デバッグ プログラムを、動かしながら学ぶような時は特に、デバッグ機能があることが 重要になります。幸運にもYACCは、多数のフィードバックを返す機能を持って います。この機能はいくらかオーバーヘッドを必要とするので、使用にあたっ ては幾つかのスイッチをイネーブルにする必要があります。 文法をコンパイルする時は、YACC のコマンドラインに、--debug や --verbose をつけます。文法ファイルの C ヘッダ部には、以下を付加しま す。 int yydebug=1; これは 'y.output' という、出力されたステートマシンを説明するファイルを 生成します。 生成されたバイナリを実行すると、このファイルは、現在起こっていることに ついて、*非常にたくさんの* 情報を出力してくれます。これには、ステート マシンがどんなステートを保有しているのか、どんなトークンが読み込まれて いるのか等の情報も含まれます。 Peter Jinks はdebugging によくあるエラーや、 エラーへの対処の仕方などを載せています。 7.1. ステートマシン YACC で生成した構文解析器は、内部的には 'ステートマシン' というものを 実行しています。名前が示すように、これは、いくつかのステート（状態）を とり得るマシン（機械）のことです。どのステートからどのステートへ遷移す るかを決定する規則、というのも存在します。全ては筆者が前述した、いわゆ る 'root' 規則が起点となります。 Example 7 の y.output からの出力を引用すると - state 0 ZONETOK , and go to state 1 $default reduce using rule 1 (commands) commands go to state 29 command go to state 2 zone_set go to state 3 このステートは、デフォルトでは 'commands' 規則を用いて還元します。これ は、前述した再帰に関する規則であり、個々のコマンド文、セミコロン、更に 続くコマンドから構成される 'commands' を定義しています。 このステートは、解釈できるトークン - この場合 ZONETOK 即ち 'zone' とい う単語 - に到達するまで還元します。それから、ステート 1 へ遷移し、zone コマンドをさらに詳しく処理します。 state 1 zone_set -> ZONETOK . quotedname zonecontent (rule 4) QUOTE , and go to state 4 quotedname go to state 5 最初の行は現在の場所を示す '.' を含んでいます - ZONETOK は既に見つかっ たので、次に 'quotedname' を探しています。quotedname は QUOTE で始まる ので、ステート 4 に遷移することになります。 以上についてもう少し掘り下げたい方は、Example 7 をデバッグの章で触れた フラグを付けてコンパイルしてみてください。 7.2. コンフリクト: 'shift/reduce', 'reduce/reduce' YACC がコンフリクトについて警告を出す時は、何か問題がある時でしょう。 コンフリクトを解決する作業には、ときに職人芸のような特殊さがあり、あな たの使用している言語について多くのことを教えてくれることでしょう - そ れもあなたが知りたかったこと以上のことを。 問題は、連続するトークンをどう解釈するか、という点を中心に起こります。 以下の二つのコマンドを受け付ける必要がある言語を、定義するとしましょ う。 delete heater all delete heater number1 これをするには、以下の文法定義が必要です。 delete_heaters: TOKDELETE TOKHEATER mode { deleteheaters($3); } mode: WORD delete_a_heater: TOKDELETE TOKHEATER WORD { delete($3); } もう問題の臭いがしてきましたね。ステートマシンは 'delete' という単語を 読むことから始めて、次のトークンが何であるかによって、遷移先を決定する 必要があります。次のトークンというのは、ヒーターの削除方法を指定する モード、もしくは削除すべきヒーターの名前です。 問題は両方のコマンドにとって、次のトークンが WORD になるということで す。 YACC は、この場合どうして良いかわかりません。これが 'reduce/reduce'、更には 'delete_a_heater' ノードに決して達することがな い、という警告になります。 この場合のコンフリクトは、簡単に解決できますが（最初のコマンド名を' delete heaters all' に変更したり、'all' を独立したトークンとして定義す るなど）、もっと複雑になることもあります。--verbose フラグを付加し てyaccを通すと生成される y.output ファイルは、そんな時に非常に助けとな ります。 8. 関連情報 GNU YACC (Bison) には、YACC のシンタックスを詳しく記述したすばらしい info ファイル (.info) が付属してきます。Lex は一度しか触れられていませ んが、その点を除けば優れています。.info ファイルは Emacs や 'pinfo' と いった、使い勝手の良いツールで読むことができます。以下の GNU サイトで も入手可能です：BISON Manual . Flex には優れた man ページが付属してきます。Flex で何ができるか、ざっ とでも理解している人には、とても有用でしょう。Flex Manual もオンラインで入手可能です。 この Lex と YACC のイントロダクションを終えて、もう少し情報が欲しいと 思われた方もいるでしょう。以下の本は、筆者は全く読んでいませんが、タイ トルはいい感じです - Bison-The Yacc-Compatible Parser Generator Charles Donnelly and Richard Stallman によるものです。この本を気 に入ったAmazon ユーザもいらっしゃるようです。 Lex & Yacc John R. Levine, Tony Mason and Doug Brown によるものです。 ちょっと古いですが、このテーマに関しては教科書的存在です。Amazon にレビューがあります。 Compilers : Principles, Techniques, and Tools Alfred V. Aho, Ravi Sethi, Jeffrey D. Ullman によるものです。通 称 'ドラゴンブック'。1985年に出たというのに、えんえんと増刷され ています。コンパイラ開発に関しては教科書的存在です。Amazon Thomas Niemann は Lex と YACC を使ったコンパイラと電卓の作り方について ドキュメントを書いており、ここ にあ ります。 comp.compilers というニュースグループも usenet にあり、なかなか利用価 値があります。ですが、参加している人たちは構文解析器の専属ヘルプデスク 要員ではありません! 投稿する前に、彼らのページ は興味深いので見ること、特に質問は FAQ にちゃんと目を通した上で投げるこ と。 Lex - A Lexical Analyzer Generator by M. E. Lesk and E. Schmidt は筆者 が引用したドキュメントのひとつです。ここ で入手できます。 Yacc: Yet Another Compiler-Compiler by Stephen C. Johnson は筆者が YACC について引用したドキュメントの一つです。ここ で入手できます。ス タイルについてのヒントが載っています。 9. 謝辞 o Pete Jinks o Chris Lattner o John W. Millaway o Martin Neitzel o Esmond Pitt o Eric S. Raymond o Bob Schmertz o Adam Sulmicki o Markus Triska o Erik Verbruggen o Gary V. Vaughan (read his awesome Autobook ) o Ivo van der Wijk ( Amaze Internet ) 訳注: 翻訳にあたっては、山下義之さん、小林雅典さんに有益なコメントをい ただきました。ありがとうございました。