Ich bin neu in der funktionalen Programmierung und habe mich gefragt, wie man das Problem der Berechnung der Menge der nullbaren Nichtterminale in einer kontextfreien Grammatik auf rein funktionale Weise löst, ohne Variablenzuweisungen zu verwenden.
Ein nullbares Nichtterminal ist ein Nichtterminal, das direkt leer ist, z. B. A ::= , oder mit einem Körper, der nicht löschbare Nichtterminale enthält, z. B. A ::= B C D, wobei alle B C und D leer ergeben.
Ich verwende die folgenden Definitionen in Scala, um eine Grammatik zu definieren:
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 SymbolEin grundlegender Algorithmus besteht darin, alle direkt nullbaren Nichtterminale zu sammeln und in eine Menge zu packen. Dann wird in jeder Iteration versucht zu bestimmen, welche Produktionsregeln alle nullbaren Nichtterminale in ihrem Körper haben. Diese Nichtterminale werden der Menge hinzugefügt, bis kein neues Nichtterminal mehr in der Menge hinzugefügt wird.
Ich habe dieses Verfahren in Scala als implementiert:
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
}Obwohl der Code viel kürzer ist als die entsprechende Java-Version, verwendet er Variablen. Alle Vorschläge um dieses Stück Code funktional umzuschreiben?
