Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

Syntax.Cursor

The mechanical half of recursive descent: a token cursor with peek, advance, and expect, and a Pratt driver over a binding-power table.

Deliberately not a combinator library. There is no alternation operator, no backtracking engine, no grammar vocabulary; a caller writes the grammar by hand, in ordinary functions, and hands this module the two things a hand-written parser gets subtly wrong. The first is span arithmetic: joining two spans, covering a consumed run, and pointing a caret at a position where nothing was read. The second is expectation merging: unmet expectations join a set held at the furthest token the cursor ever reached, so a refusal names every alternative tried at the position the parse died at rather than only the last one attempted. Rewinding is where that record is classically lost, so rewinding is a named operation (cursor_restore) that returns the position and keeps the record.

Expectations are token wire names, the vocabulary of Syntax.Token, and a refusal renders as a Syntax.Diagnostic under the compiler’s own parse codes. A parser built on this cursor therefore reports through the same document every other syntax fault does, with no error type of its own.

Types

Cursor

type Cursor = Cursor {
  toks: Array(Token),
  pos: Int,
  stop: Int,
  far: Int,
  wanted: List(String)
}

A token cursor: the tokens being read, the read position, the byte offset the end-of-input caret points at, and the failure record (the furthest position at which an expectation was recorded, and the names recorded there). The failure record is part of the cursor rather than of a failure value because it must outlive every failure a parse recovers from.

Reply

type Reply(a) = Took(a, Cursor) | Stuck(Cursor)

The reply of a cursor step: the value and the advanced cursor, or the cursor alone. A refusal still carries a cursor, because the failure record it accumulated is the part worth reporting.

Assoc

type Assoc = ALeft | ARight | ANone deriving (Eq)

How an infix operator groups a chain of its own level. A non-associative operator declines a second application at its level, leaving the second operator unconsumed for the caller to refuse.

Infix

type Infix = Infix { op: String, level: Int, assoc: Assoc }

One infix operator: the token spelling, its level (higher binds tighter), and how it associates.

Prefix

type Prefix = Prefix { op: String, level: Int }

One prefix operator: the token spelling and the level its operand is parsed at. An operator that binds tighter than that level is pulled into the operand; one that binds looser takes the prefix application as its left operand.

Pratt

type Pratt(a) = Pratt {
  infixes: List(Infix),
  prefixes: List(Prefix),
  leaf: (Cursor) -> Reply(a),
  bin: (String, a, a) -> a,
  pre: (String, a) -> a
}

Everything the driver needs that is not the cursor: the two operator tables, the leaf parser, and the two node builders. The leaf parser owns primaries, and so owns parentheses, and so owns the recursion back into the driver: the driver knows about operators and nothing else.

Functions and Values

span_join

span_join : (Syntax.Source.Span, Syntax.Source.Span) -> Syntax.Source.Span

The smallest span covering both: the earlier start and the later end. The one operation a parser needs to give a node built from parts the extent of those parts.

let s = span_join(span_at(2), span_at(11))
(s.lo, s.hi)

(2, 11)

span_at

span_at : (Int) -> Syntax.Source.Span

The empty span at a byte offset: the caret a diagnostic points with when it has a position but nothing was consumed there.

let s = span_at(12)
(s.lo, s.hi)

(12, 12)

span_cover

span_cover : (List(Syntax.Source.Span)) -> Option(Syntax.Source.Span)

The smallest span covering every span in the list, or None for the empty list. Joining has no identity over spans (the empty span at offset zero is a position, not a neutral element), so the empty case is absent rather than invented.

cursor_of

cursor_of : (List(Syntax.Token.Token), Int) -> Syntax.Cursor.Cursor

A cursor over a token list. stop is the byte offset the end-of-input caret points at, normally the length of the source the tokens were lexed from, so a refusal past the last token still carries a position.

cursor_count

cursor_count : (Syntax.Cursor.Cursor) -> Int

The number of tokens the cursor reads over.

cursor_at_end

cursor_at_end : (Syntax.Cursor.Cursor) -> Bool

Whether every token has been consumed.

cursor_peek_at

cursor_peek_at : (Syntax.Cursor.Cursor, Int) -> Option(Syntax.Token.Token)

The token k positions ahead of the read position, or None past the end.

cursor_peek

cursor_peek : (Syntax.Cursor.Cursor) -> Option(Syntax.Token.Token)

The token at the read position, or None at the end. Peeking never consumes and never records an expectation: a parser that looks before it leaps says what it wanted with cursor_note.

cursor_kind

cursor_kind : (Syntax.Cursor.Cursor) -> Option(Syntax.Token.TokenKind)

The kind of the token at the read position, or None at the end.

cursor_span

cursor_span : (Syntax.Cursor.Cursor) -> Syntax.Source.Span

The span the cursor points at: the next token’s span, or the end-of-input caret when the stream is exhausted.

cursor_advance

cursor_advance : (Syntax.Cursor.Cursor) -> Syntax.Cursor.Cursor

The cursor advanced past one token. At the end this is the identity, so a parser that advances on a token it did not check cannot run off the stream.

cursor_since

cursor_since : (Syntax.Cursor.Cursor, Syntax.Cursor.Cursor) -> Syntax.Source.Span

The span covering the tokens consumed between saved and c, or the caret at the current position when nothing was consumed. A parser gives a node its extent by saving the cursor before it and asking for the run after it, rather than by joining the spans of its parts by hand and forgetting the delimiters.

end_of_input

end_of_input : () -> String

The name the end of the token stream is expected under. Not a token, so not a token kind, but an expectation like any other.

cursor_note_name

cursor_note_name : (Syntax.Cursor.Cursor, String) -> Syntax.Cursor.Cursor

Record name as admissible at the read position, consuming nothing.

The record only ever moves forward. A name recorded past the furthest position reached replaces the set and moves the mark; a name at the furthest position joins the set; a name behind it is dropped. That ordering is the whole point: a parse that tries an alternative, gets three tokens deep and fails, then rewinds, must still report what was wanted three tokens in, not what was wanted at the place it rewound to.

cursor_note

cursor_note : (Syntax.Cursor.Cursor, Syntax.Token.TokenKind) -> Syntax.Cursor.Cursor

Record a token kind as admissible at the read position. The name recorded is the kind’s wire name, so an expectation set, a token artifact, and a diagnostic’s expected field all speak one vocabulary.

cursor_expect

cursor_expect : (Syntax.Cursor.Cursor, Syntax.Token.TokenKind) -> Syntax.Cursor.Reply(Syntax.Token.Token)

Consume the next token when its kind is k. On a mismatch nothing is consumed and k joins the expectation set at this position, so a parser that tries several kinds in turn accumulates all of them: expecting one of a set is spelled as expecting each of its members at one position, never as a separate combinator.

cursor_expect_fixed

cursor_expect_fixed : (Syntax.Cursor.Cursor, String) -> Syntax.Cursor.Reply(Syntax.Token.Token)

Consume the next token when it is the fixed token spelled s.

cursor_expect_end

cursor_expect_end : (Syntax.Cursor.Cursor) -> Syntax.Cursor.Reply(Unit)

Require that every token has been consumed, recording the end of the stream as the expectation when one is left over.

cursor_restore

cursor_restore : (Syntax.Cursor.Cursor, Syntax.Cursor.Cursor) -> Syntax.Cursor.Cursor

Rewind to a saved cursor while keeping the failure record reached since.

A parser that tries an alternative and gives it up restores with this: the position returns, the expectations do not. Rebuilding the saved cursor by hand instead is the classic way to report the expectations of the position the parse retreated to rather than of the position it died at.

let c0 = cursor_of(Nil, 0)
let c1 = cursor_note_name(c0, "ident")
str_join(", ", cursor_expected(cursor_restore(c0, c1)))

ident

cursor_expected

cursor_expected : (Syntax.Cursor.Cursor) -> List(String)

The names recorded at the furthest position reached, in the order they were first recorded.

let c = cursor_note_name(cursor_of(Nil, 3), "ident")
str_join(", ", cursor_expected(cursor_note_name(c, "int")))

ident, int

cursor_canonical

cursor_canonical : (Syntax.Cursor.Cursor) -> List(String)

The canonical expectation set of a refusal: the recorded names deduplicated and byte-lexicographically sorted, so the set a diagnostic carries does not depend on the order alternatives were tried, and a harmless reordering of a parser’s branches moves no artifact bytes.

let c = cursor_note_name(cursor_of(Nil, 3), "int")
str_join(", ", cursor_canonical(cursor_note_name(c, "ident")))

ident, int

cursor_far_span

cursor_far_span : (Syntax.Cursor.Cursor) -> Syntax.Source.Span

The span the failure record points at: the token at the furthest position reached, or the end-of-input caret.

cursor_message

cursor_message : (Syntax.Cursor.Cursor) -> String

The rendered message of an unmet expectation: the merged expectation set and what stood there instead.

parse_syntax_code

parse_syntax_code : () -> String

The compiler’s general parse-fault code, the one home for the string on this side of the seam.

parse_eof_code

parse_eof_code : () -> String

The compiler’s exhausted-stream code: the token stream itself ended while the parser wanted more.

cursor_code

cursor_code : (Syntax.Cursor.Cursor) -> String

The stable code an unmet expectation carries: the parser’s end-of-input code when the furthest position reached is past the last token, and its general syntax code otherwise. Both match the compiler’s own parse codes.

cursor_diagnostic

cursor_diagnostic : (Syntax.Cursor.Cursor) -> Syntax.Diagnostic.Diagnostic

The refusal an unmet expectation produces: a parse-phase diagnostic at the furthest position reached, carrying the canonical expectation set. The message keeps the order alternatives were tried, for a reader; the set is sorted, for the artifact. A cursor failure is a diagnostic and never a bespoke error value, so a hand-written parser’s refusals join the same document the compiler’s own do.

infix_left_bp

infix_left_bp : (Syntax.Cursor.Infix) -> Int

The power binding an infix operator’s left operand.

Levels are doubled so each has a half step above it. A left-associative operator’s right power sits in that half step, which stops a second operator of the same level from being pulled into the right operand; a right associative operator’s left power sits there instead, which lets it be. A non-associative operator is left-shaped here and refuses the repeat outright.

infix_right_bp

infix_right_bp : (Syntax.Cursor.Infix) -> Int

The power an infix operator’s right operand is parsed at.

prefix_bp

prefix_bp : (Syntax.Cursor.Prefix) -> Int

The power a prefix operator’s operand is parsed at.

infix_lookup

infix_lookup : (List(Syntax.Cursor.Infix), String) -> Option(Syntax.Cursor.Infix)

The entry for an operator spelling in an infix table, or None when the spelling is not an infix operator.

prefix_lookup

prefix_lookup : (List(Syntax.Cursor.Prefix), String) -> Option(Syntax.Cursor.Prefix)

The entry for an operator spelling in a prefix table, or None when the spelling is not a prefix operator.

pratt_expr

pratt_expr : forall a. (Syntax.Cursor.Pratt(a), Syntax.Cursor.Cursor, Int) -> Syntax.Cursor.Reply(a)

Parse one expression whose operators all bind at least as tightly as min_bp: one operand, then every operator that outbinds the caller.

pratt_parse

pratt_parse : forall a. (Syntax.Cursor.Pratt(a), Syntax.Cursor.Cursor) -> Syntax.Cursor.Reply(a)

Parse one expression at the loosest binding power. Tokens after it are left for the caller, which is what makes this usable inside a larger grammar.

pratt_all

pratt_all : forall a. (Syntax.Cursor.Pratt(a), Syntax.Cursor.Cursor) -> Syntax.Cursor.Reply(a)

Parse one expression and require the whole token stream to be consumed. A trailing operator the driver declined (a repeated non-associative one) is refused here, at the position it stands.

expr_infix_table

expr_infix_table : () -> List(Syntax.Cursor.Infix)

The infix table of Prism’s own expression grammar, loosest first. Levels are relative: only their order and each operator’s associativity carry meaning, and both are pinned against the compiler’s parser by a differential test rather than by this comment.

expr_prefix_table

expr_prefix_table : () -> List(Syntax.Cursor.Prefix)

The prefix table of Prism’s own expression grammar: unary minus, sitting between multiplication and exponentiation. -x * y is (-x) * y and, by the mathematical convention, -x ^ y is -(x ^ y).