Calculating nullable nonterminals of a grammar in a functional way (preferably in Scala)

Question

I'm new to functional programming and was wondering how one solves the problem of calculating the set of nullable nonterminals in a context-free grammar in a pure functional way without using variable assignments.

A nullable nonterminal is a nonterminal directly yielding empty, e.g., A ::= , or having a body containing of nullable nonterminals, e.g., A ::= B C D, where all B C and D yield empty.

I'm using the following definitions in Scala to define a grammar:

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

A basic algorithm is that to gather all directly nullable nonterminals and put them in a set. Then in each iteration try to determine which production rules have all nullable nonterminals on their body. Those nonterminals will be added to the set until no new nonterminal is added to the set.

I have implemented this procedure in Scala as:

  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   
}

Although the code is much shorter than the equivalent Java version, it uses variables. Any suggestions to rewrite this piece of code in a functional style?

Answer 1

Here is a more idiomatic Scala solution:

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)
  }

}

The while statement is replaced with a recursive function - loop. Also, avoid using isInstanceOf - pattern matching is much better suited for this.

Small observation - make the Symbol class sealed, since this can enforce warnings of missing cases in pattern matches.