Parserkombinatoren in Java

parser.java

/*
Parserkombinatoren in Java
angelehnt an Kap. 8 "Fallstudie: Parserkombinatoren"
siehe https://docs.google.com/file/d/0B10KTl9VYQT0SEtTcWlYUk5NaUU/edit?usp=sharing
- mit Tests, arbeitet mit immutablen Daten
- Lazy-Parser für rekursive Grammatiken
- Tag-Parser zur Annotation von Grammatiken
*/

import java.util.*;
import java.util.function.*;
import java.util.stream.*;

List<Character> str2lst(String s) {
    List<Character> lst = new ArrayList<>();
    for (char c : s.toCharArray()) {
        lst.add(c);
    }
    return Collections.unmodifiableList(lst);
}

sealed interface Parser<T>
    permits Success, Fail, Item, Or, Maybe, And, Many, More, Lazy,
            Drop, Tag {
        Result<T> parse(List<T> lst);
}

record Result<T>(Optional<List<Object>> recognized, List<T> rest) {
    static <T> Result<T> of(List<Object> recognized, List<T> rest) {
        if (recognized == null) return new Result<T>(Optional.empty(), rest);
        return new Result<T>(Optional.of(recognized), rest);
        
    }
    Result<T> andThen(Result<T> other) {
        if (this.hasFailed() || other.hasFailed())
            return new Fail<T>().parse(List.<T>of()); // unknown original parse input
        List<Object> combinedRecognized = new ArrayList<>();
        combinedRecognized.addAll(this.recognized().get());
        combinedRecognized.addAll(other.recognized().get());
        return new Result<T>(Optional.of(Collections.unmodifiableList(combinedRecognized)),
                             other.rest());
    }
    boolean hasFailed() { return recognized().isEmpty(); }
    boolean hasNotFailed() { return !hasFailed(); }
};

record Success<T>() implements Parser<T> {
    public Result<T> parse(List<T> lst) {
        return Result.<T>of(List.of(), lst);
    }
}

record Fail<T>() implements Parser<T> {
    public Result<T> parse(List<T> lst) {
        return Result.<T>of(null, lst);
    }
}

record Item<T>(T itm) implements Parser<T> {
    public Result<T> parse(List<T> lst) {
        if (lst.isEmpty() || !lst.get(0).equals(itm))
            return new Fail<T>().parse(lst);
        return Result.<T>of(List.of(itm),
                            Collections.unmodifiableList(lst.subList(1, lst.size())));
    }
}

record Or<T>(Parser<T>... parsers) implements Parser<T> {
    public @SafeVarargs Or { } // needed to suppress compiler warning
    public Result<T> parse(List<T> lst) {
        return Arrays.stream(parsers)
            .map(p -> p.parse(lst))
            .filter(Result<T>::hasNotFailed)
            .findFirst()
            .orElseGet(() -> new Fail<T>().parse(lst));
    }
}

record Maybe<T>(Parser<T> parser) implements Parser<T> {
    public Result<T> parse(List<T> lst) {
        return new Or<T>(parser, new Success<T>()).parse(lst);
    }
}

record And<T>(boolean strict, Supplier<Stream<Parser<T>>> parsers) implements Parser<T> {
    public @SafeVarargs And(boolean strict, Parser<T>... parsers) {
        this(strict, () -> Arrays.<Parser<T>>stream(parsers));
    }
    public @SafeVarargs And(Parser<T>... parsers) {
        this(true, parsers);
    }
    public Result<T> parse(List<T> lst) {
        Result<T> res = new Success<T>().parse(lst);
        Result<T> preliminaryRes;
        Iterable<Parser<T>> iterableParsers = () -> parsers.get().iterator();
        for (Parser<T> parser : iterableParsers) {
            preliminaryRes = res.andThen(parser.parse(res.rest()));
            if (preliminaryRes.hasFailed()) {
                if (strict) return new Fail<T>().parse(lst);
                break;
            }
            res = preliminaryRes;
        }
        return res;
    }
}

record Many<T>(Parser<T> parser) implements Parser<T> {
    public Result<T> parse(List<T> lst) {
        return new And<T>(false, () -> Stream.<Parser<T>>generate(() -> parser)).parse(lst);
    }
}

record More<T>(Parser<T> parser) implements Parser<T> {
    public Result<T> parse(List<T> lst) {
        return new And<T>(parser, new Many<T>(parser)).parse(lst);
    }
}

record Lazy<T>(Supplier<Parser<T>> parser) implements Parser<T> {
    public Result<T> parse(List<T> lst) {
        return parser.get().parse(lst);
    }
}

record Drop<T>(Parser<T> parser) implements Parser<T> {
    public Result<T> parse(List<T> lst) {
        Result<T> res = parser.parse(lst);
        if (res.hasNotFailed()) return new Success<T>().parse(res.rest());
        return res;
    }
}

record Tag<T>(String tag, Parser<T> parser) implements Parser<T> {
    public Result<T> parse(List<T> lst) {
        Result<T> res = parser.parse(lst);
        if (res.hasFailed()) return res;
        return Result.<T>of(List.of(tag, res.recognized().get()), res.rest());
    }
}

// Tests for Item
assert new Item<Character>('a').parse(str2lst("")).equals(
    new Fail<Character>().parse(str2lst(""))) : "Item fails on empty input";
assert new Item<Character>('a').parse(str2lst("bcd")).equals(
    new Fail<Character>().parse(str2lst("bcd"))) : "Item simply fails";
assert new Item<Character>('a').parse(str2lst("abcd")).equals(
    Result.<Character>of(List.<Object>of('a'), str2lst("bcd"))) : "Item recognizes 'a'";

// Tests for Or
assert new Or<Character>(new Item<Character>('a'), new Item<Character>('b')).
    parse(str2lst("cde")).equals(
        new Fail<Character>().parse(str2lst("cde"))) : "Or fails altogether";
assert new Or<Character>(new Item<Character>('a'), new Item<Character>('b')).
    parse(str2lst("")).equals(
        new Fail<Character>().parse(str2lst(""))) : "Or fails on empty input";
assert new Or<Character>(new Item<Character>('a'), new Item<Character>('b')).
    parse(str2lst("acde")).equals(
        Result.<Character>of(List.<Object>of('a'), str2lst("cde"))) : "Or recognizes 'a'";
assert new Or<Character>(new Item<Character>('a'), new Item<Character>('b')).
    parse(str2lst("bcde")).equals(
        Result.<Character>of(List.<Object>of('b'), str2lst("cde"))) : "Or recognizes 'b'";

// Tests for And (strict)
assert new And<Character>(new Item<Character>('a'), new Item<Character>('b')).
    parse(str2lst("cde")).equals(
        new Fail<Character>().parse(str2lst("cde"))) : "And_strict fails altogether";
assert new And<Character>(new Item<Character>('a'), new Item<Character>('b')).
    parse(str2lst("acde")).equals(
        new Fail<Character>().parse(str2lst("acde"))) : "And_strict fails on 'b'";
assert new And<Character>(new Item<Character>('a'), new Item<Character>('b')).
    parse(str2lst("")).equals(
        new Fail<Character>().parse(str2lst(""))) : "And_strict fails on empty input";
assert new And<Character>(new Item<Character>('a'), new Item<Character>('b')).
    parse(str2lst("abcde")).equals(
        new Result<Character>(Optional.<List<Object>>of(List.of('a', 'b')), str2lst("cde"))) : "And_strict recognizes 'a' and 'b'";

// Tests for And (relaxed)
assert new And<Character>(false, new Item<Character>('a'), new Item<Character>('b')).
    parse(str2lst("")).equals(
        new Success<Character>().parse(str2lst(""))) : "And_relaxed no match on empty input";
assert new And<Character>(false, new Item<Character>('a'), new Item<Character>('b')).
    parse(str2lst("cde")).equals(
        new Success<Character>().parse(str2lst("cde"))) : "And_relaxed no match";
assert new And<Character>(false, new Item<Character>('a'), new Item<Character>('b')).
    parse(str2lst("acde")).equals(
        new Item<Character>('a').parse(str2lst("acde"))) : "And_relaxed one match";
assert new And<Character>(false, new Item<Character>('a'), new Item<Character>('b')).
    parse(str2lst("abcde")).equals(
        new And<Character>(new Item<Character>('a'), new Item<Character>('b')).parse(str2lst("abcde"))) : "And_relaxed two matches";

// Tests for Many
assert new Many<Character>(new Item<Character>('a')).parse(str2lst("")).equals(
    new Success<Character>().parse(str2lst(""))) : "Many no match on empty input";
assert new Many<Character>(new Item<Character>('a')).parse(str2lst("b")).equals(
    new Success<Character>().parse(str2lst("b"))) : "Many no match";
assert new Many<Character>(new Item<Character>('a')).parse(str2lst("ab")).equals(
    new Item<Character>('a').parse(str2lst("ab"))) : "Many one match";
assert new Many<Character>(new Item<Character>('a')).parse(str2lst("aab")).equals(
    new And<Character>(new Item<Character>('a'), new Item<Character>('a')).parse(str2lst("aab"))) : "Many two matches";

// Tests for More
assert new More<Character>(new Item<Character>('a')).parse(str2lst("")).equals(
    new Fail<Character>().parse(str2lst(""))) : "More no match on empty input";
assert new More<Character>(new Item<Character>('a')).parse(str2lst("b")).equals(
    new Fail<Character>().parse(str2lst("b"))) : "More no match";
assert new More<Character>(new Item<Character>('a')).parse(str2lst("ab")).equals(
    new Item<Character>('a').parse(str2lst("ab"))) : "More one match";
assert new More<Character>(new Item<Character>('a')).parse(str2lst("aab")).equals(
    new And<Character>(new Item<Character>('a'), new Item<Character>('a')).parse(str2lst("aab"))) : "More two matches";

// Tests for Drop
assert new Drop<Character>(new Item<Character>('a')).parse(str2lst("abc")).equals(
    new Success<Character>().parse(str2lst("bc"))) : "Drop dropped match";
assert new Drop<Character>(new Item<Character>('a')).parse(str2lst("bc")).equals(
    new Fail<Character>().parse(str2lst("bc"))) : "Drop had no match";
assert new Drop<Character>(new Item<Character>('a')).parse(str2lst("")).equals(
    new Fail<Character>().parse(str2lst(""))) : "Drop had no match on empty input";

// USING PARSER COMBINATORS

/* Anwendungsbeispiele:
jshell> new Item<Character>('a').parse(List.of('a','b','c'))
$19 ==> Result[recognized=Optional[[a]], rest=[b, c]]

jshell> new Item<Character>('a').parse(List.of('b','c'))
$20 ==> Result[recognized=Optional.empty, rest=[b, c]]

jshell> new Or<Character>(new Item<Character>('a'), new Item<Character>('b')).parse(str2lst("abcd"))
$22 ==> Result[recognized=Optional[[a]], rest=[b, c, d]]

jshell> new Or<Character>(new Item<Character>('a'), new Item<Character>('b')).parse(str2lst("bacd"))
$23 ==> Result[recognized=Optional[[b]], rest=[a, c, d]]

jshell> new Or<Character>(new Item<Character>('a'), new Item<Character>('b')).parse(str2lst("cd"))
$24 ==> Result[recognized=Optional.empty, rest=[c, d]]
*/

// A SIMPLE GRAMMAR

Parser<Character> p = new More<Character>(new Item<Character>('a'));

Parser<Character> sign = new Or<Character>(new Item<Character>('+'), new Item<Character>('-'));
Parser<Character> dig1_9 = new Or<Character>(
    new Item<Character>('1'),
    new Item<Character>('2'),
    new Item<Character>('3'),
    new Item<Character>('4'),
    new Item<Character>('5'),
    new Item<Character>('6'),
    new Item<Character>('7'),
    new Item<Character>('8'),
    new Item<Character>('9')
);
Parser<Character> dig0_9 = new Or<Character>(new Item<Character>('0'), dig1_9);
Parser<Character> integer = new And<Character>(
    new Maybe<Character>(sign), dig1_9, new Many<Character>(dig0_9)
);

Parser<Character> integer0 = new Or<Character>(new Item<Character>('0'), integer);

// integer0.parse(str2lst("123"))
// ==> Result[recognized=Optional[[1, 2, 3]], rest=[]]

assert integer0.parse(str2lst("12")).equals(
    Result.<Character>of(List.of('1', '2'), List.of())) : "integer0 gets 12";
assert integer0.parse(str2lst("12ab")).equals(
    Result.<Character>of(List.of('1', '2'), List.of('a', 'b'))) : "integer0 gets 12 and rest";
assert integer0.parse(str2lst("-12")).equals(
    Result.<Character>of(List.of('-', '1', '2'), List.of())) : "integer0 gets -12";
assert integer0.parse(str2lst("+12")).equals(
    Result.<Character>of(List.of('+', '1', '2'), List.of())) : "integer0 gets +12";
assert integer0.parse(str2lst("01")).equals(
    Result.<Character>of(List.of('0'), List.of('1'))) : "integer0 gets 0";
assert integer0.parse(str2lst("+0")).equals(
    new Fail<Character>().parse(str2lst("+0"))) : "integer0 rejects +0";
assert integer0.parse(str2lst("-0")).equals(
    new Fail<Character>().parse(str2lst("-0"))) : "integer0 rejects -0";

// RECURSIVE GRAMMAR

Parser<Character> aParser;
Parser<Character> bParser;
aParser = new And<Character>(new Item<Character>('a'), new Lazy<Character>(() -> new Many<Character>(bParser)));
bParser = new And<Character>(new Item<Character>('b'), new Lazy<Character>(() -> new Many<Character>(aParser)));

// jshell> aParser.parse(str2lst("abba"))
// ==> Result[recognized=Optional[[a, b, b, a]], rest=[]]
// jshell> aParser.parse(str2lst("aabbaa"))
// $34 ==> Result[recognized=Optional[[a]], rest=[a, b, b, a, a]]

assert aParser.parse(str2lst("abba")).equals(
    Result.<Character>of(List.<Object>of('a','b','b','a'), List.<Character>of())) : "aParser matches abba";
assert aParser.parse(str2lst("aabbaa")).equals(
    Result.<Character>of(List.of('a'), str2lst("abbaa"))) : "aParser matches abba";

// ANNOTATED GRAMMAR

Parser<Character> flt = 
    new And<>(integer0,
              new Item<>('.'),
              new More<>(dig0_9));

Parser<Character> fltTagged = 
    new Tag<>("float", new And<>(
        new Tag<>("left", integer0),
        new Drop<>(new Item<>('.')),
        new Tag<>("right", new More<>(dig0_9))));

/*
jshell> flt.parse(str2lst("123.45"))
$48 ==> Result[recognized=Optional[[1, 2, 3, ., 4, 5]], rest=[]]

jshell> fltTagged.parse(str2lst("123.45"))
$49 ==> Result[recognized=Optional[[float, [left, [1, 2, 3], right, [4, 5]]]], rest=[]]
 */

assert flt.parse(str2lst("3.45")).equals(
    new And<Character>(
        new Item<Character>('3'),
        new Item<Character>('.'),
        new Item<Character>('4'),
        new Item<Character>('5')).parse(str2lst("3.45"))) : "float parser without tags";
assert fltTagged.parse(str2lst("3.45")).toString().equals(
    "Result[recognized=Optional[[float, [left, [3], right, [4, 5]]]], rest=[]]") : "float parser tagged";

System.out.println("Tests completed!");

In meinem Buch "Funktionale Programmierung mit Clojure" (hier frei zum Download) behandle ich in Kapitel 8 als Fallstudie Parserkombinatoren. Mit den jüngeren Sprachfeatures von Java (Datenklassen und Sealed Interfaces) gelingt der Nachbau relativ gut. Warum mir Parserkombinatoren so gut als Anschauungsbeispiel in Java gefallen? Es kommen viele fortgeschrittene Programmierkonzepte bzw. Sprachkonstrukte von Java zum Einsatz: Datenklassen, Sealed Interfaces, Streams, Optional, Lambda-Ausdrücke, Iterable, @SafeVarargs, generische Programmierung, Lösung von forward referencing durch Laziness.

Was ich bei der Umsetzung gelernt habe:

• Datenklassen, also Records, sind ein sehr schönes Sprachfeature, das die Ausdrucksstärke des Codes erhöht und ihn kürzer macht.
• Sealed Interfaces helfen sehr bei der Modellierung von Datentypen
• Die Parser werden über den Konstruktor in den Datenklassen konfiguriert und die Kombination in der parse-Methode umgesetzt; das ist die OO-Variante im Vergleich zu den rein funktionalen Parser-Kombinatoren.
• Beim kombinierten Gebrauch von Records und Sealed Interfaces liefert der Compiler im Fehlerfall teils Hinweise, die einen auf eine völlig falsche Fährte bringen können. Denn ein Typfehler in einem implementierenden Record verletzt schlussendlich das Sealed Interface. Man muss die Compilerhinweise durchsuchen, um zum eigentlichen Anlass für den Fehler vorzudringen.
• Da ich hauptsächlich mit der JShell programmiere: Nach solchen Fehlermeldungen ist ein /reset ein Muss, sonst kommt die JShell vollkommen durcheinander. Auch lohnt sich hier die Überprüfung während der Entwicklung mit /types, ob es in den Datentypen keine offene Referenzen gibt
• Java bietet nur rudimentäre Operationen für immutable Datentypen an (Beispiel: List.of(1,2,3)). Die Parser gehen stets von immutablen Listen aus, verwenden zur Konstruktion neuer Listen mutable Listen (ArrayList) und markieren diese dann mittels Collections.unmodifiableList() als immutabel. Dieses Vorgehen scheint mir ein guter Kompromiss zu sein bei der unzureichenden Unterstützung für Immutabilität.
• Über die Versionen hinweg habe ich die Result-Datenklasse durch andThen mit der Fähigkeit ausgestattet, zwei Parse-Ergebnisse zu kombinieren. Damit ist der Code in den Parsern "sauberer" geworden und die innere strukturelle Gleichheit vom And-Parser und dem Many-Parser ist noch deutlicher hervorgetreten, was zu einem Refactoring geführt hat. Nun nutzt der Many-Parser den And-Parser zur Umsetzung. Dafür waren zwar einige Umbauten am And-Parser erforderlich, aber das war zuliebe des Prinzips "Don't Repeat Yourself" (DRY) nötig.
• Der Lazy-Parser ist sehr einfach zu ergänzen gewesen und löst das Problem des forward referencing bei rekursiven Grammatiken sehr elegant
• Der Drop-Parser ist dazu da, um Parser-Ergebnisse zu verwerfen; seine Implementierung ist trivial.
• Für den Tag-Parser dient zur Annotation von Parser-Ergebnissen in recognized. Ich habe mich dazu entschieden, bei recognized mit List<Object> zu arbeiten, um nahe bei der Clojure-Vorlage zu bleiben. Ganz ideal ist das nicht, da man mit Object die Typdifferenzierung in der Liste aufgibt. Im Gegenzug bekommt man eine schlanke Umsetzung geschenkt.

Ein paar Anmerkungen zum And und zum Many-Parser:

Schielt man auf die Clojure-Implementierung im Clojure-Buch (S. 94), dann kann der Many-Parser den Code des And-Parsers wiederverwenden; in Clojure habe ich den more-Parser mit and-lazy realisiert.

(defn more [parser] (apply and-lazy (cycle [parser])))

1. In Clojure ist der "Trick", aus dem parser-Argument für Many mit cycle [parser] einen unendlich lange "Argumentkette" zu erzeugen. Dadurch, dass der And-Parser einen Strom an Parsern erwartet, ist dieses Verhalten mit einem Generator nachbildbar. Die Idee entspricht dem folgenden, einfachen Beispiel:

for(Integer i : (Iterable<Integer>)(() -> IntStream.range(0,10).iterator()))
    System.out.println(i);

2. Der And-Parser muss für den Many-Parser nicht strikt auf die Passung aller Argumente bestehen. Hier wird solange nach einer Passung gesucht, bis der unendlich generierende parser-Strom einen Misserfolg hat. Ist das boolsche Flag strict auf false gesetzt, greift die "relaxte" Suche nach Passungen. Das entspricht dem and-lazy in Clojure. Die for-Schleife im And-Parser lässt sich nicht in praktikabler Weise durch einen Stream ersetzen. Das liegt daran, dass sich die Stromverarbeitung nicht aus z.B. einem reduce heraus abbrechen lässt. Es gibt keine Möglichkeit, Ströme "kurz zu schließen" und vorzeitig von "innen" heraus abzubrechen.