6

所以我得到了这样的东西：

abstract class Term
case class App(f:Term,x:Term) extends Term
case class Var(s:String) extends Term
case class Amb(a:Term, b:Term) extends Term //ambiguity

一个 Term 可能如下所示：

App(Var(f),Amb(Var(x),Amb(Var(y),Var(z))))

所以我需要的是 Amb 类指示的所有变体。这用于表示一个模棱两可的解析森林，我想键入检查每个可能的变体并选择正确的变体。在这个例子中，我需要：

App(Var(f),Var(x))
App(Var(f),Var(y))
App(Var(f),Var(z))

在 scala 中创建这些变化的最佳方法是什么？效率会很好，但并不是真正的要求。如果可能的话，我喜欢避免使用反射。

4

3 回答 3

5

Scala 提供的模式匹配解决了这类问题。解决方案如下所示：

def matcher(term: Term): List[Term] = {
  term match {
    case Amb(a, b) => matcher(a) ++ matcher(b)
    case App(a, b) => for { va <- matcher(a); vb <- matcher(b) } yield App(va, vb)
    case v: Var    => List(v)
  }
}
于 2013-09-26T11:41:50.977 回答
4

您可以使用遍历树并扩展歧义的递归函数非常干净地做到这一点：

sealed trait Term
case class App(f: Term, x: Term) extends Term
case class Var(s: String) extends Term
case class Amb(a: Term, b: Term) extends Term

def det(term: Term): Stream[Term] = term match {
  case v: Var    => Stream(v)
  case App(f, x) => det(f).flatMap(detf => det(x).map(App(detf, _)))
  case Amb(a, b) => det(a) ++ det(b)
}

请注意，我使用的是密封特征而不是抽象类，以便利用编译器检查穷举的能力。

它按预期工作：

scala> val app = App(Var("f"), Amb(Var("x"), Amb(Var("y"), Var("z"))))
app: App = App(Var(f),Amb(Var(x),Amb(Var(y),Var(z))))

scala> det(app) foreach println
App(Var(f),Var(x))
App(Var(f),Var(y))
App(Var(f),Var(z))

如果您可以更改TermAPI，您可以或多或少地在def det: Stream[Term]其中添加一个方法。

于 2013-09-26T11:43:55.847 回答
0

由于我的抽象语法相当大（而且我有多个），所以我尝试了 Kiama 的运气。这是 Travis Brown 和 Mark 与 Kiama 一起发布的版本。

它不漂亮，但我希望它有效。欢迎评论。

  def disambiguateRule: Strategy = rule {
    case Amb(a: Term, b: Term) =>
      rewrite(disambiguateRule)(a).asInstanceOf[List[_]] ++
      rewrite(disambiguateRule)(b).asInstanceOf[List[_]]
    case x => 
      val ch = getChildren(x)
      if(ch.isEmpty) {
        List(x)
      }
      else {
        val chdis = ch.map({ rewrite(disambiguateRule)(_) }) // get all disambiguate children
        //create all combinations of the disambiguated children
        val p = combinations(chdis.asInstanceOf[List[List[AnyRef]]]) 
        //use dup from Kiama to recreate the term with every combination
        val xs = for { newchildren <- p } yield dup(x.asInstanceOf[Product], newchildren.toArray)
        xs
      }
  }

  def combinations(ll: List[List[AnyRef]]): List[List[AnyRef]] = ll match {
    case Nil      => Nil
    case x :: Nil => x.map { List(_) }
    case x :: xs  => combinations(xs).flatMap({ ys => x.map({ xx => xx :: ys }) })
  }

  def getChildren(x: Any): List[Any] = {
    val l = new ListBuffer[Any]()
    all(queryf {
      case a => l += a
    })(x)
    l.toList
  }
于 2013-10-04T09:44:15.833 回答