Scala:如何使用类型集合？

Question

我正在为一种小语言手工编写一个递归下降解析器。在我的词法分析器中，我有:

trait Token{def position:Int}
trait Keyword  extends Token
trait Operator extends Token

case class Identifier(position:Int, txt:String) extends Token
case class If        (position:Int)             extends Keyword
case class Plus      (position:Int)             extends Operator
/* etcetera; one case class per token type */

我的解析器运行良好，现在我想合并一些错误恢复:替换、插入或丢弃标记，直到某个同步点。

为此，如果有一个在无效的 Scala 中看起来像这样的函数会很方便

def scanFor(tokenSet:Set[TokenClass], lookahead:Int) = {
  lexer.upcomingTokens.take(lookahead).find{ token =>
    tokenSet.exists(tokenClass => token.isInstanceOf[tokenClass])
  }
}

我会调用它，例如:scanFor(Set(Plus, Minus, Times, DividedBy), 4)

但是TokenClass当然不是一个有效的类型，而且我不知道如何创建之前的集合。

作为替代方案:

1. 我可以创建一个新特征，并使我想要检查的 token 集中的所有 token 类扩展该特征，然后针对该特征执行 instanceOf 检查。但是，我可能有几个这样的集合，这可能会使它们难以命名，并且代码以后难以维护。
2. 我可以创建 isXXX:Token=>Boolean 函数，并创建这些函数的集合，但这看起来不太优雅

有什么建议吗？

Answer 1

如果这样的组合只有少数，我实际上建议使用额外的特征。它很容易编写和理解，并且运行时速度很快。说起来也不算太糟糕

case class Plus(position: Int)
extends Operator with Arithmetic with Precedence7 with Unary

但是还有很多替代方案。

如果您不介意繁琐的手动维护过程并且需要真正快速的东西，那么为每个 token 类型定义一个 ID 号(您必须手动保持不同)将允许您使用 Set[Int] 或 BitSet 甚至只是一个 Long 来选择您喜欢的类。然后，您可以执行集合操作(​​并集、交集)来相互构建这些选择器。编写单元测试来帮助使挑剔的部分变得更加可靠并不难。如果您至少可以列出所有类型:

val everyone = Seq(Plus, Times, If /* etc */)
assert(everyone.length == everyone.map(_.id).toSet.size)

因此，如果您认为性能和可组合性至关重要，那么您不必对这种方法过于 panic 。

您还可以编写自定义提取器，它可以(更慢地)通过模式匹配提取正确的标记子集。例如，

object ArithOp {
  def unapply(t: Token): Option[Operator] = t match {
    case o: Operator => o match {
      case _: Plus | _: Minus | _: Times | _: DividedBy => Some(o)
      case _ => None
    }
    case _ => None
  }
}

如果操作类型不正确，

将为您提供None。 (在本例中，我假设除了 Operator 之外没有父级。)

最后，您可能可以将类型表示为联合和 HList，并使用 Shapeless 以这种方式挑选它们，但我个人没有使用解析器执行此操作的经验，因此我不确定您可能会遇到什么困难.