Sigma

Appearance

Error recovery ​

By default parsing stops at the first failure. That's fine for a validator, but an editor or a compiler front-end needs every error in the file and a tree it can still work with. Sigma builds that out of two pieces. commit marks the point past which a failure is a real syntax error, and recover resynchronises when one happens.

This page grows one small grammar until it does both.

The grammar ​

The language parsed below has three statements: a binding, a call, and a block.

let width = 320;
print(width, 2);
{ let scale = 2; }

The grammar is roughly this:

text
program   = body
body      = statement*
statement = binding | print | block
binding   = "let" name "=" value ";"
print     = "print" "(" [ value ( "," value )* ] ")" ";"
block     = "{" body "}"
name      = letters
value     = digits | letters

letters   = ? letters ?
digits    = ? digits ?

The AST is a discriminated union of object shapes. The error node is what a recovered region resolves to later.

ts
type Node =
  | { kind: 'let'; name: string; value: string | number }
  | { kind: 'print'; args: Array<string | number> }
  | { kind: 'block'; body: Array<Node> }
  | { kind: 'error'; span: Span }

Next are the lexemes. token attaches trailing whitespace to whatever it wraps, so the rules below don't have to mention it everywhere.

ts
const ws = optional(whitespace())

function token<T>(parser: Parser<T>): Parser<T> {
  return first(parser, ws)
}

const Semi = token(string(';'))
const Comma = token(string(','))
const Equals = token(string('='))
const Open = token(string('('))
const Close = token(string(')'))
const OpenBrace = token(string('{'))
const CloseBrace = token(string('}'))

const Name = token(letters())
const Num = token(integer())
const Value = choice(Num, Name)

Since blocks contain statements, the rules are mutually recursive, which is what grammar is for.

ts
const Lang = grammar({
  Program(): Parser<Array<Node>> {
    return inner(ws, this.Body, eof())
  },

  Body(): Parser<Array<Node>> {
    return many(this.Statement)
  },

  Statement(): Parser<Node> {
    return choice(this.Binding, this.Print, this.Block)
  },

  Binding(): Parser<Node> {
    return map(
      last(
        token(string('let')),
        outer(Name, Equals, first(Value, Semi)),
      ),
      ([name, value]) => ({ kind: 'let', name, value }),
    )
  },

  Print(): Parser<Node> {
    return map(
      last(
        token(string('print')),
        inner(Open, sepBy(Value, Comma), first(Close, Semi)),
      ),
      (args) => ({ kind: 'print', args }),
    )
  },

  Block(): Parser<Node> {
    return map(
      inner(OpenBrace, this.Body, CloseBrace),
      (body) => ({ kind: 'block', body }),
    )
  },
})

On valid input it returns both statements.

ts
run(Lang.Program).with(`
let width = 320;
print(width, 2);
`)
ts
{
  isOk: true,
  start: 0,
  end: 35,
  pos: 35,
  value: [
    { kind: 'let', name: 'width', value: 320 },
    { kind: 'print', args: [ 'width', 2 ] }
  ],
  errors: []
}

The first failure wins ​

Add another statement and break it by dropping its name:

ts
run(Lang.Program).with(`
let width = 320;
let = 240;
print(width, 2);
`)
ts
{
  isOk: false,
  start: 18,
  end: 18,
  pos: 18,
  expected: 'end of input',
  label: null,
  errors: []
}

There is one error, and it is the wrong one. Position 18 is the start of let = 240;, and the complaint is that the file didn't end there.

choice tries Binding, which consumes let and fails on the missing name. choice then rewinds and tries Print, then Block, and none of them match. choice keeps the failure that got the furthest, the missing name at position 22. many reads the failure as "no more statements", discards it, and stops. eof then fails on the leftovers and reports its own complaint. The real problem, a missing name after let, is gone.

There's also nothing to recover from. As far as the grammar is concerned, no statement started here at all.

Committing to a parse ​

commit prevents backtracking once the parser is past a certain point. Here that point is each rule's opening token, e.g. after let the construct can only be a binding.

ts
const Lang = grammar({
  // ...

  Binding(): Parser<Node> {
    return map(
      last(
        token(string('let')),
        outer(Name, Equals, first(Value, Semi)),
        commit(outer(Name, Equals, first(Value, Semi)), 'let'),
      ),
      ([name, value]) => ({ kind: 'let', name, value }),
    )
  },

  Print(): Parser<Node> {
    return map(
      last(
        token(string('print')),
        inner(Open, sepBy(Value, Comma), first(Close, Semi)),
        commit(inner(Open, sepBy(Value, Comma), first(Close, Semi)), 'print'),
      ),
      (args) => ({ kind: 'print', args }),
    )
  },

  Block(): Parser<Node> {
    return map(
      inner(OpenBrace, this.Body, CloseBrace),
      last(OpenBrace, commit(first(this.Body, CloseBrace), 'block')),
      (body) => ({ kind: 'block', body }),
    )
  },
})

A committed failure stops being backtracked over. choice gives up instead of trying Print, and the failure is propagated with the label attached:

ts
run(Lang.Program).with(`
let width = 320;
let = 240;
print(width, 2);
`)
ts
{
  isOk: false,
  start: 22,
  end: 22,
  pos: 22,
  expected: 'letters',
  label: 'let',
  errors: []
}

Position 22 is the =, and the message names what is missing. See commit for what commitment does to each combinator.

The parsing still stops at the first error, but commitment produced a recoverable failure.

Recovering ​

recover takes a parser, a resynchronisation strategy, an optional fallback, and options. On a committed failure it runs the strategy from the position the failure was reported at. If the strategy finds a resynchronisation point, recover records the failure and resolves to the fallback value in place of the malformed region.

A statement list has a boundary at each terminator, so the strategy is syncPast over ;. Only Body changes:

ts
function errorNode(_: Failure, span: Span): Node {
  return { kind: 'error', span }
}

const Lang = grammar({
  // ...

  Body(): Parser<Array<Node>> {
    return many(this.Statement) 
    return many(recover(this.Statement, syncPast(Semi), errorNode)) 
  },

  // ...
})

One pass over the same input now yields all three statements, with the broken one standing in as an error node:

ts
run(Lang.Program).with(`
let width = 320;
let = 240;
print(width, 2);
`)
ts
{
  isOk: true,
  start: 0,
  end: 46,
  pos: 46,
  value: [
    { kind: 'let', name: 'width', value: 320 },
    { kind: 'error', span: { start: 18, end: 29 } },
    { kind: 'print', args: [ 'width', 2 ] }
  ],
  errors: [
    {
      isOk: false,
      start: 22,
      end: 22,
      pos: 22,
      expected: 'letters',
      label: 'let',
      errors: []
    }
  ]
}

The result stays isOk: true and the failure moves to errors. The error node's span covers the whole statement, from where Statement started to where the strategy stopped.

recover ignores uncommitted failures, which is what lets many stop cleanly. At the end of the input Statement fails before reaching any commit, that failure passes straight through, and many stops instead of producing a trailing error node for whatever is left.

Choosing a resynchronisation point ​

The strategy is an ordinary parser, and which one you pick decides how much input a single error will strip. Here a terminator goes missing instead of a name:

ts
run(Lang.Program).with(`
let width = 320
let height = 240;
`)
ts
{
  isOk: true,
  start: 0,
  end: 35,
  pos: 35,
  value: [ { kind: 'error', span: { start: 1, end: 35 } } ],
  errors: [
    {
      isOk: false,
      start: 17,
      end: 18,
      pos: 17,
      expected: ';',
      label: 'let',
      errors: []
    }
  ]
}

Both statements collapsed into a single error node. syncPast(Semi) scans for the next ;, and with the first one gone, the next one belongs to the following statement, which gets swallowed along with the broken one.

syncTo stops before its match instead of consuming it, which is what you want when the resynchronisation point starts the next construct rather than terminating the broken one. Sync on the statement keywords instead:

ts
const StatementStart = choice(string('let'), string('print'), string('{'), string('}')) 

const Lang = grammar({
  // ...

  Body(): Parser<Array<Node>> {
    return many(recover(this.Statement, syncPast(Semi), errorNode)) 
    return many(recover(this.Statement, syncTo(StatementStart), errorNode)) 
  },

  // ...
})

Now only the broken statement is lost:

ts
run(Lang.Program).with(`
let width = 320
let height = 240;
`)
ts
{
  isOk: true,
  start: 0,
  end: 35,
  pos: 35,
  value: [
    { kind: 'error', span: { start: 1, end: 17 } },
    { kind: 'let', name: 'height', value: 240 }
  ],
  errors: [
    {
      isOk: false,
      start: 17,
      end: 18,
      pos: 17,
      expected: ';',
      label: 'let',
      errors: []
    }
  ]
}

Neither strategy can fail. syncPast always advances unless it's already at the end of input, which guarantees a recovery inside a loop makes progress. syncTo only advances when the failure is reported past the start of the region, which holds for a commit placed after a distinguishing token like the ones above.

Recovering out of a block ​

Blocks nest, and a scan for the next } would stop at the wrong one. Take an extra token placed before an inner block:

{ let x = 1; oops { let y = 2; } }

Body stops at oops, the 'block' commit triggers because } isn't there, and the malformed region runs to the end of the outer block. Skipping to the first } would end up in the middle of it. syncNested tracks depth instead, so the inner { ... } raises and lowers it again and the scan stops after the brace that balances the outer one.

It is the only one of the three strategies that can fail. If the region never closes, syncNested gives up and recover re-raises the original failure, still committed, for a recovery point further out to deal with.

The block gets its own recovery point, with options.label restricting it to failures committed as 'block':

ts
const Lang = grammar({
  // ...

  Block(): Parser<Node> {
    return map( 
      last(OpenBrace, commit(first(this.Body, CloseBrace), 'block')),
      (body) => ({ kind: 'block', body }),
    ) 
    return recover( 
      map( 
        last(OpenBrace, commit(first(this.Body, CloseBrace), 'block')),
        (body) => ({ kind: 'block', body }),
      ),
      syncNested(OpenBrace, CloseBrace),
      errorNode,
      { label: 'block' },
    ) 
  },

  // ...
})

There are now two recovery points, one inside the other, and the innermost one that accepts a failure handles it. A broken statement inside the block is handled by the recover in Body and never reaches this one. The label option makes this recover decline anything not committed as 'block', so such a failure stays committed and goes to the next recovery point outward.

ts
run(Lang.Program).with(`
{ let x = 1; oops { let y = 2; } }
let z = 3;
`)
ts
{
  isOk: true,
  start: 0,
  end: 47,
  pos: 47,
  value: [
    { kind: 'error', span: { start: 1, end: 36 } },
    { kind: 'let', name: 'z', value: 3 }
  ],
  errors: [
    {
      isOk: false,
      start: 14,
      end: 15,
      pos: 14,
      expected: '}',
      label: 'block',
      errors: []
    }
  ]
}

A broken statement inside an otherwise well-formed block is caught by Body instead, and the block itself survives:

ts
run(Lang.Program).with(`
{ let x = 1;
  let = 2;
}
`)
ts
{
  isOk: true,
  start: 0,
  end: 27,
  pos: 27,
  value: [
    {
      kind: 'block',
      body: [
        { kind: 'let', name: 'x', value: 1 },
        { kind: 'error', span: { start: 16, end: 25 } }
      ]
    }
  ],
  errors: [
    {
      isOk: false,
      start: 20,
      end: 20,
      pos: 20,
      expected: 'letters',
      label: 'let',
      errors: []
    }
  ]
}

Inserting a missing token ​

A strategy that consumes nothing turns recover into token insertion: nothing skips no region at all, so recover records the missing token and the parse carries straight on from where it stopped.

ts
const InsertedSemi = recover(commit(Semi, 'semi'), nothing(), () => null) 

const Lang = grammar({
  // ...

  Binding(): Parser<Node> {
    return map(
      last(
        token(string('let')),
        commit(outer(Name, Equals, first(Value, Semi)), 'let'),
        commit(outer(Name, Equals, first(Value, InsertedSemi)), 'let'),
      ),
      ([name, value]) => ({ kind: 'let', name, value }),
    )
  },

  // ...
})

The file with the missing semicolon now parses completely, and the omission is properly reported:

ts
run(Lang.Program).with(`
let width = 320
let height = 240;
`)
ts
{
  isOk: true,
  start: 0,
  end: 35,
  pos: 35,
  value: [
    { kind: 'let', name: 'width', value: 320 },
    { kind: 'let', name: 'height', value: 240 }
  ],
  errors: [
    {
      isOk: false,
      start: 17,
      end: 18,
      pos: 17,
      expected: ';',
      label: 'semi',
      errors: []
    }
  ]
}

WARNING

Use it in a fixed position such as a sequence, never inside a repetition, where a zero-width recovery stops the loop.

Accounting for the whole file ​

many stops at the first uncommitted failure, which is what ends the loop at the end of input, but it also means input matching no rule at all is left unparsed, and eof fails on it:

ts
run(Lang.Program).with(`
let a = 1;
xyz
`)
ts
{
  isOk: false,
  start: 12,
  end: 12,
  pos: 12,
  expected: 'end of input',
  label: null,
  errors: []
}

Give the loop a last alternative that always fails, and commit to it. "Nothing matched here" turns into a real syntax error, and the recovery point handles it like any other:

ts
const Unknown = commit(fail('statement'), 'unknown') 

const Lang = grammar({
  Program(): Parser<Array<Node>> {
    return inner(ws, this.Body, eof()) 
    return inner( 
      ws,
      many(recover(choice(this.Statement, Unknown), syncPast(Semi), errorNode)),
      eof(),
    ) 
  },

  // ...
})
ts
run(Lang.Program).with(`
let a = 1;
xyz;
let b = 2;
`)
ts
{
  isOk: true,
  start: 0,
  end: 28,
  pos: 28,
  value: [
    { kind: 'let', name: 'a', value: 1 },
    { kind: 'error', span: { start: 12, end: 17 } },
    { kind: 'let', name: 'b', value: 2 }
  ],
  errors: [
    {
      isOk: false,
      start: 12,
      end: 12,
      pos: 12,
      expected: 'statement',
      label: 'unknown',
      errors: []
    }
  ]
}

Note that the catch-all goes in Program, not in Body. Body has to stop at a block's }, but Unknown would commit on that brace, and syncPast(Semi) would then scan past it looking for a ;. A well-formed { let x = 1; } would come back as one error node.

Falling back to another parse ​

recover answers a committed failure with an error node. Sometimes the right answer is a different parse instead.

Commitment is a property of the rule, so every use of Statement inherits it, including uses that only want to try it speculatively. Say a lenient mode should keep unrecognised lines as raw text. This section starts again from the grammar as it was before the catch-all was added:

ts
type Node =
  | { kind: 'let'; name: string; value: string | number }
  | { kind: 'print'; args: Array<string | number> }
  | { kind: 'block'; body: Array<Node> }
  | { kind: 'error'; span: Span }
  | { kind: 'raw'; text: string }

const Lang = grammar({
  Program(): Parser<Array<Node>> {
    return inner(ws, this.Body, eof()) 
    return inner(ws, many(choice(this.Statement, this.Raw)), eof()) 
  },

  Raw(): Parser<Node> {
    return map( 
      first(regexp(/[^;]*/, 'text'), Semi),
      (text) => ({ kind: 'raw', text }),
    ) 
  },

  // ...
})

This does not work. The committed failure ends the choice before Raw is reached:

ts
run(Lang.Program).with(`
let width = 320;
let = 240;
print(width, 2);
`)
ts
{
  isOk: false,
  start: 22,
  end: 22,
  pos: 22,
  expected: 'letters',
  label: 'let',
  errors: []
}

backtrack turns the failure back into an ordinary one for that one call site, leaving Statement committed everywhere else. choice backtracks again and Raw gets its turn:

ts
const Lang = grammar({
  Program(): Parser<Array<Node>> {
    return inner(ws, many(choice(this.Statement, this.Raw)), eof()) 
    return inner(ws, many(choice(backtrack(this.Statement), this.Raw)), eof()) 
  },

  // ...
})
ts
run(Lang.Program).with(`
let width = 320;
let = 240;
print(width, 2);
`)
ts
{
  isOk: true,
  start: 0,
  end: 46,
  pos: 46,
  value: [
    { kind: 'let', name: 'width', value: 320 },
    { kind: 'raw', text: 'let = 240' },
    { kind: 'print', args: [ 'width', 2 ] }
  ],
  errors: [] 
}

Note the empty errors. backtrack forgets the failure. Nothing is reported, nothing is consumed, and nothing stands in for the region. Use it when a committed rule has to be speculative somewhere, and use recover when the malformed region has to end up in the diagnostics.

Reading the result ​

Every result carries errors, and a successful result with a non-empty errors is a partial parse. The value is usable, and each entry describes a syntax error. run tolerates recovered failures and tryRun throws on them.

Recoveries made inside a region that is then rejected go with it. Whatever a rejected choice alternative or a failed optional recovered along the way is dropped, so errors only describes input that made it into the result. lookahead drops its recoveries on success, because the same region is about to be parsed for real and would otherwise be reported twice. A run that fails outright is the exception. Its errors still holds what was recovered before the parser gave up, including regions the failure rewound past.

Placing commits ​

Two guidelines work for most grammars.

  1. Commit after a token that makes the construct unambiguous. Once a keyword or an opening bracket has been consumed, the parser is no longer choosing between alternatives.

  2. Put recovery points where the language has a boundary. Statement lists resynchronise on the terminator and block structures on balanced delimiters. Recovering at a level with no such boundary tends to produce noise.

Sigma doesn't deduplicate or suppress diagnostics, so every recovery you allow ends up in errors. A recovery point per statement gives one error per broken statement, one per token gives far more. When one mistake produces many errors, the fix is usually a coarser recovery point.