04.112014

DSL-Parser Generierung in Scala

Ob nun für Konfigurationsdateien, Daten die importiert werden sollen oder als leicht verständliche Schnittstelle für das eigentliche Programm - oft ist es wünschenswert anstelle einer generischen Lösung (XML, JSON, CSV, ...) eine direkt auf das Problem zugeschnittene, also domänenspezifische Sprache (DSL) zu verwenden. Heute stelle ich kurz und knapp Parser Generierung mit Scala vor, einer funktionalen und objektorientierten Sprache die auf der JVM läuft.

Alle nötigen Werkzeuge finden wir in den Standardbibliotheken von Scala. Zunächst stellen wir sicher, dass scala-parser-combinators im Klassenpfad bereitsteht - in Scala-IDE 3.0.4 mit Scala 2.11 muss diese bei neuen Projekten manuell hinzugefügt werden.

Zu Demonstrationszwecken bauen wir einen Parser für Koch und Backzutaten. Wir wollen also eine Liste wie etwa "3 Eier, 200ml Wasser, 100g Mehl und 20g Zucker" in ihre Bestandteile zerlegen um diese beispielsweise in ein digitales Rezeptbuch einzutragen.

Für diese Zwecke muss der eingegebenen Text zunächst in seine Bestandteile (Tokens) zerlegt werden. Diese Aufgabe erledigt die Klasse
scala.util.parsing.combinator.syntactical.StandardTokenParsers. Dem Token Parser bringen wir zunächst bei, dass Maßangaben wie "kg" und "ml" reservierte Ausdrücke sind, die immer als eigenständige Tokens betrachtet werden sollen. Somit erhalten wir das Skelett für den Zutatenparser:

import scala.util.parsing.combinator.syntactical.StandardTokenParsers
class IngredientsDSL extends StandardTokenParsers {
	lexical.delimiters  ++= List(",")
	lexical.reserved += ("ml", "l", "kg", "g", "mg", "EL", "TL", "Päckchen", "und")
}

Nun definieren wir einzelne Regeln um eine Zutatenliste zu definieren. Hier bietet sich ein Top-Down-Ansatz an:

  • Eine Liste von Zutaten sind mehrere Zutaten getrennt durch ein Trennzeichen
  • Eine Zutat ist eine Mengenangabe und der Name einer Zutat
  • Eine Mengenangabe ist entweder eine Gewichtsangabe, eine Volumenangabe oder eine Anzahl

Nach diesem Prinzip erweitern wir den Parser:

	def volumeMeasure = numericLit ~ ("ml"|"l"|"EL"|"TL"|"Päckchen")
	def volumeItem = volumeMeasure ~ ident

	def weightMeasure = numericLit ~ ("g"|"mg"|"kg")
	def weightedItem = weightMeasure ~ ident

	def item = numericLit ~ ident
	def ingredient = weightedItem | volumeItem | item

	def listSeperator =  "," | "und"
	def ingredients = repsep(ingredient, listSeperator)

Nun fehlt natürlich noch ein Einstiegspunkt und schon ist der Parser fertig:

import scala.util.parsing.combinator.syntactical.StandardTokenParsers
class IngredientsDSL extends StandardTokenParsers {
	lexical.delimiters  ++= List(",")
	lexical.reserved += ("ml", "l", "kg", "g", "mg", "EL", "TL", "Päckchen", "und")

	def volumeMeasure = numericLit ~ ("ml"|"l"|"EL"|"TL"|"Päckchen")
	def volumeItem = volumeMeasure ~ ident

	def weightMeasure = numericLit ~ ("g"|"mg"|"kg")
	def weightedItem = weightMeasure ~ ident

	def item = numericLit ~ ident
	def ingredient = weightedItem | volumeItem | item

	def listSeperator =  "," | "und"
	def ingredients = repsep(ingredient, listSeperator)

	def doMatch() {
	  val dsl =
	  """
	    200g Magerquark, 4 EL Milch, 8 EL Öl, 1 Ei,
	    400g Mehl, 1 Päckchen Backpulver, 1 TL Salz und 1 TL Oregano
	  """
	  ingredients(new lexical.Scanner(dsl)) match {
	    case Success(res, _) => println(res)
	    case Failure(msg, _) => println(msg)
	    case Error(msg, _) => println(msg)
	  }
	}
}

object IngredientsDSL {
  def main(args: Array[String]): Unit = {
    new IngredientsDSL().doMatch();
  }
}

Nach Start des Programmes ist auf der Konsole die folgende Ausgabe zu sehen:

List(((200~g)~Magerquark), ((4~EL)~Milch), ((8~EL)~Öl), (1~Ei), ((400~g)~Mehl), ((1~Päckchen)~Backpulver), ((1~TL)~Salz), ((1~TL)~Oregano))

Wer möchte kann Progammlogik, wie etwa eine Normalisierung der Mengenangaben, oder aber den Abgleich der Zutaten mit einer Datenbank direkt im Parser verbauen. So kann beispielsweise die Definition des Gewichtes immer auf Gramm berechnet werden:

	def weightMeasure = numericLit ~ ("g"|"mg"|"kg") ^^ {
	  case value ~ "g" => value.toInt
	  case value ~ "mg" => value.toInt * 0.001
	  case value ~ "kg" => value.toInt * 1000
	}

Für eine ausführliche Erklärung zu Scala und den vielen tollen Features lohnt sich ein Blick auf die offizielle Seite und den dort befindlichen Tutorials

Jetzt noch alles kräftig verrühren, mit etwas Mehl ausrollen und gut belegen. Dann bei 250 Grad 20-25 Minuten in den Ofen.
Guten Appetit!