Skip to content

b06.md

Latest commit

 

History

History
395 lines (312 loc) · 16.7 KB

b06.md

File metadata and controls

395 lines (312 loc) · 16.7 KB

Blatt 06: Visitor vs. Pattern Matching, Records

Zusammenfassung

Wir wollen eine kleine Songliste erstellen und nach unseren Lieblingssongs filtern.

Betrachten Sie dazu das Repo "Filter-DSL".

Basismodellierung

Die Songs werden über die Record-Klasse filter.model.MediaItem repräsentiert, die auch gleich noch Methoden zum Einlesen von Songs aus einer CSV-Datei bereitstellt:

public record MediaItem(String title, String artist, Genre genre, int year) {

    /** file system (e.g. JFileChooser) */
    public static List<MediaItem> loadFromPath(Path path);

    /** classpath resource (src/main/resources) */
    public static List<MediaItem> loadFromResource(String resourcePath);
}

Im Ressourcen-Verzeichnis src/main/resources/ liegt die Datei songlist.txt im CSV-Format, die bereits einige nette Songs enthält.

Zum Anzeigen der Liste gibt es eine kleine GUI: filter.app.FilterApp:

Filter-DSL

Die Suche erfolgt über eine kleine Filtersprache. Die Grammatik dazu finden Sie in Filter.g4. Darüber lassen sich verschiedene, unterschiedlich komplexe Suchausdrücke ("Queries") formulieren, beispielsweise:

  • artist == "Beatles"
  • year == 1965
  • artist == "Beatles" and year == 1965
  • genre in ("rock", "jazz") or year <= 1990 and not artist == "Beatles"
primary  : comparison | '(' expr ')' ;
comparison
         : IDENTIFIER op=COMPOP value=literal
         | IDENTIFIER IN '(' literal (',' literal)* ')'
         ;
literal  : STRING | NUMBER ;
COMPOP   : '==' | '!=' | '<' | '<=' | '>' | '>=' ;

Zum Bilden von Ausdrücken wird ein Feldname (z.B. artist, year) mit einem Wert verglichen: artist == "Beatles" oder year < 1965 oder ... Hierzu stehen die üblichen Vergleichsoperatoren zur Verfügung. Alternativ kann mit einem in-Ausdruck eine Variable mit den Werten in einer geklammerten Liste verglichen werden: genre in ("rock", "jazz", "metal", "grunge"). Der Ausdruck wird wahr, wenn die Variable genre einen der in der Liste aufgezählten Werte hat.

Ausdrücke können auch geklammert werden, d.h. (artist == "Beatles") ist ein gültiger Ausdruck.

expr    : orExpr ;

orExpr  : andExpr (OR andExpr)* ;
andExpr : notExpr (AND notExpr)* ;
notExpr : NOT notExpr | primary ;

Zum Bilden komplexerer Ausdrücke stehen zusätzlich noch die Operatoren or, and und not zur Verfügung:

  • or: Mit or lassen sich zwei oder mehr Ausdrücke ODER-verknüpfen, d.h. mindestens einer der verknüpften Teilausdrücke muss wahr sein, damit der gesamte Ausdruck wahr wird. Beispiel: artist == "Beatles" or year <= 1965
  • and: Mit and lassen sich zwei oder mehr Ausdrücke UND-verknüpfen, d.h. alle verknüpften Teilausdrücke müssen wahr sein, damit der gesamte Ausdruck wahr wird. Beispiel: year <= 1990 and artist == "Beatles"
  • not: Mit not wird ein Ausdruck negiert, d.h. der Ausdruck unter dem not muss falsch sein, damit der gesamte Ausdruck wahr wird. Beispiel: not artist == "Beatles"

Über die Grammatik Filter.g4 sind Vorrangregeln (Präzedenzregeln) für die Ausdrücke definiert. Am stärksten binden die Vergleichsoperatoren und die Klammern um Ausdrücke, gefolgt von not, and und or (in dieser Reihenfolge). Die scheinbar mehrdeutige Query genre in ("rock", "jazz") or year <= 1990 and not artist == "Beatles" entspricht also dieser geklammerten Variante (genre in ("rock", "jazz")) or ((year <= 1990) and (not (artist == "Beatles"))) (für eine visuelle Darstellung siehe den AST im nächsten Abschnitt).

Für diese Grammatik erzeugt uns ANTLR wieder einen Lexer und Parser sowie die Basisklassen für das Visitor-Pattern; die im Projekt vorbereitete build.gradle enthält bereits alle für dieses Blatt nötigen Dependencies und Plugins. Das Zusammenstecken der ANTLR-Klassen brauchen Sie nicht mehr erledigen: Es gibt in der Klasse filter.ast.builder.AstBuilders bereits die Methode FilterParser.QueryContext parse(String query), wo der Aufbau der verschiedenen generierten ANTLR-Klassen bereits erledigt ist, und die Sie nutzen können, um eine Query wie artist == "Beatles" zu parsen und in einen Parse-Tree zu verwandeln. Die Klasse bietet zusätzlich noch die Methode Expr fromQuery(String query, Function<FilterParser.QueryContext, Expr> translator) an, um in einem Schritt das Parsing zu erledigen und über den injizierten AstBuilderPattern oder AstBuilderVisitor einen deutlich reduzierten Baum (den sogenannten Abstract Syntax Tree, AST) zu erzeugen. Die Modellierung für den AST selbst ist ebenfalls bereits vorgegeben (Klassen im Package filter.ast.nodes).

AST

Der von ANTLR erzeugte Parse-Tree ist oft sehr groß und enthält in den einzelnen Zweigen jeweils alle dort durchlaufenen Regeln der Grammatik. Bei der späteren Verarbeitung stört das oft, so dass man aus dem Parse-Tree eine deutlich komprimierte Version für die weiteren Schritte erzeugt, den sogenannten "Abstract Syntax Tree" (AST).

Beispielsweise würde für den Filterausdruck genre in ("rock", "jazz") or year <= 1990 and not artist == "Beatles" und der Grammatik Filter.g4 der folgende Parse-Tree aufgebaut werden:

Bei genauerer Betrachtung stellt man fest, dass nach erfolgreichem Abschluss der Parsing-Phase viele der Zwischenknoten redundant oder überflüssig sind und man den Baum in eine deutlich kompaktere Form transformieren kann:

Or
  InList genre
    - "rock"
    - "jazz"
  And
    Comparison year <= 1990
    Not
      Comparison artist == "Beatles"

Die Modellierung des AST ist nicht trivial und hängt stark vom Verwendungszweck ab. Für uns in Prog2 sind die Klassen für den AST bereits vorgegeben im Package filter.ast.nodes:

package filter.ast.nodes;

public sealed interface Expr {
  record And(Expr left, Expr right) implements Expr {}
  record Or(Expr left, Expr right) implements Expr {}
  record Not(Expr inner) implements Expr {}
  record Comparison(String field, CompOp op, Value value) implements Expr {}
  record InList(String field, List<Value> values) implements Expr {}
}

public sealed interface Value {
  record Str(String text) implements Value {}
  record Num(int value) implements Value {}
}

public enum CompOp {
  EQ { public String toString() { return "=="; } },
  NE { public String toString() { return "!="; } },
  LT { public String toString() { return "<"; } },
  LE { public String toString() { return "<="; } },
  GT { public String toString() { return ">"; } },
  GE { public String toString() { return ">="; } };
}

Der gemeinsame Obertyp für alle Knoten im Baum ist Expr (Ausdruck). Es gibt die einzelnen Klassen zur Repräsentation der verschiedenen Ausdrücke in Expr. Die Kindknoten fast aller Baumknoten sind ihrerseits wieder vom Typ Expr, nur beim Knoten Comparison ist das rechte Kind ein Value (Wert). Es gibt zwei Arten von Werten in Value: Str und Num.

Damit lassen sich die Parse-Trees zu Filter.g4 in deutlich kompaktere Strukturen übersetzen mit gleichwertiger Bedeutung. Zwei Punkte verdienen besondere Beachtung:

  1. In der Grammatik können die and- und or-Ausdrücke mit beliebig vielen Vergleichen gebildet werden, d.h. year <= 1990, year <= 1990 and artist == "Beatles" und year <= 1990 and artist == "Beatles" and year > 1960 etc. wären gültige Ausdrücke. In der AST-Struktur haben die And- und Or-Knoten jeweils genau zwei Kindknoten. Dies muss passend übertragen werden:

    • Ein Kindknoten im and- oder or-Ausdruck: Comparison
    • Zwei Kindknoten im and- bzw. or-Ausdruck: And bzw. Or
    • Sonst: Geeignet klammern und dann in die And- bzw. Or-Knoten übersetzen, d.h. aus year <= 1990 and artist == "Beatles" and year > 1960 wird im AST (year <= 1990 and artist == "Beatles") and year > 1960

  2. Klammern werden nicht explizit im AST repräsentiert. Die Klammerung wird über die Tiefe im Baum ausgedrückt: Je weiter innen die Klammerung, um so tiefer im Baum taucht der Knoten auf. Beispiel:

    (year <= 1990 or artist == "Beatles") and year > 1960

    And
    Or
        Comparison year <= 1990
        Comparison artist == "Beatles"
    Comparison year > 1960

Den AST erhält man, indem man den Parse-Tree traversiert (Visitor-Pattern oder manuell über Pattern Matching) und dabei die kompaktere Baum-Version erzeugt. Dazu sind die Klassen filter.ast.builder.AstBuilderVisitor und filter.ast.builder.AstBuilderPattern angelegt. Diese fertig zu programmieren ist Ihre Aufgabe.

Pretty-Printing, Evaluierung und GUI

Im Package filter.ast.printer finden Sie einen vordefinierten Pretty-Printer AstPrinter, der einen AST mit der Methode String toString(Expr expr) in einen geklammerten String konvertiert. Diese Klasse können Sie gut bei den Approval Tests einsetzen.

Zusätzlich gibt es in filter.ast.eval einen Evaluator. Mit der Methode boolean matches(MediaItem item, Expr expr) wird geprüft, ob ein konkreter Song (MediaItem item) zu einer Query gegeben als AST (Expr expr) passt. Intern setzt dieser Evaluator zum Übersetzen der Query den filter.ast.builder.AstBuilderPattern ein.

Im Package filter.app gibt es eine fertige FilterApp. Dies ist eine Swing-GUI mit einem Menü zum Laden einer Textdatei mit Medien-Einträgen im CSV-Format und der Anzeige der Songs in einer editier- und sortierbaren Tabelle. Es gibt ein Eingabefeld für die Filter-Query. Die Treffer werden im Ergebnisbereich ausgegeben sowie in der Tabelle farblich hervorgehoben.

Important

Wichtig: Die Filterung in der Filter-App wird über den filter.ast.eval.Evaluator realisiert und funktioniert deshalb erst, wenn Sie den AST-Builder filter.ast.builder.AstBuilderPattern implementiert haben.

Wie wird aus Text ein Filter-Ausdruck?

Der Weg von der Texteingabe zum Evaluator ist:

  1. Lexer & Parser (ANTLR) aus String $\to$ FilterParser.QueryContext (Parse-Tree-Wurzel)
  2. AST-Builder aus FilterParser.QueryContext $\to$ Expr (Ihr eigener AST)
  3. Evaluator aus (MediaItem, Expr) $\to$ boolean (passt / passt nicht)

In dieser Übung geht es primär um Schritt 2: Wie übertrage ich die Parse-Tree-Struktur in die vorgegebenen AST-Strukturen?

Aufgaben

Aufgabe 1: JUnit-Testfälle

Bevor wir an die AST-Builder gehen, definieren Sie sich eine Reihe von relevanten Testfällen (JUnit). Nutzen Sie dazu die leere Klasse filter.ast.AstTest.

Aufgabe 2: AST-Builder mit dem Visitor-Pattern

Sie finden im Package filter.ast.builder die vorbereitete Klasse AstBuilderVisitor, die vom durch ANTLR generierten Basisvisitor FilterBaseVisitor<Void> ableitet und den AST durch den Einsatz des Visitor-Patterns erzeugt.

Die Startmethode Expr translate(FilterParser.QueryContext ctx) wird mit dem Parse-Tree als Argument aufgerufen und soll dann die rekursive Verarbeitung über das Visitor-Pattern anstoßen.

Die relevanten Methoden sind bereits vorgegeben - Füllen Sie diese nun noch mit Leben.

Tip

Hinweis: Implementieren Sie wie in der Vorlesung gezeigt einen zustandsbehafteten Visitor. Sie arbeiten entsprechend aktiv mit mehreren Stacks, beispielsweise Deque<Expr> und Deque<Value>. Prinzipiell ist der Ablauf pro Knoten ungefähr dieser: Sie besuchen rekursiv die Kindknoten eines Knotens, nehmen sich danach Objekte von den Stacks und verarbeiten diese Objekte und pushen das Ergebnis wieder auf den richtigen Stack.

Aufgabe 3: AST-Builder mit manueller Traversierung und typbasiertem Pattern Matching

Sie finden im Package filter.ast.builder die vorbereitete Klasse AstBuilderPattern, die eine manuelle Traversierung des Parse-Trees durchführen soll und dabei Pattern Matching auf Typen einsetzen soll und so den AST aufbaut. Die relevanten Methoden sind auch hier bereits vorgegeben, die Startmethode ist wieder Expr translate(FilterParser.QueryContext ctx). Implementieren Sie die vorgegebenen Methoden und nutzen Sie dabei nach Möglichkeit aktiv switch/case auf Klassen/Records/Enums.

Tip

Sie brauchen für den AstBuilderPattern keinen internen Zustand - es wird alles über die Argumente und Rückgabewerte der Methoden über- bzw. zurückgegeben. In den Methoden arbeiten Sie mit direkten Zugriffen auf die jeweiligen Kontext-Methoden.

Aufgabe 4: Vergleich Visitor-Pattern vs. Pattern Matching

Vergleichen Sie die beiden AST-Builder miteinander. Was sind aus Ihrer Sicht jeweils die Vor- und Nachteile der beiden Varianten?

Aufgabe 5: AST-Normalisierung mit Pattern Matching

Leider gibt die Form unserer Grammatik nicht so viel für Pattern Matching her, wie man sich für das Üben von Expression Switch/Case und Pattern Matching wünschen würde. Für eine geeignetere Grammatik bräuchten Sie tiefere Kenntnisse, die wir erst im dritten Semester in Compilerbau besprechen.

Damit Sie trotzdem noch ein wenig Pattern Matching üben können: Vervollständigen Sie bitte die Methode Expr simplify(Expr e) in der Klasse filter.ast.builder.AstBuilders. Schreiben Sie eine Abbildung AST $\to$ AST, die beispielsweise doppelte Not eliminiert. Nutzen Sie hier aktiv Pattern Matching und Expression Switch/Case. Denken Sie daran, dass unsere AST-Klassen eine sealed Klassenhierarchie sind und dass für die Modellierung Record-Klassen genutzt wurden - Zeigen Sie, wie Sie aktiv Dekonstruktion einsetzen!

Aufgabe 6: Approval Testing

Für das Überprüfen der durch die Builder generierten ASTs mit der Zielvorstellung ("Orakel") muss man das Orakel mühsam von Hand durch das verschachtelte Erzeugen von Objekten aufbauen. Beispielsweise wäre für die einfache Query artist == "Beatles" and year == 1965 der erwartete AST bereits recht umständlich formuliert:

var expr =
    new Expr.And(
        new Expr.Comparison("artist", CompOp.EQ, new Value.Str("Beatles")),
        new Expr.Comparison("year", CompOp.EQ, new Value.Num(1965)));

Hier bietet sich Approval Testing an - konvertieren Sie die von Ihren Buildern erzeugten Bäume mit Hilfe des vorimplementierten Printers filter.ast.printer.AstPrinter in einen String (Methode String toString(Expr expr)) und nutzen Sie Approval Testing für die Definition des Orakels. Setzen Sie dazu die Bibliothek ApprovalTests.Java ein.

Schreiben Sie sich verschiedene Approval Tests mit repräsentativen und unterschiedlich komplexen Query-Ausdrücken, und vergleichen Sie auch die beiden Builder-Varianten miteinander. Nutzen Sie die leere Klasse filter.ast.ApprovalTest.

Aufgabe 7: Property-based Testing

Formulieren Sie verschiedene Eigenschaften für die AST-Builder.

Beispielsweise sollte ein "Roundtrip" für jeweils beide Builder (individuell, aber auch gegenseitig verschränkt) möglich sein: Query -> Parsing -> AST -> Pretty-Print -> Parsing -> AST. Sie könnten mit einer festen, selbstdefinierten Query starten oder als Parameter für einen Property-Test mit jqwik die in der Klasse filter.ast.RoundtripPropertiesTest vordefinierten Arbitraries nutzen: @Property boolean foo(@ForAll("simpleQueries") String query) {...}.

Treffen Sie zusätzlich Annahmen über Expressions und Values, beispielsweise über die logischen Eigenschaften der AND-Verknüpfung.

Implementieren Sie diese Property Tests in der Klasse filter.ast.RoundtripPropertiesTest.

Bearbeitung und Abgabe

  • Bearbeitung: Einzelbearbeitung
  • Abgabe Post Mortem im ILIAS: bis 22. Juni, 08:00 Uhr
  • Vorstellung im Praktikum: 22./24. Juni

Unless otherwise noted, this work is licensed under CC BY-SA 4.0.

Last modified: 533f190 2026-06-15 b06: fix typos