|
次のページ
前のページ
目次へ
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 が振られ ています。 このことから、全アスキー文字をトークンとすることも可能です。例えば、電 卓を作る場合など、これまでの経験を生かすと、以下のように字句解析器を書 けることになるでしょうか。
YACC 文法には、以下を含むことになります:
これは無駄に複雑なだけです。数値を表すトークン id を、文字列を使って簡 略表記すると、字句解析器は以下のように書き直せます:
[0-9]+ yylval=atoi(yytext); return NUMBER; [ \n]+ /* eat whitespace */; . return (int) yytext[0]; 最後のドットは、マッチしなかった文字全てを表します。 一方、YACC文法は
随分わかりやすく、また短くなりました。アスキー文字を表すトークンをヘッ ダの %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 の *型そのもの* を定義する必要がありました。しか し、これがいつも適当であるとは限りません。複数のデータ型を扱えなくては ならないこともあるかも知れないからです。仮想温度調節器の例に戻って、制 御するべきヒーターを選びたいとしたら、以下のようになります。
ポイントは yylval が共用体になって、文字列と整数の両方を保持することが できる、ということです - 同時に一緒ではありませんが。 以前、YACC に対して yylval の型を、YYSTYPE として定義していたのを思い 出してください。これは、YACC の %union 文という、より簡単な方法 で、共用体として定義することもできたのではないでしょうか。 Example 4 に基づいて、Example 7 の YACC 文法を書いてみます。まずはその 導入部分 -
数字と文字列のみを含む、共用体を定義します。それから拡張された %token シンタックスで、YACC に共用体のどの部分に、それぞれのトー クンがアクセスすべきか指示しています。 この場合、以前やったように STATE トークンに int 型を割り当てます。同様 に、温度を読み取るための NUMBER トークンも割り当てます。 新しいのは WORD トークンで、文字列であると宣言されています。 字句解析プログラムのファイルも、多少変更があります。
お気づきになったように、もう yylval そのものには直接アクセスしておらず、 アクセスしたい部分を示すのに、サフィックスを付加しています。YACC には 以下のような魔法があるので、YACC 文法ではこれは不要です。
前述の %token 宣言のおかげで、YACC は自動的に共用体から '文字列' メンバを読み取ってくれています。また、ここでは後で、コマンドの送り先に なっているヒーターをユーザに通知するのに使われる、$2 のコピーも格納し ています。
詳細は example7.y を参照ください。 次のページ 前のページ 目次へ |
[ |