Haskell, Fay で数式パーサを作った
題名通り数式パーサを作って見ました。
これです。
ExpressionParser
masaponto/ExpressionParser · GitHub
Fayとは
fayはHaskellのサブセットです。
Haskellっぽいコードをjavascriptに変換してくれます。
公式
Home · faylang/fay Wiki · GitHub
また、以下のページで紹介されています。
さらば愛しき JavaScript —— 愛と欲望の果てに Haskell は 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 は空白をパースします。
- 四則演算、カッコ、冪乗、階乗をパースできます。
- いろいろ怪しい。
作った感想(?)
参考書籍
- 作者: Graham Hutton,山本和彦
- 出版社/メーカー: オーム社
- 発売日: 2009/11/11
- メディア: 単行本(ソフトカバー)
- 購入: 14人 クリック: 503回
- この商品を含むブログ (117件) を見る
- 作者: Miran Lipovača,田中英行,村主崇行
- 出版社/メーカー: オーム社
- 発売日: 2012/05/23
- メディア: 単行本(ソフトカバー)
- 購入: 25人 クリック: 580回
- この商品を含むブログ (67件) を見る
追記
ガンマ関数の実装はこちらを参考にしました。
【GO FOR IT】実数の階乗 (i)(ii)(iii) - MIND_THE_GAP