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

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

可为空的非终结符是直接产生空值的非终结符，例如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

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

我已经在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版本短得多，但是它使用变量。有什么建议
以功能样式重写这段代码？

最佳答案

这是一个更惯用的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类设置为sealed，因为这可以在模式匹配中强制执行有关丢失情况的警告。

关于scala - 以函数方式计算语法的可为空的非终结符(最好在Scala中)，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/14427899/