bisonとflexで自作パーサーを作る

この記事は情報系の学生が、レポートの代わりにちまちま作り上げた記事です。一応は、調べていろいろ書いたつもりなんですが、間違っていないこともないです。全てが正しいと思わず、「あれっ」って思ったら、必ず確認してください！！
そして、間違いがあったら指摘してもらえるとうれしいです。

---

前回の続編

前回は、再帰下降法を用いてC言語の数式パーサーを作りました。今回は、bisonとflexを用いて同様のパーサーを作成します。再帰下降法と異なり簡単に字句解析・構文解析が行えるのが特徴です。

ソース一式

今回作成したソースはGistに載せておきます。

flex（The Fast Lexical Analyzer)

flexとはlexの上位互換版になります。lexは字句解析ルーチンを生成します。flexはlexよりも少ない時間でテーブルを生成できつつ、効率の良いテーブルとなっています。

bison

bisonとはyaccの上位互換版です。bisonは文脈自由文法の仕様を入力として、その文法を解析するためのC言語の関数を生成します。ここではC言語を用いているためC言語関数を生成しますが、Pythonなどのbisonを使用すればPythonコードを吐き出してくれる...はずです。

flex + bison

つまり、flexとbisonを用いることで、自己流の定義ファイルや言語解釈をしてくれるプログラムを作ることが出来ます。

flexとbisonのインストール

ここではUnix系の方法を記載しています。WindowsだとWindows on Bashを使ってもらえば使えるかと思います。

# Ubuntu系
apt-get install flex bison gcc make

# mac
## homebrew用
brew install flex bison gcc make

## macports用
sudo port install flex bison gcc make

ファイル構成

今回は字句解析のためのlexファイルと構文解析のためのyaccファイル、その他演算に必要な関数や構造体を定義するための関数ファイル（.h .c）の４つを用意します。これらを分割コンパイルするため、Makefileを作成し、コンパイルすることとします。今回のそれぞれのファイル名は以下のようにしました。これか各個人において変更してもらっても大丈夫です。

• calculator.l
• calculator.y
• myFunction.h
• myFanction.c

Makefile

分割されたファイルを指定したコマンドで自動的にコンパイルしてくれる、makeコマンドを利用するための定義ファイルです。Makefile内にmakeコマンドが実行されたときの処理を記述します。

mycalc: y.tab.o lex.yy.o myFunction.o
    g++ -o mycalc y.tab.o lex.yy.o myFunction.o

y.tab.o: calculator.y
    g++ -c y.tab.c

lex.yy.o: calculator.l
    flex -l calculator.l
    g++ -c lex.yy.c

myFunction.o: myFunction.c
    g++ -c myFunction.c

clean:; rm mycalc y.tab.c y.tab.h lex.yy.c *.o

このmakeファイルで生成されるファイルは

• mycalc
• y.tab.c
• y.tab.h
• y.tab.o
• lex.yy.c
• lex.yy.o
• myFunction.o

です。実行ファイルはmycalcになっています。このmycalcはy.tab.o, lex.yy.o, myFunction.oを利用してコンパイルしています。makefileの詳細については以下をご覧になってください。

calculator.l

"%%"の内側に、正規表現とパターン処理を記述します。"%{ ...... %}"内には、C言語のソースを記述することが出来ます。これをflexコマンドでコンパイルすればlex.yy.cというC言語のソースコードが吐き出されます。

トークンの定義

字句解析を行うには、入力された文字列を最小単位である字句（トークン）に分割しなければいけません。そのトークンを定義します。例えば、C言語では

• int, double, for, while などの予約語
• 関数名、変数名などの識別子
• 各種演算子

などがトークンとされています。flexでは、BNFに似た規則定義をすることで、字句解析器を自動生成してくれます。"%{ %}"内にC言語を記述できます。処理に必要なヘッダーや関数などを定義しておきます。

%{
  #include <stdio.h>
  #include <stdlib.h>
  #include <string.h>
  
  // yacc header
  #include "y.tab.h"

  // myfunction header
  #include "myFunction.h"

  map<string, double> varStack;

  extern "C" int yywrap( void ){ return 1 ; }
%}

map<string, double> varStackは、変数をストックしておくためのmap変数です。keyを変数名にして、valueを値として代入します。

#include "y.tab.h"はこの後に説明する bison をコンパイルしたときに生成されるヘッダファイルです。

パターンマッチング処理

flexで整数、小数、文字列を識別するには、以下のような正規表現を書く。

[0-9]+ {
    ....
}

[0-9]+\.[0-9]+ {
    ....
}

[_a-zA-Z]*[_a-zA-Z0-9]+ {
    ...
}

また、トークンは以下のように定義する

"*"	 return MUL ;
"/"	 return DIV ;
"%"  return SUR ;
"+"	 return ADD ;
"-"	 return SUB ;

そのため簡単なファイルの内容は、このように書けます。

%{
  #include <stdio.h>
  #include <stdlib.h>
  #include <string.h>
  
  // yacc header
  #include "y.tab.h"

  // myfunction header
  #include "myFunction.h"

  map<string, double> varStack;

  extern "C" int yywrap( void ){ return 1 ; }
%}

%%
"*"	 return MUL ;
"/"	 return DIV ;
"%"   return SUR ;
"+"	 return ADD ;
"-"	 return SUB ;

[0-9]+ {
    ....
}

[0-9]+\.[0-9]+ {
    ....
}

[_a-zA-Z]*[_a-zA-Z0-9]+ {
    ...
}
%%

extern宣言については用語説明に記載してあります。

calculator.y

構文解析を行なうための処理を記述します。構文をBNF記法で記述すれば、構文パターンに応じた状態遷移テーブル（LR法、LL法など）を自動生成し、その遷移テーブル（用語説明を参照）を用いたC言語の処理プログラムを出力してくれる。このファイルをbisonコマンドでコンパイルすることで、y.tab.cとy.tab.hが生成される。この生成されたパーサーの処理内容はy.tab.cに記載されているため、確認することができます。
yaccやbisonもlex同様、"%{ %}"内にC/C++を記述します。このファイルの"%{%}"内には、yaccが定義する内部関数のプロトタイプ宣言をしないといけません。これは、extern宣言になります。

C言語のヘッダー部定義

%{
#include "myFunction.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <map>
using namespace std;


// yaccが定義する内部関数のプロトタイプ宣言
extern int yyerror( const char* ) ;
extern int yyparse( void ) ;
extern int yylex( void ) ;
extern char* yytext ;
extern FILE* yyin ;
%}

使用する変数の定義

入力文字列は、lexで受け取ります。lexではyylvalを参照して格納する変数にアクセスします。このyylvalに紐づける変数群は"%union{...}"で記述します。

%union {
  struct number* str;
}

このように、記述することで、lexファイルからは以下のようにアクセスすることが可能になります。仮に整数が入力されたとします。

[0-9]+ {
  yylval.str = new struct number;
  yylval.str->type = T_INT;
  yylval.str->val = atof(yytext);
  return NUMBER;
}

lexで宣言したトークンをbisonで再定義

また、bisonファイルでlexで定義したトークンを使用するには%tokenで定義する必要があります。lexで以下の定義したとすれば

" "  {}
"\n" return CR ;

"("  return SBK ;
")"  return EBK ;

"++" return INC ;
"--" return DEC ;

"*"	return MUL ;
"/"	return DIV ;
"%"  return SUR ;

"+"	return ADD ;
"-"	return SUB ;

"<<" return LEFT_SHIFT ;
">>" return RIGHT_SHIFT ;

"<"  return LEFT_CLS ;
">"  return RIGHT_CLS ;
"<=" return LEFT_CLS_EQ ;
">=" return RIGHT_CLS_EQ ;

"==" return EQ_EQ ;
"!=" return NOT_EQ ;

"="  return EQ ;
"+=" return ADD_EQ ;
"-=" return SUB_EQ ;
"*=" return MUL_EQ ;
"/=" return DIV_EQ ;
"%=" return SUR_EQ ;

これを、bisonファイルで利用するためには、以下のようにトークンを定義します。

%token CR
%token SBK EBK
%token INC DEC
%token MUL DIV SUR
%token ADD SUB
%token LEFT_SHIFT RIGHT_SHIFT
%token LEFT_CLS RIGHT_CLS LEFT_CLS_EQ RIGHT_CLS_EQ
%token EQ_EQ NOT_EQ
%token EQ ADD_EQ SUB_EQ MUL_EQ DIV_EQ SUR_EQ

さらに、さっきのunionで定義された変数がそれぞれどのトークン属性を持つかを、同様にして定義します。

// %token <変数名> 対応するトークン
%token <str> NUMBER
%token <str> CHARACTER

構文解析BNF

例として以下に、構文解析BNFを示します。

%%
input : line
      | input line
      ;

line : expr CR { printf(">> %f\n", $1->val) ; }
     | CR      { exit(0) ; } /* 未入力Enterは終了 */
     ;

expr : term	                { $$ = $1 ; }
     | expr LEFT_CLS expr     { $$ = Comparing($1, $3, LEFT_CLS) ; }
     | expr RIGHT_CLS expr    { $$ = Comparing($1, $3, RIGHT_CLS) ; }
     | expr LEFT_CLS_EQ expr  { $$ = Comparing($1, $3, LEFT_CLS_EQ) ; }
     | expr RIGHT_CLS_EQ expr { $$ = Comparing($1, $3, RIGHT_CLS_EQ) ; }
     | expr LEFT_SHIFT expr   { $$ = Shiftoperator($1, $3, LEFT_SHIFT) ; }
     | expr RIGHT_SHIFT expr  { $$ = Shiftoperator($1, $3, RIGHT_SHIFT) ; }
     | expr ADD term          { $$ = newVal($1, $3, ADD) ; }
     | expr SUB term          { $$ = newVal($1, $3, SUB) ; }
     ;

term : factor          { $$ = $1 ; }
     | term MUL factor { $$ = newVal($1, $3, MUL) ; }
     | term DIV factor { $$ = newVal($1, $3, DIV) ; }
     | term SUR factor { $$ = newVal($1, $3, SUR) ; }
     ;

factor : NUMBER                  { $$ = $1 ; }
       | CHARACTER               { $$ = Variant($1, NULL) ; }
       | CHARACTER ADD_EQ expr   { $$ = Substitution($1, $3, ADD_EQ) ; }
       | CHARACTER SUB_EQ expr   { $$ = Substitution($1, $3, SUB_EQ) ; }
       | CHARACTER MUL_EQ expr   { $$ = Substitution($1, $3, MUL_EQ) ; }
       | CHARACTER DIV_EQ expr   { $$ = Substitution($1, $3, DIV_EQ) ; }
       | CHARACTER SUR_EQ expr   { $$ = Substitution($1, $3, SUR_EQ) ; }
       | CHARACTER EQ expr       { $$ = Variant($1, $3) ; }
       | INC CHARACTER           { $$ = front_incdec($2, INC) ; }
       | DEC CHARACTER           { $$ = front_incdec($2, DEC) ; }
       | CHARACTER INC           { $$ = back_incdec($1, INC) ; }
       | CHARACTER DEC           { $$ = back_incdec($1, DEC) ; }
       | SBK expr EBK            { $$ = $2 ; }
       ;
%%

トークン演算子

ここでの$$や$1は、BNFで記述されているトークンに紐づいています。つまり、仮に構文解析した結果

factor: CHARACTER ADD_EQ expr { $$ = Substitution($1, $3, ADD_EQ) ; } 

だったとします。この時、各紐付けは以下のようになっています。

factor    -> $$
CHARACTER -> $1
expr      -> $3

となっています。そのため、動作としては Substitution関数 に引数として$1, $3, ADD_EQを渡し、計算した結果を$$であるfactorとする。という処理になります。もちろん、"{}"の中に直接演算処理を書いてもいいのですが、今回は構造体などを使っているため、面倒だったので、関数化して呼び出して使うことにしました。ここで使う関数は後述するmyFunction.c, myFunction.hに定義、実装してあります。

myFunction.h

主に演算子系関数や構造体を宣言します。calculator.l, calculator.y, myFunction.cでこのファイルをインクルードすることでmyFunction.cに記述した関数処理を行なうことができます。多重インクルードを防ぐために#ifndef ~ #endif内に記述することとします。enumについてはこちらです。

#ifndef MYFUNCTION_H
#define MYFUNCTION_H

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <map>

// トークン識別番号利用のため include
#include "y.tab.h"

using namespace std;

// 変数用スタック
extern map<string, double> varStack;

// 変数の種別一覧
enum numberType {
  T_NULL = 0,
  T_INT,
  T_DOUBLE,
  T_STR,
  T_BOOL
} ;

// 入力用構造体
struct number {
  enum numberType type;
  union {
    char sval[100];
    double val;
  } ;
} ;

// 演算関数を宣言
bool isVarFound (struct number* data) ;
struct number* newVal (struct number* p1, struct number* p2, int op) ;
struct number* Variant (struct number* name, struct number* value) ;
struct number* back_incdec (struct number* variant, int op) ;
struct number* front_incdec (struct number* variant, int op) ;
struct number* Substitution (struct number* variant, struct number* num, int op) ;
struct number* Shiftoperator (struct number* source, struct number* target, int op) ;
struct number* Comparing (struct number* p1, struct number* p2, int op) ;

#endif /* end of include guard: MYFUNCTION_H */

myFinction.c

ヘッダーで定義した関数の実体を記述します。特に目立ったことは何もしていません。コードを見てもらえれば大丈夫だと思うんですが、唯一しているのは、関数内にローカルクラスを定義して、ローカル関数を実現させていることぐらいです。

ローカルクラスを使ったローカル関数

C++では、関数内でクラスを定義する「ローカルクラス」というものが許可されています。関数内で定義したクラスのスコープ範囲は、その定義したクラスのみです。ローカルクラスもクラスなので、メンバ関数を保持することができます。このメンバ関数のスコープも、定義されている関数内なので実質「関数内関数」として扱うことができます。

int main ( void ) {
  struct L_Func {
    static int add ( int a, int b )
    {
      return a + b;
    }
  } ;

  std::cout << L_Func::add(1, 2) << std::endl ;
}

関数オブジェクト

実際はこれでもいいのですが、いちいちローカルクラス名を書くのが面倒なので、「関数オブジェクト」を使います。無名構造体を定義して、()演算子をオーバーロードして関数オブジェクト化します。

int main ( void ) {

  struct {  // 無名構造体
    int operator()( int a, int b )
    {
      return a + b;
    }
  } add;  // ローカル構造体変数

  std::cout << add(1, 2) << std::endl ;
}

ローカル関数外の変数へのアクセス

しかし、このローカル関数は外側のauto変数へアクセスすることができません。アクセスするにはstatic宣言をする必要があります。なので、static宣言して変数に再代入して利用するなどの一手間を加える必要があります。

...

  // ローカル関数参照用変数
  static int s_op;
  s_op = op;

  // 計算用ローカル関数を定義
  struct {
    double operator()(double p0, double p1) {
      double res = 0;
      switch (s_op) {
        case LEFT_SHIFT: {
          // printf("LEFT\n");
          res = (int)p0 << (int)p1;
          break;
        }
        case RIGHT_SHIFT: {
          // printf("RIGHT\n");
          res = (int)p0 >> (int)p1;
          break;
        }
        default: {
          // printf("DEFAULT\n");
          break;
        }
      }
      return res;
    };
  } Calc;
...

まとめ

こんなに長々と書きましたが、結局何が言いたいかというと、たった数式を解析して演算させるだけのパーサーを作るだけで、こんなにも色々な手法・技術があるということを改めて知ったということです。全然聞いたことも内容な単語とかもでてきて調べて、理解するのが大変でした...。これからも興味を持ったら調べて、実際に作ってみようと思いましたね。

用語解説

extern

extern宣言とは、宣言だけを行い定義は行わないものです。つまり、extern宣言を用いる「宣言はするが、実体・定義はどこにあるか保証しない」とすることで、異なるソースファイル間で変数を共有することができます。しかし、ファイルを分割するということは、機能を分けているということであり、それらをまたいで変数を共有することは推奨されません。つまりextern宣言は乱用しないということです。

また、extern "C" とはCとC++間で発生する マングリング を回避するために利用します。

マングリング

CとC++が混在したプログラムを書いて、コンパイルをした時に定義した関数が undefined でエラーになることが多々あるのですが、それはC++のマングルという機能が働いているからだと思われます。C++コンパイラは基本的にシンボルが一意の名前を持つように 名前マングル（マングリング）という処理を行います。つまり、以下のようなコードをCとC++でそれぞれコンパイルして、中間コードを確認すると...

// gcc -c c.c
#include <stdio.h>

void example_function();
int main ( void ) {
  example_function();
  return 0;
}

// gcc -c cp.cpp
#include <iostream>

void example_function();
int main ( void ) {
  example_function();
  return 0;
}

$ gcc -c c.c
$ nm c.o
                 U _example_function
0000000000000000 T _main


$ gcc -c c.cpp
$ nm c.o
                 U __Z16example_functionv
0000000000000000 T _main

このように、Cコンパイラでは宣言した関数名がそのままシンボル名になっているのに対し、C++コンパイラでは、宣言した関数名にいくつかの情報を付け加えた物をシンボル名にしています。この「いくつかの情報を付け加えてシンボル名にする」のが マングリング です。つまり、C++からCの関数をコールする場合、シンボル名が異なるので呼び出すことができません。そのため、undefinedとして処理されます。そのため、このC++コンパイラの マングリング を回避するために、extern "C" { ... }という記法があります。これで囲まれた中で宣言された関数はCの関数とされ、マングリングされません。

// gcc -c cp.cpp
#include <iostream>

extern "C" void example_function();
int main ( void ) {
  example_function();
  return 0;
}

先ほどのコードのプロトタイプ宣言にextern "C"を付与しました。これでコンパイルし、中間コードを確認すると....

$ gcc -c c.cpp
$ nm c.o
                 U _example_function
0000000000000000 T _main

という風に、マングリングされていません。そのため、CとC++が混在し、かつ、相互で呼び出しを行うことを考える時にはextern "C"が必要になります。が、上でも説明したようにextern宣言は乱用しないように...。

構文解析（LR, LL, LALR法）

構文解析では主に２種類の方法を用いて構文解析が行われる。

トップダウン構文解析

入力されたテキストを、入力された順番で解析します。そしてそれを元にして生成規則を適用していきます。LL法が言語として主流であり、左端導出を使用します。トークンを先読みするLL(k)法が使われている場合もある。

ボトムアップ構文解析

入力されたテキストを最後に入力された要素から逆順で解析し、生成規則を適用していく。トップダウン構文解析とは異なり、LR法が言語として主流となっていて、右端導出を使用しています。yaccなどは先読み（Look-Ahead）を行うLR法、別名LALR法を使用している。

前回の記事に書いた「再帰下降での構文解析」は、ボトムアップ構文解析の解析手法の１つである。が、LL法と異なり、左再帰が含まれていると、無限ループが発生し正常に解析を行うことができません。左再帰とは、生成規則の先頭に自分自身が再定義されていることを指し、右再帰はその逆を表します。

X => X + Z ; 左再帰
X => Z + X ; 右再帰

LL構文解析

LL構文解析では「解析表」と呼ばれる表を用いて、構文解析を行う。そもそも、LL構文解析のアルゴリズムとしては以下のようになる。

スタート符号をスタックにプッシュ
while( スタック != null )
{
    スタックの先頭要素が...？
        非終端記号: 解析表の生成規則で記号を置き換える（置き換えられなければエラー）
        終端記号　: スタップから要素をポップして、入力された記号を１つ削除
}
最終的にスタックと入力が両方空になれば構文解析成功

というようなアルゴリズムをとる。実際の解析例をあげる。

まずは、以下のように生成規則を定義する。

1. A  -> ZA'
2. A' -> E
3. A' -> +BA'
4. B  -> CB'
5. B' -> E
6. B' -> *CB'
7. C  -> i
8. C  -> (A)

そして、LL(1): 「１トークン先読み構文解析表」を以下に示す。スタック先頭の非終端記号がXで、次に入力される記号がZのときに、適用すべき生成規則である。

X\Z	i	+	*	(	)	$
A	1			1
A'		3			2	2
B	4			4
B'		5	6		5	5
C	7			8

このとき、スタック先頭がAで、次の入力される記号がiだった場合、適用される生成規則は 1 となるので、スタック先頭AをA -> ZA'を用いて置き換える。ということになります。解析例は長くなるので載せませんが、スタック先頭の要素、次に入力される記号さえ見ておけば、書くことができます...。

enum（列挙型）

列挙型を利用すると、定数の集合に名前をつけることができます。そして、新しい型のように扱うことができます。

enum Sex {
  MALE, 
  WOMAN
};

定数は明示しなければ0からの連番となります。また、明示することもできます。

enum ErrorType {
  INPUT_ERROR   = -1,
  OUTPUT_ERROR  = -2,
  UNKNOWN_ERROR = -999
};

enumのサイズ

enumのサイズはコンパイラオプションで指定しない限り、sizeof(int)より大きくはなりません。が、Cでは型が曖昧なのであくまでもint相当で、signedかunsignedかは実装に依存します。基本的にはsizeof(int)と等価と考えていいと思われます。

enumの型

Cでは、単なる定数の列挙であったが、C++ではenum型として厳密になった。つまりは

enum {
  CONST_VAL
};

try
{
  throw CONST_VAL;
}
catch (const int e)
{
  ...
}

では、コンパイルを行うことができない。C++ではenumに名前をつけ、型とします。

enum const_vals {
  CONST_VAL
};

try
{
  throw CONST_VAL;
}
catch (const const_vals e)
{
  ...
}

これより、型としてはenum const_vals型となります。