Huy Vo Huy Vo - 1 month ago 10
Scala Question

How to build a parse tree of simple expressions

Let's build a parser tree for simple expressions such as

3 - 4 * 5
, using
scala.util.parsing.combinator._
:

def expr: Parser[Any] = term ~ opt(("+"|"-") ~ expr)
def term: Parser[Any] = factor ~ opt(("*"|"/") ~ factor)
def factor: Parser[Any] = wholeNumber | "(" ~> expr <~ ")"


With
3 - 4 * 5
, the result tree is:

expr
/ | \
term - expr
| / | \
factor term * term
| | |
number factor factor
| | |
3 number number
| |
4 5


which is right. But with
3 - 4 + 5
my tree doesn't seem to correct:

expr
/ | \
term - expr
| / | \
factor term + term
| | |
number factor factor
| | |
3 number number
| |
4 5


How can I fix that? I thought this was solution:

def expr: Parser[Any] = expr ~ opt(("+"|"-") ~ term)


but it's way too wrong...

My full code:

import scala.util.parsing.combinator._


class Expr

case class Number(value: Int) extends Expr {
override def toString = s"$value"
}

case class Operator(left: Expr, right: Expr, f: (Int, Int) => Int) extends Expr {
override def toString = s"($f, $left, $right)"
}

class SimpleLanguageParser extends JavaTokenParsers {

def expr: Parser[Expr] = (term ~ opt(("+" | "-") ~ expr)) ^^ {
case a ~ None => a
case a ~ Some("+" ~ b) => Operator(a, b, _ + _)
case a ~ Some("-" ~ b) => Operator(a, b, _ - _)
}

def term: Parser[Expr] = (factor ~ opt(("*" | "/" ) ~ term)) ^^ {
case a ~ None => a
case a ~ Some("*" ~ b) => Operator(a, b, _ * _)
case a ~ Some("/" ~ b) => Operator(a, b, _ / _)
}

def factor: Parser[Expr] = wholeNumber ^^ (n => Number(Integer.parseInt(n))) | "(" ~> expr <~ ")"

}

object Main {
def main(args: Array[String]) = {
val parser = new SimpleLanguageParser
val result = parser.parse(parser.expr, "3 - 4 + 5")
println(result)
}
}

Answer

I think term ~ opt(("+"|"-") ~ expr) couldn't reserve the order of +/- operations.

def largerExpr: Parser[Any] = expr ~ opt(("+"|"-") ~ expr)
def expr: Parser[Any] = term ~ opt(("+"|"-") ~ term)

EIDT

def expr1: Parser[Expr] = (expr ~ opt(("+" | "-") ~ expr)) ^^ {
    case a ~ None => a
    case a ~ Some("+" ~ b) => Operator(a, b, _ + _)
    case a ~ Some("-" ~ b) => Operator(a, b, _ - _)
}

def expr: Parser[Expr] = (term ~ opt(("+" | "-") ~ term)) ^^ {
    case a ~ None => a
    case a ~ Some("+" ~ b) => Operator(a, b, _ + _)
    case a ~ Some("-" ~ b) => Operator(a, b, _ - _)
}

Your result would be (<function2>, 3, (<function2>, 4, 5)), the result using expr1 is (<function2>, (<function2>, 3, 4), 5)