mpcを使ってみた - Nosの日記

mpc*1はcommon lisp用のパーサコンビネータライブラリ。
Common Lisp で Lispインタプリタを作ってみた – さくらんぼの技術備忘録などを見て気になったので使ってみた。

使用例

以下はマニュアルにあるメールアドレス < user >@< host > をパースする例。
まずパッケージを定義。

(defpackage simple-address
  (:use :cl :mpc :mpc.characters))

(in-package :simple-address)

で、userやhostの部分に入っていい文字を定義する。

(defun =address-character ()
  (=or (=satisfies #'alphanumericp)
       (=one-of '(#\- #\_ #\. #\+))))
;; アルファベット、数字、-、_、.、+ が許される

これを使って求めるパーサーを実装する。

(defun =simple-address ()
  (=let* ((user (=string-of (=address-character)))
          (_ (=character #\@))
          (host (=string-of (=address-character))))
    (=result (list user host))))
;; =let* 中の _ は文字@を無視するという意味。結果を =result を使って返す。

あとは run 関数で走らせる事が出来る:

(run (=simple-address) "foo@example.com")
 ⇒ ("foo" "example.com")

(run (=simple-address) "!!!@@@.com")
 ⇒ NIL

このlisp的シンタックスにするための =let* マクロがいいね。

ごく簡単な電卓

練習として整数だけ(分数も結果的に扱えるのだが)対応のごく簡単な4則演算+括弧の電卓を作ってみた。
simple-math-parser.lisp

(defpackage simple-math
  (:use :cl :mpc :mpc.characters :mpc.numerals))

(in-package :simple-math)

(defun =add-op ()
  (=let* ((op (=one-of '(#\+ #\-))))
    (=result (case op (#\+ '+) (#\- '-)))))

(defun =mul-op ()
  (=let* ((op (=one-of '(#\* #\/))))
    (=result (case op (#\* '*) (#\/ '/)))))

(defun =primary ()
  (=or
   (=let* ((_ (=character #\())
	   (p (=add-expr))
	   (_ (=character #\))))
     (=result p))
   (=integer-number)))

(defun =mul-expr ()
  (=let* ((result (=primary))
	  (rights (=zero-or-more (=list (=skip-whitespace (=mul-op))
					(=skip-whitespace (=primary))))))
    (=result (loop for r in rights
		do (setf result (list (car r) result (cadr r)))
		finally (return result)))))

(defun =add-expr ()
  (=let* ((result (=mul-expr))
	  (rights (=zero-or-more (=list (=skip-whitespace (=add-op))
					(=skip-whitespace (=mul-expr))))))
    (=result (loop for r in rights
		do (setf result (list (car r) result (cadr r)))
		finally (return result)))))
  
(defun =simple-math ()
  (=prog1 (=add-expr)
	  (=end-of-input)))

;; (run (=simple-math) "1+2-3*4/4")

(defun main ()
  (loop (princ "> ") (princ (eval (run (=simple-math) (read-line)))) (fresh-line)))

(main)

こんな感じ↓

$ clisp
(略)
[1]> (ql:quickload :mpc)
To load "mpc":
  Load 1 ASDF system:
    mpc
; Loading "mpc"

(:MPC)
[2]> (load "simple-math-parser.lisp")
;; Loading file /User/nos/simple-math-parser.lisp ...
> 2*(3+4)
14
> 1+2/3
5/3

使ってみて

ちょっとはまったのは、=ifや=and、=prog2などがマクロでなく関数なので、引数が全て評価されてしまうという事。これが原因で再帰的なパーサーを書こうとすると意図しないスタックオーバーフローが発生する。例えば上の電卓で =primary を

(defun =primary ()
  (=if (=character #\()
       (=prog2 (=character #\()
	       (=add-expr)
	       (=character #\)))
       (=integer-number)))

と書くとrunした際にスタックオーバーフローする。この=ifの条件部分が成功しようがしまいが"(=add-expr)"が評価されてしまうので、関数の間で呼び出し関係が循環しているとスタックがあふれるまで停止しないわけだ。 =let* がショートサーキットに振る舞うマクロなのでこっちを使えば回避出来るのだけど…。これマクロに置き換えて不都合あるかなあ。ちょっと暇なときに調べてみたい。

しかしその欠点を差し引いてもよくできたライブラリと思う。使っていてあとソースを見てみると思いのほか短くて驚く。