Resilient Parsing with Ungrammar

Ungrammar is a small DSL for defining concrete syntax trees (CSTs), originally created for use in rust-analyzer. Its author describes it as "the ASDL for concrete syntax trees." Unlike an abstract syntax tree, a CST preserves every token from the source — including delimiters and other syntactic elements — which makes it useful for full-fidelity tooling like language servers.

A new Go re-implementation, go-ungrammar, demonstrates the approach. Given an Ungrammar file describing a CST (for example, a simple calculator language), it parses the definition and produces a tree structure that can represent parsed language input.

Program = Stmt*

Stmt = AssignStmt | Expr

AssignStmt = 'set' 'ident' '=' Expr

Expr =
    Literal
  | UnaryExpr
  | ParenExpr
  | BinExpr

UnaryExpr = op:('+' | '-') Expr

ParenExpr = '(' Expr ')'

BinExpr = lhs:Expr op:('+' | '-' | '*' | '/' | '%') rhs:Expr

Literal = 'int_literal' | 'ident'

Syntactically, Ungrammar resembles EBNF, but it is deliberately simpler. It leaves precedence, ambiguity, and lexical rules to other layers of the compiler front-end. Its purpose is purely to define the shape of a parse tree, not to govern how the input is tokenized or disambiguated.

Lexing and Parsing in Practice

go-ungrammar consists of a hand-written lexer and a recursive descent parser. Both are designed to be resilient: the lexer never aborts on invalid input, instead emitting an ERROR token and continuing, while the parser collects all errors it encounters and attempts to resynchronize after each one. This is important for handling incomplete or malformed input gracefully.

Consider a faulty Ungrammar definition:

foo = @
bar = ( joe
x = y

Here, two problems stand out:

  • @ is not a valid Ungrammar token
  • The ( in the second rule is never closed, which can confuse parsers that scan ahead for a terminator

When run, go-ungrammar reports all issues in a single error list rather than stopping at the first failure:

1:7: unknown token starting with '@' (and 2 more errors)

1:7: unknown token starting with '@'
2:1: expected rule, got bar
3:1: expected ')', got x

Handling Ambiguity and Recovery

Recovery is nuanced because Ungrammar is whitespace-insensitive and has an inherent ambiguity:

foo = bar baz = barn

In a rule definition like foo = bar baz, is bar baz the right-hand side of foo, or does baz = begin a new rule? go-ungrammar resolves this with an NODE = lookahead: if it sees a plain identifier followed by an equals sign, it treats that as the start of a new rule.

In the faulty example above, the parser's first recovery happens when it expects a right-hand side after foo = but finds none — the @ was already reported and skipped, leaving an empty RHS, which is invalid. The parser notes the error, resynchronizes, and proceeds to parse the bar = rule. A second error is reported for the unterminated (, but the parser still parses the contents and continues to the valid x = y rule.

The partial result corresponds to this tree:

bar = joe
x = y

For foo, nothing could be parsed. For bar, the missing ) is noted but the contents are still captured. This ability to parse incomplete or erroneous input and produce a partial tree is critical for resilient tooling, especially language servers that must handle input as the user types.

Building a robust error-recovering parser for a language as simple as Ungrammar is arguably over-engineering, but it serves as a valuable exercise in front-end construction technique.