どもー、しげる塾 一期生のかとうです。
を見て悲しくなった。Javaってひどい。0.1は文字列で渡さないと誤差が出るってさ。泣ける。
C#なら
Console.WriteLine( 1.00M - 9M * .10M );
でOK
「Javaってかわいそうとか、ひどい」っていわれたので、BigDecimalで動作する計算式言語を作ってみたw
使い方はこんな感じ。計算式を文字列で渡してください。結果はBigDecimalで返ってきます。
System.out.println(new Calculator().eval("1 - (9 * 0.1)"));
結果はもちろん期待通りw
0.1
少しはかわいくなったかなw
jarファイルはこちら。
calculator-1.0.0.jar 
さーて、どうやって実装してるのー？と興味を思った方は続きをw
Calculatorの内側
ここからはパーサの話なんでマニアックですw
Calculator内部でやらせていることは、このようなコードです。数行だけですw
String script = "1 + 2 - 3 * 4 / 5"; CalcParser calcParser = new CalcParser(new StringReader(script)); Expression expression = calcParser.expression(); EvaluateContext evaluateContext = new EvaluateContext(10, RoundingMode.HALF_UP); BigDecimal result = Evaluator.eval(evaluateContext, expression);
CalcParserが構文解析のキモになります。
Expression expression = calcParser.expression();
Expressionというのが抽象構文木(AST)といって構文を表すモデルのツリーとなっています。
AST = new Subtract(new Add(new Value("1"), new Value("2")), new Divide(new Multiply(new Value("3"), new Value("4")), new Value("5")))
1 + 2 - 3 * 4 / 5 = 0.6000000000それをEvaluatorで解析して計算を行い計算結果を返すのがCalculatorのお仕事になります。
BNF
さて、キモとなるCalcParserですが、スクラッチでコードを書いて実装を書いてもよいのですが、面倒なんでJavaCCというパーサのコードを自動生成するツールを使います。
それにはまずJavaCCに当該言語がどのような構文を取りうるか設定しなければなりません。そこでBNFの登場です。といいながら、煙に巻くw
この計算式言語のBNF*1は以下。括弧が使える普通の四則演算が記述できます。
Expression ::= AddExpr$e ; e
AddExpr ::= MultExpr$a AddRest(a)$r ; r
AddRest(a) ::= '+' MultExpr$b {next = new Add(a,b);} AddRest(next)$r ; r
| '-' MultExpr$b {next = new Subtract(a,b);} AddRest(next)$r ; r
| empty ; a
MultExpr ::= UnaryExpr$a MultRest(a)$r ; r
MultRest(a) ::= '*' UnaryExpr$b {next = new Multiply(a,b);} MultRest(next)$r ; r
| '/' UnaryExpr$b {next = new Divide(a,b);} MultRest(next)$r ; r
| empty ; a
UnaryExpr ::= '+' UnaryExpr$e ; new Plus(e)
| '-' UnaryExpr$e ; new Minus(e)
| PrimaryExpr$e ; e
PrimaryExpr ::= '(' Expression$e ')' ; new Parenthesized(e)
| Value$v ; v
Value ::= NUMBER$t ; new Value(t.image)ちなみに、NUMBERは、(["0" - "9"])+(["."] (["0" - "9"])+)?とします。
- =より左が非終端記号で、反対に右側に登場するNUMBERや''で囲まれている記号が終端記号っていいます。非終端記号は、終端記号を導出する関数のようなものと覚えていればいいと思います。
Value ::= NUMBER$t ; new Value(t.image)
NUMBER$tとは t = NUMBERと同じ意味で、NUMBERのトークンを表します。;より右側に記述しているのはValueを処理した時に実行されるアクションを指します。{}で記述したところもアクションを表します。t.imageはトークンが表す具体的な文字列です。
四則演算も簡単なようで奥が深いですw
左再帰除去とかやってますが、、、難しすぎw
http://ja.wikipedia.org/wiki/%E5%B7%A6%E5%86%8D%E5%B8%B0
詳しくは しげる塾塾長であーる しげるんば にきいてくらはいw
JavaCC
JavaCCに以下のようなファイルを食わせると、CalcParserの実装を生成します。
/**
* JavaCC file
*/
options {
STATIC=false;
JDK_VERSION = "1.6";
}
PARSER_BEGIN(CalcParser)
package jp.tricreo.calc.parser;
import jp.tricreo.calc.model.*;
public class CalcParser {
}
PARSER_END(CalcParser)
SKIP :
{
" "
| "\r"
| "\t"
| "\n"
}
TOKEN : /* OPERATORS */
{
< PLUS: "+" >
| < MINUS: "-" >
| < MULTIPLY: "*" >
| < DIVIDE: "/" >
}
TOKEN :
{
< NUMBER: ( <DIGIT> )+(["."] (<DIGIT>)+ )? >
| < #DIGIT: ["0" - "9"] >
}
private Expression multExpr():
{
Expression a, r;
}
{
a = unaryExpr() r = multiRest(a)
{ return r; }
}
private Expression multiRest(Expression a):
{
Expression b, r, next;
}
{
<MULTIPLY> b = unaryExpr() {next = new Multiply(a,b);} r = multiRest(next)
{ return r; }
| <DIVIDE> b = unaryExpr() {next = new Divide(a,b);} r = multiRest(next)
{ return r; }
|
{ return a; }
}
private Expression unaryExpr():
{
Expression e;
}
{
<PLUS> e = unaryExpr()
{ return new Plus(e); }
| <MINUS> e = unaryExpr()
{ return new Minus(e); }
| e = primaryExpr()
{ return e; }
}
private Value value():
{
Token t;
}
{
t = <NUMBER>
{ return new Value(t.image); }
}
private Expression primaryExpr():
{
Value v;
Expression e;
}
{
"(" e = expression() ")"
{ return new Parenthesized(e); }
| v = value()
{ return v; }
}
private Expression addRest(Expression a):
{
Expression b,r,next;
}
{
<PLUS> b = multExpr() {next = new Add(a, b);} r = addRest(next)
{ return r; }
| <MINUS> b = multExpr() {next = new Subtract(a, b);} r = addRest(next)
{ return r; }
|
{ return a; }
}
private Expression addExpr():
{
Expression a,r;
}
{
a = multExpr() r = addRest(a)
{ return r; }
}
Expression expression():
{
Expression e;
}
{
e = addExpr()
{ return e; }
}BNFとJavaコードが混在しているのでかなりヘンタイな感じですがw なんとか読めますよね？
戻り値は演算のためのモデルクラスを返しています。
長くなったので、残りは次のエントリでw
