Lexen und Parsen
Jede Aether-Grammatik läuft in zwei Stufen. Der Lexer zerlegt die Eingabe in Tokens und nimmt die längste Übereinstimmung; der Parser erkennt dann Regeln über diesen Tokens und nimmt die erste passende Alternative.
Längste Übereinstimmung
An jeder Stelle probiert der Lexer jedes Token, das die Regeln erreichen können, und behält die längste Übereinstimmung. Bei Gleichstand gewinnt das Token, das in der Datei zuerst steht. Ein Literal in einer Regel gilt dort als deklariert, wo es zuerst vorkommt, und ein Token, das gar nichts erfasst, gewinnt nie.
In der Einstellungs-Grammatik ist true sowohl ein TRUE als auch ein gleich langer NAME. TRUE ist zuerst deklariert, also funktioniert debug = true. Stehen TRUE und FALSE unter NAME, wird true zum Namen, und den nimmt kein value an:
debug = true
1:9: unexpected "true" -- expected one of: FALSE, NUMBER, STRING, TRUE 1 | debug = true | ^
Gelext wird vor dem Parsen, über die ganze Eingabe; der Lexer kann also nicht wissen, welches Token der Parser gern hätte. Ein Schlüsselwort, das keine längeren Wörter verschlucken darf, braucht eine Vorausschau wie in IF := "if" !ALNUM.
Geordnete Auswahl
In einer Regel probiert a | b zuerst a, und passt a, ist die Auswahl endgültig — auch wenn der Rest der Eingabe danach scheitert:
A := "a" B := "b" s := pre B pre := A B | A
"abb" → ok "ab" → 1:3: unexpected end of input -- expected B
pre nimmt a b, und s findet kein b mehr. Mit einer Vorausschau vor der Alternative, die mehr Kontext braucht, pre := A B &B | A, passen beide Eingaben — oder man wählt die GLR-Engine, die beide Lesarten offenhält.
Leerraum
Mit @skip TOKEN — oder standardmäßig SPACE — darf dieses Token vor jedem Teil einer Regel außer dem ersten stehen und zwischen Wiederholungen. Rund um die ganze Eingabe fällt es weg: Jede Engine entfernt Skip-Tokens vor dem ersten und nach dem letzten Token. Deshalb genügt der Einstellungs-Grammatik ein schlichtes document := entry*, und sie nimmt trotzdem einen Kommentar in der ersten Zeile:
# service port = 8080
ok
Das kam mit Ichor 0.4. Vorher musste eine Grammatik, deren Eingabe mit Leerraum beginnen oder enden durfte, das selbst sagen, meist als TRIVIA? … TRIVIA? um ihre Wurzelregel. Das ist weiterhin erlaubt, nur nicht mehr nötig; seit Ichor 0.6 kommt auch Aethers eigene Grammatik ohne aus.
~ vor einem bloßen Token- oder Regelnamen verbietet das Überspringen an genau dieser Stelle, für Teile, die aneinanderstoßen müssen:
@grammar "version" @root version NUMBER := DIGIT+ version := NUMBER "." ~NUMBER
"1.2" → ok "1 .2" → ok "1. 2" → 1:3: unexpected " " -- expected NUMBER
@noskip schaltet das Überspringen für Grammatiken ab, in denen Leerraum Syntax ist; ~ ist dann ein Fehler.
Unter @engine lr und @engine glr wird das Skip-Token gar nicht erst in die Regeln eingefügt: Seit Ichor 0.7.2 fällt es vor dem Parsen aus dem Token-Strom. Es werden dieselben Eingaben akzeptiert, Erfassungen behalten ihren inneren Leerraum wie unter PEG (seit 0.7.3), und eine Liste zwischen Klammern wie "[" WORD* "]" bringt die LR-Tabelle nicht mehr am Skip-Token zum Stehen. Daraus folgt zweierlei: Eine Regel kann das Skip-Token dort nicht selbst nennen, und ~ wird dort abgelehnt, weil es nichts heraushalten könnte:
@grammar "version" @root version @engine lr NUMBER := DIGIT+ version := NUMBER "." ~NUMBER
5:24: ~ cannot keep the @skip token out under @engine lr, which drops skip tokens from the stream before parsing -- use @engine peg, or @noskip and write the skip token out
Wo Leerraum für eine LR-Grammatik zählt, sagt sie @noskip und schreibt den Leerraum aus.
Erfassungen
Eine Erfassung benennt den Teil einer Übereinstimmung, den der weiterverarbeitende Code erhält. key:NAME erfasst unter key; ein bloßer Verweis auf ein deklariertes Token oder eine Regel wird ungefragt unter dem eigenen Namen erfasst; ein Literal in Anführungszeichen wird nur erfasst, wenn es benannt ist — es nackt zu schreiben ist genau die Art, wie eine Grammatik sagt, dass es ihr egal ist. Eine Erfassung innerhalb von *, + oder {…} ergibt immer eine Liste — leer oder mit einem Element, aber nie einen nackten Wert und nie nichts.
NUMBER := DIGIT+
expr := term (op:("+" | "-") term)*
term := NUMBER"1 + 2 - 3" → %{term: ["1", "2", "3"], op: ["+", "-"]}
"1" → %{term: ["1"], op: []}Die Ergebnisse sind die Erfassungen des Standardbaums, den Ichor baut, wenn kein Actions-Modul übernimmt; alle drei Engines liefern dasselbe. term erfasst nur NUMBER, sein Wert ist also diese eine Erfassung.
Eine Regel, die gar nichts erfasst, ist der Text, den sie erkannt hat, vom ersten bis zum letzten Token. sign unten hat nur nackte Literale, sein Wert ist also das Vorzeichen selbst. Bis Ichor 0.3 war es ein leerer Knoten, und was es erkannt hatte, ging verloren. Ob eine Regel erfasst, entscheidet die Grammatik, nie die Eingabe.
@grammar "number" @root number NUMBER := DIGIT+ number := sign NUMBER sign := "+" | "-"
"-42" → %{sign: "-", NUMBER: "42"}name: vor etwas anderem als einem bloßen Verweis — einer Gruppe, einem optionalen Teil, einer Wiederholung — erfasst den Text, den dieser Teil erkannt hat. Ein Verweis, den es direkt umschließt, wird nur unter name erfasst, nie zusätzlich unter seinem eigenen Namen; sign:sign? ist also ein Wert. Fehlt der optionale Teil, ist der Wert leerer Text:
@grammar "number" @root number NUMBER := DIGIT+ number := sign:sign? NUMBER sign := "+" | "-"
"-42" → %{sign: "-", NUMBER: "42"}
"42" → %{sign: "", NUMBER: "42"}Die Erfassungen innerhalb einer erfassten Gruppe bleiben daneben erhalten:
WORD := ALPHA+ line := pair:(key:WORD "=" value:WORD)
"a = b" → %{value: "b", key: "a", pair: "a = b"}Seit Ichor 0.6 sind sich jede Engine und beide Backends in beiden Punkten einig. Vorher erfassten die PEG-Backends einen umschlossenen Verweis zusätzlich unter seinem eigenen Namen, sodass sign:sign? als Liste mit zwei Einträgen herauskam, und die LR- und GLR-Engines verwarfen die Erfassungen innerhalb einer erfassten Gruppe.
Layout
Für Sprachen, in denen Einrückung Struktur ist, verlangt @indent(e), dass e in einer tieferen Spalte als der aktuellen Bezugsspalte beginnt, und macht seine eigene Spalte zur neuen Bezugsspalte; @samecol(e) verlangt, dass e genau in der Bezugsspalte beginnt. Ohne umschließendes @indent ist die Bezugsspalte 0. Beide nehmen auch einen einzelnen Term ohne Klammern. Dies stammt aus einer YAML-Grammatik in Ichors Tests:
mapping := pair (NEWLINE @samecol pair)* pair := SCALAR COLON (inline_value | NEWLINE @indent(block_value))
server: → ok host: x port: 1 server: → 3:2: unexpected "port" -- expected NEWLINE host: x port: 1
Engines
| Pragma | Parser | Für |
|---|---|---|
@engine peg | geordnete Auswahl, top-down — der Standard | die meisten Grammatiken; direkte Linksrekursion wird automatisch umgeschrieben |
@engine lr | Shift-Reduce über einer SLR(1)-Tabelle | linksrekursive Grammatiken; ein Konflikt ist ein Build-Fehler |
@engine glr | GLR, verzweigt an Konflikten | mehrdeutige Grammatiken; Gleichstände entscheidet die Deklarationsreihenfolge, und Shift schlägt Reduce |
Die Engine ändert nur, wie Regeln erkannt werden; Tokens werden gleich gelext. Regeln für lr und glr dürfen Folge, Auswahl, Wiederholung, Erfassungen und Verweise nutzen, aber kein &, !, @indent, @samecol und kein @native auf Regelebene — eine Parse-Tabelle hat keinen Platz für Backtracking.
@grammar "sum" @root expr @engine lr NUMBER := DIGIT+ PLUS := "+" expr := expr PLUS term | term term := NUMBER
Vorab generiert, mit use Ichor oder mix ichor.gen, übernimmt ein Parser seine Engine aus @engine, welche es auch ist. Interpretiert hat jede Engine ihren eigenen Runner: Grammar.VM führt peg aus, Grammar.LR lr und Grammar.GLR glr. Mit der Grammatik oben lehnt Grammar.VM ab:
Grammar.VM.parse(sum, "1 + 2")
this grammar is tagged @engine lr -- Grammar.VM only runs @engine peg grammars; use Grammar.LR/Grammar.GLR instead
Fehlermeldungen
Scheitert ein PEG-Parse, meldet Ichor das am weitesten entfernte Token, das irgendeine Alternative erreicht hat: was dort stand und was angenommen worden wäre. Was eine Vorausschau nicht erkannt hat, zählt nicht mit, und Eingabe, die nach einer vollständigen Übereinstimmung übrig bleibt, wird an ihrem ersten Token gemeldet, nicht am Leerraum davor. Mit der Ausdrucks-Grammatik aus Erfassungen:
NUMBER := DIGIT+
expr := term (op:("+" | "-") term)*
term := NUMBER"1 + " → 1:5: unexpected end of input -- expected NUMBER "1 2" → 1:3: unexpected "2" -- expected one of: "+", "-" "+ 1" → 1:1: unexpected "+" -- expected NUMBER
Das kam mit Ichor 0.7; vorher sagte ein gescheiterter PEG-Parse nur, dass die Wurzelregel nicht passt, und zwar am ersten Token. Die LR- und GLR-Engines halten am selben Token an, zählen aber nicht auf, was sie erwartet hätten:
@engine lr
NUMBER := DIGIT+
expr := term (op:("+" | "-") term)*
term := NUMBER"1 + " → 1:5: unexpected end of input "1 2" → 1:3: unexpected "2" -- did not expect more input here
Auch Fehler aus einem Actions-Modul bekommen eine Position. Jede Erfassung trägt als span mit, wo sie erkannt wurde, {zeile, spalte, länge}, und ebenso ein Standardknoten. Ein Fehler, den handle_rule/3 oder handle_token/3 ohne Zeile zurückgibt, wird dort platziert, wo seine Regel oder sein Token erkannt wurde, und mit dieser Zeile und einem Caret gezeigt. Diese Action lehnt Einstellungen ab, die sie nicht kennt, in der Einstellungs-Grammatik:
def handle_rule(:entry, captures, ctx) do
{:ok, %{key: key, value: value}, ctx} = Ichor.Actions.eval_all(captures, ctx)
if key in ~w(port debug name),
do: {:ok, {key, value}, ctx},
else: {:error, Ichor.Error.new(message: "unknown setting #{inspect(key)}", stage: :action)}
endport = 8080 colour = "red"
2:1: unknown setting "colour" 2 | colour = "red" | ^
Für diesen Eintrag ist captures.key.span gleich {2, 1, 6}. Beide Backends und jede Engine platzieren solche Fehler seit Ichor 0.6.