プログラミングユーティリティ

`lex` と `yacc` の併用

コンパイラプロジェクトに取り組んでいる場合、または入力言語の妥当性を検査するプログラムを開発する場合には、システムツールの yacc (第 3 章「yacc - コンパイラコンパイラ」を参照) を使用することがあります。yacc は、パーサーを生成します。パーサーは、入力を解析してその入力の構文に誤りがないことを検証するプログラムです。

多くの場合、コンパイラの開発では lex と yacc を併用して作業を行うことができます。

すでに説明したように、プログラムは、関数 yylex() を繰り返し呼び出して、lex が生成したスキャナを使用します。yacc が生成したパーサーはこれと同じ名前を使用して字句アナライザを呼び出すので、lex と yacc を併用する場合にこの名前は好都合です。

lex を使用してコンパイラ用の字句アナライザを作成する場合は、lex の各アクションはトークンを返す文で終了してください。トークンとは、整数値を使用して定義された語句です。

返されるトークンの整数値によって、字句アナライザが何を見つけたかがパーサーに示されます。その後、パーサー (yacc によって呼び出された yyparse()) は制御を再開して、字句アナライザに対して別の呼び出しを行い、次のトークンを取得します。

コンパイラでは、見つかったその言語の予約語 (予約語がある場合) によって、または識別子、定数、算術演算子、関係演算子のどれが見つかったのかによって、トークンの値は異なります。後者の場合は、アナライザはトークンの厳密な値も指定する必要があります。つまり、識別子、定数の値 (9 や 888 など)、算術演算子の種類 (+ や * など)、関係演算子の種類 (= や > など) を指定する必要があります。

以下に、C のような言語のトークンを認識するスキャナの lex ソースの一部を示します。

表 2-2 トークンを認識する lex ソースの例

begin return(BEGIN); end return(END); while return(WHILE); if return(IF); package return(PACKAGE); reverse return(REVERSE); loop return(LOOP); [a-zA-Z][a-zA-Z0-9]* { tokval = put_in_tabl(); return(IDENTIFIER); } [0-9]+ { tokval = put_in_tabl(); return(INTEGER); } ¥+ { tokval = PLUS; return(ARITHOP); } ¥- { tokval = MINUS; return(ARITHOP); } > { tokval = GREATER; return(RELOP); } >= { tokval = GREATEREQL; return(RELOP); }

begin           return(BEGIN); 
end             return(END); 
while           return(WHILE); 
if              return(IF); 
package         return(PACKAGE); 
reverse         return(REVERSE); 
loop            return(LOOP); 
[a-zA-Z][a-zA-Z0-9]*   
             { tokval = put_in_tabl(); 
                        return(IDENTIFIER); } 
[0-9]+       { tokval = put_in_tabl(); 
                        return(INTEGER); } 
¥+           { tokval = PLUS;
                        return(ARITHOP); } 
¥-           { tokval = MINUS;                 
                        return(ARITHOP); } 
>            { tokval = GREATER;                 
                        return(RELOP); } 
>=           { tokval = GREATEREQL;              
                        return(RELOP); }

返されるトークンと、tokval に割り当てられる値は、整数です。プログラムを理解しやすくするために、整数値をそのまま使用するのではなく、BEGIN、END、WHILE などの説明的な語句を使用してパーサーが解釈する整数を表してください。

整数値と語句の関連付けは、C パーサーを呼び出すルーチンの #define 文を使用して定義します。たとえば、以下のように定義します。

#define BEGIN 1 
#define END 2 
 ... 
#define PLUS 7 
 ...

また、いずれかのトークン型の整数を変更する場合は、その特定の整数が現われる個所をすべて変更するのではなく、パーサーの #define 文を変更してください。

yacc を使用してパーサーを生成するには、lex ソースの定義セクションに以下の文を挿入します。

#include "y.tab.h"

-d オプションを付けて yacc を呼び出したときに作成されるファイル y.tab.h は、BEGIN や END などのトークン名を有効な整数に関連付ける #define 文を、生成されたパーサーに提供します。

表 2-2 の予約語は、返される整数値だけで十分表すことができます。他のトークン型については、変数 tokval にその整数値が保存されます。

この変数は広域的に定義されているので、パーサーと字句アナライザはその変数にアクセスできます。yacc も、同じ用途の変数 yylval を提供します。

表 2-2 には tokval に値を割り当てる方法が 2 種類示されている点に注目してください。

1 つは、関数 put_in_tabl() による方法です。関数 put_in_tabl() は、識別子または定数の名前と型をシンボルテーブルに配置するので、コンパイラはその名前と型を参照できます。

put_in_tabl() は、現在位置に加えて型の値も tokval に割り当てるので、パーサーはその情報をすぐに使用して入力テキストの構文上の正当性を判定できます。関数 put_in_tabl() は、コンパイラの作成者がパーサーのユーザールーチンセクションに配置するルーチンです。
もう 1 つは、特定の整数を tokval に割り当てる方法です。tokval には、スキャナが認識した算術演算子または関係演算子を表す特定の整数が割り当てられます。

たとえば、#define 文によって変数 PLUS が整数 7 に関連付けられている場合には、+ が認識されると、そのアクションは + を表す値 7 を tokval に割り当てます。

スキャナは、演算子の一般クラス (つまり、ARITHOP または RELOP で表される整数) を、パーサーに返す値で示します。

lex と yacc を併用するときには、どちらを先に実行しても構いません。以下のコマンドを実行すると、ファイル y.tab.c にパーサーが生成されます。
```
$ yacc d grammar.y
```

すでに説明したように、-d オプションを使用すると、ファイル y.tab.h が作成されます。このファイルには、yacc によって割り当てられた整数のトークン値とユーザー定義のトークン名を関連付ける #define 文が含まれています。lex は以下のコマンドで呼び出すことができます。

$ lex lex.l

次に、以下のコマンドを使用して出力ファイルのコンパイルとリンクを行うことができます。

$ cc lex.yy.c y.tab.c -ly -ll

-ll オプションで lex ライブラリをロードする前に、-ly オプションで yacc ライブラリをロードして、提供されている main() が yacc パーサーを呼び出すようにしています。

また、CC と共に yacc を使用するには (特に、.l ファイル内の yyback()、yywrap()、yylook()() などのルーチンが外部 C 関数になる場合)、コマンド行に以下のコマンドを入力する必要があります。

$ CC -D__EXTERN_C__ ... ファイル名

lex と yacc の併用

`lex` と `yacc` の併用