Parserkombinatoren in Scala – Erste Schritte

Parserkombinatoren sind ein Werkzeug, um Parser in Scala zu erstellen. Dieser Artikel soll den Einstieg in das Thema etwas erleichtern.
Im Laufe der zweiteiligen Artikelserie entsteht ein Parser für eine DSL. Die verschiedenen Aspekte von Parserkombinatoren in Scala werden nach und nach diskutiert.

Was sind Parserkombinatoren?

Unter einem Parser verstehen wir eine Funktion, die einen Strom von (String)-Tokens in ein neues Format (meist einen Baum) umwandelt. Ein Kombinator ist eine Funktion höheren Grades, die zwei übergebene Funktionen in eine neue Funktion umwandelt.
Demnach ist hier ein Parserkombinator eine Funktion, die aus mehreren Parsern einen neuen Parser erzeugt.

Abhängigkeiten

Laßt uns starten!
Zunächst muß ein Scalaprojekt erstellt werden. Die aktuelle Scalaversion 2.11.5 ist die Version unserer Wahl. Sehr einfach ist die Erstellung eines neuen Projektes über den Werkzeugkasten von Typesafe (Activator ).

Seit Scala 2.11 ist die „Scala Standard Parser Combinator Library“ Bibliothek nicht mehr Teil der Scala Standardbibliotheken, die automatisch mit Scala ausgeliefert werden. Sie muß als externes Jar nachgeladen werden.
Um die Bibliothek unserem Projekt zur Verfügung zu stellen, werden alle Abhängigkeiten, wie gewohnt, mit GroupId, ArtifactId und Version eingetragen. Zusätzlich wird noch ScalaTest mit aufgenommen, um unseren Parser anschließend testen zu können.
Die build.sbt sieht so aus:

1name := """ParserCombinator"""
2 
3version := "1.0"
4 
5scalaVersion := "2.11.5"
6 
7libraryDependencies ++= Seq(
8      "org.scalatest" %% "scalatest" % "2.1.6" % "test",
9      "org.scala-lang.modules" %% "scala-parser-combinators" % "1.0.2"
10)

Wir starten mit einem sehr einfachen Parser, um uns erstmal ein Bild von der neuen Herangehensweise zu machen.
„Ausgeliehen“ ist unser Beispiel zunächst von der offiziellen Scala Doku .
Der Parser soll ein Wort, bestehend aus Kleinbuchstaben, parsen können.
Dazu erstellen wir uns eine Klasse SimpleParser:

1package de.codecentric.wittig.scala.parser
2import scala.util.parsing.combinator._
3 
4class SimpleParser extends RegexParsers {
5  def word = """[a-z]+""".r ^^ { _.toString }
6}

Friemeln wir uns das mal auseinander:
Unser SimpleParser erbt von RegexParsers. Dieser bringt ein paar wichtige Methoden mit. Unter anderem existiert eine Methode parse, die wir später noch benutzen werden.
Der erste Teil der Methode word ist schnell erklärt:

1"""[a-z]+""".r

verwandelt den String [a-z]+ in ein Objekt vom Typ Regex. Wir hätten hier auch

1new Regex("[a-z]+")

anstattdessen schreiben können.
^^ kann eine Funktion übergeben werden, die genau dann ausgeführt wird, wenn das Parsen durch den Regex erfolgreich war. Wir nennen diese Funktion im Folgenden „Transformationsfunktion“, weil sie das Ergebnis entsprechend transformiert.
In unserem Fall wird also der Input in einen String transformiert/gemapped.

Aufruf des Parsers

Erstellen wir uns noch schnell eine Klasse, die den Parser aufruft:

1package de.codecentric.wittig.scala.parser
2import scala.util.parsing.combinator._
3 
4object Main extends SimpleParser with App {
5  val parsed = parse(word, "hallowelt")
6  println(parsed)
7}

Die Methode parse gibt ein ParseResult[String] zurück. In der Console sehen wir nun
[1.6] parsed: hallo welt
Das ist interessant: [1.6] sagt uns, dass von der 1. Position bis zur 6. Position gematcht wurde. Das wird uns später helfen die Korrektheit unseres Parsers besser prüfen und testen zu können.

Jetzt wird das ParseResult „entpackt“. Dafür stellt uns die Bibliothek die Klassen Success , Failure und Error zur Verfügung auf die wir case-matchen können:

1parsed match {
2    case Success(wordMatch, _) => println(wordMatch)
3    case Failure(txt, _)       => println(s"Fehler: $txt")
4    case Error(txt, _)         => println(s"Error: $txt")
5  }

1package de.codecentric.wittig.scala.parser
2import scala.util.parsing.combinator._
3 
4class SimpleParser extends RegexParsers {
5  def word = """[a-z]+""".r ^^ { _.toString }
6  def number = """(0|[1-9])*""".r ^^ { _.toInt }
7  def freq = word ~ ":" ~ number ^^ { case wd ~ f ~ nu => (wd, nu)}
8}

Hier wurde der Parser um zwei weiter Methoden erweitert: number und freq. Die Methode number unterscheidet sich nicht nicht stark von der Methode word, außer, dass sie einen anderen regulären Ausdruck benutzt, der auf numerische Werte matched.
Außerdem gibt diese Methode ein ParseResult[Int] zurück, da in der Transformationsfunktion das gematchte Ergebnis mit toInt in einen Integer umgewandelt wird.

Vom Lexer zum Parser

Etwas neues und einer besonderen Erklärung bedarf hier nun die Methode freq.
Was/Warum ist nun an dieser Methode anders?
Die beiden ersten Methoden word und number sind Lexermethoden, die die Wörter der Grammatik erkennen und gegebenenfalls transformieren.
Die Methode freq ist anstattdessen eine Kombinatormethode, die die Lexermethoden word und number kombiniert. Für die Kombination wird hier die Tilde ~ benutzt, mit der die sequentielle Abfolge der Grammatikwörter abgefragt wird. Auch diese Methode besitzt eine Transformationsfunktion, die für unser einfaches Beispiel ein Tupel zurückgibt.
Neben der Tilde gibt es noch eine Reihe von anderen Kombinationsmöglichkeiten. Hier eine Liste der wichtigsten Kombinatoren:

• | ist der „Oder“-Kombinator.
• ~ ist der „Sequenz“-Kombinator.
• ~> funktioniert wie der „Sequenz“-Kombinator, inkludiert aber nur den rechten Teil in das Ergebnis.
• <~ funktioniert wie der „Sequenz“-Kombinator, inkludiert aber nur den linken Teil in das Ergebnis.
• ^^ {function} ist der bereits bekannte „Transformations“-Kombinator.
• ^^^ {value} ist der „Ersetzer“-Kombinator. Hier wird das Ergebnis mit dem übergebenen Wert ersetzt.
• opt und ? ist der „Optionale“-Kombinator
• rep und * wird für Wiederholungen von Lexer- oder Kombinatormethoden benutzt.

Aufgerufen wird der Parser nun mit folgenden Zeilen:

1package de.codecentric.wittig.scala.parser
2import scala.util.parsing.combinator._
3 
4object Main extends SimpleParser with App {
5  val parsed = parse(freq, "hallowelt:8888")
6  println(parsed)
7}

Als Ergebnis sehen wir in der Konsole nun wir erwartet:
[1.15] parsed: (hallowelt,8888)

Fazit

Ziel des Artikel war es, die Grundidee der Funktionsweise von Parserkombinatoren vorzustellen. Mit diesem möglichst einfachen Beispiel wurde dieser Grundstein gelegt, sodass wir nächste Woche im zweiten Teil dieser Serie ein bisschen tiefer ins Details gehen können. Dort erstellen wir einen Parser für eine DSL, den wir elegant mit ScalaTest absichern werden.