Creating AST for arithmetic expression in Scala

Question

I would like to make an AST for arithmetic expression using fastparse from Scala. For me a arithmetic expression is like:

var_name := value;   // value can be an integer, or a whole expression

For the moment I have this parsers:

def word[_:P] = P((CharIn("a-z") | CharIn("A-Z") | "_").rep(1).!)
def digits[_ : P] = P(CharIn("0-9").rep.!)

def div_mul[_: P] = P( digits~ space.? ~ (("*" | "/").! ~ space.? ~/ digits).rep ).map(eval)
def add_sub[_: P] = P( div_mul ~ space.? ~ (("+" | "-").! ~ space.? ~/ div_mul).rep ).map(eval)
def expr[_: P]= P( " ".rep ~ add_sub ~ " ".rep ~ End )

def var_assig[_:P] = P(word ~ " " ~ ":=" ~ " " ~ (value | expr) ~ ";")

I want to create AST for arithmetic expression (2+3*2 for example).

Expected result: Assignment[2,plus[mult,[3,2]]] // symbol[left, right]

My questions is:

• What should be like the Tree class/object, if it is necessary, because I want to evaluate that result? This class I will use for the rest parse(if, while).

• What should be like the eval function, who takes the input an string, or Seq[String] and return a AST with my expected result?

Answer 1

Here is my way of doing it. I have defined the components of the Arithmetic Expression using the following Trait:

sealed trait Expression
case class Add(l: Expression, r: Expression) extends Expression
case class Sub(l: Expression, r: Expression) extends Expression
case class Mul(l: Expression, r: Expression) extends Expression
case class Div(l: Expression, r: Expression) extends Expression
case class Num(value: String) extends Expression

And defined the following fastparse patterns (similar to what is described here: https://com-lihaoyi.github.io/fastparse/#Math)

def number[_: P]: P[Expression] = P(CharIn("0-9").rep(1)).!.map(Num)
def parens[_: P]: P[Expression] = P("(" ~/ addSub ~ ")")
def factor[_: P]: P[Expression] = P(number | parens)

def divMul[_: P]: P[Expression] = P(factor ~ (CharIn("*/").! ~/ factor).rep).map(astBuilder _ tupled)
def addSub[_: P]: P[Expression] = P(divMul ~ (CharIn("+\\-").! ~/ divMul).rep).map(astBuilder _ tupled)
def expr[_: P]: P[Expression] = P(addSub ~ End)

Instead of the eval function that was used in the map, I have written a similar one, which returns a folded entity of the previously defined case classes:

def astBuilder(initial: Expression, rest: Seq[(String, Expression)]): Expression = {
  rest.foldLeft(initial) {
    case (left, (operator, right)) =>
      operator match {
        case "*" => Mul(left, right)
        case "/" => Div(left, right)
        case "+" => Add(left, right)
        case "-" => Sub(left, right)
      }
  }
}

And if we would run the following expression:

val Parsed.Success(res, _) = parse("2+3*2", expr(_))

The result would be: Add(Num(2),Mul(Num(3),Num(2)))