「おまいらはS式が好きすぐる。」という感想にぐっときたので、S式について考え直してみることにした。具体的にはパーザを書くよ。
S式そのものはとてもシンプル。アトムか、ドットペアか。つまり、
S式 : アトム
| ( S式 . S式 )
;
おなじみの (apple orange pizza) みたいなリストは、実際には null で終わっているドットペアの簡略表記にすぎない。この例であれば、その本当のすがたは (apple . (orange . (pizza . null))) という入れ子になったドットペア。そういえば null って本当は何のことなんだろう？ いつも()って書いてるから、空っぽなリストぐらいにしかみなしてなかったけど、よく考えるとよくわからん。
まあとにかく、この「アトムか、ドットペアか」という単純な構文ルールだけをパーザジェネレータに与えてS式パーザを作りたい。
YACCを使ってやってみよう。試行錯誤のすえ、構文解析の部分はこんな感じにした。
%{
#define YYSTYPE Sexp*
%}
%token ATOM
%token DOT
%token LPAREN
%token RPAREN
%%
list: { prompt(lineno); }
| list '\n'
| list sexp '\n' { prints($2); prompt(lineno); }
;
sexp: ATOM
| LPAREN sexp DOT sexp RPAREN { $$ = mk_oblist($2, $4); }
;ここで Sexp はS式をあらわす構造体で、直感的にAtomとPairの共用体として定義した。
typedef struct Sexp {
short type;
union {
struct Atom *atom;
struct Pair *pair;
} u;
} Sexp;Atomは浮動小数点数か文字列とする。Pairはもちろんcarとcdrで構成される。
typedef struct Atom{
short type;
union {
double num; /* type = 0 */
char *sym; /* type = 1 */
} u;
} Atom;
typedef struct Pair {
struct Sexp *car;
struct Sexp *cdr;
} Pair;そしてこの Pair を作る関数が mk_oblist。
基本的には以上でおしまい。なんだけど、これだけではリスト表記をパーズできないのでつまらない。リスト表記のための構文規則を付け足せばいい話なんだけど、「アトムか、ドットペア」というS式のシンプルさに無駄にこだわることにして、字句解析のほうで対応したった！ もしかしたらちょっとしたプッシュダウンオートマトンの勉強をしたことになったのかもしれないけど、めんどくさいし面白くないので説明は省略。とりあえず自宅のDebian Lenny上ではこんなふうに動くものができた。
$ ./es
es0> (((((42)))))
(((((42.000000 . null) . null) . null) . null) . null)
es1> (the answer is 42)
(the . (answer . (is . (42.000000 . null))))
es2> (() ())
(null . (null . null))
浮動小数点数だと、
42という答えがなんだかうそっぽい。
Expand S-expression にちなんで es という名前にしています。ソースはこちら。
es.tar.gz
