2008/03/23

「S式はアトムまたはドットペア」を真に受けてyaccでパースする話

「おまいらは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

No comments :