I'm just learning the Scala parser combinator library. I've experimented a working parser that parses some arithmetic expressions with an abstract syntax tree. So when I call
phrase(expr)(tokens)
and my parser parses all the input then gives me an evaluation. But how can I have a step by step evaluation?
Say
3 + 4 * 7
it prints
3 + 28
then
31
in separate lines.
I've scan through the apis but the docs there are not very helpful ... Thanks for help.
Here's a really simple implementation of what you are trying to do:
First, we define an expression hierarchy. You will need to tailor this to your specific problem.
trait Expr {
def eval: Int
}
case class IntLeaf(n: Int) extends Expr {
def eval = n
override def toString = "%d".format(n)
}
case class Sum(a: Expr, b: Expr) extends Expr {
def eval = a.eval + b.eval
override def toString = "(%s + %s)".format(a, b)
}
Then, a function that combines only the bottom-most branch.
def combineLeaves(e: Expr): Expr = {
e match {
case IntLeaf(n) => IntLeaf(n)
case Sum(IntLeaf(a), IntLeaf(b)) => IntLeaf(a + b)
case Sum(a, b) => Sum(combineLeaves(a), combineLeaves(b))
}
}
Then, a function that combines the tree one level at a time, printing as it goes.
def printEval(e: Expr) {
println(e)
e match {
case IntLeaf(n) =>
case _ => printEval(combineLeaves(e))
}
}
Now, the Parser. Again, you'll have to tailor this to your data.
object ArithmeticParser extends RegexParsers {
private def int: Parser[IntLeaf] = regex(new Regex("""\d+""")).map(s => IntLeaf(s.toInt))
private def sum: Parser[Sum] = ("(" ~> expr ~ "+" ~ expr <~ ")").map { case (a ~ _ ~ b) => Sum(a, b) }
private def expr = int | sum
def parse(str: String): ParseResult[Expr] = parseAll(expr, str)
def apply(str: String): Expr = ArithmeticParser.parse(str) match {
case ArithmeticParser.Success(result: Expr, _) => result
case _ => sys.error("Could not parse the input string: " + str)
}
}
And here's how you use it:
scala> printEval(ArithmeticParser("((1 + 7) + ((3 + 9) + 5))"))
((1 + 7) + ((3 + 9) + 5))
(8 + (12 + 5))
(8 + 17)
25