This post is about a piece of infrastructure that we rebuilt over the last few months: the parser of the template language used inside LexiFi’s products. More precisely, it is about the switch from a classic parser producing an abstract syntax tree (AST) to one producing a concrete syntax tree (CST). The main difference between these two kinds of tree is that the concrete syntax tree preserves every single character of the source: keywords, punctuation, whitespace, comments and even the parts that do not parse.

The immediate motivation was the creation of a code formatter, but the CST is a useful foundation for other tools as well. In the sections that follow we will explain why the formatter needed a CST, how we rewrote the old parser without changing its observable behaviour, how the OCaml types of the CST are designed, and which properties the new design allowed us to state and check in our test suite. We hope this will be useful to others writing tools for their own languages.

Background: the template language

LexiFi’s products include a small, dynamically typed language used to write user-defined computations and to produce documents (reports, term sheets, etc). It has the usual constructs: var bindings, if ... then ... else ... end, for loops, functions, records, lists, pattern matching, etc. Its distinguishing feature is that it is a template language: code can contain fragments of text delimited by {{ ... }}, and text can contain fragments of code delimited by [[ ... ]], nested arbitrarily:

var x = 1; (* the answer *)
if x > 0 then {{ <b>[[x]] is positive</b> }} end

This is all you need to know about the language to follow this post. Template files are often written by non-developers and can be fairly big: the largest one in our test corpus, a production template that we will refer to as “the monster” in what follows, weighs in at ~840 KB.

Until recently, the language was parsed into an AST using ocamllex and ocamlyacc, following a fairly standard approach.

The trouble with formatting an AST

The starting point was our attempt to write a code formatter for the language. The obvious approach is to write a pretty-printer for the AST: parse, then print the tree back with a nice layout. It works well for most of the language, but it fails rather badly in a few aspects:

  • Comments: the AST does not record comments (or whitespace of any kind), so preserving them becomes quite difficult.
  • Parentheses: the AST does not record parentheses, so the printer must re-create the ones that are needed, and cannot preserve redundant ones that the user added for readability.
  • Multiple representations: some constructs can be written in more than one way (e.g. our language has two binding constructs, var and let), but they are represented the same way in the AST, so the pretty-printer cannot preserve the form used in the input. Similarly, elseif ... end is desugared into else if ... end end.
  • Trailing separators: whether a list or record has a trailing separator, as in {a = 1;}, is not recorded.
  • Literals: the exact syntax of number literals (1_000 vs 1000) is lost.
  • Syntax errors: of course, nothing is known about the parts of the file that are syntactically invalid (there is no AST produced for them).

These limitations (especially the first one) make the AST-based pretty-printer of little use in practice.

There are ways around this. One can collect comments from the lexer and try to reattach them to nearby AST nodes after the fact by comparing locations, or add special AST nodes for “floating” comments. But this makes the complexity explode, and requires fragile heuristics to work. And of course, this only addresses the first bullet point above: the other limitations would need separate solutions.

As is clear from the above discussion, the fact that the AST forgets many “concrete” aspects of what the user wrote (which is precisely what makes the AST useful for, say, an interpreter) makes it wholly unsuitable as input for a source code formatter. The solution, then, is to have the parser return a tree-shaped representation of the source code that preserves everything (a concrete syntax tree, or CST), derive the AST from it, and write the formatter against the CST.

What we wanted

With the objective of writing a parser producing a CST, we set out with three requirements for the new tree:

  • Lossless: printing the tree gives back the source, byte for byte.
  • Total: the parser never fails. Any input, valid or not, produces a tree, and that tree is still lossless.
  • Location-free: the tree does not store source positions. Positions can be re-derived from the tree itself.

The first two are the defining properties of a CST. The third one is less commonly found as a requirement, and we will come back to it below.

Step one: replace the parser without changing anything

Producing a CST requires fine control over the token flow. For example, we need to be able to access tokens corresponding to syntactically invalid parts of the input. This is difficult, if not impossible, to do with a parser generator.

So the first step was to replace the ocamlyacc parser with a hand-written recursive-descent parser. Crucially, at this stage the new parser still targeted the old AST, and the goal was for it to produce exactly the same AST as the old one, locations included, on every input. Without this specification, replacing the parser for a language that is heavily used in production would have been a much dicier proposition.

To make this goal checkable, we wrote the test suite first:

  • ~650 test cases, written in a small DSL (several cases per file, containing inputs and a textual representation of the corresponding AST for each one), about half of them exercising error recovery;
  • the expected output for each case was generated using the old parser;
  • the new parser is run on all cases and must agree;
  • we used bisect_ppx to make sure that the test suite exercises 100% of the new parser.

Aiming for exact compatibility, including the exact locations attached to nodes by the old parser and its error-recovery behaviour, forced us to complicate the new parser in a number of places. Error recovery in the old parser was implemented using ocamlyacc’s error rules, which are notoriously difficult to understand and to replicate using recursive descent, but we made the effort to match the old parser exactly, at least on all test cases. Exact compatibility gave us a precise specification, against which every change could be checked mechanically. It also made the work well suited to AI coding agents: every disagreement between the two parsers is a reproducible test case, which an agent can investigate and fix on its own, with the test suite telling it unambiguously when it is done.

Once the new parser was ready, we kept the old parser around, both as an oracle in the test suite and as a fallback in case of problems. We also checked that the new parser was not slower than the old one.

Step two: make the tree concrete, one node at a time

With the new parser in place, the tree was made “concrete” incrementally. First, the new parser got its own token and tree types (initially identical to the ones used for the old parser), together with a CST→AST conversion which, initially, was essentially the identity function. Then, one construct at a time, nodes were made concrete: their type was refined, the new parser was changed to produce the more concrete tree, and the CST→AST conversion was adapted accordingly. In this way, the tree produced by the new parser preserved more and more of the “concrete” input: keywords and punctuation, then trivia (see below), then error recovery data.

Each of these steps was safe thanks to the test suite from step one: whatever the state of the CST at any given time, the AST derived from it had to be the same as the one produced by the old parser, locations included.

The OCaml types

Let us now look at the types. The real CST has ~60 token constructors, ~35 expression constructors and a dozen auxiliary types (see Appendix), so we will show simplified versions.

The AST

We begin with the AST. Here is a simplified version of it:

type loc = { start: Lexing.position; stop: Lexing.position }

type expr = { loc: loc; desc: desc }

and desc =
  | Var of string
  | Int of int
  | Binop of binop * expr * expr
  | App of expr * expr list
  | If of expr * expr * expr           (* a missing else becomes Unit *)
  | Let of { pat: expr; def: expr; body: expr }
  | Record of (string * expr) list
  | Seq of expr * expr
  | Unit
  | SyntaxError of string

The representation is standard: each node has a location and a description, if is just three subexpressions, and syntax errors are represented by a message.

Tokens and trivia

The CST starts at the tokens. Whitespace and comments are called trivia, and each token carries the trivia that precede it:

type trivia =
  | Space
  | Whitespace of string
  | Comment of string

type token =
  | IF | THEN | ELSE | ELSEIF | END | VAR | EQUAL
  | LPAREN | RPAREN | LBRACE | RBRACE | COMMA | SEMI (* ... *)
  | LIDENT of string
  | INT of string                      (* the source text, not an int *)
  | ERROR of lexical_error literal     (* something the lexer could not read *)
  | EOF
  | TRIVIA of trivia * token           (* leading whitespace and comments *)

A few remarks about this definition:

  • Trivia are always leading: they are attached to the token that follows them. Trivia at the end of the file are attached to EOF. This is a simple rule that never needs to make a choice (contrast with “which AST node does this comment belong to?”).

  • Trivia are stored inline, by wrapping the token: TRIVIA (Space, IF) is the keyword if preceded by a single space. A more conventional design would use a record:

    { trivia: trivia list; token: token }

    The downside of this uniform representation is that the CST ends up taking more space and requires more allocation, even for simple tokens such as keywords. We measured: on the monster file, 54% of tokens have no trivia at all, and 39% are preceded by exactly one space. With the inline representation, the first case costs nothing, and the second case costs one small block (Space is a constant constructor) instead of a record and a list cell.

  • Literals keep their source text. INT "1_000" is not INT 1000: the formatter can then print the literal exactly as written, and the conversion to an integer (with its overflow check) moves to the CST→AST step.

  • The lexer is total too: something it cannot read (an invalid character, a string literal with a bad escape, etc) becomes an ERROR token holding the offending text, and lexing resumes after it.

Generic building blocks

A good part of a CST is made of the same few patterns: something between delimiters, a list with separators, two things separated by a token. We captured these as generic types:

type 'a with_token = { desc: 'a; token: token }

type 'a delimited = {
  left: token;
  content: 'a content;
  right: token;
}

and 'a content =
  | Content of 'a
  | Delimited of 'a delimited

type 'a separated_list =
  | Zero
  | Many of { first: 'a; rest: (token * 'a) list; trailing: token option }

type ('a, 'b) separated_pair = { first: 'a; sep: token; second: 'b }

'a with_token attaches a semantic value (such as the name of a variable) to the token it came from. In general the CST never discards the input token values. This is important because the token values are the ones containing the trivia (whitespace and comments). It also makes it possible to recover the original token stream by a simple in-order walk of the CST.

The type 'a separated_list represents a list of elements which are separated by a single token, possibly followed by a trailing one. For example, the elements of [1, 2,3 ,] (note the irregular spacing):

Many {
  first = Int { desc = "1"; token = INT "1" };
  rest = [
    COMMA, Int { desc = "2"; token = TRIVIA (Space, INT "2") };
    COMMA, Int { desc = "3"; token = INT "3" };
  ];
  trailing = Some (TRIVIA (Space, COMMA));
}

Note that the starting and ending delimiters are represented separately, as we explain next.

The type 'a delimited represents a fragment surrounded by delimiters such as parentheses or brackets. Note that the type definition can represent multiple balanced “runs” of delimiters, e.g. for ((e)):

{
  left = LPAREN;
  content = Delimited { left = LPAREN; content = Content e; right = RPAREN };
  right = RPAREN;
}

None of these types is specific to our language, and we suspect that they would carry over almost unchanged to the CST of any other language.

Expressions

Below is the simplified CST version of expressions (the full type definition is available in Appendix):

type expr =
  | Var of string with_token
  | Int of string with_token
  | Binop of expr * binop with_token * expr
  | App of expr * expr option separated_list delimited
  | If of if_expr
  | VarLet of var_expr
  | Record of record_field separated_list delimited
  | Paren of expr option delimited
  | SyntaxError of syntax_error

and if_expr = {
  if_: token; cond: expr option;
  then_: token; then_body: expr option;
  else_: if_cont;
}

and if_cont =
  | IfEnd of token
  | IfElse of { else_: token; body: expr option; end_: token }
  | IfElseIf of if_expr

and var_expr = {
  var: token; pat: expr; equal: token; def: expr;
  body: seq_cont option;
}

and seq_cont =
  | SeqSep of { semi: token; expr: expr option }
  | SeqSeq of expr

and record_field = { label: string with_token; equal: token; value: expr }

and syntax_error = { skipped: token list; before: token; message: string }

Comparing with the AST, the differences are:

  1. Locations. Every AST node has a loc. The CST has none; we will see below how they are recovered.

  2. Keywords and punctuation. In the AST, If is just three subexpressions. The CST keeps the if, then, else/elseif and end tokens, each with its leading comments and whitespace.

  3. Syntactic variants. elseif and else if ... end end are the same AST node, but different CST nodes (IfElseIf vs IfElse containing an If).

  4. Parentheses. There is no Paren node in the AST. There is one in the CST, which allows the formatter to see the parentheses the user wrote and to decide which ones to keep.

  5. Separators. AST lists are plain OCaml lists. CST lists keep each separator, and the optional trailing one.

  6. Literals. Int of int vs Int of string with_token, as discussed above.

  7. Missing parts. cond: expr option, then_body: expr option: an if with a missing condition is still an if, with cond = None, instead of a syntax error that swallows the whole construct. This is what allows error recovery to be precise, and the editor to keep providing assistance inside a half-written if.

  8. Errors. An AST syntax error is just a message. A CST syntax error keeps the tokens that the parser skipped while recovering. This is the key to totality: the parser may give up on understanding part of the input, but it never drops it.

To make this concrete, consider the following fragment:

if x then (* yes *) 1 end

Its AST is

If (Var "x", Int 1, Unit)

with a location on every node, and no trace of the comment. Its CST is the following:

If {
  if_ = IF;
  cond = Some (Var { desc = "x"; token = TRIVIA (Space, LIDENT "x") });
  then_ = TRIVIA (Space, THEN);
  then_body = Some (Int {
    desc = "1";
    token =
      TRIVIA (Space, TRIVIA (Comment "(* yes *)", TRIVIA (Space, INT "1")))
  });
  else_ = IfEnd (TRIVIA (Space, END));
}

Every character of the source is in there, in order.

Where did the locations go?

The CST does not store any source positions. Instead, positions can be derived from the tree: the position of a node is the position of the start of the file, plus the size of everything that comes before it. Because the CST includes every token of the input, and the tokens (with their trivia) account for every character of the input, it is possible to recover the exact size of the source code fragment corresponding to any subtree of the CST.

Every token (and hence every CST node) can be assigned a “size”. This could be the number of characters, but since our final objective is to recover (line, column) positions, we use the following more interesting type:

type size = {
  lnum : int;  (* number of newlines *)
  cnum : int;  (* number of characters *)
  bol  : int;  (* offset of the start of the last line, if lnum > 0 *)
}

Sizes can be added in a natural way:

let zero_size = { lnum = 0; cnum = 0; bol = 0 }

let add_size left right =
  { lnum = left.lnum + right.lnum;
    cnum = left.cnum + right.cnum;
    bol = if right.lnum = 0 then left.bol else left.cnum + right.bol }

Finally, starting from an initial Lexing.position (the standard OCaml type for source code positions), we can iteratively produce the “next” position by adding a size to it:

let add_to_pos (pos : Lexing.position) size =
  { pos with
    pos_lnum = pos.pos_lnum + size.lnum;
    pos_cnum = pos.pos_cnum + size.cnum;
    pos_bol =
      if size.lnum = 0 then pos.pos_bol else pos.pos_cnum + size.bol }

The size of a token (with its trivia) is computed from its text, and the size of a node is the sum of the sizes of its children.

The CST→AST conversion is then written as a set of “builders”, which compute, bottom-up, both the AST node and the size of the corresponding CST node, while threading the start position down. The locations in the AST are thus rebuilt during the conversion, and they are checked to be exactly those that the old parser used to produce.

Why go to this trouble? A few reasons:

  • The tree is relocatable. CST nodes do not have absolute locations attached to them, so a subtree can be moved, copied, or reused at a different place without patching any positions. This is the property that makes it possible to share subtrees between versions of a document, which is useful for incremental parsing.

  • No redundancy, no inconsistency. Storing locations in a CST means storing the same information twice (once in the text of the tokens and once in the positions), with the possibility of the two disagreeing, typically after a transformation of the tree.

  • Memory. Positions are big: a Lexing.position is a record with four fields, and a location is two of them. At an intermediate stage, when the CST still stored positions, it used 16 MiB on the monster file, versus 12 MiB for the AST. Once positions were removed, the CST went down to 8.6 MiB, now noticeably smaller than the AST.

The CST does have a cost in time, however. Since the AST used by the interpreter is now built in two steps (source to CST, then CST to AST), parsing takes about twice as long as before: on the monster file, about 0.05s instead of 0.02s. The absolute timings are small enough that, in practice, this is not noticeable.

“Theorems” you can test

One of the nicer aspects of having a CST is that it turns a number of desirable properties into simple statements that can be checked in the test suite, on every test case and on our corpus of real templates. Here are the ones we check:

  • The lexer is total and lossless. It never raises, and concatenating the source text of the tokens it produces (trivia included) gives back the input, byte for byte.

  • The parser is total and lossless. For every input s, valid or not, listing the tokens of the CST gives back the tokens produced by the lexer:

    Tokens.root (parse s) [] = lex s

    (Here, Tokens.root is a function that walks the CST in-order and returns the list of tokens encountered.) When this fails, the test prints a window of tokens around the first difference, which makes such bugs easy to track down.

  • The new parser refines the old one. On every test case:

    ast_of_cst (parse s) = Old_parser.parse s      (* locations included *)

Application: the formatter

The formatter was the original motivation, and it was our first application of the new CST. Thanks to the CST, its implementation was routine, and the result has a number of properties that would have been hard to obtain otherwise.

It starts as the identity. The formatter is a printer for the CST. Any construct whose layout it does not handle can still be printed verbatim from its tokens. This means that the formatter can be developed and improved incrementally, adding layout rules one construct at a time, without ever being “incorrect” (dropping tokens or producing syntactically invalid output). It also means that invalid input is handled gracefully: the parts that do not parse are reproduced as they are, and the rest of the file is formatted normally.

It never loses a comment. Comments are trivia, attached to tokens, and the formatter prints every token.

Every output is verified. Before returning anything, the formatter reparses its own output and compares it with the input: the token streams must be equal, ignoring whitespace. This is a very strong check: it covers comments, string literals and the text fragments of the template, which must be preserved byte for byte, since otherwise the documents produced by the template would change.

If the check does not pass, the formatter returns an error and the source is left untouched.

Gluing safety. It is not always possible to remove the whitespace between two tokens. For example, in a list of lists such as [ [1], [2] ], the two closing brackets cannot be glued together: ]] is a token on its own in our language (it closes a code fragment). Similarly, ( * ) cannot become (*), which opens a comment. To avoid this, before gluing two tokens, we lex their concatenated text and check that the lexer still produces the same first token.

Conclusion

In this post we described the switch of our template language from an AST to a CST. If we had to summarize the lessons we learned:

  • Store trivia as leading trivia on tokens, with trailing trivia attached to EOF.
  • Keep the tokens that error recovery skips: this is what makes the parser total.
  • Derive locations instead of storing them.
  • When rewriting a parser, use the old one as the specification.
  • Write the formatter so that it starts as the identity, and verify every output.

Next: a CST for OCaml?

We consider the introduction of this CST-based parser a success, and are very happy with the result. In fact, we were so satisfied that our colleague Émile started an experimental formatter for OCaml using the same approach: fromage. So far the results are quite promising! We may end up adopting it, and finally enter the promised land of auto-formatted code. (And yes, we evaluated OCamlFormat several times in the past, but for a number of reasons, some technical and some not, we never made the jump.)

Questions? You can reach me at nicolas.ojeda.bar@lexifi.com. Happy hacking!

Appendix: the full CST definition

For reference, here is the complete definition of the CST types, as found in our codebase (only the helper functions declared alongside are omitted). The comments show the concrete syntax represented by each case, writing E for expressions, P for patterns and l for labels.

type binop =
  | Add | Sub | Mul | Div             (** +  -  *  / *)
  | Equal | NotEqual                  (** =  != *)
  | Lt | Lte | Gt | Gte               (** <  <=  >  >= *)
  | And | Or                          (** &&  || *)

type trivia =
  | Space                             (** a single space *)
  | Whitespace of string              (** any other whitespace *)
  | Comment of string                 (** (* ... *) *)

type 'a literal = {
  value: 'a;                          (** the decoded value *)
  raw: string;                        (** the source text *)
}

type lexical_error = {
  message: string;
  offset_start: int;                  (** the part of the token to underline *)
  offset_stop: int;
}

(** A fragment of template text, with its delimiters. *)
type template = {
  offset_start: int;    (** length of the opening delimiter, if any *)
  op_start: bool;       (** opened by "{{" (not "]]" or start of file) *)
  t: string;            (** the text itself *)
  op_end: bool;         (** closed by "[[" (not "}}") *)
  terminated: bool;     (** false if the end of file was reached first *)
}

and token =
  | EOF | DO | ELSE | ELSEIF | END | FOR | FUN | IF | IN
  | INCLUDE | INCLUDE_HOME | LET | THEN | WILDCARD | MATCH | TO | VAR
  | WITH | AND | BACKTICK | BAR | COLONEQUAL | COMMA | DOT | QUESTIONMARK
  | JOKER | EQUAL | GT | GTE | HASH | LBRACE | LBRACKET | LPAREN
  | LT | LTE | MINUS | NOTEQUAL | OR | PLUS | RBRACE | RBRACKET | RIGHTARROW
  | SIMPLERIGHTARROW | RPAREN | SEMI | COLON | SLASH | STAR | PIPE
  | STRING of string literal          (** "..." *)
  | TEMPLATE of template literal      (** template text *)
  | LIDENT of string                  (** x *)
  | UIDENT of string                  (** C *)
  | INT of string                     (** 42, 1_000 *)
  | FLOAT of string                   (** 3.14, 1e3 *)
  | ERROR of lexical_error literal    (** text the lexer could not read *)
  | TRIVIA of trivia * token          (** whitespace or comment, then token *)

(** A value, together with the token it comes from. *)
type 'a with_token = {
  desc: 'a;
  token: token;
}

type binary_operation =
  | Binop of binop
  | Pipe                              (** |> *)
  | Compose                           (** # *)

(** ( X ), [ X ], { X }, and nested runs such as (( X )) *)
type 'a delimited = {
  left: token;
  content: 'a content;
  right: token;
}

and 'a content =
  | Content of 'a
  | Delimited of 'a delimited

(** X1 SEP ... SEP Xn, optionally followed by a trailing SEP *)
type 'a separated_list =
  | Zero                              (** empty *)
  | Many of {
      first: 'a; rest: (token * 'a) list;
      trailing: token option;
    }

(** X1 SEP X2 *)
type ('a, 'b) separated_pair = {
  first: 'a;
  sep: token;
  second: 'b;
}

type record_label =
  | Label of string                   (** l *)
  | String of string literal          (** "l" *)

type for_pattern =
  | Bind of {                         (** P1 => P2 in E *)
      pat1: expr; arrow: token; pat2: expr;
      in_: token; source: expr option;
    }
  | Range of {                        (** P = E1 to E2 *)
      pat: expr; equal: token; lower: expr option;
      to_: token; upper: expr option;
    }
  | In of {                           (** P in E *)
      pat: expr; in_: token;
      source: expr option;
    }

(** using M; E *)
and using_expr = {
  using: token;
  opened: expr;
  semi: token;
  body: expr option;
}

(** include("file"), include_home("file") *)
and include_expr = {
  include_: token;
  home: bool;
  filename: string literal with_token delimited;
}

(** E1 `f` E2 *)
and infix_app_expr = {
  lhs: expr;
  op: string with_token delimited;
  rhs: expr;
}

(** if E1 then E2 ... *)
and if_expr = {
  if_: token;
  cond: expr option;
  then_: token;
  then_body: expr option;
  else_: if_cont;
}

and if_cont =
  | IfEnd of token                    (** ... end *)
  | IfElse of {                       (** ... else E end *)
      else_: token; body: expr option; end_: token;
    }
  | IfElseUnclosed of expr            (** ... else E, missing end *)
  | IfElseIf of if_expr               (** ... elseif E1 then E2 ... *)

(** for FOR_PATTERN do E end *)
and for_expr = {
  for_: token;
  pat: for_pattern;
  do_: token;
  body: expr option;
  end_: token;
}

(** E1; E2, E1 E2 *)
and seq_expr = {
  first: expr;
  second: seq_cont;
}

(** fun(P1, ..., Pn) => E end *)
and fun_expr = {
  fun_: token;
  args: expr one_or_delimited;
  arrow: token;
  body: expr;
  end_: token;
}

(** (.l) *)
and label_fun = {
  lparen: token;
  dot: token;
  label: string with_token;
  rparen: token;
}

(** let P = E1 in E2 *)
and let_expr = {
  let_: token;
  pat: expr;
  equal: token;
  def: expr option;
  in_: token;
  body: expr option;
}

(** var P = E1; E2 *)
and var_expr = {
  var: token;
  pat: expr;
  equal: token;
  def: expr;
  body: seq_cont option;
}

(** fun f(P1, ..., Pn) = E1 end; E2 *)
and fun_rec_expr = {
  fun_: token;
  pat: expr;
  args: expr one_or_delimited;
  equal: token;
  def: expr option;
  body: seq_cont option;
  end_: token;
}

(** match E with | P1 => E1 | ... | Pn => En end (first | optional) *)
and match_expr = {
  match_: token;
  scrutinee: expr option;
  with_: token;
  bar: token option;
  cases: match_case separated_list;
  end_: token;
}

and match_case =
  | MatchCase of (expr, expr option) separated_pair     (** P => E *)
  | MatchCaseError of { pat: syntax_error; body_span: error_span }

(* The span of a syntax error, as reported to the user, is expressed relative
   to the tokens of the error rather than with absolute positions. *)
and token_edge =
  | Start
  | Stop
  | Offset of int               (** number of characters into the token *)

and error_cursor =
  | Skipped of int * token_edge (** n-th skipped token (from the end if < 0) *)
  | Before of token_edge        (** the token where recovery stopped *)

and error_span = {
  from: error_cursor;
  until: error_cursor;
}

and syntax_error = {
  skipped: token list;          (** the tokens skipped by error recovery *)
  before: token;                (** the next token (not part of the error) *)
  message: string;
  span: error_span;
}

and expr =
  | SyntaxError of syntax_error
  | Var of string with_token            (** x *)
  | Wildcard of token                   (** _ *)
  | If of if_expr
  | For of for_expr
  | App of expr * expr one_or_delimited (** E(E1, ..., En), E{...},
                                            E[...], E ?? *)
  | String of string literal with_token (** "..." *)
  | Int of string with_token            (** 42 *)
  | Float of string with_token          (** 3.14 *)
  | Neg of token * expr                 (** -E *)
  | Dot of (expr, string with_token) separated_pair
                                        (** E.l *)
  | QuestionMark of (expr, string with_token) separated_pair
                                        (** E?l *)
  | Seq of seq_expr
  | Echo of template literal with_token (** template text *)
  | Fun of fun_expr
  | LabelFun of label_fun
  | Constr of string with_token         (** C *)
  | Binop of expr * binary_operation with_token * expr
                                        (** E1 op E2 *)
  | Let of let_expr
  | VarLet of var_expr
  | FunRec of fun_rec_expr
  | LightFun of (expr one_or_delimited, expr) separated_pair
                                        (** P => E, (P1, ..., Pn) => E *)
  | Record of record_field separated_list delimited
                                        (** { F1; ...; Fn } *)
  | List of expr separated_list delimited
                                        (** [E1, ..., En] *)
  | Assign of (string with_token, expr) separated_pair
                                        (** x := E *)
  | Match of match_expr
  | ExtendRecord of (expr, record_field separated_list) separated_pair delimited
                                        (** { E with F1; ...; Fn } *)
  | Open of (expr, expr option delimited) separated_pair
                                        (** M.(E) *)
  | Using of using_expr
  | Include of include_expr
  | Joker of token                      (** ?? *)
  | InfixApp of infix_app_expr
  | InfixFun of binop with_token delimited
                                        (** (+), (&&), ... *)
  | Paren of expr option delimited      (** (E), () *)

and seq_cont =
  | SeqSep of { semi: token; expr: expr option }
                                        (** ; E, ; *)
  | SeqSeq of expr                      (** E, with no separator *)

and record_field =
  | FieldPun of { question: token option; label: string with_token }
                                        (** l, ?l *)
  | FieldAssign of {                    (** l = E, "l" = E, ?l = E *)
      question: token option; label: record_label with_token;
      equal: token; value: expr;
    }
  | FieldJoker of token                 (** ?? *)

and 'a one_or_delimited =
  | One of 'a                           (** X *)
  | Delimited of 'a option separated_list delimited
                                        (** (X1, ..., Xn) *)

(** E EOF *)
type root = {
  body: expr option;
  eof: token;
}