bison & flexメモ その６
C言語でbisonとflexを使う方法のメモ
式の構文木を作ってみる。
mainからyyparse()を呼んで入力した式の構文木を作成してそのポインタを返す。そのポインタからeval_tree()で式を評価、free_tree()で構文木の為に確保したメモリの解放を行う。構文木はNode型の構造体を定義して、それを積み重ねていくことで作成している。
よくわからないのが、構文木のトップのポインタをmain側へ渡す方法。yyparse()で渡せないので、とりあえずnode.c内にstaticなポインタを作成してbison側でset_tree()を呼び、main側でget_tree()を呼ぶことで、これを介して渡しているけれども正しい方法なのか不明。
expr.y
%{
#include <stdio.h>
#include "node.h"
/* デバッグ用 */
/*#define YYDEBUG 1*/
/* エラー内容を詳細に報告 */
#define YYERROR_VERBOSE 1
%}
/* ここで宣言した変数は共用体yylvalのメンバとしてアクセス可能 */
%union {
Node *node;
double val;
}
%token NUMBER
%token PLUS MINUS MULT DIV
%token LP RP EOL ERR
%left MINUS PLUS
%left MULT DIV
%left NEG
/* < >の中は%union{ }に書いたメンバ名 */
%type <node> exp
%type <val> NUMBER
/* 以下、%%〜%%間は構文規則 */
%%
line : { set_tree(NULL);}
| exp { set_tree($1); }
;
exp : NUMBER { $$ = node_num_new($1); }
| exp PLUS exp { $$ = node_new(OP_ADD, $1, $3);}
| exp MINUS exp { $$ = node_new(OP_SUB, $1, $3);}
| exp MULT exp { $$ = node_new(OP_MUL, $1, $3);}
| exp DIV exp { $$ = node_new(OP_DIV, $1, $3);}
| MINUS exp %prec NEG { $$ = node_new(OP_NEG, $2, NULL);}
| LP exp RP { $$ = $2; }
;
%%
void yyerror(char *s)
{
printf("%s\n",s);
}
expr.l
%{
#include <stdio.h>
#include "node.h" /* こちらを先にincludeする */
#include "expr.tab.h"
/* 読み込みファイルが複数ある場合に使用、今は1を返す様にしておく */
int yywrap(void){ return 1;}
%}
%%
[0-9]+ { /* ここで読んだ値がbison側の構文規則 NUMBERの$1の値になる */
yylval.val = atof(yytext);
return(NUMBER);
}
[0-9]+\.[0-9]+ { /* ここで読んだ値がbison側の構文規則 NUMBERの$1の値になる */
yylval.val = atof(yytext);
return(NUMBER);
}
"+" return(PLUS);
"-" return(MINUS);
"*" return(MULT);
"/" return(DIV);
"(" return(LP);
")" return(RP);
" " {}
"\n" {}
. { yyerror("Illegal character");
return(ERR);
}
%%
main.c
#include <stdio.h>
#include "node.h"
extern int yyparse(void);
extern FILE *yyin;
extern int yydebug; /* デバッグ用 */
int main(int argc, char ** argv){
Node *p;
int ret;
/* デバッグ用 */
/*yydebug = 1;*/
/* yyinをファイル入力に切り替え */
if((yyin = fopen( argv[1], "r")) == NULL){
fprintf(stderr,"Can't open a input file!\n");
return 1;
}
ret = yyparse(); /* 入力した式の構文解析実施 */
printf("yyparse return : %d\n", ret);
if(ret == 0){
p = get_tree(); /* 構文木の取得 */
if(p == NULL)
printf("tree is NULL\n");
else{
printf("tree value = %g\n", eval_tree(p)); /* 構文木の評価と表示 */
free_tree(p); /* 構文木で使用したメモリの解放 */
}
}
return ret;
}
node.h
#ifndef NODE_H
#define NODE_H
#include <stdlib.h>
typedef enum{ OP_ADD = 1, OP_SUB, OP_MUL, OP_DIV, OP_NEG, OP_NUM
} NodeType;
typedef struct Node_def Node;
struct Node_def{
NodeType type;
double val;
Node *left;
Node *right;
};
void set_tree(Node *);
Node *get_tree(void);
Node *node_alloc(void);
Node *node_new(NodeType, Node *, Node *);
Node *node_num_new(double);
void free_tree(Node *);
double eval_tree(Node *);
#endif /*NODE_H*/
node.c
#include "node.h"
static Node *tree_root; /* mainとbison間の構文木受け渡し用ポインタ */
/* bison(yyparse)で作成した構文木のルートポインタを設定 */
void set_tree(Node *p){
tree_root = p;
}
/* 設定された構文木のルートポインタを取得（mainから呼ばれる） */
Node *get_tree(void){
return tree_root;
}
/* 構文木のノードに必要なメモリを取得 */
Node *node_alloc(void){
Node *p;
p = (Node *)malloc(sizeof(Node));
return p;
}
/* 構文木のノードを新規作成 */
Node *node_new(NodeType t, Node *left, Node *right){
Node *p;
p = node_alloc();
p->type = t;
p->left = left;
p->right = right;
return p;
}
/* 数値用ノードの作成 */
Node *node_num_new(double v){
Node *p;
p = node_alloc();
p->type = OP_NUM;
p->val = v;
p->left = NULL;
p->right = NULL;
return p;
}
/* 構文木のメモリの解放 */
void free_tree(Node *p){
if(p == NULL) return;
Node *left;
Node *right;
left = p->left;
right = p->right;
free(p);
if(left != NULL)
free_tree(left);
if(right != NULL)
free_tree(right);
}
/* 構文木の評価 */
double eval_tree(Node *p){
NodeType t;
double ret;
t = p->type;
switch(t){
case OP_NUM:
ret = p->val;
break;
case OP_ADD:
ret = eval_tree(p->left) + eval_tree(p->right);
break;
case OP_SUB:
ret = eval_tree(p->left) - eval_tree(p->right);
break;
case OP_MUL:
ret = eval_tree(p->left) * eval_tree(p->right);
break;
case OP_DIV:
ret = eval_tree(p->left) / eval_tree(p->right);
break;
case OP_NEG:
ret = eval_tree(p->left) * -1;
break;
}
return ret;
}
Makefile
TARGET = expr BISON_SRC = $(TARGET).y BISON_H = $(TARGET).tab.h BISON_C = $(TARGET).tab.c BISON_O = $(TARGET).tab.o BISON_OUT = $(BISON_C) $(BISON_H) $(TARGET).output FLEX_SRC = $(TARGET).l FLEX_C = lex.yy.c FLEX_O = lex.yy.o C_FILES = $(BISON_C) $(FLEX_C) node.c main.c OBJ = $(FLEX_O) $(BISON_O) node.o main.o all : $(TARGET) $(TARGET) : $(OBJ) gcc -o $@ $(OBJ) $(FLEX_C) : $(FLEX_SRC) $(BISON_H) flex $(FLEX_SRC) $(BISON_OUT) : $(BISON_SRC) bison -dv $(BISON_SRC) .c.o : gcc -c $< clean : rm -f *.exe rm -f lex.yy.c expr.tab.c rm -f lex.yy.h expr.tab.c rm -f *.output rm -f *.o lex.yy.o: lex.yy.c expr.tab.h expr.tab.o: expr.tab.c expr.tab.h node.h node.o: node.c node.h main.o: main.c node.h
sample.txt
(1+2+3 + 4+5+6+7+8+9+10) *3.14 *-1 /2
実行結果
~$ ./expr.exe sample.txt yyparse return : 0 tree value = -86.35
