Elmの練習とパーサーに親しむのを兼ねて、論理演算のためのパーサーを作ってみた。 パーサーの知識が無であるため無駄な実装をしている可能性が大きいので、親切な方はissuesなどでご指摘いただけると大変ありがたい。
真理値と否定だけの言語を作る
論理和・論理積（と括弧表記）に対応するのが最終目標だが、まずは真・偽の定数表現と否定だけを持つ言語から始めて、そこから言語を拡張していくことにした。 我々の最初の言語は次のようなタームからなる。
type Term =
T
| F
| Not Term説明するまでもないと思うが、TはTrue, FはFalseに対応する。否定はなんらかの論理項を1つだけ受け取るので、NotはTerm型の値を1つ受け取るコンストラクタとして定義している。以下は全てTerm型の値となる。
t = T
u = Not F
v = Not (Not T)文字列をパースしてTermとして評価する
我々の目標は、文字列を入力として受け取って、Termとして解釈することである。 パーサーをスクラッチで組むのが自殺行為なのは私でも知っているので、Elmの作者が作ったParserライブラリのお世話になる。 ライブラリの仕様については、公式ドキュメントやこちらの記事などが十分に詳しくわかりやすいので、ここでは気持ちの説明だけに留める。
import Parser exposing (..)
term: Parser Term
term =
oneOf
[succeed T
|. keyword "T"
, succeed F
|. keyword "F"
, succeed Not
|. keyword "not"
|. spaces
|= lazy (\_ -> term)
]
spaces : Parser ()
spaces =
ignore zeroOrMore (\char -> char == ' ')メインのパーサーtermは、大枠で言えばoneOfという関数にパーサーのリストを渡したものである。
上で定義したデータ型Termは、T, F, Not Termの3つのいずれかに当てはまるので、それらのうちのどれかとして評価できればよい。
oneOfはパースしたい文字列に対し、パーサーリストの先頭からパースを試みる。
パースに成功したらそこで値を返し、失敗したらリストの次のパーサーを試していく作りになっている。
真理値をパースするのは簡単で、このパーサーでは文字列”T”, “F”がそれぞれT, Fとして解釈される。
例えば対象文字列が”F”の場合、Tとしてのパースは失敗するが次のFでは成功しそのままFを返す。
“not”で始まる文字列は否定だと解釈したい。
その際、notとそれに続く論理項の間のスペースの扱いを決めたい。
多くのプログラミング言語では、複数個続くスペースは無視されることが多い。
なんでもよいが、”x=1”と”x = 1”と”x = 1”とはパースされれば違いはない。
それを踏襲するかたちで今回は「スペース無しでも何個あっても可」ということにする1。
そのためのパーサーとしてtermの後にspacesという関数を定義している。
spacesは「ゼロ個以上のスペースにマッチする」パーサーで、マッチした文字列を全て無視する。
NotはTerm型を受け取るコンストラクタだったので、ゼロ個以上のスペースの後ろにはTermとしてパース可能な文字列が来ることが期待される。
Termをパースするためにはどうすればいいか？
もちろん今作ってるtermパーサーを使えばいいのです。
|= lazy (\_ -> term)の部分で残りの文字列をTermとしてパースしてくれる2。
さて、これまで|.と|=というなにやら怪しい演算子を無視していたが、ざっくり言えば前者が値を無視し、後者が値を受け取る演算子だ。
TとFは文字列が”T”や”F”であることがわかりさえすればよいので、|.で無視。
一方否定は論理項を1つ受け取るので、”not”の後に続く文字列をTermとして解釈したものを渡してあげる必要があり、そのとき使うのが|=。
ひとまずこれで真理値、否定を持つ言語をパースすることが出来るようになった。 次回は論理積を追加しようとしたら躓いた話。 ここでえらい苦労したのでブログに残してやろうと思い立ったという裏話もある。