Scala Parserkombinatoren im Dienste des Bieres

1 Kommentar

Bier ist mehr als 5000 Jahre alt und wurde (möglicherweise durch Zufall?) im alten Ägypten durch halbgebackenes, vergorenes Brot erfunden. Super Sache, denn dadurch sind wir heute nicht nur um ein wohlschmeckendes Getränk reicher, wir haben auch einen Anwendungsfall, an dem wir unsere hier vorgestellten Parserkombinatoren in Scala ausprobieren können.

Wenn man weiß wie gut Bier schmecken kann, wie relativ einfach der Herstellungsprozess ist und daß jeder Bürger 200 Liter Bier herstellen darf, ohne Biersteuer entrichten zu müssen, kommt unweigerliche der Gedanke auf, sich eine Brauanlage und somit auch ein neues Hobby anzuschaffen.
Gesagt, getan. Wie geht’s nun weiter?

Jedes Bier besteht nach deutschem Reinheitsgebot aus Malz, Hopfen, Wasser und Hefe. Der Brauvorgang richtet sich nach einem bestimmten Rezept, in dem angegeben wird welche Malzsorten, Hefen, Hopfensorten und Wassermengen benutzt werden und in welcher Weise und zu welchem Zeitpunkt diese Zutaten miteinander verheiratet werden.

Natürlich hat das Rezept großen Einfluss auf die Farbe, die Blume und den Geschmack des Bieres. Bis das Lieblingsrezept gefunden ist, gehen einige Brauversuche ins Land. Dabei werden die Rezepte mit anderen Hobbybrauen getauscht und verglichen. Falls jetzt noch alle Rezepte im gleichen Format vorliegen, drängt sich uns Informatikern der Gedanke auf diese via Progrämmchen einzulesen und z.B. in eine Rezeptdatenbank zu speichern oder seinen Brauvorgang zu automatisieren.

Die DSL

Es folgt ein Rezept in der „Von-Menschen-Für-Menschen“-Form, in der es häufig zwischen Hobbybrauern ausgetauscht wird:

Name: Maibock
Menge: 22l
Schüttung:
  Pilsener Malz 4000g
  Münchener Malz 2000g
Brauwasser:
  20l Hauptguss
  13l Nachguss
Hopfen:
  Spalter Select 5,3% Alpha 50g
  Magnum 13,5% Alpha 10g
  Cascade 5,0% Alpha 23g
Hefe:
  Untergährige Trockenhefe Saflager W34/70
Maischen:
  Einmaischen 59°C
  1. Rast nach 10 Min 57°C
  2. Rast nach 60 Min 63°C
  Abläutern 78°C

Das Domänenmodell

Im Folgenden bauen wir einen Parser, der dieses Rezept parst und in unser Domänenmodell transformiert.
Das Domänenmodell ist recht einfach gehalten und spiegelt obige DSL als Scalaklassen ab:

case class Rezept(name: String, menge: Option[Int], schuettung: List[Schuettung], brauwasser: Brauwasser, hopfen: List[Hopfen], hefe: String, maischvorgang: Maischvorgang)
case class Schuettung(malzname: String, menge: Number)
case class Brauwasser(hauptguss: Number, nachguss: Number)
case class Hopfen(name: String, alphaSaeuregehalt: Double, menge: Number)
case class Maischvorgang(einmaischen: Number, rasten: List[Rast], ablaeutern: Number)
case class Rast(nummer: Int, dauer: Int, grad: Int)

Die erste Regel

Anders als im ersten Teil dieser Serie, wird für den RezeptParser nicht der RegexParsers sondern der JavaTokenParsers als Vaterklasse verwendet. Diese stellt zusätzlich zu den Methoden, die der RegexParser bietet, ein paar Standardparsermethoden zur Verfügung. Beispielsweise:
ident -> matched auf einen gültigen Java Identifier
wholeNumber -> matched eine Natürliche Zahl

Fangen wir ganz vorne bei unserer ersten Parsermethode an:

object RezeptParser extends JavaTokenParsers {
    def liter = wholeNumber <~ "l|Liter".r ^^ { _.toInt }
}

Hier wird eine Ganzzahl (wholeNumber), gefolgt von einem „l“ oder „Liter“ gematched. Durch das <~ wird lediglich der linke Teil, also die Ganzzahl übernommen und in der Transformationsfunktion ^^ in einen Integer umgewandelt.

Daß beide angegebene Tokens matchen müssen, aber nur ein bestimmter Teil übernommen wird, gilt auch für die nächste Regel:

def menge = "Menge:" ~> liter // ^^ { _.toInt } ist hier nicht nötig,

Hier wird durch das ~> nur der rechte Teil übernommen, der auf den oben definierten Parser „liter“ verweist. Dieser gibt einen Int (genauer gesagt ein Parser[Int]) zurück. Damit dieser Parser auch ein Parser[Int] zurückgibt, ist eine Transformation somit nicht mehr nötig.

Der Test

Jetzt kommen wir zu einem besonderen Schmankerl der Parserkombinatoren: Die einfache Testbarkeit der einzelnen Parsermethoden. Um unsere bisher definierten Parsermethoden mit ScalaTest zu testen ist nichts weiter nötig als

class RezeptParserTest extends FunSuite {
 
  test("Liter") {
    val liter = RezeptParser.parse(RezeptParser.liter, " 33l").get
    assert(liter == 33)
  }
 
  test("Menge in l") {
    val menge = RezeptParser.parse(RezeptParser.menge, "Menge: 33l").get
    assert(menge == 33)
  }
 
  test("Menge in Liter") {
    val menge = RezeptParser.parse(RezeptParser.menge, "Menge: 33 Liter").get
    assert(menge == 33)
  }
}

Gut erkennbar ist hier schon wie schön unabhängig voneinander alle Parsermethoden getestet werden können. Dieses Art des Testens sichert nicht nur unseren Code ab, sie läd auch zum Probieren ein und beschleunigt das Verstehen und Entwickeln von Parserkombinatoren.

Wie wird nun mit Wiederholungen umgegangen?
An oben vorgestellter Rezept-DSL werden mehrere Hopfensorten angegeben:

Hopfen:
  Spalter Select 5,3% Alpha 50g
  Magnum 13,5% Alpha 10g
  Cascade 5,0% Alpha 23g

Es existiert eine Überschrift „Hopfen:“. Darunter werden 0 bis n unterschiedliche Hopfensorten angegeben. Die unterschiedlichen Hopfenangaben folgen jedoch immer dem gleichen Muster. Um den Textblock für die Hopfen parsen zu könne, wird unsere Klasse um folgende Methoden erweitert:

def hopfen = "Hopfen:" ~> rep(hops)
def hops = string ~ alphasaeure ~ gramm ^^ { case n ~ alpha ~ menge => Hopfen(n.trim, format.parse(alpha).doubleValue(), menge.toInt) }

Mit rep wird angegeben, daß 0 bis n Wiederholungen erwartet werden. Interessant ist nun die Transformationsfunktion von hops. Hier werden in einer Partiellen Funktion mit Pattern Matching die verschiedenen Wörter, die dem ersten Teil der Parsermethode entsprechen, gematched. Das ist für den Entwickler sehr bequem, da nur der Positivfall betrachtet werden muß. Anschließend wird eine Instanz der Klasse Hopfen erzeugt. Insgesamt gibt der Parser „hops“ dementsprechend ein ParseResult[Hopfen] zurück.

Es folgt die komplette Parserklasse:

package de.codecentric.wittig.scala.parser.rezept
 
import scala.util.parsing.combinator.RegexParsers
import scala.util.parsing.combinator.JavaTokenParsers
import java.text.NumberFormat
import java.util.Locale
 
object RezeptParser extends JavaTokenParsers {
 
  override val whiteSpace = """(\s|#.*#)+""".r
 
  val format = NumberFormat.getInstance(Locale.GERMANY);
 
  def liter = wholeNumber <~ "l|Liter".r ^^ { _.toInt }
  def gramm = wholeNumber <~ "g|Gramm".r ^^ { _.toInt }
  def alphasaeure = dezimal <~ "% Alpha"   def string = """[a-zA-ZäÄüÜöÖß\s]*""".r   def dezimal = """(\d+(\,\d*)?|\d*\,\d+)""".r   def name = "Name:" ~> ident
  def menge = "Menge:" ~> liter
  def schuett = string ~ gramm ^^ { case malzsorte ~ grammanzahl => Schuettung(malzsorte.trim, grammanzahl.toInt) }
  def schuettung = "Schüttung:" ~> rep(schuett)
  def brauwasser = "Brauwasser:" ~> liter ~ "Hauptguss" ~ liter ~ "Nachguss" ^^ { case hg ~ ht ~ ng ~ nt => Brauwasser(hg.toInt, ng.toInt) }
  def hopfen = "Hopfen:" ~> rep(hops)
  def hops = string ~ alphasaeure ~ gramm ^^ { case n ~ alpha ~ menge => Hopfen(n.trim, format.parse(alpha).doubleValue(), menge) }
  def hefe = "Hefe:" ~> """.*""".r
  def maischvorgang = "Maischen:" ~> einmaischen ~ rep(rast) ~ ablaeutern ^^ { case ein ~ rasten ~ aus => Maischvorgang(ein, rasten, aus) }
  def einmaischen = ("Einmaischen" ~ opt("bei")) ~> grad ^^ { _.toInt }
  def rast = wholeNumber ~ ". Rast bei" ~ grad ~ "für" ~ wholeNumber <~ "min|Min|Minuten".r ^^ { case nummer ~ r ~ g ~ f ~ m => Rast(nummer.toInt, m.toInt, g) }
  def ablaeutern = ("Abläutern" ~ opt("bei")) ~> grad ^^ { _.toInt }
  def grad = wholeNumber <~ ("°|Grad".r ~ "C|Celsius".r) ^^ { _.toInt }   def rezept = name ~ opt(menge) ~ schuettung ~ brauwasser ~ hopfen ~ hefe ~ maischvorgang ^^ { case name ~ menge ~ schuettung ~ brauwasser ~ hopfen ~ hefe ~ maischen => Rezept(name, menge, schuettung, brauwasser, hopfen, hefe, maischen) }
 
  def apply(rezeptAsString: String): ParseResult[Rezept] = parse(rezept, rezeptAsString)
 
}

Nach dem ersten Schrecken über die Syntax der ~, ^^ und ~> Operatoren, erkennt man schnell die Einfachheit und Übersichtlichkeit dieser Art des Parsens.

Eine besondere Aufmerksamkeit sollte der Parsermethode „hefe“ geschenkt werden:

def hefe = "Hefe:" ~> """.*""".r

Wer bereits schonmal eine Grammatik für einen Parser geschrieben hat, wird das Problem der Mehrdeutigkeit von Lexerregeln kennen. Obige Regel, die 0 bis n beliebige Zeichen aktzeptiert, sprengt (falsch positioniert) oft jede Grammatik.
Der Lexer matcht quasi bei jedem belieben Zeichen, was zur Folge hat, daß sich der Parser beschwert: Denn egal welcher Input geliefert wird, der Parser wird immer das gleiche Wort (nämlich hefe) geliefert bekommen.
Genau das ist bei Parserkombinatoren nicht der Fall, da hier nur die einzelnen Lexer-/Parserregeln greifen können, die explizit innerhalb der jeweiligen Kombinatormethode angegeben werden.

Standardmäßig werden alle Whitespaces (Als Regex: \\s) zwischen den Tokens automatische „geskipped“. Dieses Verhalten kann durch Überschreiben von val whiteSpace und/oder def skipWhitespace, das der Parser von RegexParsers erbt, angepasst werden.
Mit

  override val whiteSpace = """(\s|#.*#)+""".r

wird der Parser dahingehend angepasst, daß Kommentare in der Form #Kommentar# vom Parser nicht mehr beachtet werden.

Der Parser ist nun soweit fertiggestellt, sodaß folgende Testmethode grünes Licht gibt:

test("Maibock") {
  val maibockRezept = """
    Name: Maibock
    Menge: 22l
    Schüttung:
      Pilsener Malz 4000g
      Münchener Malz 2000g
    Brauwasser:
      20l Hauptguss
      13l Nachguss
    Hopfen:
      Spalter Select 5,3% Alpha 50g
      Magnum 13,5% Alpha 10g
      Cascade 5,0% Alpha 23g
    Hefe: #Kommentar, der geskipped wird#
      Untergärige Trockenhefe Saflager W34/70
    Maischen:
      Einmaischen 50°C
      1. Rast bei 57°C für 10 Min
      2. Rast bei 63°C für 60 Min
      Abläutern 78°C"""
    val maibock = RezeptParser(maibockRezept)
    maibock match {
      case RezeptParser.Success(mb, _) => {
 
        assert(mb.name == "Maibock")
        assert(mb.menge == Some(22))
        assert(mb.schuettung.size == 2)
        assert(mb.schuettung(0).malzname == "Pilsener Malz")
        assert(mb.schuettung(0).menge == 4000)
        assert(mb.schuettung(1).malzname == "Münchener Malz")
        assert(mb.schuettung(1).menge == 2000)
        assert(mb.brauwasser.hauptguss == 20)
        assert(mb.brauwasser.nachguss == 13)
        assert(mb.hopfen(0).name == "Spalter Select")
        assert(mb.hopfen(2).name == "Cascade")
        assert(mb.hefe.startsWith("Untergärige Tro"))
        assert(mb.maischvorgang.einmaischen == 50)
        assert(mb.maischvorgang.rasten(0) == Rast(1, 10, 57))
        assert(mb.maischvorgang.rasten(1) == Rast(2, 60, 63))
        assert(mb.maischvorgang.ablaeutern == 78)
      }
      case RezeptParser.NoSuccess(msg, r) => { println(s"Fehler: $msg => $r"); fail }
    }
  }

Fazit

Dem Leser sollte die Idee von Parserkombinatoren nun deutlicher geworden sein. Mit der Scalakombinatorik lassen sich sehr einfach und schnell Parser schreiben. Besonders durch die einfache Testbarkeit der einzelnen Regeln/Methoden stellt sich der Erfolg sehr schnell und vor allem frustlos ein. Wen die anfangs etwas seltsam anmutende Syntax nicht abschreckt, wird sich mit dieser Art des Parsens schnell anfreunden.
Als Pferdefuß muß leider noch die suboptimale Performanz angesprochen werden. Spielt Performanz eine entscheidene Rolle, sollte man Parboiled2 als Alternative in Erwägung ziehen.

Notiz am Rande:
Am besten funktioniert der Rezeptparser übrigens, wenn vor Gebrauch der Maibock durch ein leckeres Kölsch ersetzt wird 😉

Gunther entwickelt seit 12 Jahren in Java, setzt dort mit Begeisterung vor allem die funktionalen Features ein.
Er freut sich über jede neue Herausforderung in Scala und bloggt über seine Erfahrung in der JVM-Sprache.

Share on FacebookGoogle+Share on LinkedInTweet about this on TwitterShare on RedditDigg thisShare on StumbleUpon

Kommentare

Kommentieren

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.