3

我想使用 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，因为我想评估该结果？这个类我将用于其余的解析（如果，同时）。

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

4

1 回答 1

3

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

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)

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

于 2021-04-26T11:40:03.080 回答