scala - 在 Scala 中为算术表达式创建 AST

Question

我想使用 Scala 中的 fastparse 为算术表达式制作 AST。对我来说，算术表达式是这样的:

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

目前我有这个解析器:

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) ~ ";")

我想为算术表达式创建 AST(例如 2+3*2)。

预期结果:Assignment[2,plus[mult,[3,2]]]//symbol[left, right]

我的问题是:

• Tree 类/对象应该是什么，如果有必要，因为我想评估那个结果？这个类我将用于其余的 parse(if, while)。

• eval 函数应该是什么样子，它接受一个字符串或 Seq[String] 的输入并返回一个包含我预期结果的 AST？

Answer 1

这是我的做法。我已经使用以下特征定义了算术表达式的组件:

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

并定义了以下 fastparse 模式(类似于此处描述的内容: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)

我编写了一个类似的函数，而不是 map 中使用的 eval 函数，它返回先前定义的案例类的折叠实体:

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

如果我们运行以下表达式:

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

结果将是:Add(Num(2),Mul(Num(3),Num(2)))