Lexing and parsing

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:

debug = true

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

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. It is not spliced before the first part or after the last, so a grammar whose input may start or end with whitespace says so itself. Without the first TRIVIA? in the settings grammar, a leading comment fails:

document := entry* TRIVIA?

# service
port = 8080

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

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

@noskip turns skipping off for grammars where whitespace is syntax, and ~ is then an error.

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.

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

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

Engines

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