Scala Parserkombinatoren im Dienste des Bieres

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:

1Name: Maibock
2Menge: 22l
3Schüttung:
4  Pilsener Malz 4000g
5  Münchener Malz 2000g
6Brauwasser:
7  20l Hauptguss
8  13l Nachguss
9Hopfen:
10  Spalter Select 5,3% Alpha 50g
11  Magnum 13,5% Alpha 10g
12  Cascade 5,0% Alpha 23g
13Hefe:
14  Untergährige Trockenhefe Saflager W34/70
15Maischen:
16  Einmaischen 59°C
17  1. Rast nach 10 Min 57°C
18  2. Rast nach 60 Min 63°C
19  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:

1case class Rezept(name: String, menge: Option[Int], schuettung: List[Schuettung], brauwasser: Brauwasser, hopfen: List[Hopfen], hefe: String, maischvorgang: Maischvorgang)
2case class Schuettung(malzname: String, menge: Number)
3case class Brauwasser(hauptguss: Number, nachguss: Number)
4case class Hopfen(name: String, alphaSaeuregehalt: Double, menge: Number)
5case class Maischvorgang(einmaischen: Number, rasten: List[Rast], ablaeutern: Number)
6case 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:

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

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:

1def 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

1class RezeptParserTest extends FunSuite {
2 
3  test("Liter") {
4    val liter = RezeptParser.parse(RezeptParser.liter, " 33l").get
5    assert(liter == 33)
6  }
7 
8  test("Menge in l") {
9    val menge = RezeptParser.parse(RezeptParser.menge, "Menge: 33l").get
10    assert(menge == 33)
11  }
12 
13  test("Menge in Liter") {
14    val menge = RezeptParser.parse(RezeptParser.menge, "Menge: 33 Liter").get
15    assert(menge == 33)
16  }
17}

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:

1Hopfen:
2  Spalter Select 5,3% Alpha 50g
3  Magnum 13,5% Alpha 10g
4  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:

1def hopfen = "Hopfen:" ~> rep(hops)
2def 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:

1package de.codecentric.wittig.scala.parser.rezept
2 
3import scala.util.parsing.combinator.RegexParsers
4import scala.util.parsing.combinator.JavaTokenParsers
5import java.text.NumberFormat
6import java.util.Locale
7 
8object RezeptParser extends JavaTokenParsers {
9 
10  override val whiteSpace = """(\s|#.*#)+""".r
11 
12  val format = NumberFormat.getInstance(Locale.GERMANY);
13 
14  def liter = wholeNumber <~ "l|Liter".r ^^ { _.toInt }
15  def gramm = wholeNumber <~ "g|Gramm".r ^^ { _.toInt }
16  def alphasaeure = dezimal <~ "% Alpha"   def string = """[a-zA-ZäÄüÜöÖß\s]*""".r   def dezimal = """(\d+(\,\d*)?|\d*\,\d+)""".r   def name = "Name:" ~> ident
17  def menge = "Menge:" ~> liter
18  def schuett = string ~ gramm ^^ { case malzsorte ~ grammanzahl => Schuettung(malzsorte.trim, grammanzahl.toInt) }
19  def schuettung = "Schüttung:" ~> rep(schuett)
20  def brauwasser = "Brauwasser:" ~> liter ~ "Hauptguss" ~ liter ~ "Nachguss" ^^ { case hg ~ ht ~ ng ~ nt => Brauwasser(hg.toInt, ng.toInt) }
21  def hopfen = "Hopfen:" ~> rep(hops)
22  def hops = string ~ alphasaeure ~ gramm ^^ { case n ~ alpha ~ menge => Hopfen(n.trim, format.parse(alpha).doubleValue(), menge) }
23  def hefe = "Hefe:" ~> """.*""".r
24  def maischvorgang = "Maischen:" ~> einmaischen ~ rep(rast) ~ ablaeutern ^^ { case ein ~ rasten ~ aus => Maischvorgang(ein, rasten, aus) }
25  def einmaischen = ("Einmaischen" ~ opt("bei")) ~> grad ^^ { _.toInt }
26  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) }
27  def ablaeutern = ("Abläutern" ~ opt("bei")) ~> grad ^^ { _.toInt }
28  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) }
29 
30  def apply(rezeptAsString: String): ParseResult[Rezept] = parse(rezept, rezeptAsString)
31 
32}

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:

1def 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

1override 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:

1test("Maibock") {
2  val maibockRezept = """
3    Name: Maibock
4    Menge: 22l
5    Schüttung:
6      Pilsener Malz 4000g
7      Münchener Malz 2000g
8    Brauwasser:
9      20l Hauptguss
10      13l Nachguss
11    Hopfen:
12      Spalter Select 5,3% Alpha 50g
13      Magnum 13,5% Alpha 10g
14      Cascade 5,0% Alpha 23g
15    Hefe: #Kommentar, der geskipped wird#
16      Untergärige Trockenhefe Saflager W34/70
17    Maischen:
18      Einmaischen 50°C
19      1. Rast bei 57°C für 10 Min
20      2. Rast bei 63°C für 60 Min
21      Abläutern 78°C"""
22    val maibock = RezeptParser(maibockRezept)
23    maibock match {
24      case RezeptParser.Success(mb, _) => {
25 
26        assert(mb.name == "Maibock")
27        assert(mb.menge == Some(22))
28        assert(mb.schuettung.size == 2)
29        assert(mb.schuettung(0).malzname == "Pilsener Malz")
30        assert(mb.schuettung(0).menge == 4000)
31        assert(mb.schuettung(1).malzname == "Münchener Malz")
32        assert(mb.schuettung(1).menge == 2000)
33        assert(mb.brauwasser.hauptguss == 20)
34        assert(mb.brauwasser.nachguss == 13)
35        assert(mb.hopfen(0).name == "Spalter Select")
36        assert(mb.hopfen(2).name == "Cascade")
37        assert(mb.hefe.startsWith("Untergärige Tro"))
38        assert(mb.maischvorgang.einmaischen == 50)
39        assert(mb.maischvorgang.rasten(0) == Rast(1, 10, 57))
40        assert(mb.maischvorgang.rasten(1) == Rast(2, 60, 63))
41        assert(mb.maischvorgang.ablaeutern == 78)
42      }
43      case RezeptParser.NoSuccess(msg, r) => { println(s"Fehler: $msg => $r"); fail }
44    }
45  }

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 😉