2010年7月24日土曜日

lex/yacc 超基礎 電卓でも作ってみる

電卓を作るとlexとyaccの使い方がだいたい分かる。


こんな計算ができれば十分か。
2*5.2+0.3-(2+3)



◆ レキシカルアナライザのコンフィグ(calc.l)
/* Cコードの記載 */
%{
#include <stdio.h>
#include "y.tab.h"


/* yywrap関数の定義がないとlexのライブラリのリンクが必要になり、
  環境によってコンパイルが面倒なことになることがあるらしい。 */

int
yywrap(void)
{
    return 1;
}
%}


/* 規則部 */
/* 入力された文字列が正規表現にマッチした場合、

   その後ろのCのコードが実行される。 */
%%
"+"             return ADD;
"-"             return SUB;
"*"             return MUL;
"/"             return DIV;
"("             return LP;
")"             return RP;
"\n"            return CR;

([1-9][0-9]*)|0|([0-9]+\.[0-9]*) {
    double temp;
    sscanf(yytext, "%lf", &temp);
    yylval.double_value = temp;
    return DOUBLE_LITERAL;
}
[ \t] ;
. {
    fprintf(stderr, "lexical error.\n");
    exit(1);
}
%%
数字列を即時処理するならば、yytextをそのまま返すことも可能である。
しかし、もう一度字句解析に戻ると破壊的な利用をされるため、 "temp"に格納する。



◆ パーサ側のコンフィグ(calc.y)
// Cコードの記載 
%{
#include <stdio.h>
#include <stdlib.h>
#define YYDEBUG 1
%}


// トークンと非終端子の型宣言
%union {
    int          int_value;
    double       double_value;
}


// トークンの宣言
/* DOUBLE_LITERAL に関してはトークンの種類が分かるだけではなく、
  値を持つので、その型(%unionのメンバ)も指定する。 */

%token <double_value>      DOUBLE_LITERAL
%token ADD SUB MUL DIV CR LP RP


// 非終端子の型宣言
/* 規則部で利用される"$$"、"$1"、"$2"などの変数に代わる
非終端子の
   型宣言は必須。 */
%type <double_value> expression term primary_expression


// 構文規則と、アクションを記述した規則部
%%
line_list
    : line
    | line_list line
    ;
line
    : expression CR
    {
        printf(">>%lf\n", $1);
    }
    | error CR
    {
        yyclearin;
        yyerrok;
    }
    ;
expression
    : term
    | expression ADD term
    {
        $$ = $1 + $3;
    }
    | expression SUB term
    {
        $$ = $1 - $3;
    }
    ;
term
    : primary_expression
    | term MUL primary_expression
    {
        $$ = $1 * $3;
    }
    | term DIV primary_expression
    {
        $$ = $1 / $3;
    }
    ;
primary_expression
    : DOUBLE_LITERAL
    | LP expression RP
    {
        $$ = $2;
    }
    | SUB primary_expression
    {
        $$ = -$2;
    }
    ;
%%


int
yyerror(char const *str)
{
    extern char *yytext;
    fprintf(stderr, "parser error near %s\n", yytext);
    return 0;
}


int main(void)
{
    extern int yyparse(void);
    extern FILE *yyin;


    yyin = stdin;
    if (yyparse()) {
        fprintf(stderr, "Error ! Error ! Error !\n");
        exit(1);
    }
}



◆ コンパイルとリンク
% yacc -dv calc.y 
% lex calc.l
% gcc -o calc y.tab.c lex.yy.c


もしくは・・・
% bison --yacc -dv calc.y 
% flex calc.l
% gcc -o calc y.tab.c lex.yy.c


コンフリクトが出た場合、bisonが出すy.outputの方が原因調査しやすい。



◆ 使ってみる
% ./calc 
2*5.2+0.3+(2+3)
15.7



こちらを参考にさせていただきました。