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

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 <y.tab.h> 直後に、記述する必要があり ます。

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 <number> STATE
%token <number> NUMBER
%token <string> WORD

数字と文字列のみを含む、共用体を定義します。それから拡張された %token シンタックスで、YACC に共用体のどの部分に、それぞれのトー クンがアクセスすべきか指示しています。

この場合、以前やったように STATE トークンに int 型を割り当てます。同様 に、温度を読み取るための NUMBER トークンも割り当てます。

新しいのは WORD トークンで、文字列であると宣言されています。

字句解析プログラムのファイルも、多少変更があります。

%{
#include <stdio.h>
#include <string.h>
#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 を参照ください。


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