Antra
/

Themen

PEG-Grammatiken mit Antra::PEG

Antra::PEG bringt Parsing Expression Grammars im Janet-Stil nach Antra. Die Grundideen, viele Operatoren und die allgemeine Arbeitsweise sind dabei zu großen Teilen von Janet übernommen und dann auf normale Antra-Datenstrukturen abgebildet.

Wenn du die Ursprungsquelle ansehen willst: die Sprache selbst steht unter janet-lang.org, und die PEG-Dokumentation ist unter janet-lang.org/docs/peg.html zu finden.

Die Grammatik selbst ist dabei kein Sonderformat, sondern einfach ein normaler Antra-Wert: eine Map aus Regeln, Arrays, Keywords, Strings, Zahlen und Character-Ranges.

import Antra::PEG as PEG

const grammar = %{
    main: [:sequence, "hello", -1]
}

println(PEG.match(grammar, "hello"))

Das Ergebnis ist bei Erfolg der Capture-Stack als Array, sonst undef.

Wenn du lieber im normalen Antra-Stil mit %Ok[...] und %Err[...] arbeiten willst, gibt es zusätzlich PEG.match_result(...):

println(PEG.match_result(grammar, "hello"))
println(PEG.match_result(grammar, "hellx"))

Diese Variante liefert %Ok[captures] bei Erfolg und %Err[message] bei Fehlschlag.

Für Byte-Parsing gibt es zusätzlich PEG.match_bytes(...). Diese Variante arbeitet nicht auf normalen Strings, sondern auf ByteString-Werten aus Antra::Bytes.

Wenn du mit PEGs noch gar keine Erfahrung hast, lies vorher oder parallel das Tutorial in 25-peg-tutorial-fuer-einsteiger.md.

Grundidee#

Eine Grammatik ist eine Map mit benannten Regeln. Der Einstiegspunkt ist immer die Regel :main.

const grammar = %{
    main: [:sequence, :word, ":", :word, -1],
    word: [:some, :w]
}

Regelreferenzen passieren über Keywords wie :word oder :main.

Wichtig zur Syntax in Antra#

Janet zeigt PEG-Beispiele oft s-expression-artig mit Leerzeichen:

(sequence (some :w) ":" (some :d))

In Antra wird dasselbe als normales Array mit Kommas geschrieben:

[:sequence, [:some, :w], ":", [:some, :d]]

Das ist die wichtigste Übersetzungshilfe: Janet-Operatoren bleiben als Keywords erkennbar, aber die umgebende Form ist normale Antra-Datenstruktur-Syntax.

Primitive Patterns#

Strings#

Strings matchen exakt und case-sensitiv.

"cat"

Positive Integers#

Eine positive Zahl konsumiert blind genau so viele Zeichen.

3

-1 für End-of-Input#

-1 matcht nur dann, wenn der gesamte Resttext bereits verbraucht ist.

[:sequence, "abc", -1]

Wenn du Vollverbrauch willst, hängst du -1 typischerweise ans Ende von :main.

Character-Ranges#

Character-Ranges verwenden Einzelzeichen-Strings als Endpunkte.

'a'..'z'
'0'..'9'

Sie matchen genau ein Zeichen im angegebenen Bereich.

Regex-Primitiv#

Wenn du an der aktuellen Position einen bereits kompilierten Regex pruefen willst, kannst du :regex verwenden.

[:regex, regex"[0-9]+"]

Wichtig dabei:

  • :regex ist nur fuer Text-PEGs gedacht
  • der Match ist an der aktuellen Position verankert
  • das Primitiv legt selbst keine Captures an

Wenn du den gematchten Text im Ergebnis haben willst, kombinierst du es wie gewohnt mit [:capture, ...]:

[:capture, [:regex, regex"[0-9]+"]]

Benannte Regex-Gruppen werden auf PEG-Ebene aktuell noch nicht als eigene User-Surface exportiert. Eine moegliche spaetere Erweiterung dafuer ist [:capture_named, [:regex, ...]], aber das ist derzeit nur als Vorschlag in specs/spec_peg_capture_named.md beschrieben und nicht Teil der aktuellen implementierten PEG-Doku.

Eingebaute Zeichenklassen#

Wenn ein Keyword nicht auf eine benutzerdefinierte Regel zeigt, prüft Antra::PEG die eingebauten Klassen aus der PEG-Spezifikation:

  • :a - alphanumerisch (A-Z, a-z, 0-9)
  • :d - Ziffern
  • :w - Buchstaben
  • :s - Whitespace
  • :h - hexadezimale Zeichen
  • :g - druckbare ASCII-Zeichen

Wichtig: Diese Zuordnung folgt der hier eingeführten Antra-Spezifikation, nicht der Janet-Default-Tabelle. Insbesondere ist hier :a alphanumerisch und :w steht nur für Buchstaben.

Kombinatoren#

Sequenz und Choice#

[:sequence, a, b, c]
[:*, a, b, c]

[:choice, a, b, c]
[:+, a, b, c]

:+ probiert Alternativen von links nach rechts. Wie bei Janet ist PEG-Matching gierig und hat kein allgemeines Backtracking; die Reihenfolge der Alternativen entscheidet also.

Wiederholung#

[:any, x]
[:some, x]
[:opt, x]
[:?, x]
[:repeat, 3, x]
[:between, 1, 5, x]

[:any, x] schlägt nie fehl. [:some, x] verlangt mindestens einen Treffer.

Lookahead#

[:not, x]
[:!, x]
[:if, cond, patt]

Diese Formen konsumieren den Lookahead selbst nicht. :if prüft cond an der aktuellen Position und matcht erst dann patt.

Suchen im Text#

[:to, x]
[:thru, x]

[:to, x] konsumiert bis direkt vor den Treffer von x, [:thru, x] konsumiert den Treffer mit.

Commit mit :cut#

[:cut]

[:cut] setzt in einem begonnenen Branch einen Commit-Punkt. Wenn danach in diesem Branch später ein Match fehlschlägt, probiert [:choice, ...] keine spätere Alternative mehr.

Das ist nützlich, wenn du nach einem klaren Präfix weißt: Ab hier sind wir im richtigen Ast, also soll bei Fehlern lieber eine präzise Diagnose kommen als stilles Zurückfallen auf andere Alternativen.

Beispiel:

const grammar = %{
    main: [:+,
        [:sequence, "a", [:cut], [:expect, "b", "letter b"], -1],
        [:sequence, "a", "c", -1]
    ]
}

Auf Eingabe "ac" verhindert [:cut], dass nach dem Präfix "a" noch in die zweite Alternative zurückgewechselt wird.

Captures#

Captures schreiben Werte auf einen internen Capture-Stack. Genau dieser Stack wird von PEG.match(...) zurückgegeben.

Text capturen#

[:capture, patt]
[:<-, patt]

Das Ergebnis ist der exakt konsumierte Textabschnitt als String.

Gruppen#

[:group, patt]

Alle tieferen Captures aus patt werden in ein Unter-Array gepackt.

Position und Konstanten#

[:position]
[:constant, :done]

[:position] legt die aktuelle Byte-/Zeichenposition als Integer auf den Stack, [:constant, v] legt einen statischen Wert ab.

Binary-Parsing mit ByteString#

Für binärorientierte Daten gibt es einen zweiten Einstieg:

import Antra::PEG as PEG
import Antra::Bytes as Bytes

my data = Bytes.from_hex("504b54314f4b30303432")

Gematcht wird dann mit PEG.match_bytes(...) statt PEG.match(...):

const grammar = %{
    main: [:sequence,
        [:capture, [:bytes, 4]],
        [:capture, [:bytes, 2]],
        [:capture, [:bytes, 4]],
        -1
    ]
}

println(PEG.match_bytes(grammar, data))

Das Ergebnis enthält bei [:capture, [:bytes, n]] dann ByteString-Werte statt normaler Strings.

Auch hier gibt es eine Result-Variante:

println(PEG.match_bytes_result(grammar, data))

Das ist besonders praktisch, wenn ein falscher Eingabetyp oder ein Parsefehler nicht als Ausnahme hochfliegen, sondern als normaler Wert weitergegeben werden soll.

Fehlerdiagnosen#

PEG.match(...) und PEG.match_bytes(...) bleiben absichtlich minimal. Bei Fehlschlag geben sie einfach undef zurück.

Für bessere Diagnosen nutzt du PEG.match_result(...) oder PEG.match_bytes_result(...). Diese APIs merken sich den weitesten bekannten Fehlschlag und bauen daraus eine Fehlermeldung.

Bei Text-Eingaben enthält die Meldung:

  • Zeile
  • Spalte
  • Offset
  • erwartete Eingabe
  • gefundene Eingabe

Zusätzlich wird eine kleine Zeilenansicht mit Caret eingebettet.

Bei match_bytes_result(...) gibt es statt Zeile/Spalte einen Byte-Offset und den gefundenen Hex-Wert.

Erste Byte-Primitiven#

Die erste Version unterstützt diese binären PEG-Operatoren:

  • [:bytes, n] - konsumiert genau n Bytes
  • [:byte, n] - matcht genau ein Byte mit dem Wert n
  • [:u8] - liest ein Byte und legt den Integer auf den Capture-Stack
  • [:u16be] - liest 2 Bytes big-endian und legt den Integer auf den Stack
  • [:u16le] - liest 2 Bytes little-endian und legt den Integer auf den Stack
  • [:u32be] - liest 4 Bytes big-endian und legt den Integer auf den Stack
  • [:u32le] - liest 4 Bytes little-endian und legt den Integer auf den Stack
  • [:u64be] - liest 8 Bytes big-endian und legt den Integer auf den Stack
  • [:u64le] - liest 8 Bytes little-endian und legt den Integer auf den Stack
  • [:cstring] - liest Bytes bis zum Null-Byte und legt einen ByteString auf den Stack
  • [:take, patt] - liest erst mit patt eine Längenangabe und danach genau so viele Bytes als ByteString

Wichtig:

  • Diese Operatoren funktionieren nur in PEG.match_bytes(...).
  • In normalem PEG.match(...) bleiben Grammatik und Captures textorientiert.
  • String-Literale in match_bytes(...) werden als UTF-8-Bytes verglichen.

Length-Prefixed Daten mit :take#

[:take, patt] ist für typische Binärformate gedacht, bei denen erst eine Länge und dann ein Payload kommt.

Beispiel mit 16-Bit-Big-Endian-Länge:

import Antra::PEG as PEG
import Antra::Bytes as Bytes
import Antra::Bytes as B

const grammar = %{
    main: [:sequence, [:take, [:u16be]], -1]
}

my %Ok[result] = PEG.match_bytes_result(grammar, Bytes.from_hex("000548656c6c6f"))
println(result[0])
println(B.to_string(result[1]))

Das Ergebnis ist dann zuerst die gelesene Länge und danach der entnommene ByteString.

Ersetzen / Transformieren#

[:replace, patt, |x| -> num(x)]

patt wird normal gematcht. Danach werden die dabei entstandenen Captures an die Funktion übergeben, und deren Rückgabewert ersetzt die alten Captures.

Erwartete Fehler klar benennen#

[:expect, patt, "heading text"]

[:expect, ...] ist für bessere Fehlermeldungen gedacht. Das Pattern patt wird normal gematcht. Wenn es fehlschlägt, wird in der Result-Fehlermeldung nicht nur ein technisches Detail, sondern die angegebene Erwartung verwendet.

Das ist vor allem zusammen mit PEG.match_result(...) nützlich, zum Beispiel:

const grammar = %{
    main: [:sequence,
        [:some, "#"],
        [:expect, " ", "space after heading markers"],
        [:expect, [:some, :w], "heading text"],
        -1
    ]
}

Damit wird aus einem rohen Parsefehler eine deutlich verständlichere Diagnose.

Rekursive Grammatiken#

Wie in Janet liegt die eigentliche Stärke in benannten Regeln und Rekursion.

const grammar = %{
    pair: [:group, [:sequence, [:capture, [:some, :w]], ":", [:capture, :value]]],
    value: [:+, :number, [:some, :w]],
    number: [:sequence, [:opt, [:+, "+", "-"]], [:some, '0'..'9']],
    main: [:sequence, :pair, -1]
}

Regeln dürfen sich gegenseitig referenzieren. Die Implementierung ist rekursiv; sehr tiefe oder schlecht geschriebene Grammatiken können daher wie bei Janet Stack oder Laufzeit belasten.

Komplettes Beispiel#

import Antra::PEG as PEG

const kv_grammatik = %{
    main: [:some, [:sequence, :paar, [:any, [:+, ",", :s]]]],
    paar: [:group, [:sequence, [:capture, [:some, :w]], ":", [:any, :s], [:capture, :wert]]],
    wert: [:+, :zahl, [:some, :w]],
    zahl: [:sequence, [:opt, [:+, "+", "-"]], [:some, '0'..'9']]
}

my daten = PEG.match(kv_grammatik, "User: admin, ID: 105")
println(daten)

Ergebnis:

[["User", "admin"], ["ID", "105"]]

CSV-Beispiel Schritt für Schritt#

Ein gutes PEG-Beispiel ist CSV, weil man daran sofort sieht, warum PEGs mehr leisten als simples split(",").

Das Problem ist: Kommas sind normalerweise Trenner, aber innerhalb von Quotes plötzlich normaler Inhalt.

Name,Beruf
"Müller, Hans",Entwickler

Wenn man hier stumpf auf Kommas splittet, bekommt man bei "Müller, Hans" das falsche Ergebnis.

Die einfache CSV-Grammatik aus dem Beispiel trennt das deshalb in drei Ebenen:

  • main liest mehrere Zeilen
  • zeile liest mehrere Felder plus Zeilenende
  • feld unterscheidet zwischen quoted und unquoted Text
const csv_grammatik = %{
    main: [:sequence, [:some, :zeile], -1],

    zeile: [:group, [:sequence,
        :feld,
        [:any, [:sequence, ",", :feld]],
        [:+, "\r\n", "\n"]
    ]],

    feld: [:+, :escaped_text, :normal_text],

    escaped_text: [:sequence,
        '"',
        [:capture, [:to, '"']],
        '"'
    ],

    normal_text: [:capture, [:any, [:sequence,
        [:not, [:+, ",", '"', "\n", "\r"]],
        1
    ]]]
}

Wichtig daran:

  • :group macht aus jeder Zeile ein eigenes Unter-Array
  • :capture sammelt nur den eigentlichen Feldinhalt
  • [:to, '"'] liest in quoted fields bis direkt vor das schließende Quote

Für dieses einfache Beispiel reicht das schon für eine tabellenartige Struktur:

[["Name", "Beruf"], ["Müller, Hans", "Entwickler"]]

Mathe-Beispiel Schritt für Schritt#

Ein anderes gutes PEG-Beispiel ist ein Mathe-Ausdruck wie:

5 * (3 + 2) - 8 / 4

Hier reicht es nicht, einfach nur Zahlen und Operatoren zu erkennen. Wir wollen auch die Struktur verstehen:

  • was gehört zusammen?
  • was steckt in Klammern?
  • was bindet stärker?

Darum ist die Grammatik in Ebenen aufgebaut:

  • summe für + und -
  • produkt für * und /
  • faktor für Zahlen oder Klammern
const mathe_grammatik = %{
    main: [:sequence, :summe, -1],

    summe: [:+,
        [:replace, [:sequence,
            :produkt,
            [:any, :s],
            [:capture, [:+, "+", "-"]],
            [:any, :s],
            :summe
        ], |lhs, op, rhs| -> mk_bin(lhs, op, rhs)],
        :produkt
    ],

    produkt: [:+,
        [:replace, [:sequence,
            :faktor,
            [:any, :s],
            [:capture, [:+, "*", "/"]],
            [:any, :s],
            :produkt
        ], |lhs, op, rhs| -> mk_bin(lhs, op, rhs)],
        :faktor
    ],

    faktor: [:+, :zahl, :klammer]
}

Das Entscheidende ist hier nicht nur das Matchen, sondern :replace:

  • Zahlen werden direkt zu %Num[...]
  • Operator-Knoten werden direkt zu %Add[...], %Sub[...], %Mul[...], %Div[...]

So entsteht direkt ein einfacher AST statt nur einer Liste von Strings.

Für den Beispielausdruck ergibt das etwa:

[%Sub[%Mul[%Num[5], %Add[%Num[3], %Num[2]]], %Div[%Num[8], %Num[4]]]]

Das ist als Beispiel besonders nützlich, weil man daran sieht, dass PEGs nicht nur Text erkennen, sondern beim Parsen auch direkt strukturierte Werte bauen können.

Aktueller Stand in Antra#

Der aktuelle Umfang von Antra::PEG deckt den umgesetzten Kern aus der Spezifikation ab:

  • String-, Integer-, -1- und Character-Range-Primitives
  • Built-ins :a, :d, :w, :s, :h, :g
  • :sequence / :*, :choice / :+, :any, :some, :opt / :?, :repeat, :between
  • :to, :thru, :not / :!, :if
  • :capture / :<-, :group, :position, :constant, :replace

Noch nicht umgesetzt sind die weitergehenden Janet-Features wie peg/compile, look, if-not, backref, backmatch, drop, only-tags, line, column, argument, accumulate, cmt, Binär-Integer-Captures oder number-/lenprefix-Helfer.

Quelle dieser Seite