lexとyaccの記述方法の説明

イントロ

lexとyaccとはコンパイラ生成をするためのものである。lexは字句解析ルーチン、yaccは構文解析ルーチンを生成するツールである。

linuxではlexの代わりにflex、yaccの代わりにbisonが使える。

基本的にflexとbisonの仕様に沿って説明していきます。

lex(A lexical nalyzer generator)

lexの使い方

記述方法とかは後々として、実行するまでの流れを書く。

lexのプログラムは拡張子が.lとなり、lexのソースプログラムをsample.l、実行ファイルをexecutableとする。

またflexコマンドを実行するとlex.yy.cというファイルが出力される

$ flex sample.l
$ gcc -lfl lex.yy.c -o executable
$ ./executable

gccのところの-lflオプションはflexのライブラリをリンクしています。

lexプログラムの記述方法

lexプログラムは3部構成となっており、%%によって分割されます。

定義部
%%
ルール部
%%
ユーザコード部

また定義部とユーザコード部はなくても構いません。

以下にmanpageにもあるflexのサンプルコードを載せます。上記3部はこのサンプルコードを元に簡単に解説していきます。

このサンプルコードは入力された文字の行数と文字数を数えるプログラムになっています。

%{
            int num_lines = 0, num_chars = 0;
%}

%%
\n      ++num_lines; ++num_chars;
.       ++num_chars;

%%
main()
        {
        yylex();
        printf( "# of lines = %d, # of chars = %d\n",
                num_lines, num_chars );
        }

定義部

定義部では文字変換のための定義、広域で用いられるC言語のソースコードを記述します。

ここでは主にC言語のソースコードを書くことになると思います(自分がここでC言語以外の記述をしていないのでわからない)

C言語のソースコードは%{と%}で囲みます。サンプルコードを見ればわかりやすいと思います。

ここで書かれたコードはyacc等、外部からもアクセス可能となります。

%{
            int num_lines = 0, num_chars = 0;
%}

ルール部

ルール部では字句解析のための規則を記述します。入力された文字列を判別するための正規表現と、正規表現で認識した祭に行う処理を記述します。

サンプルプログラムでは改行のパターンに一致した際に、num_linesとnum_charsをインクリメントし、それ以外の全ての文字でnum_charsをインクリメントします。

\n      ++num_lines; ++num_chars;
.       ++num_chars;

ルール部では最長のルールに一致するものを調べます。上に記述したルールに一致していても、その後に一致する最長の正規表現が見つかればそのパターンの処理を行います。

またルールに一致しなかった場合には標準出力として出力されるので、最後に全てに一致するルールを追加して何もしないようにしておく必要があります。

ユーザコード部

ルール部で使用する局所的な関数やlex単体で使用する場合main関数をC言語で記述します。おしまい

yacc(yet another compiler compiler)

yaccの記述方法

yaccプログラムも3部構成となっており、%%によって分割されます。 コメントも/**/で記述することができます

宣言部
%%
ルール部
%%
プログラム部

宣言部

ここではC言語のコードや符を宣言します。ここで宣言した符がルール部での構文規則で利用できます。

符はlexでのアクションの戻り値を利用します。

符の宣言には%token, %left, %right, %nonassocを使用します。これらは複数行書くことができ、また下の行で宣言された符の優先順位が高くなります。

符の宣言は%token 大文字列 大文字列のような形式で宣言します。宣言方法の違いは以下の通り

  • %token:符の宣言
  • %left:符の宣言と同時に左優先の結合を宣言する
  • %right:符の宣言と同時に右優先の結合を宣言する
  • %nonassoc:符の宣言と同時に結合をしないことを宣言する

宣言方法はこのような形になります。この例ではPOWERの優先順位が一番高くなります

%token LP RP

%left ADD SUB

%right POWER

ルール部

構文解析のための構文規則をここでは記述します。記述方法はBNFの感じです。

BNFで使う:==は:で、構文規則の最後には;を付けます。

必要な処理は{}で囲み、C言語で記述します。宣言部で定義した変数やプログラム部で記述した関数をこの中で使用できます。

ルール部はこんな形になります

NAME1 : TOKEN1 NAME1 {Program1} NAME2 {Program2}
      | TOKEN3 {Program3}
      ;

擬似変数の利用

構文間や構文規則内のデータの受け渡しに擬似変数を利用します。この変数はyaccのコンパイル時に自動的に宣言されるため、ルール部では宣言する必要はありません。

疑似変数は$n(n=1,2,3)や$$で表されます。

$nはルール部の右辺のn番目の項が渡す値、

$$は代入専用の疑似変数でアクション内で利用する場合、i個目のアクションで$$=4とした場合、次の項では$iとして参照可能となります。 また構文規則間での受け渡しも可能で、この場合は$$への代入文の中で一番右にある代入文で代入された値がサ変にある非終端記号が渡す値になります。

プログラム部

lexと同じくプログラム部では関数を記述します。またlexが出力したプログラムをIncludeします

main関数も必要に応じて書きます。

#include "lex.yy.c"

終わりに(終わらない)

書いてたら長くなってきたので次の記事でyaccのサンプルコードとともにlexとの連携も含めて書いていきます。

yaccに関してはコードを見つつ、この説明を見ていけば雰囲気はわかります(私がそうでした)

ということで次で簡単な電卓のソースコードを見せつつ説明していきます。