「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