読者です 読者をやめる 読者になる 読者になる

GNU Bisonの使い方(C言語)

GNU Bisonは人が読んで理解しやすい文法ファイル(*.y)から、C,C++そしてJavaのparserを生成してくれるツールです。それぞれに多少APIが異なると思いますが、ここではC言語で使う場合に定義しないといけない関数、アクセスできるグローバル変数について説明したいと思います。

文法ファイル

%{
#define YYSTYPE double  // YYSTYPEはyylvalの型。指定しなければintになる。
int yylex(void);
void yyerror(char*);
#include <stdlib.h>
#include <stdio.h>
static double* result;
%}

%token NUM EOL
%%
line:EOL
   | exp EOL { result = (double*)malloc(sizeof(double));
               *result = $1; return 1;}
;
exp: NUM
   | exp exp '+' { $$ = $1 + $2;}
   | exp exp '-' { $$ = $1 - $2;}
   | exp exp '*' { $$ = $1 * $2;}
   | exp exp '/' { $$ = $1 / $2;}
;
%%

static double *result;
static const char* input;
double* parse(const char* source) {
  result = NULL;
  input = source;
  yyparse();
  return result;
}

int yylex(void) {
 int c;
 if(input == NULL || *input == '\0')
   return EOL;
 do{
   c = *input++;
  }while(isspace(c) || c == '\n');
 if(isdigit(c)) {
   yylval = c - '0';
   return NUM;
 }
 
 return c;
}

void yyerror(char* s) {
  fprintf(stderr, "%s\n", s);
  exit(1);
}

文法ファイルは3つの部分に分かれます。上下の部分はC言語になっているので、そこから説明を始めます。bisonの方が生成するparserとしてyyparse(void)がありますが、この関数は中でyylexを繰り返し呼びます。parseする処理を行うには、グローバル変数yylvalの値とyylexが返すトークンの種類に関する情報が必要になります。yylvalの型はYYSTYPE(これ自体はマクロ)になります。YYSTYPEはトークンの型で、デフォルトでint型ですが、#defineなどで定義し直すことができます(上の例ではとりあえずdoubleにしてます)。文法違反した場合はyyparseはyyerror(char*)を呼ぶので、これも定義しておく必要があります。

文法の定義の仕方(directive)


あとで書く

bisonコマンドの使い方


とりあえず、bisonを使ったプログラムを走らせるまでやってみます。main関数(ファイル名はmain.cとしましょう)の方はこんな感じです。

#include "rpn.h"
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <string.h>
#include "y.tab.c"
void test_parse(void) {
 double* result = NULL;

 result = parse("12+");
 assert(3 == *result && "exp: exp '+' exp");
 free(result);

 result = parse("32-");
 assert(1 == *result && "exp: exp '-' exp");
 free(result);

 result = parse("72*");
 if(result != NULL)
   assert(14 == *result && "exp: exp '-' exp");
 free(result);

 result = parse("32/");
 if(result != NULL)
   assert(1.5 == *result && "exp: exp '-' exp");
 free(result);

 result = parse("1 5 -");
 if(result != NULL)
   assert(-4 == *result && "skip space");
 free(result);

 result = parse("1\n 2 +");
 if(result != NULL)
   assert(3 == *result && "skip '\n'");
 free(result);


}

int main(int argc, char* argv[]) {
  if(argc == 2 && strcmp(argv[1], "test") == 0) {
    test_parse();
    printf("all tests done\n");
    exit(0);
  } else if(argc >=2) {
    char exp[80] = "";
    int i;
    for(i = 1; i < argc; i++)
      strcat(exp, argv[i]);
    printf("%lf\n",*parse(exp));
    exit(0);
  }
  return 1;
}

"bison -y "をすればデフォルトでy.tab.cが生成されます。これをインクルードしてますから、"gcc main.c"とするだけで実行ファイルが生成されます。"./a.out test"でテストが走り、"a.out (逆ポーランド記法の式)"で計算された結果が標準出力されます。