S式PEGパーサ:プロトタイプ完成

一応簡単な例は動くことが確認できた。まだまだバグがいっぱいあるだろうけど、動くと嬉しいね！

gosh> (parse-string-with
       ((add <- < mult lval > #\+ < add rval > :return `(+ ,lval ,rval)
	     / < mult val > :return val)
	(mult <- < prim lval > #\* < mult rval > :return `(* ,lval ,rval)
	      / < prim val > :return val)
	(prim <- #\( < add val > #\) :return val / < decim val > :return val)
	(decim <- < digit nch > :return (- (char->integer nch) (char->integer #\0)))
	(digit <- #[0-9]))
       "(1*2+3)*4*(5+(6+7)*8)")
(* (+ (* 1 2) 3) (* 4 (+ 5 (* (+ 6 7) 8))))

動作としては次のような文法定義

((add <- < mult lval > #\+ < add rval > :return `(+ ,lval ,rval)
      / < mult val > :return val)
 (mult <- < prim lval > #\* < mult rval > :return `(* ,lval ,rval)
       / < prim val > :return val)
 (prim <- #\( < add val > #\) :return val / < decim val > :return val)
 (decim <- < digit nch > :return (- (char->integer nch) (char->integer #\0)))
 (digit <- #[0-9]))

から、抽象構文木

'((:definition (:identifier add)
  (:expression
   (:sequence ((:identifier-clause (:identifier mult) :capture lval)
	       (:char #\+)
	       (:identifier-clause (:identifier add) :capture rval))
	      :callback `(+ ,lval ,rval))
   (:sequence ((:identifier-clause (:identifier mult) :capture val))
	      :callback val)))
 (:definition (:identifier mult)
  (:expression
   (:sequence ((:identifier-clause (:identifier prim) :capture lval)
	       (:char #\*)
	       (:identifier-clause (:identifier mult) :capture rval))
	      :callback `(* ,lval ,rval))
   (:sequence ((:identifier-clause (:identifier prim) :capture val))
	      :callback val)))
 (:definition (:identifier prim)
  (:expression
   (:sequence ((:char #\()
	       (:identifier-clause (:identifier add) :capture val)
	       (:char #\)))
	      :callback val)
   (:sequence ((:identifier-clause (:identifier decim) :capture val))
	      :callback val)))
 (:definition (:identifier decim)
  (:sequence ((:identifier-clause (:identifier digit) :capture nch))
	     :callback (- (char->integer nch) (char->integer #\0))))
 (:definition (:identifier digit)
  (:sequence ((:char-set #[0-9]))
	     :callback ())))

を生成して、ここからPEGライブラリを使うコードに変換してやる。

(let ()
  (define add ($or ($do (lval mult) (G7996 ($char #\+)) (rval add)
			($return `(+ ,lval ,rval)))
		   ($do (val mult) ($return val))))
  (define mult ($or ($do (lval prim) (G8000 ($char #\*)) (rval mult)
			 ($return `(* ,lval ,rval)))
		    ($do (val prim) ($return val))))
  (define prim ($or ($do (G8003 ($char #\()) (val add) (G8005 ($char #\)))
			 ($return val))
		    ($do (val decim) ($return val))))
  (define decim ($do (nch digit)
		     ($return (- (char->integer nch) (char->integer #\0)))))
  (define digit ($one-of #[0-9]))
  (parse-string add "(1*2+3)*4*(5+(6+7)*8)"))

svnにソースコードをaddしたのが8/31で、多分8/30から書き始めたので、おおよそ4日ほどかかったことになる。第一の目標であるプロトタイプ完成には、思いの外早く到達することができた。ここからは一旦ペースを落として、Modern compiler implementation in Cと並行してやっていこうかと思う。

C言語のPEGパーサジェネレータ自作が、休み中の目標。これができれば、来学期の言語処理系実装の演習でパーサを手書きしなくても済むだろうし*1。

*1:パーサジェネレータを書いたのに、勉強のためにパーサを手書きしろとは言われないだろう、さすがに