自分で処理系を作るなんてことは考えたことが無かったのですが、先日のエントリに頂いたコメントで、seagullさんに、「Lisp処理系は、技術者なら一度は作ってみることをおすすめしますよ。」と勧められたので、ちょっと考えて(妄想して)みました。

昔、処理系とか関係なく単純に興味を持ってlex yacc(flex bison)について調べたことがあったんですが、あまりの難しさにシッポを巻いたことを思い出しました。ちょっとした処理系なら、別に自分で適当に構文解析すればいいんだろうけど、先人の知恵が詰っているであろう(完全に推測)lex & yaccの世界に触れてみる意味も含めて、字句解析、構文解析の仕組みを調べてみました。

Bison入門

逆ポーランド記法電卓の例を読んでみました。例に出ていた計算機をLisp風にして遊んでみました。

理解してないけど、いじってみたparser.y

%{
#define YYSTYPE double
#include <stdio.h>
#include <ctype.h>
int yylex(void);
int yyerror(const char *s);
int yyparse(void);
%}
%token NUM
%%
input:    /* 空 */
        | input line
;
line:     '\n'
        | exp '\n'  { printf ("\t%.10g\n", $1); }
;
exp:      NUM                     { $$ = $1;         }
        | '(' '+' exp exp ')'     { $$ = $3 + $4;    }
        | '(' '-' exp exp ')'     { $$ = $3 - $4;    }
        | '(' '*' exp exp ')'     { $$ = $3 * $4;    }
        | '(' '/' exp exp ')'     { $$ = $3 / $4;    }
;
%%
main()
{
yyparse();
}
yyerror(const char *s)
{
printf("ERROR: %s\n", s);
}
yylex ()
{
int c;
/* 空白類を読み飛ばす  */
while ((c = getchar ()) == ' ' || c == '\t');
/* 数値を処理する   */
if (c == '.' || isdigit (c)) {
ungetc (c, stdin);
scanf ("%lf", &yylval);
return NUM;
}
/* ファイルの終わりを処理する  */
if (c == EOF)
return 0;
/* 1文字を返す */
return c;
}

コンパイル

$ bison parser.y
$ gcc parser.tab.c

実行

$ ./a.exe
(+ (- 100 1) 1000)
1099
(* 3 3)
9
(/ 10 3)
3.333333333
(+ 1 2 3)
ERROR: syntax error

2項の四則演算だけのLisp完成。

まとめ

yacc(bison)の定義が、関数型言語的すぎなのが驚きだった。やはり、先人の知恵、恐るべし。

↓のところなんて、Haskellっぽい。

exp:      NUM                     { $$ = $1;         }
        | '(' '+' exp exp ')'     { $$ = $3 + $4;    }
        | '(' '-' exp exp ')'     { $$ = $3 - $4;    }
        | '(' '*' exp exp ')'     { $$ = $3 * $4;    }
        | '(' '/' exp exp ')'     { $$ = $3 / $4;    }
;

というお遊びはここまでにして、今度はちゃんとlex & yaccに入門したいと思います。

• Lex and YACC primer/HOWTO http://www.linux.or.jp/JF/JFdocs/Lex-YACC-HOWTO-4.html