4

>次のパーサー コンビネータのスニペットは、 を使用するなどしてバイナリ比較操作を一般化するという目的を示してOrdered[T]います。GtASTレベルでこれを達成しているようですが、この概念を拡張するのに苦労しています.

intGtパーサーは機能しますが、これを一般化しOrdered[T]て、2 番目のパーサーを作成する必要がないようにすることは可能floatGtですか (したがって、サポートされているすべての順序付け可能な型 * サポートされているすべての op に対して 1 つ - 感謝しません)。

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作成できる関数を定義しました。これらの演算は、部分式パーサーと演算を受け取る を使用してパーサーに変換できます。これは、int 型と float 型のすべての順序付け操作にマップされます。Seq[OrderOp]OrderableorderExpr

このアプローチに関するいくつかの問題:

  • すべての二項演算の AST 型階層には、ノード型が 1 つしかありません。これは、評価だけを行っている場合は問題ありませんが、書き換え操作 (たとえば、明らかなトートロジーや矛盾を排除する) を行いたい場合は、BinOp の現在の定義でこれを行うには情報が不十分です。
  • orderExpr個別のタイプごとにマッピングする必要がありました。これを修正する方法があるかもしれませんが、時間がなくなりました。
  • orderExprは、左右の部分式が同じパーサーで解析されることを期待しています。
于 2012-10-13T15:48:08.717 に答える