Packrat Parser for S-exp PEG

parsing

S式で定義したPEGから、パーサを作れたらいいなーと思ってパーサジェネレータを製作中。パーサジェネレータの、S式で表現したPEGをパースする部分ができあがってきた。

;;
;; multitive '+' additive / multitive
;; 
(parse '(< multitive lval > #\+ < additive rval > :return (+ lval rval)
         / < multitive val > :return val ))

< Identifier CaptureName > で、Identifierにマッチした部分をCaptureNameに束縛、:returnで返す値を計算する。これは、(Identifier CaptureName)のようにS式で構造化された表現にするか迷ってたんだけど、とりあえず今は簡単のために完全にフラットなシンボル/リテラルの列になるようにしてある。ただ、今のままだと < と > の前後にスペースが必要であまり美しくないので、いずれ変えると思う。その場合、括弧のネストができなさそうな気がする。

上のPEGをパースした構文木は次のようになる。

(:alter
 (:sequence
  ((:identifier multitive :capture lval)
   #\+
   (:identifier additive :capture rval))
  :callback (+ lval rval))
 (:sequence
  ((:identifier multitive :capture val))
  :callback val))

パーサが一通りできた後は、構文木からパーサを生成する処理を書く。とりあえず構文木からRuiさんのPEGライブラリを使ってパーサを生成してみて、それから自前でパーサを生成できるようになるところまでが当面の目標。

S式PEGパーサを書くにあたって、S式PEGをPEG*1で定義したんだけど、その段階で結構混乱した。自分が記述しているのが、どのレベルの文法なのか、つまりメタ言語としてのPEGなのか、S式PEGなのかが頭の中でごっちゃになって大変だった。言語処理系っておもしろい。

*1:対象が文字列じゃないから、厳密には違うっぽい