Lexen und Parsen

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:

debug = true

1:1: unexpected "debug" -- did not expect more input here
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"  → input does not match :s

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. Vor dem ersten und nach dem letzten Teil wird es nicht eingefügt; eine Grammatik, deren Eingabe mit Leerraum beginnen oder enden darf, sagt das also selbst. Ohne das erste TRIVIA? scheitert die Einstellungs-Grammatik an einem Kommentar am Anfang:

document := entry* TRIVIA?

# service
port = 8080

2:1: unexpected "port" -- did not expect more input here

~ 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"  → input does not match :version

@noskip schaltet das Überspringen für Grammatiken ab, in denen Leerraum Syntax ist; ~ ist dann ein Fehler.

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.

expr := term (op:("+" | "-") term)*

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:1: unexpected " " -- did not expect more input here
  host: x
 port: 1

Engines

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