Huy Vo - 1 year ago 62

Scala Question

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

`3 - 4 * 5`

`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`

`expr`

/ | \

term - expr

| / | \

factor term * term

| | |

number factor factor

| | |

3 number number

| |

4 5

which is right. But with

`3 - 4 + 5`

`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...

`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 Source

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)`