Arithmetic expression parser in Scala

[Michi]

Hi,

I'm trying to write a simple arithmetic expression parser in Scala.
This simple code

abstract class Expr
case class Number(value: Double) extends Expr
case class UnaryOp(operator: String, arg: Expr) extends Expr
case class BinaryOp(operator: String, left : Expr, right: Expr)
extends Expr

object Calc {
def evaluate(e: Expr): Double = {
e match {
case Number(x) => x
case UnaryOp("-", x) => -(evaluate(x))
case BinaryOp("+", x1, x2) => (evaluate(x1) + evaluate(x2))
case BinaryOp("-", x1, x2) => (evaluate(x1) - evaluate(x2))
case BinaryOp("*", x1, x2) => (evaluate(x1) * evaluate(x2))
case BinaryOp("/", x1, x2) => (evaluate(x1) / evaluate(x2))
}
}

import scala.util.parsing.combinator._

object ExprParser extends JavaTokenParsers {
def expr: Parser[Expr] =
(term <~ "+") ~ expr ^^ { case lhs~rhs => BinaryOp("+", lhs,
rhs) } |
(term <~ "-") ~ expr ^^ { case lhs~rhs => BinaryOp("-", lhs,
rhs) } |
term
def term: Parser[Expr] =
(factor <~ "*") ~ term ^^ { case lhs~rhs => BinaryOp("*", lhs,
rhs) } |
(factor <~ "/") ~ term ^^ { case lhs~rhs => BinaryOp("/", lhs,
rhs) } |
factor
def factor : Parser[Expr] =
"(" ~> expr <~ ")" |
floatingPointNumber ^^ {x => Number(x.toDouble) }

def parse(text : String) = parseAll(expr, text)
}

def parse(text: String) = ExprParser.parse(text).get

def evaluate(text: String): Double = evaluate(parse(text))
}

parses most arithmetic expressions correctly. What it cannot parse
correctly are arithmetic expressions of the form 1-2-3-4. The result
should be -8, but it is actually -2. The problem obviously is that the
parser handles the term from right to left: 4-3-2-1.

How do I have to modify the above parser to handle expressions of the
form 1-2-3-4?

Thanks,
Michael

[Tony Sloane]

Hi Michael,

Actually the problem is that your parsers are right recursive, not left (which is more traditional for these operators). Your example expression is being parsed as if you had written

1-(2-(3-4))

which has value -2.

Try rephrasing your parsers as, for example,

expr = expr + term
| expr - term
| term

and you should get the result you expect. (Yes, Scala's parser combinators can handle left recursive productions, at least simple ones.)

cheers,
Tony

[Michi]

Hi Tony

I modified my parser to be left recursive:

object ExprParser extends JavaTokenParsers {
def expr: Parser[Expr] =

(expr <~ "+") ~ term ^^ { case lhs~rhs => BinaryOp("+", lhs,
rhs) } |
(expr <~ "-") ~ term ^^ { case lhs~rhs => BinaryOp("-", lhs,

rhs) } |
term
def term: Parser[Expr] =

(term <~ "*") ~ factor ^^ { case lhs~rhs => BinaryOp("*", lhs,
rhs) } |
(term <~ "/") ~ factor ^^ { case lhs~rhs => BinaryOp("/", lhs,

rhs) } |
factor
def factor : Parser[Expr] =
"(" ~> expr <~ ")" |
floatingPointNumber ^^ {x => Number(x.toDouble) }

def parse(text : String) = parseAll(expr, text)
}

I now get a StackOverflowError:
Exception in thread "main" java.lang.StackOverflowError
at calculator.Calc$ExprParser$.expr(Calc.scala:19)
...

I realized that the problem is, that my parser is right-recursive and
started to write a tree transformer that reorders the tree-nodes to
make them left-associative. But I would obviously like to avoid this,
if this is possible, so I would appreciate further input how to do
this.

Thanks,
Michael

[Michi]

I read somehwere that it is necessary to use lazy vals instead of defs
for right-recursive parsers:

abstract class Expr
case class Number(value: Double) extends Expr
case class UnaryOp(operator: String, arg: Expr) extends Expr
case class BinaryOp(operator: String, left : Expr, right: Expr)
extends Expr

object Calc {
def evaluate(e: Expr): Double = {
e match {
case Number(x) => x
case UnaryOp("-", x) => -(evaluate(x))
case BinaryOp("+", x1, x2) => (evaluate(x1) + evaluate(x2))
case BinaryOp("-", x1, x2) => (evaluate(x1) - evaluate(x2))
case BinaryOp("*", x1, x2) => (evaluate(x1) * evaluate(x2))
case BinaryOp("/", x1, x2) => (evaluate(x1) / evaluate(x2))
}
}

import scala.util.parsing.combinator._

object ExprParser extends JavaTokenParsers {

lazy val expr: Parser[Expr] =

(expr <~ "+") ~ term ^^ { case lhs~rhs => BinaryOp("+", lhs,
rhs) } |
(expr <~ "-") ~ term ^^ { case lhs~rhs => BinaryOp("-", lhs,
rhs) } |
term

lazy val term: Parser[Expr] =

(term <~ "*") ~ factor ^^ { case lhs~rhs => BinaryOp("*", lhs,
rhs) } |
(term <~ "/") ~ factor ^^ { case lhs~rhs => BinaryOp("/", lhs,
rhs) } |
factor

lazy val factor : Parser[Expr] =

"(" ~> expr <~ ")" |
floatingPointNumber ^^ {x => Number(x.toDouble) }

def parse(text : String) = parseAll(expr, text)
}

def parse(text: String) = ExprParser.parse(text).get

def evaluate(text: String): Double = evaluate(parse(text))
}

But it still throws a stack overflow error. Is there something I am
doing wrong or why does right-recursion not work?

Thanks,
Michael

[Michi]

Hi,

> But it still throws a stack overflow error. Is there something I am
> doing wrong or why does right-recursion not work?

This should oviously be left-recursion.

Michael

[Michi]

I found the solution:

object ExprParser extends JavaTokenParsers with PackratParsers {
lazy val expr: PackratParser[Expr] =

(expr <~ "+") ~ term ^^ { case lhs~rhs => BinaryOp("+", lhs,
rhs) } |
(expr <~ "-") ~ term ^^ { case lhs~rhs => BinaryOp("-", lhs,
rhs) } |
term

lazy val term: PackratParser[Expr] =

(term <~ "*") ~ factor ^^ { case lhs~rhs => BinaryOp("*", lhs,
rhs) } |
(term <~ "/") ~ factor ^^ { case lhs~rhs => BinaryOp("/", lhs,
rhs) } |
factor

lazy val factor : PackratParser[Expr] =

"(" ~> expr <~ ")" |
floatingPointNumber ^^ {x => Number(x.toDouble) }

def parse(text : String) = parseAll(expr, text)
}

Thanks,
Michael

[Tommaso Galleri]

Hi,

Or you could have used something like:

lazy val expr = term ~ rep(
"+" ~> term ^^ (...) |
"-" ~> term ^^ (...)
) ^^ {
... foldleft ...
}

And you would not have had to move to a packrat parser to support your
left recursive grammar (packrat parsers are good, just telling you
another solution).

Regards,

Tommaso

I found the solution:

Thanks,
Michael

The information included in this email and any files transmitted with it may contain information that is confidential and it must not be used by, or its contents or attachments copied or disclosed, to persons other than the intended addressee. If you have received this email in error, please notify BJSS. In the absence of written agreement to the contrary BJSS' relevant standard terms of contract for any work to be undertaken will apply. Please carry out virus or such other checks as you consider appropriate in respect of this email. BJSS do not accept responsibility for any adverse effect upon your system or data in relation to this email or any files transmitted with it. BJSS Limited, a company registered in England and Wales (Company Number 2777575), VAT Registration Number 613295452, Registered Office Address, First Floor, Coronet House, Queen Street, Leeds, LS1 2TW

[Tony Sloane]

I'm glad you got there. Sorry, for forgetting to mention the lazy val thing
in my first response...

cheers,
Tony