読者です 読者をやめる 読者になる 読者になる

Masaponto's Blog

お勉強メモ

Haskell, Fay で数式パーサを作った

題名通り数式パーサを作って見ました。
これです。

ExpressionParser
masaponto/ExpressionParser · GitHub

Fayとは

fayはHaskellのサブセットです。
Haskellっぽいコードをjavascriptに変換してくれます。

公式
Home · faylang/fay Wiki · GitHub

また、以下のページで紹介されています。

さらば愛しき JavaScript —— 愛と欲望の果てに Haskell は fay と出逢う。 - これは圏です

Introduction to Fay - 純粋関数空間

パーサ

プログラミングHaskell」という本で数式パーサについて書かれていたので、それを参考に実装しました。

再帰下降構文解析です。
しかし数式のような左結合を含む文法の場合、再帰下降構文解析では一つ問題があります。
単純に左結合させようと

expr ::= expr '+' term | expr '-' term | term

という実装にすると、無限再起になってしまうのです。左再起というそうです。

参考
chainl と左再帰 - あどけない話
左再帰 - Wikipedia
pasberth.com - このページは表示できません。

これを解決するために、

expr ::= term '+' term | term '-' term | term

にして " '+' term " の部分を可能な限り繰り返してパースし、リストにtermの結果の値を保存し、その後でリストの要素の和を求める形にしました。  

例えば、1-2+3*2-4 の場合、まず、1, '-' 2, '+' 6, '-' 4 とパースされます。そして [1,-2,6,-4] というリストを作ります。
で、このリストの要素を左から足し算していく、って感じです。

結局、パーサのBNF(?)はこれ。

expr ::= term '+' term | term '+' term '+' term | .... |  term '-' term | term '-' term '-' term | .... | term
term ::= pow '*' pow | pow '*' pow '*' pow | ... | pow '/' pow | pow '/' pow '/' pow | .... | pow
pow ::= factorialP '^' pow | factorialP
factorialP ::=  factor '!' | factor
factor ::= '(' expr ')' | number
number ::= '-' decimal | decimal
decimal ::= space nat space
nat ::= digit '.' digit | digit
digit ::= 0 | 1 | 2 | 3 | ...
  • space は空白をパースします。
  • 四則演算、カッコ、冪乗、階乗をパースできます。
  • いろいろ怪しい。

作った感想(?)

  • github-pages 便利
  • ブラウザで動くの楽しい
  • fayはサブセットのため制限があって少し大変
  • fayすごい
  • Haskellすごい

参考書籍

プログラミングHaskell

プログラミングHaskell

すごいHaskellたのしく学ぼう!

すごいHaskellたのしく学ぼう!

追記

ガンマ関数の実装はこちらを参考にしました。
【GO FOR IT】実数の階乗 (i)(ii)(iii) - MIND_THE_GAP