Bisonの多機能電卓の変更

2011-01-09
#compiler

定期的にスクリプト言語作りたい熱が発生する。まあできることからコツコツと、Bisonを使ったパーサの演習。多機能電卓では関数が第一級じゃないので関数をコピーすることができない：

f = cos  #<- エラー！

これをできるようにするには、式の型をdoubleで扱っているところをバリアント型にする必要がある：

/// 値の型
typedef enum {
  VAR_DOUBLE,
  VAR_FNCTPTR,
} VarType;

/// バリアント
typedef struct {
  VarType type;
  union {
    double d;
    double (*fnctptr)(double);
  } u;
} Value;
||<
そしてシンボルテーブルに値が格納されてしまっているのを止める：
>|c|
typedef struct symrec {
  struct symrec* next;
  char* name;
} symrec;

そして関数がトークンのタイプとなっていて構文にされていたのを、

exp
  ...
  | FNCT '(' exp ')'           { ＄＄ = (*($1->value.fnctptr))($3); }

（↑↓使う場合には＄＄を全角から半角に戻してください）

式の値の型によって呼び出すようにする必要がある。expに関数呼び出しを入れたままだとコンフリクトが発生するのでprimに追い出す：

exp
  : prim                     { ＄＄ = $1; }
  ...

prim
  : VAL               { ＄＄ = $1; }
  | SYM               { if (!refer(&＄＄, $1)) YYERROR; }
  | prim '(' exp ')'  { if (!funcall(&＄＄, $1, $3)) YYERROR; }
;

以降全ソース：

%{

#include <math.h>
#include <stdio.h>

#define FALSE  (0)
#define TRUE   (1)

int yylex(void);

/// エラーが起きると yyparse から呼び出される
void yyerror(const char* s) {
  printf("%s\n", s);
}

/// 値の型
typedef enum {
  VAR_DOUBLE,
  VAR_FNCTPTR,
} VarType;

/// バリアント
typedef struct {
  VarType type;
  union {
    double d;
    double (*fnctptr)(double);
  } u;
} Value;

/// シンボル
typedef struct symrec {
  struct symrec* next;
  char* name;
} symrec;

int refer(Value*, symrec*);
void assign(const char*, Value);
int funcall(Value*, Value, Value);
int arith1(Value*, Value, double (*)(double));
int arith2(Value*, Value, Value, double (*)(double, double));
double add(double x, double y)  { return x + y; }
double sub(double x, double y)  { return x - y; }
double mul(double x, double y)  { return x * y; }
double div(double x, double y)  { return x / y; }
double neg(double x)  { return -x; }
void dump_value(FILE*, Value);

%}

%union {
  Value val;    // 値
  symrec* sym;  // シンボルテーブルポインタ
}

%token <val>  VAL
%token <sym>  SYM
%type  <val>  exp prim

/* 演算子の優先の低い順に並べる */
%right '='
%left  '+' '-'
%left  '*' '/'
%left  UNARY_NEG  /* 単項－ */
%left  '^'

%%

input
  :  /* 空文字列 */
  | input line
;

line
  : '\n'
  | exp '\n'    { putchar('\t'); dump_value(stdout, $1); putchar('\n'); }
  | error '\n'  { yyerrok; }
;

exp
  : prim                     { ＄＄ = $1; }
  | SYM '=' exp              { assign($1->name, ＄＄ = $3); }
  | exp '+' exp              { if (!arith2(&＄＄, $1, $3, add)) YYERROR; }
  | exp '-' exp              { if (!arith2(&＄＄, $1, $3, sub)) YYERROR; }
  | exp '*' exp              { if (!arith2(&＄＄, $1, $3, mul)) YYERROR; }
  | exp '/' exp              { if (!arith2(&＄＄, $1, $3, div)) YYERROR; }
  | '-' exp %prec UNARY_NEG  { if (!arith1(&＄＄, $2, neg)) YYERROR; }
  | exp '^' exp              { if (!arith2(&＄＄, $1, $3, pow)) YYERROR; }
  | '(' exp ')'              { ＄＄ = $2; }
;

prim
  : VAL               { ＄＄ = $1; }
  | SYM               { if (!refer(&＄＄, $1)) YYERROR; }
  | prim '(' exp ')'  { if (!funcall(&＄＄, $1, $3)) YYERROR; }
;

%%

#include <ctype.h>
#include <malloc.h>
#include <string.h>

symrec* sym_table = NULL;

symrec* putsym(const char* sym_name) {
  symrec* ptr = (symrec*)malloc(sizeof(symrec));
  ptr->name = (char*)malloc(strlen(sym_name) + 1);
  strcpy(ptr->name, sym_name);
  ptr->next = sym_table;
  sym_table = ptr;
  return ptr;
}

symrec* getsym(const char* sym_name) {
  symrec* ptr;
  for (ptr = sym_table; ptr != NULL; ptr = ptr->next) {
    if (strcmp(ptr->name, sym_name) == 0)
      return ptr;
  }
  return NULL;
}

static int skip_spaces() {
  int c;
  while (c = getchar(), c == ' ' || c == '\t');
  return c;
}

static int read_symbol(int c) {
  static char* buf;
  static int length;
  symrec* s;
  int i = 0;
  do {
    if (i >= length) {  // あふれたのでバッファを大きくする
      if (length == 0)    length = 16/2;
      buf = (char*)realloc(buf, (length *= 2) + 1);
    }
    buf[i++] = c;   // 文字をバッファに加える
    c = getchar();  // 次の文字を読む
  } while (c != EOF && isalnum(c));
  ungetc(c, stdin);
  buf[i] = '\0';

  s = getsym(buf);
  if (s == NULL)
    s = putsym(buf);
  yylval.sym = s;
  return SYM;
}

/// 字句解析として yyparse から呼び出される
int yylex(void) {
  int c = skip_spaces();
  if (c == EOF)    return 0;
  if (c == '.' || isdigit(c)) {  // 数値
    ungetc(c, stdin);
    scanf("%lf", &yylval.val.u.d);
    yylval.val.type = VAR_DOUBLE;
    return VAL;
  }
  if (isalpha(c)) {  // 識別子
    return read_symbol(c);
  }
  // その他の文字は文字リテラルトークン
  return c;
}

void set_double(Value* p, double x)  { p->type = VAR_DOUBLE; p->u.d = x; }
void set_fnctptr(Value* p, double (*f)(double))  { p->type = VAR_FNCTPTR; p->u.fnctptr = f; }

int arith1(Value* result, Value a, double (*f)(double)) {
  if (a.type != VAR_DOUBLE) {
    fprintf(stderr, "Can't operate arithmetic: ");
    dump_value(stderr, a);
    fprintf(stderr, "\n");
    return FALSE;
  } else {
    set_double(result, f(a.u.d));
    return TRUE;
  }
}

int arith2(Value* result, Value a, Value b, double (*f)(double, double)) {
  if (a.type != VAR_DOUBLE) {
    fprintf(stderr, "Can't operate arithmetic: ");
    dump_value(stderr, a);
    fprintf(stderr, "\n");
    return FALSE;
  } else if (b.type != VAR_DOUBLE) {
    fprintf(stderr, "Can't operate arithmetic: ");
    dump_value(stderr, b);
    fprintf(stderr, "\n");
    return FALSE;
  } else {
    set_double(result, f(a.u.d, b.u.d));
    return TRUE;
  }
}

void dump_value(FILE* ofp, Value v) {
  switch (v.type) {
  case VAR_DOUBLE:  fprintf(ofp, "%.10g", v.u.d); break;
  case VAR_FNCTPTR:  fprintf(ofp, "function"); break;
  default:  fprintf(ofp, "?? Illegal value"); break;
  }
}

#include <map>
#include <string>
using namespace std;

static map<string, Value> GlobalVariableTable;

int refer(Value* result, symrec* sym) {
  map<string, Value>::const_iterator it = GlobalVariableTable.find(sym->name);
  if (it == GlobalVariableTable.end()) {
    fprintf(stderr, "unbound `%s'\n", sym->name);
    return FALSE;
  } else {
    *result = GlobalVariableTable[sym->name];
    return TRUE;
  }
}

void assign(const char* name, Value val) {
  GlobalVariableTable[name] = val;
}

int funcall(Value* result, Value fnct, Value x) {
  if (fnct.type != VAR_FNCTPTR) {
    fprintf(stderr, "Can't call: ");
    dump_value(stderr, fnct);
    fprintf(stderr, "\n");
    return FALSE;
  } else if (x.type != VAR_DOUBLE) {
    fprintf(stderr, "Illegal argument: ");
    dump_value(stderr, x);
    fprintf(stderr, "\n");
    return FALSE;
  } else {
    set_double(result, fnct.u.fnctptr(x.u.d));
    return TRUE;
  }
}


void init_table() {
  struct {
    const char* fname;
    double (*fnct)(double);
  } static const arith_fncts[] = {
    { "sin",   sin,  },
    { "cos",   cos,  },
    { "atan",  atan, },
    { "ln",    log,  },
    { "exp",   exp,  },
    { "sqrt",  sqrt, },
    { 0, 0 }
  };

  int i;
  for (i = 0; arith_fncts[i].fname != NULL; ++i) {
    Value v;
    set_fnctptr(&v, arith_fncts[i].fnct);
    assign(arith_fncts[i].fname, v);
  }
}

int main() {
  init_table();
  yyparse();
  return 0;
}
  • グローバル変数はstd::mapでてきとーに
  • 元からだけど、符号反転の優先順位がおかしい
-abc = 123
    -123

関連記事

新着記事