Lispで演算子順位構文解析
夏休みが終わってしまいました。
そして同時に前期の成績が発表されました。
春先に「単位が足りなくい」という恐ろしくリアルな夢を見ましたが、
どうやら無事に4年生に進むことは出来そうです(4年で卒業出来るかはまだ分かりません(笑))。
という訳で(?)Lispで演算子順位構文解析を行うプログラムを書きました。
工夫した点はマクロを使って予め優先順位のテーブルをコードに展開したこと。
キャッシュのことを考えたら展開した方が遅いかもしれませんが、それは気にしない方針で。
あと、手を抜いた点はストリームからの読み込みはread関数を使ったこと。
演算子に大して何もしないリーダマクロ関数を設定して楽をしてます。
「マイナス」と「引く」を区別できない気もするけど、それも気にしない方針で。
(def-op-parser test-parser (input stack acc) () (((#\+ 1 :left) (let ((x (pop acc)) (y (pop acc))) (push `(+ ,y ,x) acc))) ((#\* 2 :left) (let ((x (pop acc)) (y (pop acc))) (push `(* ,y ,x) acc)))) ((( #\( #\) ) )))
まず、def-op-parserというマクロを使ってパーサ関数を定義。
第1引数は作成する関数の名前、第2引数は後で使う変数の名前。
第3引数はリテラルに対する操作(今回はなし)。
第4引数は演算子とその優先順位、結合性、還元時の操作。
第5引数は括弧とその還元時の操作(今回はなし)。
そんで、これを使ってみたらこんな感じです。
OP-PARSER> (with-input-from-string (s "(1+2*3+4)*5+6*7") (test-parser s)) (+ (* (+ (+ 1 (* 2 3)) 4) 5) (* 6 7))
なんか上手くいってるっぽい。やったね。
▲完成したときの心境
で、うかべんまで残り1ヵ月程となってしまいましたが、ネタの方が全然出来てません。
そろそろペースを上げてものを作っていかないと…
この構文解析も里々のパースの為に作ったものです。
それにしても、里々って、Lispの様に括弧を使って関数呼び出し等を行う言語なのに、
算術式において優先順位の為に括弧を使うってどうなんだろう…
半角と全角で区別って言うのは流石にかっこ悪い気がする…