次のページ 前のページ 目次へ

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 <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 ファイルの全文

前のセクションでは、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
$

本当にやりたかったこととは多少ずれていますが、無理のない学習曲線を辿る という意味でも、ここでかっこいいコードやテクニックをいっぺんに紹介する のは避けています。

4.2 引数を扱えるように拡張した、温度調節器

ここまでで、温度調節器のコマンドを正しく構文解析することができるように なっただけでなく、エラーの通知処理も適切に行えるようになりました。しか し、(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 を試してみてください。入力が適切な形で出力されるはずです。

4.3 設定ファイルの構文解析

以前に触れた設定ファイルの一部を、もう一度見てみましょう。

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


次のページ 前のページ 目次へ