esrap-peg パッケージを実際に使ってみる

(require :esrap-peg) はできたが・・・

さて esrap-peg パッケージを使ってみようとしたが、いきなり「使い方がようわからん」状態に陥る。

esrap-peg パッケージでエクスポートされている関数(or マクロ)は以下

  • basic-parse-peg
  • parse-peg-file
  • ast-eval
  • peg-code
  • peg-compile
  • def-peg-matchers

この他に変数 *esrap-peg-patern-package* がエクスポートされている。

この関数のうち、parse-peg-file と peg-code, peg-compile に関しては esrap-peg についてくる test.lisp などを見ながらしばらく唸っていれば、おおよその使い方はわかってくる。そして、REPL 上で使ってみれば、すぐにその結果から何が出てくるかもおおよそわかるのは流石に Lisp の良いところ。

おおよそすぐに分かったところのこと

  1. PEG の文法定義ファイルを作成する(ex: foo.peg)
  2. (esrap-peg:parse-peg-file "foo.peg")  を評価すると foo.peg で定義した文法に従ったパーサコードが返されます(多重値で戻ってくるので一番上の値)
  3. このパーサコードを peg-compile に食わせてあげます(ex> (esrap-peg:peg-compile (esrap-peg:parse-peg-file "foo.peg")) )
  4. ここまで順調に成功していれば、esrap:parse 関数が組みあがっています

esrap:parse 関数は、esrap-peg パッケージではなくて esrap パッケージの代物で、 esrap パッケージのパーサ構築のための関数を呼んで組み上げるのが本来の esrap でのスタイルなんでしょうけれど、PEG でその部分を代行させてしまうのが esrap-peg と。

そして出来上がった esrap:parse 関数ですが、


> (esrap:parse 'statement "......")

の様な形で使える。”…..” には foo.peg で定義した文法に従ったコードが入る。ここは text であれば良いので、REPL 上で安直に試すには文字列で直に書いて問題なく動く。ファイルに書いておくなら、それを読み込んでここにはめ込んでやれば良い。

でですね、こうすると esrap:parse 関数が何を返すかというと、文法定義に従って与えられたコードを構文解釈した結果のまさしく S 式の形(カッコだらけ)の構文解析木です。

構文解析木は得られたけれど・・・

さてここまでで無事、構文解析木を得られるようにはなったわけですが、これだけだとまさしく文法に従った形式をチェックしただけで、その意味は全然まったく解釈していません。けれど、よっぽど特例を除いて大概の場合は大切なのは意味の方なわけです。

どういうことかというと、文法に従って例えば整数値が記されているとしたら、「ちゃんと整数値の表現形式に適っている」なんてのは本来の目的物ではなくて、「その表現された整数値はナンボなのか?」が大概において一番重要なのです。

すなわち、esrap:parse 関数が出来て、構文解析木を得られるようになっただけでは、「・・・の表現形式に適っている」を確認しかできないので、「その表現されたものはなんなのか?」に答えられるようにせんといかんわけです。

例えば lex/yacc で「整数表記を解釈して整数値を返す」的なことをやるには、(これだけなら yacc はいらなくて)lex で字句解析した際にでも、表記を整数値に変換して、適当に解析結果に貼り付けておくとかしたりするわけです。こうして置けば、構文解析結果を受けて、「ふむ、整数であるか。して値は?」となれば貼っ付いている整数値を持ってきて「カクカクシカジカでっせ」となるわけです。

これと似たことをやれるようにするお助けの仕組みも esrap-peg にはちゃんとありました。あるんですけど、もうほとんど undocument でアングラな世界に入っている感じです。「ソース読め」って感じでした。

そもそも、最初はそのような手立てが準備されているかさえ分からない状態で、仕方がないのでグーグル先生にお伺いを立ててみまして、esrap-peg  の利用例を探してみました。これがまた無くて難儀したのですが、Quicklisp のところにあるパッケージの中で query-fs という SQL 文への橋渡し的パッケージがあり、それが esrap-peg を利用していたので、まずはそれを読んでみました。

その結果、各文法要素に対して意味解釈したいところで、その文法要素(シンボルがそれぞれ割り振られる)に対して意味を与える関数を貼り付けます。実際には、割り当てのシンボルのプロパティーに peg-handler という項目で関数本体を貼り付けてます。このためのマクロが esrap-peg:def-peg-fun です。esrap-peg:def-peg-matchers というマクロもあるのですが、これはどうせほとんどの文法要素に対して def-peg-fun するので、それを一気にやってしまえというマクロです。このマクロはちょっとやりすぎの気があって、パッケージ全容を分かりづらくしているきらいも若干感じられました。

そしてその貼り付けられた関数を容易に呼べるようにしたのが、esrap-peg:ast-eval 関数です。ast-eval は貼り付けられた関数を呼ぶ際に、引数として構文解析木の割り当てのシンボルから先の部分を渡してくれます(って言われても良く分からないと思いますので、あとでサンプル示します)。

def-peg-fun で所望の要素に対して意味解釈(まあ実際なんでもできるので意味を解釈以上にいろいろできますが)する関数を貼り付けて、それを ast-eval で評価する形です。貼り付ける関数を上手いこと絡繰っておけば、得られた構文解析木の根っこに対して ast-eval を掛けてやれば、全体の意味解釈をさせることができる。

と書くと、どうせシンボルが張り付いているなら、関数としてそれを定義してしまえば普通の eval でも動くのでは?とも思えるところですが、実際に eval って問題ない式を吐くような文法定義がやたらめったら大変になるので、これは諦めた方が良さそうです。

というような感じでおおよそわかったのですが、やっぱりドキュメントがなかったので、使用例だけでは良く分からず、結局 esrap-peg のソースの該当部分も読み、REPL でその辺りをいじくり倒して理解した感じ。

ソース読めとはいえ、まだしも esrap-peg:parse-peg-file や esrap-peg:peg-compile (中で調整して esrap-peg:peg-code を上手いこと呼んでいるので読むとしたら、その実体は esrap-peg:peg-code)を読んで理解するのに比べれば楽そうなので、良かったのですけれど、正月休み挟んだため案外時間が掛かってしまいました。

使用例

peg ファイルの例:


statement <- spaces expression spaces

expression <- (expression spaces add spaces multiplicative_expression)
    / (expression spaces sub spaces multiplicative_expression)
    / multiplicative_expression

multiplicative_expression <-
    (multiplicative_expression spaces mult spaces primary_expression)
    / (multiplicative_expression spaces div spaces primary_expression)
    / (multiplicative_expression spaces mod spaces primary_expression)
    / primary_expression

primary_expression <- constant
    / ('(' spaces expression spaces ')')

constant <- integer_constant

integer_constant <- decimal_integer_constant

decimal_integer_constant <- sign_part? digit+

sign_part <- '+' / '-'

## Lex!

alphabet <- [a-zA-Z]
digit <- [0-9]

# operator

add <- '+'
sub <- '-'
mult <- '*'
div <- '/'
mod <- '%'

#

spaces <- [ \t]*
eol <- '\r\n' / '\n' / '\r' / eof
eof <- !.

以上、文法定義終了。これを適当なファイルにでっち上げておく。例えば、foo.peg。

次は Lisp のコード(読みづらさ優先, 中身精査してません・・・esrap-peg の関数は import するなりして・・・:


(require :esrap-peg) ;; or (asdf:load-system "esrap-peg") etx...
#| まあ適当にインポートするなりユーズパッケージするなりして
   いちいち esrap-peg 名前空間を表記しないですむようにした方が
   楽です。その前提で下は書いてあるので、そうしないなら下で使われている
   全ての esrap-peg の関数と esrap:parse はそれぞれパッケージ名付きで
   書き直しが必要です。 |#

(peg-compile   (parse-peg-file   "foo.peg"))

(defun val_digits (x &optional (y 0))  ;; 頭の沸いた関数でゴメン
  (cond ((not x) y)
        ('t (val_digits (cdr x) (+ (* 10 y) (parse-integer (cadr (car x))))))))

(def-peg-fun identifier (x)) (def-peg-fun defined_identifier (x))

(def-peg-fun statement (x)   (ast-eval (second x)))

(def-peg-fun expression (x)
  (cond ((atom (car x)) (ast-eval x)) ; x == MULTIPLICATIVE_EXPRESSION
        ((eq 'add (car (third x))) (+ (ast-eval (car x)) (ast-eval (fifth x))))
        ((eq 'sub (car (third x))) (- (ast-eval (car x)) (ast-eval (fifth x))))
        ('t (break))))

(def-peg-fun multiplicative_expression (x)
  (cond ((atom (car x)) (ast-eval x)) ; x == PRIMARY_EXPRESSION
        ((eq 'mult (car (third x))) (* (ast-eval (car x)) (ast-eval (fifth x))))
        ((eq 'div (car (third x))) (/ (ast-eval (car x)) (ast-eval (fifth x))))
        ((eq 'mod (car (third x))) (mod (ast-eval (car x)) (ast-eval (fifth x))))
        ('t (progn (format 't "MULTIPLICATIVE EXPRESSION ERROR: ~A" (third x))))))

(def-peg-fun primary_expression (x)
  (cond ((eq 'constant (car x)) (ast-eval x))
        ((eq 'defined_identifier (car x)) (ast-eval x))
        ('t (ast-eval (third x))))) ; open-r-brachet spaces EXPRESSION spaces close-r-bracket

(def-peg-fun constant (x)   (ast-eval x))

(def-peg-fun integer_constant (x)   (ast-eval x))

(def-peg-fun decimal_integer_constant (x)
  (cond ((not (car x)) (val_digits (car (cdr x))))
        ((equal (car (cdr (car x))) "-") (- (val_digits (car (cdr x)))))
        ('t (val_digits (car (cdr x))))))

こんな感じ。上にも書いたけれど、esrap-peg の関数も esrap-peg:def-peg-fun のような形式で書けば、(require :esrap-peg) してあるだけでも動きます。ところどころ残念な感じの残骸が・・・気にしない・・・

これをエヴァって、

(esrap:parse 'statement "1 + 24 / (1 + 3) ")

とか評価して得た解析木に esrap-peg:ast-eval すれば 7 とか返事が来るんじゃないかな。

PEG 定義が若干冗長なのは、先々の実験で identitier なんぞ使って変数など使えるようにしてみるときの拡張の準備のためです。悪しからず。

ここでのコードのライセンスについて

上記、PEG ならびに Common Lisp のコードはこのサイトで提示しているコードの基本 License に掲げるものに従う。

カテゴリー: ソフトウェア, プログラミング, 開発設計 タグ: パーマリンク

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください