Parser aus kontextfreien Grammatiken erzeugen mit Instaparse

Inhaltsverzeichnis

Instaparse ist eine Clojure-Bibliothek zum Schreiben von Parsern, die außerdem das Manipulieren und Erzeugen von Grammatiken zur Laufzeit ermöglicht. Das ergibt Chancen für interessante Anwendungen.

In vielen Bereichen der Programmierung haben standardisierte Formate Einzug gehalten und die noch vor einigen Jahren üblichen spezialisierten Textformate verdrängt. Programme verwenden für ihre Konfigurationen häufig Init- oder Properties-Dateien, REST-Services sprechen meist JSON, zum Speichern tabellarischer Daten bietet sich CSV an, und XML erscheint weiterhin allgegenwärtig.

Andere Bereiche verwenden nach wie die technisch gut untersuchten Parser. Dieser Artikel stellt einige solcher Beispiele vor und zeigt, dass Parser nicht nur für Erfinder neuer Programmiersprachen attraktiv sind.

Interessierte Leser können alle Beispiele des Artikels in einer interaktiven REPL-Sitzung nachvollziehen. Dazu ist es notwendig, ein Clojure-Projekt zu erzeugen, dessen Projektdefinition die Abhängigkeiten instaparse-1.3.2, org.clojure/data.xml-0.0.7 und rhizome-0.2.1 angibt. Mit Leiningen, dem gängigen Build-Werkzeug für Clojure-Projekte, erfolgt die Projektdefinition in einer Datei project.clj:

(defproject instant-spass "1.0" 
  :description "Heise Instaparse"
  :dependencies 
  [[org.clojure/clojure "1.6.0"]
   [org.clojure/data.xml "0.0.7"]
   [instaparse "1.3.2"]
   [rhizome "0.2.1"]])

Mit Leiningen lässt sich ein neues Projekt anlegen, in dem Anwender obige Projektdefinition verwenden und eine interaktive REPL starten:

shell> lein new instant-spass
;; project.clj anpassen...
shell> lein repl

Komfortablere Umgebungen bieten unter anderem Emacs mit CIDER, Eclipse mit Counterclockwise oder auch IntelliJ IDEA mit dem noch recht neuen Cursive an.

Die Formatierung der REPL-Beispiele orientiert sich an der in "The Joy of Clojure" etablierten Form, den Prompt für die Eingaben (etwa user>) nicht anzuzeigen, Ausgaben während der Ausführung als Kommentare (erkennbar am Semikolon) und den Rückgabewert einem ;=> folgend darzustellen. Zum Nachvollziehen der Beispiele ist eine Namespace-Deklaration erforderlich, die Instaparse und weitere Module zur Verfügung stellen. Im mit Leiningen erstellten Projekt bietet sich die automatisch erzeugte Datei src/instant-spass/core.clj an:

(ns instant-spass.core
  (:require 
    [instaparse.core :as i]
    [instaparse.combinators :as c]
    [clojure.xml :as xml]))

Im sich ergebenden Namespace instant-spass.core sind die wichtigsten Funktionen von Instaparse durch den Import des Namespace instaparse.core via :require mit dem Präfix i/ aufrufbar.

Leichte Unterhaltung

Zur Einführung dient eine Grammatik zum Parsen einfacher Sätze. Dazu definiert der folgende Code sowohl einen Beispielsatz als auch eine einfache kontextfreie Grammatik in Form eines String.

(def article-title
  "Instant-Spaß mit Instaparse.")

(def title-grammar-1
  "sentence = words dot
   dot      = '.'
   words    = word (space word)*
   space    = ' '
   word     = #'(?U)\\w+'")

Die Produktionsregel sentence ist definiert als words gefolgt von dot. Die Definition von dot geschieht in der zweiten Produktion als ein literaler Punkt. Damit ist dot ein terminales Symbol. Da die
Definition in Form von Strings erfolgt, für die die doppelten Anführungszeichen eingebetteter Strings zu maskieren sind, erlaubt Instaparse die Angabe von Strings mit einfachen Anführungszeichen. Das erleichtert die Lesbarkeit der Grammatik ganz erheblich.

In der dritten Regel definiert die Grammatik das nichtterminale Symbol words als ein word optional gefolgt von beliebig vielen Vorkommen der Kombination space und word. Das terminale Symbol space ist als Leerzeichen definiert, und für word verwendet die Grammatik einen regulären Ausdruck.

Diese in der Grammatik zu nutzen, ist eine praktische Erweiterung von Instaparse. Die Notation orientiert sich an der Syntax regulärer Ausdrücke in Clojure und darf ebenfalls mit einfachen Anführungszeichen erfolgen. Die regulären Ausdrücke in Java unterstützen seit Java 7 die Erweiterung der Zeichenklasse für Wortzeichen (\w) auf alle Unicode-Zeichen durch Angabe von (?U).

Die folgende einfache Hilfsfunktion reicht eine als Argument übergebene Grammatik an die Funktion i/parser weiter und erzeugt so einen Parser, der sich wie eine Clojure-Funktion aufrufen lässt. Das erklärt das zusätzliche Paar Klammern: Der Rückgabewert von (i/parser grammar), der aufrufbare Parser, wird wie eine Funktion verwendet.

(defn test-title-parser [grammar title]
  ((i/parser grammar) title))

Das Ergebnis des Parse-Vorgangs ist ein Vektor, in dem die Symbole aus der kontextfreien Grammatik in Keywords, erkennbar am Doppelpunkt, erscheinen.

(test-title-parser title-grammar-1
                   article-title)
;=> [:sentence
     [:words
      [:word "Instant"]
      [:space " "]
      [:word "Spaß"]
      [:space " "]
      [:word "mit"]
      [:space " "]
      [:word "Instaparse"]]
     [:dot "."]]

Häufig sind Anwender an verschiedenen Symbolen der Grammatik nicht interessiert. Für solche Fälle hält Instaparse eine Syntax mit spitzen Klammern parat, die in der Grammatik angeben, welche Teile im Ergebnis zu unterdrücken sind. Je nachdem, ob die spitzen Klammern links oder rechts vom Gleichheitszeichen auftauchen, wird Instaparse entweder den Namen des Symbols, die gefundenen Daten oder beides filtern. Im letzteren Fall entfällt der komplette Vektor für die Produktionsregel. Der folgende Parser unterdrückt den literalen Punkt, das Symbol :dot hingegen ist weiterhin Bestandteil des Ergebnisses. Leerzeichen (space) ignoriert der Parser komplett. Dadurch wird das Resultat deutlich kompakter, und eine weitere Verarbeitung müsste weniger Aufwand betreiben, die relevanten Daten aus dem Resultat zu extrahieren.

(def title-grammar-2
  "sentence = words dot
   dot      = <'.'>
   words    = word (space word)*
   <space>  = <' '>
   <word>   = #'(?U)\\w+'")

(test-title-parser title-grammar-2
                   article-title)
;=> [:sentence 
     [:words "Instant" "Spaß" "mit"
      "Instaparse"] 
     [:dot]]