目次


Yacc...そしてLexをよみがえらせる

LexおよびYaccの紹介

Comments

Lex は、Lexical Analyzer のことを指します。Yacc は Yet Another Compiler Compiler のことを指します。では、まずは Lex に注目してみましょう。

Lex

Lex はスキャナーを生成するツールです。スキャナーとは、テキスト内の字句パターンを認識するプログラムのことです。これらの字句パターン (または正規表現) は、この後すぐに説明する特定の構文で定義されます。

マッチングする正規表現にはアクションが関連付けられます。このアクションには、トークンを戻すことも含まれます。Lex が入力をファイルまたはテキストの形で受け取る場合、正規表現でのマッチングを試みます。入力を一度に 1 文字ずつ処理して、パターンにマッチングするまで続けます。パターンにマッチングする場合、Lex は関連付けられているアクション (トークンを戻すことが含まれる) を実行します。それに対して、マッチングする正規表現がない場合、Lex は処理を停止し、エラー・メッセージを表示します。

Lex と C は緊密に結び付いています。.lex ファイル (Lex ファイルは拡張子が.lex です) は、lex ユーティリティーで処理されて、C の出力ファイルを生成します。これらのファイルは、実行可能な字句解析プログラムを生成するようにコンパイルされます。

Lex の正規表現

正規表現とは、メタ言語を使ったパターンの記述です。その表現はシンボルを使って構成されます。通常のシンボルは文字と数字ですが、Lex では特別な意味を持つ他のシンボルも使われます。以下に示す 2 つの表は、Lex で使用されるいくつかのシンボルと、その一般的な例のいくつかを示しています。

Lex での正規表現の定義
文字意味
A-Z, 0-9, a-z パターンの一部である文字と数字。
. \n 以外のすべての文字とマッチングします。
- 範囲を示すのに使用されます。たとえば、A-Z は A から Z までのすべての文字を暗黙指定します。
[ ] 文字クラスです。大括弧の中のすべての 文字とマッチングします。最初の文字が^ である場合、これは否定パターンであることを示します。たとえば、[abC] は a、b、C のどれにでもマッチングします。
* 直前のパターンのゼロ 回以上の出現とマッチングします。
+ 直前のパターンの1 回以上の出現とマッチングします。
? 直前のパターンのゼロまたは 1 回の出現とマッチングします。
$ パターンの終了文字が行の終わりのものにマッチングします。
align="center"> { } パターンが何回出現するかを示します。たとえば、A{1,3} とすると、A が 1 回または 3 回出現することを示します。
\ メタ文字をエスケープする場合に使用します。この表で定義されているような、文字の特別な意味を除外する場合にも使用します。
^ 否定。
| 表現を論理 OR します。
"<some symbols>" 文字のリテラルの意味を示します。メタ文字は保たれます。
/ 前方向に検索し、直後の表現が続く場合に限り、直前のパターンとマッチングします。たとえば、A0/1 は A01 の A0 だけとマッチングします。
( ) 一連の正規表現をグループ化します。
正規表現の例
正規表現意味

joke[rs]

jokes または joker とマッチングします。

A{1,2}shis+

AAshis、Ashis、AAshi、Ashi とマッチングします。

(A[b-e])+

b から e までの文字が続く A の 0 回以上の出現とマッチングします。

Lex でのトークンは、C での変数名と同じように宣言されます。(トークンと表現の例を以下の表に示します。) これらの表にある表現を使えば、ワード・カウント・プログラムを作成できます。最初の作業は、トークンをどのように宣言するかを示すことです。

トークンの宣言の例
トークン関連した表現意味
number ([0-9])+ 数字の 1 回以上の出現
chars [A-Za-z] 任意の文字
blank " " ブランク・スペース
word (chars)+chars の 1 回以上の出現
variable (chars)+(number)*(chars)*( number)* 

Lex でのプログラミング

Lex でのプログラミングは、3 つのステップに分けることができます。

  1. Lex が理解できる形式で、パターンに関連づけるアクションを指定する
  2. ファイルに Lex を実行して、スキャナーのための C コードを生成する
  3. C コードをコンパイルおよびリンクして、実行可能なスキャナーを生成する

注: スキャナーが Yacc を使用して開発されたパーサーの一部である場合、ステップの 1 と 2 を実行するだけで十分です。特定の問題については、Yacc のセクションと、Lex と Yacc を協働させるのセクションを参照してください。

では、Lex が理解できる種類のプログラム・フォーマットを見てみましょう。Lex プログラムは 3 つの区分に分けられます。1 つ目は汎用の C および Lex 宣言であり、2 つ目はパターン (C でコード化) であり、3 つ目は追加の C 関数です。たとえば、main() は普通 3 つ目の区分にあります。これらの区分は %% で区切られています。ここで、ワード・カウントを行う先ほどの Lex プログラムに戻って、プログラムのさまざまな区分の構成を見てみましょう。

汎用の C および Lex 宣言

この区分では、C 変数の宣言を追加できます。ここでは、ワード・カウント・プログラムがカウントしたワード数を保持するための 整数の変数を宣言します。さらに、Lex のトークンを宣言します。

ワード・カウント・プログラムの場合の宣言
        %{
        int wordCount = 0;
        %}
        chars [A-za-z\’\'\.\"]
        numbers ([0-9])+
        delim [" "\n\t]
        whitespace {delim}+
        words {chars}+
        %%

%% 記号は、Lex プログラミングにおける 3 つの区分のうちのこの最初の区分の終わりと、2 番目の区分の始まりを表しています。

マッチング・パターンに関する Lex の規則

ここでは、マッチングしたいトークンを記述するための Lex の規則を見てみましょう。(C を使用して、トークンがマッチングする場合に何を行うかを定義します。) 引き続きワード・カウント・プログラムを例にとって、トークンのマッチングに関する規則を見てみましょう。

ワード・カウント・プログラムの場合の Lex 規則
       {words} { wordCount++; /*
        increase the word count by one*/ }
        {whitespace} { /* do
        nothing*/ }
        {numbers} { /* one may
        want to add some processing here*/ }
        %%

C コード

Lex プログラミングにおける 3 番目にして最後の区分は、C 関数の宣言 (メイン関数の場合もある) です。この区分には、yywrap() 関数を含める必要があります。Lex は、ユーザーが利用できる関数と変数のセットを用意しています。その 1 つが yywrap です。一般的に、yywrap() は以下に示す例のように定義されます。この点については、『Lex の拡張機能』でも取り上げます。

ワード・カウント・プログラムの C コード区分
        void main()
        {
        yylex(); /* start the
        analysis*/
        printf(" No of words:
        %d\n", wordCount);
        }
        int yywrap()
        {
        return 1;

ここまでで、単純な字句解析プログラムを作成するのに役立つ、Lex プログラミングにおける基本的な要素について説明しました。『Lex の拡張機能』では、さらに複雑なプログラムを作成するために必要な、Lex の機能について説明します。

まとめ

.lex ファイルは、Lex のスキャナーです。これは Lex プログラムでは以下のように指定します。

$ lex <file name.lex>

こうすることによって、C コンパイラーを使用してコンパイル可能な lex.yy.c ファイルが生成されます。さらに、パーサーとともに使用して実行可能プログラムを生成するか、–ll オプションを指定してリンク・ステップで Lex ライブラリーを組み込むことができます。

Lex には以下のようなフラグがあります。

  • -c は C アクションを示します。デフォルトです。
  • -t は標準出力の代わりに lex.yy.c プログラムを作成するようにします。
  • -v は 2 行に要約した統計情報を生成します。
  • -n は -v 要約をプリントアウトしません。

Lex の拡張機能

Lex には、異なる情報を提供したり、より複雑な関数を実行するプログラムを作成したりする関数や変数があります。そのような変数や関数のいくつかを、その使用法とともに、以下の表に示します。完全なリストについては、Lex または Flex の解説書 (この記事の末尾にある『参考文献』を参照) をご覧ください。

Lex 変数
yyin FILE* 型。これは、字句解析プログラムによって解析される現行ファイルを示します。
yyout FILE* 型。これは、字句解析プログラムの出力が書き込まれる場所を示します。デフォルトでは、yyin と yyout は標準の入力と出力を示します。
yytext マッチングしたパターンのテキストが、この変数に格納されます (char* 型)。
yyleng マッチングしたパターンの長さを指定します。
yylineno 現行の行番号情報を提供します。(字句解析プログラムがサポートする場合としない場合があります。)
Lex 関数
yylex()分析を開始する関数です。Lex によって自動的に生成されます。
yywrap()この関数は、ファイル終わり (または入力終わり) が検出されるときに呼び出されます。この関数が 1 を戻す場合、解析は停止します。それで、この関数は複数のファイルを解析する場合に使用されます。コードを 3 番目の区分に書き込んで、複数のファイルを解析するように指定することができます。ストラテジーとして、すべてのファイルが解析されるまで yyin ファイル・ポインター (前述の表を参照) が異なるファイルを示すようにします。最後に、yywrap() は解析の終わりを示す 1 を戻します。
yyless(int n)この関数は、読み取られるトークンの最初の ‘n’ 文字以外をプッシュするために使用されます。
yymore()この関数は、現在のトークンに次のトークンを付加することを字句解析プログラムに通知します。

Lex に関する説明はここまでです。では次に Yacc に移りましょう。

Yacc

Yacc とは Yet Another Compiler Compiler を表します。Yacc の GNU 版は Bison と呼ばれています。これは、言語を記述する文法を、その言語のパーサーに変換するツールです。バッカス正規形式 (BNF) で作成されます。規則上、Yacc ファイルには接尾部 .y が付けられます。Yacc コンパイラーは以下に示すようなコンパイル行から呼び出されます。

        $ yacc <options>
        <filename ending with .y>

詳しい説明の前に、文法について取り上げてみましょう。これまでのセクションでは、Lex が入力シーケンスからトークンを認識するという点について見てきました。トークンのシーケンスを検査する場合、そのシーケンスの出現に対して特定のアクションを実行したいと考えることでしょう。このような場合の有効なシーケンスの仕様を文法と呼びます。Yacc 文法ファイルには、この文法の仕様が入れられます。さらに、シーケンスがマッチングするときに何を実行するかについても指定されます。

この概念をもう少しはっきりさせるために、英語の文法を例にとって考えてみましょう。トークンの組み合わせは、名詞、動詞、形容詞、そしてその他と考えることができます。これらのトークンを使用して文法的に正しい文を構成するには、定まった規則に従って組み合わせる必要があります。単純な文章では、名詞と動詞、あるいは名詞と動詞と名詞となるかもしれません。(I care. See spot run. など)

それで、今考えている事柄に当てはめれば、トークン自体は言語 (Lex) から来て、これらのトークンの許されるシーケンス (文法) は Yacc で指定されます。

Yacc でのコンパイラー作成には、次の 4 つのステップがあります。

  1. 文法ファイルに対して Yacc を実行して Yacc からパーサーを生成します。
  2. 以下のようにして文法を指定します。
    • .y ファイルに文法を書き込む (さらに、実行されるアクションを C で指定する)。
    • 入力を処理して、トークンをパーサーに渡す、字句アナライザーを作成する。これは Lex で行えます。
    • yyparse() を呼び出すことによって解析を開始する関数を作成する。
    • エラー処理ルーチン (yyerror() など) を作成する。
  3. Yacc によって生成されるコードを、他の関係のあるソース・ファイルとともにコンパイルします。
  4. オブジェクト・ファイルを、実行可能なパーサーの適切なライブラリーにリンクします。

Yacc での文法を作成する

Lex の場合と同じように、Yacc プログラムもそれぞれ %% 記号で区切られた 3 つの区分に分けられます。3 つの区分のとは、宣言、文法規則、そして C コードです。文法の仕様を説明するために、ここでは「name = age (years)」のフォーマットのファイルを解析する例を使ってみましょう。ファイルは、それぞれ空白文字で区切られた複数の名前と年齢が入っていると想定します。Yacc プログラムのそれぞれの区分を確認しながら、この例にあった文法ファイルを作成していきましょう。

C および Yacc の宣言

C 宣言は、マクロだけでなく、アクションで使用される型と変数を定義します。ヘッダー・ファイルも組み込まれます。Yacc のそれぞれの宣言部分によって、終了記号と非終了記号 (トークン) の名前が宣言され、演算子優先順位およびさまざまな記号のデータ型も記述されます。字句解析プログラム (Lex) は一般的にこれらのトークンを戻します。それで、このようなトークンはすべて Yacc 宣言で宣言する必要があります。

ファイル解析の例の中では、name、等号、および age トークンに注目します。Name はすべて文字の値であり、Age は数値です。そこで、宣言の区分は以下のようになります。

ファイル解析の例での宣言区分
        %
        #typedef char* string; /*
        to specify token types as char* */
        #define YYSTYPE string /*
        a Yacc variable which has the value of returned token */
        %}
        %token NAME EQ AGE
        %%

YYSTYPE を見て奇妙に思われるかもしれません。しかし、Lex と同様 Yacc にも、機能を拡張するために利用できる変数と関数のセットがあります。YYSTYPE は、字句解析プログラムからの値をパーサーまたは Yacc にコピーするために使われる yylval (別の Yacc 変数) の型を定義します。デフォルトは int 型です。文字ストリングは字句解析プログラムからコピーされるため、char* 型に再定義されています。Yacc の変数の詳細については、Yacc の解説書 (『参考文献』を参照) をご覧ください。

Yacc 文法規則

Yacc 文法規則は、以下に示すような形式になります。

        result: components { /*
        action to be taken in C */ }
        ;

この例では、result は規則が記述する非終了記号です。Components は、規則によって組み合わされるさまざまな終了記号と非終了記号です。Components に続けて、特定のシーケンスとマッチングするときに実行されるアクションを指定することができます。以下の例をご覧ください。

       param : NAME EQ NAME {
        printf("\tName:%s\tValue(name):%s\n", $1,$3);}
            | NAME EQ VALUE{
            printf("\tName:%s\tValue(value):%s\n",$1,$3);}
        ;

上記の例では、シーケンス NAME EQ NAME とマッチングすると、それに対応する { } の中のアクションが実行されます。さらに、ここでは便利な機能を持つ $1 と $3 も作用します。これらは、トークン NAME (1 番目のもの) と NAME (2 番目のもの。2 行目の場合は VALUE) の値を指します。字句解析プログラムは、これらの値を yylval と呼ばれる Yacc 変数によって戻します。トークン NAME の Lex コードは以下のようになります。

       char [A-Za-z]
        name {char}+
        %%
        {name} { yylval = strdup(yytext);
        return NAME; }

今回のファイル解析の例では、規則の区分は以下のようになります。

ファイル解析の文法
        file : record file
        | record
        ;
        record: NAME EQ AGE {
        printf("%s is now %s years old!!!", $1, $3);}
        ;
        %%

追加の C コード

文法ファイルの最後の区分である追加の C コードに移りましょう。(この区分はオプションです。省略したいと思うユーザーはそうできます。) main() のような関数は、yyparse() 関数 (Lex での yylex() 関数の Yacc 版) を呼び出します。一般に、Yacc は yyerror(char msg) のコードも提供されると想定します。yyerror(char msg) が呼び出されると、パーサーは必ずエラーを発生します。エラー・メッセージはパラメーターとして渡されます。シンプルな yyerror( char* ) は以下のようになります。

       int yyerror(char* msg)
        {
        printf("Error: %s
        encountered at line number:%d\n", msg, yylineno); }

yylineno は行番号情報を提供します。

今回のファイル解析の例の main 関数もこの区分に組み込まれます。

追加の C コード
       void main()
        {
            yyparse();
        }
        int yyerror(char* msg)
        {
        printf("Error: %s
        encountered \n", msg);

コードを生成するには、以下に示すコマンドを使用できます。

$ yacc –d <filename.y>

これは、出力ファイル y.tab.h および y.tab.c を生成し、UNIX の標準の C コンパイラー (たとえば、gcc) を使用してコンパイルできます。

コマンド行で使用できる他の共通オプション

  • '-d' ,'--defines' : マクロ定義の入った特別な出力ファイルを作成します。内容は、文法に定義されているトークン・タイプ名、セマンティック値タイプYYSTYPE、およびいくつかの外部変数宣言です。パーサーの出力ファイルの名前が 'name.c' であれば、'-d' ファイルの名前は 'name.h' となります。yylex 定義を別個のソース・ファイルに入れたい場合、yylex はyylval 変数とトークン・タイプ・コードを参照できなければならないため、'name.h' が必要となります。
  • '-b file-prefix' ,'--file-prefix=prefix' : すべての Yacc 出力ファイル名に使用される接頭部を指定します。入力ファイルの名前が 'prefix.c' となるように名前を選択します。
  • '-o outfile' ,'--output-file=outfile' : パーサー・ファイルの名前 outfile を指定します。他の出力ファイル名は、'-d' オプションで説明されているように outfile から構成されます。

Yacc ライブラリーは通常、コンパイルの段階で自動的に組み込まれます。しかし、コンパイル時に–ly オプションを指定することによって、明示的に組み込むこともできます。この例の場合、コンパイル・コマンド行は以下のようになります。

        $ cc <source file
        names> -ly

Lex と Yacc を協働させる

これまでは、Lex と Yacc を別個に取り上げてきました。ここからは、それらをどのように協働させることができるかを考えましょう。

プログラムは普通トークンを戻すごとに、yylex() 関数を呼び出します。これが停止するのは、ファイルの終わりか、トークンが無効な場合です。

Yacc で生成するパーサーは、トークンを取得するためにyylex() を呼び出します。yylex() は Lex によって生成するか、スクラッチから作成することができます。Lex で生成した字句解析プログラムを Yacc とともに使用する場合、Lex でパターンがマッチングするたびに、トークンが戻されなければなりません。Lex でのパターンのマッチング時に実行される、アクションの一般的な形式は以下のようになります。

       {pattern} { /* do smthg*/
        return TOKEN_NAME; }

Yacc は戻されるトークンを取得します。Yacc が –d オプションを指定して.y ファイルをコンパイルすると、ヘッダー・ファイルが生成され、それぞれのトークンごとに#define が付けられます。Lex と Yacc がともに使用される場合、ヘッダー・ファイルは、対応する Lex.lex ファイルの C 宣言区分に組み込む必要があります。

では、ここで名前と年齢のファイル解析の例に戻って、Lex および Yacc ファイルのコードを見てみましょう。

Name.y - 文法ファイル
        %
        typedef char* string;
        #define YYSTYPE string
        %}
        %token NAME EQ AGE
        %%
        file : record file
        | record
        ;
        record : NAME EQ AGE {
        printf("%s is %s years old!!!\n", $1, $3); }
        ;
        %%
        int main()
        {
        yyparse();
        return 0;
        }
        int yyerror(char *msg)
        {
        printf("Error
        encountered: %s \n", msg);
        }
Name.lex - パーサーのための Lex ファイル
        %{
        #include "y.tab.h"
        #include <stdio.h>
        #include <string.h>
        extern char* yylval;
        %}
        char [A-Za-z]
        num [0-9]
        eq [=]
        name {char}+
        age {num}+
        %%
        {name} { yylval = strdup(yytext);
        return NAME; }
        {eq} { return EQ; }
        {age} { yylval = strdup(yytext);
        return AGE; }
        %%
        int yywrap()
        {
        return 1;
        }

解説のポイントとして、Yacc によって生成されるヘッダー・ファイルy.tab.h を見てみましょう。

y.tab.h - Yacc が生成するヘッダー
            # define NAME 257
            # define EQ 258
            # define AGE 259

これで、Lex と Yacc に関する解説は終了です。では、今日はどの言語でコンパイルしますか ?


ダウンロード可能なリソース


関連トピック


コメント

コメントを登録するにはサインインあるいは登録してください。

static.content.url=http://www.ibm.com/developerworks/js/artrating/
SITE_ID=60
Zone=Linux
ArticleID=228935
ArticleTitle=Yacc...そしてLexをよみがえらせる
publish-date=11012000