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

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

Bison入門

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

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

%{#define YYSTYPEdouble#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