4

以下解析器组合器片段演示了泛化二进制比较操作的目标，例如>使用Ordered[T]. Gt似乎在 AST 级别实现了这一点，但我在扩展这个概念时遇到了麻烦。

解析器可以工作，intGt但是否可以概括这一点，Ordered[T]这样我们就不需要为floatGt（因此为所有支持的可订购类型 * 所有支持的操作 - 不，谢谢）编写第二个解析器。

object DSL extends JavaTokenParsers {
  // AST
  abstract class Expr[+T] { def eval: T }
  case class Literal[T](t: T) extends Expr[T] { def eval = t }
  case class Gt[T <% Ordered[T]](l: Expr[T], r: Expr[T]) extends Expr[Boolean] {
    def eval = l.eval > r.eval // view-bound implicitly wraps eval result as Ordered[T]
  }

  // Parsers
  lazy val intExpr: Parser[Expr[Int]] = wholeNumber ^^ { case x => Literal(x.toInt) }
  lazy val floatExpr: Parser[Expr[Float]] = decimalNumber ^^ { case x => Literal(x.toFloat) }
  lazy val intGt: Parser[Expr[Boolean]] = intExpr ~ (">" ~> intExpr) ^^ { case l ~ r => Gt(l, r) }
}
4

1 回答 1

1

我试着到处玩，这是我能想到的最好的：

import scala.util.parsing.combinator.JavaTokenParsers

object DSL extends JavaTokenParsers {
  // AST
  abstract class Expr[+T] { def eval: T }
  case class Literal[T](t: T) extends Expr[T] { def eval = t }
  case class BinOp[T,U](
    val l : Expr[T],
    val r : Expr[T],
    val evalOp : (T, T) => U) extends Expr[U] {

    def eval = evalOp(l.eval, r.eval)
  }

  case class OrderOp[O <% Ordered[O]](symbol : String, op : (O, O) => Boolean)

  def gtOp[O <% Ordered[O]] = OrderOp[O](">", _ > _)
  def gteOp[O <% Ordered[O]] = OrderOp[O](">=", _ >= _)
  def ltOp[O <% Ordered[O]] = OrderOp[O]("<", _ < _)
  def lteOp[O <% Ordered[O]] = OrderOp[O]("<=", _ <= _)
  def eqOp[O <% Ordered[O]] = OrderOp[O]("==", _.compareTo(_) == 0)

  def ops[O <% Ordered[O]] = 
    Seq(gtOp[O], gteOp[O], ltOp[O], lteOp[O], eqOp[O])

  def orderExpr[O <% Ordered[O]](
    subExpr : Parser[Expr[O]], 
    orderOp : OrderOp[O]) 
    : Parser[Expr[Boolean]] =
      subExpr ~ (orderOp.symbol ~> subExpr) ^^ 
        { case l ~ r => BinOp(l, r, orderOp.op) }

  // Parsers
  lazy val intExpr: Parser[Expr[Int]] = 
    wholeNumber ^^ { case x => Literal(x.toInt) }

  lazy val floatExpr: Parser[Expr[Float]] =
    decimalNumber ^^ { case x => Literal(x.toFloat) }

  lazy val intOrderOps : Parser[Expr[Boolean]] = 
    ops[Int].map(orderExpr(intExpr, _)).reduce(_ | _)

  lazy val floatOrderOps : Parser[Expr[Boolean]] =
    ops[Float].map(orderExpr(floatExpr, _)).reduce(_ | _)
}

本质上，我定义了一个小型案例类OrderOp，它将表示排序操作的字符串与将评估该操作的函数相关联。然后，我定义了一个能够为给定类型ops创建Seq[OrderOp]所有此类排序操作的函数。Orderable然后可以使用 将这些操作转换为解析器orderExpr，它采用子表达式解析器和操作。这映射到 int 和 float 类型的所有排序操作。

这种方法的一些问题：

  • 对于所有二元操作，AST 类型层次结构中只有一种节点类型。如果您所做的只是评估，这不是问题，但是如果您想要进行重写操作（例如，消除明显的重言式或矛盾），那么使用 BinOp 的当前定义没有足够的信息来执行此操作。
  • 我仍然需要orderExpr为每种不同的类型进行映射。可能有办法解决这个问题，但我没时间了。
  • orderExpr期望使用相同的解析器解析左右子表达式。
于 2012-10-13T15:48:08.717 回答