scala - 以函数式方式计算文法的可空非终结符(最好在 Scala 中)

Question

我是函数式编程的新手，想知道如何在不使用变量赋值的情况下以纯函数方式解决在上下文无关语法中计算可空非终结符集的问题。

可空非终结符是直接产生空的非终结符，例如 A::= 或具有包含可空非终结符的主体，例如 A::= B C D，其中所有 B C 和 D 都为空。

我在 Scala 中使用以下定义来定义语法:

case class Grammar(name:String, startSymbol:Nonterminal, rules:List[Rule])
case class Rule(head: Nonterminal, body:List[Symbol])
abstract class Symbol
case class Terminal(c:Char) extends Symbol
case class Nonterminal(name:String) extends Symbol

一个基本算法是收集所有直接可为空的非终结符并将它们放在一个集合中。然后在每次迭代中尝试确定哪些生产规则具有所有可为空的非终结符在他们的身上。这些非终结符将被添加到集合中，直到没有新的非终结符被添加到集合中放。

我已经在 Scala 中实现了这个过程:

  def getNullableNonterminals(grammar:Grammar) = {

  var nieuw : Set[Nonterminal] = (for(Rule(head, Nil) <- grammar.rules) yield head) (collection.breakOut)
  var old = Set[Nonterminal]()

  while(old != nieuw) {
    old = nieuw
    for{
        Rule(head, symbols) <- grammar.rules
        if symbols.length > 0
        if symbols.forall( s => s.isInstanceOf[Nonterminal] && old.contains(s.asInstanceOf[Nonterminal]))
       } nieuw = nieuw + head
  }
  nieuw   
}

虽然代码比等效的 Java 版本短得多，但它使用了变量。有什么建议么以函数式风格重写这段代码？

Answer 1

下面是一个更惯用的 Scala 解决方案:

object Algorithm {

  def getNullableNonterminals(grammar:Grammar) = {
    loop(grammar, Set())
  }

  @tailrec
  private def loop(grammar: Grammar, nullablesSoFar: Set[Nonterminal]): Set[Nonterminal] = {
    val newNullables = generateNew(grammar, nullablesSoFar)
    if (newNullables.isEmpty)
      nullablesSoFar //no new nullables found, so we just return the ones we have
    else
      loop(grammar, nullablesSoFar ++ newNullables) //add the newly found nullables to the solution set and we keep going
  }

  private def generateNew(grammar: Grammar, nullableSoFar: Set[Nonterminal]) = {
    for {
      Rule(head, body) <- grammar.rules
      if !nullableSoFar.contains(head)
      if body.forall(isNullable(_, nullableSoFar))
    } yield head
  }

  //checks if the symbol is nullable given the current set of nullables
  private def isNullable(symbol: Symbol, provenNullable: Set[Nonterminal]) = symbol match {
    case Terminal(_) => false
    case x@Nonterminal(_) => provenNullable.contains(x)
  }

}

while 语句被替换为递归函数 - loop。此外，避免使用 isInstanceOf - 模式匹配更适合这种情况。

小观察 - 使 Symbol 类密封，因为这可以强制警告模式匹配中的缺失案例。