Skip to content

Instantly share code, notes, and snippets.

@pocketberserker
Created January 4, 2012 17:48
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save pocketberserker/1561162 to your computer and use it in GitHub Desktop.
Save pocketberserker/1561162 to your computer and use it in GitHub Desktop.
ScalaのパーサコンビネータでΣ演算
package parser;
import util.parsing.combinator.JavaTokenParsers
import java.math.MathContext
case class Sum(init:Expression, max:Expression, expr:Expression) extends Expression
case class Value(digit:BigDecimal) extends Expression
case class Variable() extends Expression
case class Add(left:Expression, right:Expression) extends Expression
case class Sub(left:Expression, right:Expression) extends Expression
case class Plus(expr:Expression) extends Expression
case class Minus(expr:Expression) extends Expression
case class Parenthesized(expr:Expression) extends Expression
case class Multiply(left:Expression, right:Expression) extends Expression
case class Divide(left:Expression, right:Expression) extends Expression
class Calculator extends JavaTokenParsers {
def parseSumExpr(data:String) = parseAll(sumExpr, data)
def parseExpr(data:String) = parseAll(expr, data)
// sumExpr ::= "sum" "i" ":" value ".." value "of" expr
def sumExpr : Parser[Expression] =
"sum"~"i"~":"~value~".."~value~"of"~expr ^^ {
case "sum"~"i"~":"~init~".."~max~"of"~f => {
Sum(init, max, f)
}
}
// expr ::- term { "+" term | "-" term }
def expr : Parser[Expression] = chainl1(term,
"+" ^^ { op => (left, right) => Add(left, right) } |
"-" ^^ { op => (left, right) => Sub(left, right) } )
// term ::= factor { "*" factor | "/" factor }
def term : Parser[Expression] = chainl1(factor,
"*" ^^ { op => (left, right) => Multiply(left, right) } |
"/" ^^ { op => (left, right) => Divide(left, right) } )
// factor ::= unary
def factor : Parser[Expression] = unary
// unary ::= "+" unary | "-" unary | primary
def unary : Parser[Expression] =
("+"|"-")~unary ^^ {
case "+"~u => Plus(u)
case "-"~u => Minus(u)
} | primary
// primary ::= "(" expression ")" | value | variable
def primary : Parser[Expression] =
"("~>expr<~")" ^^ { expr => Parenthesized(expr) } | value | variable
// value ::= "[0-9]+"
def value : Parser[Expression] =
floatingPointNumber ^^ {
value => Value(BigDecimal(value, MathContext.DECIMAL32))
}
// variable ::= "i"
def variable : Parser[Expression] = "i" ^^ { variable => Variable() }
}
package parser;
class Eval extends ExpressionVisitor {
var variable = 0
override def visit(e:Expression) : BigDecimal = e match {
case Value(digit) => digit
case Variable() => BigDecimal(variable)
case Add(l,r) => l.accept(this) + r.accept(this)
case Sub(l,r) => l.accept(this) - r.accept(this)
case Multiply(l,r) => l.accept(this) * r.accept(this)
case Divide(l,r) => l.accept(this) / r.accept(this)
case Minus(e) => - e.accept(this)
case Plus(e) => e.accept(this)
case Parenthesized(e) => e.accept(this)
case Sum(i,m,e) => {
val init = i.accept(this).intValue()
val max = m.accept(this).intValue()
List.range(init, max+1).foldLeft(BigDecimal(0)){ (r,i) => variable = i; r + e.accept(this) }
}
}
}
package parser
trait Expression {
def accept(visitor:ExpressionVisitor):BigDecimal = {
visitor.visit(this)
}
}
package parser;
trait ExpressionVisitor {
def visit(e:Expression):BigDecimal
}
@kmizu
Copy link

kmizu commented Sep 3, 2012

ExpressionVisitorは不要じゃないですかね?単純にevalメソッドにして、evalを再帰的に呼び出せば事足りるような…。

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment