YACC は、ある値をもつトークンから構成される、入力ストリームの構文解析 をすることができます。このことは、Lex に対する YACC の関係を、はっきり と示しています。YACC はそもそも '入力ストリーム' というものが何である かを理解しておらず、トークン化された入力を必要とします。ご自身で字句解 析プログラムを書かれても良いですが、ここではそれは Lex に譲ることにし ます。
文法と構文解析器について、補足しておきます。YACC は、登場したての頃は コンパイラへの入力ファイル - つまりプログラム- の構文解析に使われてい ました。コンピュータ向けのプログラミング言語で書かれたプログラムは、通 常曖昧なところは *なく*、意味も一つに限られています。従って、YACC は曖 昧さを許容できず、shift/reduce や reduce/reduce コンフリクトなどの警告 やエラーを出します。曖昧さと YACC 特有の "問題点" について は、'コンフリクト' の章をご覧ください。
単純な言語を使って制御できる温度調節器があるとします。この温度調節器を 使ったやりとりは以下のようになります。
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 <stdio.h>
#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' という単語) そして数字から構 成されています。
前のセクションでは、YACC の文法部分だけでしたが、もう少し解説しておく ことがあります。以下は省略したヘッダの部分です。
%{
#include <stdio.h>
#include <string.h>
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 から得られます。
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 <y.tab.h> の直後に、以下を記述してくださ
い。
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
$
本当にやりたかったこととは多少ずれていますが、無理のない学習曲線を辿る という意味でも、ここでかっこいいコードやテクニックをいっぺんに紹介する のは避けています。
ここまでで、温度調節器のコマンドを正しく構文解析することができるように なっただけでなく、エラーの通知処理も適切に行えるようになりました。しか し、（Temperature set というような）曖昧な言い回しからも想像がつくよう に、プログラムは何をすべきか理解しておらず、ユーザから入力された値も受 け取っていません。
新規の設定温度値を読み込む機能を追加してみましょう。これをするためには、 字句解析器でどのように NUMBER に対するマッチがなされて、YACC で読める ような整数値に変換されるのかを知る必要があります。
Lex では、ターゲットにマッチするものがあった時、'yytext' という文字列 にマッチしたテキストを格納します。一方YACC では、数値のマッチは' yylval' 変数の値を読むことで得られます。Example 5 はその実装です。
%{
#include <stdio.h>
#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 を試してみてください。入力が適切な形で出力されるはずです。
以前に触れた設定ファイルの一部を、もう一度見てみましょう。
zone "." {
type hint;
file "/etc/bind/db.root";
};
このファイル用の字句解析器は既に作りました。あとは YACC の文法ファイル を作り、字句解析器の戻り値を YACC が理解できるような形式に修正するだけ です。
Example 6 の 字句解析器から以下のことがわかります。
%{
#include <stdio.h>
#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