ElmのParserライブラリで論理演算(3)

前回のを公開したら、親切な友人がよりよい（かつ一般的な）実装方法を教えてくれた。 そなたに感謝を。 調べたところ再帰下降構文解析というものらしい。

BNFで書くと多分こんな感じになる。

<additiveExpr> ::= <multiplicativeExpr> [ '||' <additiveExpr> ]*  ## 式の本体
<multiplicativeExpr> ::= <factor> [ '&&' <multiplicativeExpr> ]*
<factor> ::= '(' <additiveExpr> ')' | <base>
<base> ::= 'T' | 'F' | '!'<factor>

日本語で書くとこうかしら。

additiveExpr

multiplicativeExprか、それとadditiveExprの和

multiplicativeExpr

factorか、それとmultiplicativeExprの積

factor

括弧でくくられたadditiveExprかbase

base

TかFかfactorの否定

公開していたデモページの方もこちらの実装に直したので、githubから直にソースコードを埋め込む¹。

パーサー本体はadditiveExprだが、前後に空白を許容するのと、式のあとに不適切な文字列が入った時に（”T hoge”とか）failするように.| endで文字列の終了を要求するためにexprでラップしている。 関数の定義が相互参照しまくりなので最初は戸惑ったが、Parser.lazyで遅延評価にしてやるとコンパイルが通る²。 あとついでに否定を”not”から”!“に直した。

この実装でよいなと思ったのは、演算の優先度が規定されるという点だ。 括弧で順番を明示しない限り、かならず和より積が、積より否定が優先される。

これで論理和と括弧表記にもきれいに対応できた。うれぴよ。