Lexing and parsing
Every Aether grammar runs in two stages. The lexer cuts the input into tokens, taking the longest match; the parser then matches rules over those tokens, taking the first alternative that fits.
Longest match
At each position the lexer tries every token the rules can reach and keeps the longest match. A tie goes to the token that comes first in the file. A quoted literal in a rule counts as declared where it first appears, and a token that matches nothing at all never wins.
In the settings grammar, true is both a TRUE and a NAME of the same length. TRUE is declared first, so debug = true works. Move TRUE and FALSE below NAME, and true becomes a name, which no value accepts:
debug = true
1:9: unexpected "true" -- expected one of: FALSE, NUMBER, STRING, TRUE 1 | debug = true | ^
Lexing happens before parsing, over the whole input, so the lexer cannot know which token the parser would want. A keyword that must not swallow longer words needs a lookahead, as in IF := "if" !ALNUM.
Ordered choice
In a rule, a | b tries a first, and if a matches, the choice is final — even if the rest of the input then fails:
A := "a" B := "b" s := pre B pre := A B | A
"abb" → ok "ab" → 1:3: unexpected end of input -- expected B
pre takes a b, and s finds no b left. Put the alternative that needs more context behind a lookahead, pre := A B &B | A, and both inputs match — or choose the GLR engine, which keeps both readings open.
Whitespace
With @skip TOKEN — or SPACE by default — that token may stand in front of every part of a rule after the first, and between repetitions. Around the input as a whole it is dropped: every engine trims skip tokens before the first token and after the last. That is why the settings grammar can say just document := entry* and still take a comment on the first line:
# service port = 8080
ok
This came with Ichor 0.4. Before it, a grammar whose input could begin or end with whitespace had to say so itself, usually as TRIVIA? … TRIVIA? around its root rule. That is still allowed, only no longer needed; since Ichor 0.6 Aether’s own grammar does without it too.
~ in front of a bare token or rule name forbids skipping at that one place, for parts that must touch:
@grammar "version" @root version NUMBER := DIGIT+ version := NUMBER "." ~NUMBER
"1.2" → ok "1 .2" → ok "1. 2" → 1:3: unexpected " " -- expected NUMBER
@noskip turns skipping off for grammars where whitespace is syntax, and ~ is then an error.
Under @engine lr and @engine glr the skip token is not placed into the rules at all: since Ichor 0.7.2 it is dropped from the token stream before parsing. The same inputs are accepted, captures keep their inner whitespace as under PEG (since 0.7.3), and a list between brackets such as "[" WORD* "]" no longer stalls the LR table on the skip token. Two things follow: a rule there cannot name the skip token itself, and ~ is refused there, since it could not keep anything out:
@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
Where whitespace matters to an LR grammar, it says @noskip and writes the whitespace out.
Captures
A capture names the part of a match that the code processing it will receive. key:NAME captures under key; a bare reference to a declared token or rule is captured under its own name without asking; a quoted literal is not captured unless named, because writing it bare is how a grammar says it does not care. A capture inside *, + or {…} always yields a list — empty, or with one element, but never a bare value and never nothing.
NUMBER := DIGIT+
expr := term (op:("+" | "-") term)*
term := NUMBER"1 + 2 - 3" → %{term: ["1", "2", "3"], op: ["+", "-"]}
"1" → %{term: ["1"], op: []}The results are the captures of the default tree, which Ichor builds when no actions module takes over; all three engines give the same. term captures only NUMBER, so its value is that one capture.
A rule that captures nothing at all is the text it matched, from its first token to its last. sign below has only bare literals, so its value is the sign itself. Up to Ichor 0.3 it was an empty node, and what it matched was lost. Whether a rule captures is decided by the grammar, never by the input.
@grammar "number" @root number NUMBER := DIGIT+ number := sign NUMBER sign := "+" | "-"
"-42" → %{sign: "-", NUMBER: "42"}name: over anything but a bare reference — a group, an optional part, a repetition — captures the text that part matched. A reference it wraps directly is captured under name only, never under its own name as well, so sign:sign? is one value. Where the optional part is absent, the value is empty text:
@grammar "number" @root number NUMBER := DIGIT+ number := sign:sign? NUMBER sign := "+" | "-"
"-42" → %{sign: "-", NUMBER: "42"}
"42" → %{sign: "", NUMBER: "42"}The captures inside a captured group are kept beside it:
WORD := ALPHA+ line := pair:(key:WORD "=" value:WORD)
"a = b" → %{value: "b", key: "a", pair: "a = b"}Every engine and both backends agree on both rules since Ichor 0.6. Before, the PEG backends also captured a wrapped reference under its own name, so sign:sign? came out as a list of two, and the LR and GLR engines dropped the captures inside a captured group.
Layout
For languages where indentation is structure, @indent(e) requires e to start at a column deeper than the current reference column and makes its own column the new reference; @samecol(e) requires e to start exactly at the reference column. Without an enclosing @indent, the reference column is 0. Both take a single term without parentheses too. This is from a YAML grammar in Ichor’s 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 | For |
|---|---|---|
@engine peg | ordered choice, top-down — the default | most grammars; direct left recursion is rewritten automatically |
@engine lr | shift-reduce over an SLR(1) table | left-recursive grammars; a conflict is a build error |
@engine glr | GLR, forking at conflicts | ambiguous grammars; ties go to declaration order, and shift beats reduce |
The engine only changes how rules are matched; tokens are lexed the same way. Rules for lr and glr may use sequence, choice, repetition, captures and references, but not &, !, @indent, @samecol or a rule-level @native — a parse table has no room for backtracking.
@grammar "sum" @root expr @engine lr NUMBER := DIGIT+ PLUS := "+" expr := expr PLUS term | term term := NUMBER
Generated ahead of time, with use Ichor or mix ichor.gen, a parser takes its engine from @engine, whichever it is. Interpreted, each engine has its own runner: Grammar.VM runs peg, Grammar.LR runs lr and Grammar.GLR runs glr. Given the grammar above, Grammar.VM refuses:
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
Error reports
When a PEG parse fails, Ichor reports the furthest token any alternative reached: what it found there and what would have been accepted. What a lookahead failed to match does not count, and input left over after a complete match is reported at its first token, not at the whitespace before it. With the expression grammar from captures:
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
This came with Ichor 0.7; before, a failed PEG parse said only that the root rule did not match, at the first token. The LR and GLR engines stop at the same token, but do not list what they expected:
@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
Errors from an actions module are placed too. Every capture carries where it matched as span, {line, column, length}, and so does a default node. An error that handle_rule/3 or handle_token/3 returns without a line is placed where its rule or token matched, and shown with that line and a caret. This action refuses settings it does not know, in the settings grammar:
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" | ^
For that entry, captures.key.span is {2, 1, 6}. Both backends and every engine place such errors since Ichor 0.6.