The shape of
a language

01 / A program is more than a string

From text to structure

Look at a + b * 2. You probably already see an addition whose right-hand side is a multiplication. The computer starts with characters. Something has to discover which pieces belong together.

A grammar describes the permitted shapes of a language. A parser is a program that recognises those shapes in an input and usually builds a tree. A tree records nesting: a parent contains its children, just as a function contains its body.

First, a lexer groups characters into tokens: a name such as count, an integer such as 42, or punctuation such as+. A token can carry its kind, original text, and source position. Position matters when you want an error to underline the right characters.

The parser then groups tokens into constructs such as calls, expressions, and functions. Later analysis works out which declaration a name refers to and whether its type makes sense.missing + 1 can have perfectly good syntax even when missing has never been declared. Rust also performs macro expansion, which can introduce more syntax to parse.The compiler development guide describes these stages.

Decide what a token is

For our teaching language, names contain ASCII letters, digits, and underscores, and cannot start with a digit. Integers are decimal digits. Scan a whole name before recognising keywords:letter is one name, not let followed by ter. Reserve fn, let, and mut; give a lone _ its own token. Recognise -> before treating - as a standalone operator.

Ignore whitespace between tokens for now, and reject unknown characters. This is a deliberately small lexical contract: real Rust additionally has Unicode identifiers, comments, literal suffixes, several string forms, and much more. Trying to express all nesting with a conventional regular expression is the wrong tool: a parser must handle arbitrarily nested parentheses, not just recognise individual words.

02 / Learn the alphabet of rules

Read your first grammar

Here is a rule for a simple variable binding. Read= as “has this form”.

Let = "let" IDENT (":" Type)? "=" Expr ";" ;

A Let starts with the exact keywordlet, then a name, optionally a colon followed by a type, then an equals sign, an expression, and a semicolon. The final, unquoted semicolon ends our grammar rule; the quoted";" is part of the program being parsed.

This is an EBNF-style notation: Extended Backus–Naur Form. “Extended” gives us conveniences such as optional parts and repetition. Books and tools use different spellings. Our unquoted parentheses group rules; quoted"(" and ")" match actual parentheses. Our | describes permitted alternatives without choosing which to try first. Some notations use ordered alternatives, so always read their legend.

A whole rule is also called a production. To read a grammar, expand one nonterminal at a time until you reach terminals. This sequence of expansions is aderivation. Starting from Let, choose to omit the annotation, let Expr become an integer, and you obtain let count = 42;.

Lists deserve their own rule

ParameterList = "(" Parameters? ")" ;
Parameters    = Parameter ("," Parameter)* ","? ;
Parameter     = IDENT ":" Type ;

The first parameter is required insideParameters. Every further parameter comes with a comma. A final comma is optional. Making the entireParameters optional permits (), but does not accidentally permit (,). Contrast that with Parameter* ","?, which would admit a stray comma and adjacent parameters without separators.

03 / Build a language you can explain

Start with examples, then draw boundaries

Let’s call our small language Sprout. It borrows Rust’s appearance so we can practise the same design decisions. Write a few programs you want before inventing rules. This one gives us functions, typed parameters, bindings, calls, and arithmetic:

fn grow(x: i32) -> i32 {
    let doubled: i32 = x * 2;
    doubled + 1
}

fn main() {
    grow(20);
}

An item introduces a declaration such as a function. A statement is a step inside a block. An expression is something that computes a value. A type describes a kind of value. Apattern describes how to match or bind a value: a name binds it, while _ ignores it. These categories sometimes look alike, but have different jobs.

Here is our complete syntactic grammar, using the token contract from chapter 1. EOF means end of input: success must consume the whole file. The expression rules will make more sense in the next chapter.

File       = Function* EOF ;
Function   = "fn" IDENT "(" Parameters? ")" ("->" Type)? Block ;
Parameters = Parameter ("," Parameter)* ","? ;
Parameter  = Pattern ":" Type ;
Pattern    = "mut"? IDENT | "_" ;
Type       = IDENT | "&" "mut"? Type ;
Block      = "{" Statement* Expr? "}" ;
Statement  = Let | Expr ";" ;
Let        = "let" Pattern (":" Type)? "=" Expr ";" ;

Expr       = Sum ;
Sum        = Product (("+" | "-") Product)* ;
Product    = Prefix (("*" | "/") Prefix)* ;
Prefix     = "-" Prefix | Postfix ;
Postfix    = Atom Suffix* ;
Suffix     = "(" Arguments? ")" | "." IDENT | "[" Expr "]" ;
Arguments  = Expr ("," Expr)* ","? ;
Atom       = IDENT | INT | "(" Expr ")" ;

Typeis recursive: it refers to itself. An ampersand can be followed by another type, so a finite rule describes both&i32 and &mut &i32. The recursion bottoms out at a name. Each recursive step consumes an ampersand, so reading the input moves forward.

The block rule separates semicolon-terminated statements from an optional final expression. doubled + 1 is the block’s value. Add a semicolon and it becomes a statement; a block with no tail yields the unit value () in our intended semantics. Checking that a function’s body agrees with its declared return type belongs after parsing.

Make negative examples alongside positive ones: missing parameter types, two commas, a binding without =, and tokens after a completed file. A grammar is defined as much by what it rejects as by the examples it accepts.

04 / One string, two possible trees

Give operators a shape

Expr = Expr "+" Expr | Expr "*" Expr | IDENT | INT ;

This tempting rule permits two trees for a + b * 2:(a + b) * 2 and a + (b * 2). That isambiguity: the same input has more than one parse tree under the grammar. The parser cannot infer the intended grouping from the operator symbols.

Precedencechooses between different operators: multiplication binds more tightly than addition. Associativity chooses between operators at the same level: subtraction groups to the left, so a - b - c means (a - b) - c. These rules describe grouping, not a general guarantee about evaluation order or whether operands have side effects.

Sprout’s grammar expresses precedence with layers.Sum contains whole Products. A product contains whole prefix expressions. Each operand of a sum is therefore already allowed to contain multiplication. The repetition in Sum describes a flat chain; when building the AST, we explicitly fold that chain left to implement left associativity.

Try (a + b) * 2 and watch the root change from addition to multiplication. The root is the outermost operation. Then try a - b - c: the first subtraction sits inside the left child of the second.

Calls and access are expressions too

Our Postfix = Atom Suffix* rule starts with a small expression, then wraps it repeatedly. Forfactory(1).items[0], begin with the name, wrap it in a call, wrap that in field access, then wrap that in indexing. Treating a call as a suffix also lets the result of a call be called again: factory()(1).

Index(
  Field(
    Call(Name("factory"), [Int(1)]),
    "items"
  ),
  Int(0)
)

The workbench intentionally implements only names, integers, arithmetic, unary minus, and grouping. Calls, fields, and indexing belong to the fuller written grammar above; they are useful extensions to implement yourself.

05 / The grammar becomes a program

Write a parser by hand

A recursive-descent parser often gives each grammar category a function: parse_function,parse_type, parse_expression. Functions call each other as the rules do. A cursor points at the next token. peek inspects it;bump consumes it; expect consumes a required token or reports an error.

Consider the optional type annotation in a binding. You do not need to try every possible rule. A colon tells you the annotation has started. This is lookahead: inspecting upcoming input before choosing a path. The following is pseudocode; ? here propagates an error, as it would in Rust, rather than denoting an optional grammar fragment.

parse_let():
    expect("let")?
    pattern = parse_pattern()?
    type = None
    if eat(":"):
        type = Some(parse_type()?)
    expect("=")?
    value = parse_expression()?
    expect(";")?
    return Let(pattern, type, value)

eatconsumes a token only if it matches. Once it has consumed:, a type is required: a malformed annotation is not the same as an absent one. Likewise, after consuming a list comma, either allow the closing delimiter as a trailing-comma case or require the next element.

Two traps, and why they happen

Expr = Expr "+" Atom | Atomis left recursive: the first step asks for anExpr again without consuming anything. A naive recursive-descent implementation calls itself forever. Rewrite it as Expr = Atom ("+" Atom)* and use a loop that replaces the accumulated left tree. LR parsers, introduced below, can handle left-recursive rules directly.

Alternatives can also share a prefix. ForCall = IDENT "(" ... and Name = IDENT, a single name token cannot decide which alternative applies. Read the name first, then inspect the next token. This isleft factoring: moving shared work outside a choice. Our postfix rule goes further by allowing any atom to acquire suffixes.

You will sometimes see FIRST andFOLLOW sets. FIRST lists tokens that can begin a rule; FOLLOW lists tokens that can appear immediately after it in a surrounding rule. Sprout’s Type starts with a name or &. In a parameter list, a completed parameter is followed by , or ). These sets help choose alternatives and decide when optional or repeated parts should stop. A rule isnullable if it can match nothing; never repeatedly call a nullable rule without a progress check.

Pratt parsing: replace layers with binding powers

A Pratt parser is a compact way to write the expression part of a recursive-descent parser. It reads an initial operand, then keeps attaching operators strong enough for the current call. Each operator has a numericbinding power; larger numbers mean tighter grouping.

parse_expression(minimum):
    left = parse_atom_or_prefix()
    while next token is an infix operator:
        (left_power, right_power) = powers(next token)
        if left_power < minimum: break
        operator = bump()
        right = parse_expression(right_power)
        left = Binary(operator, left, right)
    return left

In the workbench, + and - use(10, 11); * and / use(20, 21). While parsing the right side of+ at minimum 11, a multiplication at 20 is admitted. Another addition at 10 is left for the outer loop. That produces left associativity. With this particular loop condition, equal left and right powers would instead admit the same operator into its right operand, giving right associativity.Matklad develops this technique with worked examples.

// An intentionally small expression language, not a Rust parser.
export type Expr = { label: string; children: Expr[] };
type Token = { text: string; at: number };

export function parseExpression(source: string) {
	if (source.length > 160)
		throw new Error('Please use at most 160 characters.');
	const tokens: Token[] = [];
	const trace: string[] = [];
	let offset = 0;
	while (offset < source.length) {
		const rest = source.slice(offset);
		const space = /^\s+/.exec(rest);
		if (space) {
			offset += space[0].length;
			continue;
		}
		const match = /^(?:[A-Za-z_][A-Za-z_0-9]*|[0-9]+|[()+*/-])/.exec(rest);
		if (!match)
			throw new Error(`Unexpected character at column ${offset + 1}.`);
		tokens.push({ text: match[0], at: offset });
		offset += match[0].length;
	}
	tokens.push({ text: '<end>', at: source.length });
	let cursor = 0;
	const peek = () => tokens[cursor];
	const take = () => tokens[cursor++];
	const fail = (message: string): never => {
		throw new Error(`${message} At column ${peek().at + 1}.`);
	};
	const powers: Record<string, [number, number]> = {
		'+': [10, 11],
		'-': [10, 11],
		'*': [20, 21],
		'/': [20, 21],
	};

	function expression(minimum: number): Expr {
		let left: Expr;
		const token = peek().text;
		if (token === '-') {
			take();
			left = { label: 'negate', children: [expression(30)] };
			trace.push(
				'Build unary −: its operand admits operators of power 30 or higher.',
			);
		} else if (token === '(') {
			take();
			left = expression(0);
			if (peek().text !== ')') fail('Expected a closing parenthesis.');
			take();
			trace.push('Close parentheses: return the enclosed tree as one operand.');
		} else if (/^(?:[A-Za-z_][A-Za-z_0-9]*|[0-9]+)$/.test(token)) {
			take();
			left = { label: token, children: [] };
			trace.push(`Read ${token} as a leaf.`);
		} else {
			fail('Expected a name, integer, unary minus, or opening parenthesis.');
		}
		while (true) {
			const operator = peek().text;
			const power = Object.hasOwn(powers, operator)
				? powers[operator]
				: undefined;
			if (!power || power[0] < minimum) break;
			take();
			trace.push(
				`Accept ${operator} (power ${power[0]} ≥ ${minimum}); parse its right side at ${power[1]}.`,
			);
			const right = expression(power[1]);
			left = { label: operator, children: [left, right] };
			trace.push(
				`Build ${operator} with the left and right trees as children.`,
			);
		}
		return left;
	}

	const tree = expression(0);
	if (peek().text !== '<end>') fail(`Unexpected token “${peek().text}”.`);
	return { tree, tokens: tokens.slice(0, -1), trace };
}

export function parenthesize(tree: Expr): string {
	if (!tree.children.length) return tree.label;
	if (tree.children.length === 1) return `(-${parenthesize(tree.children[0])})`;
	return `(${parenthesize(tree.children[0])} ${tree.label} ${parenthesize(tree.children[1])})`;
}

06 / Several routes through the same forest

Meet the parser families

A context-free grammar replaces a named category by its expansion without consulting surrounding categories. It can describe recursive nesting. It does not automatically enforce facts such as “this name was declared earlier”. Different parser strategies support different grammar shapes and make different tradeoffs.

In a bottom-up parser, shift means consume the next token onto the stack; reduce means replace a recognised sequence by the category it matches. LR reads Left to right and reconstructs a Rightmost derivation in reverse. After reading a + b with * ahead, ashift/reduce conflict asks whether to finish the addition now or read more input. Precedence can tell it to shift and finish the multiplication first. Areduce/reduce conflict means two different completed rules compete.

A conflict is not always proof that the language itself is ambiguous. It can reflect insufficient lookahead, merged parser states, or rules that need restructuring. Ask for the shortest conflicting input and draw the candidate trees before adding a precedence directive.

PEG choice deserves special care. InStart = ("a" / "ab") EOF, a PEG chooses"a" on input ab; the later end-of-input check fails. It does not reopen that already successful choice to try "ab". Put the longer alternative first in this example. This differs from the unordered alternatives in our EBNF.Bryan Ford’s PEG paper explains the recognition model and packrat connection.

Parser combinatorsare another way to express a parser: small parser functions are composed with operations like “sequence”, “choice”, and “repeat”. That is an implementation style, not a guarantee of a particular algorithm. Learn the library’s consumption, backtracking, and error rules before translating a grammar mechanically.

07 / A grammar that generates an editor parser

Tree-sitter: make structure available while typing

Tree-sittercombines a parser generator with an incremental parsing runtime. “Incremental” means it can reuse work after an edit instead of rebuilding everything from scratch. It is designed to produce useful concrete syntax trees even for code that is temporarily broken. It uses LR-style parsing with support for exploring multiple possibilities at declared conflicts.The project overview describes its editor focus.

Its grammar is written in a small JavaScript-based language.seq means sequence, choice means alternatives, repeat means zero or more, andoptional means zero or one.$.expression refers to another rule. The first rule is the entry point. Here is an independent, smaller arithmetic language: every expression must end in a semicolon, and there are no functions or unary operators.

// grammar.js — a complete, separate arithmetic language
export default grammar({
  name: 'sprout',
  extras: $ => [/\s/],
  rules: {
    source_file: $ => repeat($.statement),
    statement: $ => seq($.expression, ';'),
    expression: $ => choice(
      $.identifier, $.integer, $.group, $.binary_expression
    ),
    identifier: $ => /[a-zA-Z_][a-zA-Z_0-9]*/,
    integer: $ => /[0-9]+/,
    group: $ => seq('(', $.expression, ')'),
    binary_expression: $ => choice(
      prec.left(1, seq(
        field('left', $.expression),
        field('operator', choice('+', '-')),
        field('right', $.expression)
      )),
      prec.left(2, seq(
        field('left', $.expression),
        field('operator', choice('*', '/')),
        field('right', $.expression)
      ))
    )
  }
});

prec.left(2, ...)gives multiplication a higher precedence than addition at 1, and requests left associativity. field gives children stable roles such as left and right; consumers can ask for a role instead of counting child positions. extras allows whitespace between syntax elements. This is a translation of intent into a generator’s rules, not a line-for-line copy of the layered EBNF. See thegrammar DSL reference.

Make each rule earn its place

In a parser project created with the Tree-sitter CLI, replacegrammar.js with the example, then runtree-sitter generate. Parse a file containinga + b * 2; withtree-sitter parse example.sprout. Inspect the tree: the right child of the addition should be a multiplication. Put input and expected tree pairs in test/corpus/ and run tree-sitter test. Consult thesetup guidefor installation and project initialization.

When the generator reports a conflict, first decide whether one interpretation is always intended. If so, refactor or apply static precedence. Declare conflicts when multiple interpretations really must remain available; dynamic precedence can rank surviving interpretations during parsing. Lexical precedence, which chooses a token, is different from parse precedence, which chooses structure. Some difficult token forms need an external scanner.The grammar-writing guide explains these decisions.

A Tree-sitter tree is a syntax interface for highlighting, queries, and navigation. It does not resolve names, check Rust traits, or prove that a program compiles. Also, skipped whitespace need not appear as tree nodes: “concrete syntax tree” does not by itself mean every source byte is stored as a leaf.

08 / Choose what the tree remembers

Rowan: keep the whole source

An abstract syntax tree, or AST, keeps the structure useful for analysis.Add(Name("a"), Int(1)) may omit spaces, comments, and parentheses whose effect is already encoded by nesting. Aconcrete syntax tree, or CST, retains more of the written syntax. A lossless tree goes further: traversing its token text can reconstruct the exact source.

a /* why? */ + 1

BINARY
  NAME "a"
  SPACE " "
  COMMENT "/* why? */"
  SPACE " "
  PLUS "+"
  SPACE " "
  INTEGER "1"

Rowan is a Rust library for lossless syntax trees, not a parser generator.You supply the grammar decisions, token kinds, diagnostics, and tree construction. Its green tree stores immutable structure; red syntax nodes add contextual navigation such as parents and offsets. Immutable subtrees can be shared. These facilities help build editors, but do not choose reparse boundaries for you.The Rowan projectlinks its examples and tree design documentation.

A parser can emit events such as “start binary expression”, “consume token”, and “finish node”. A builder turns them into a tree, restoring skipped whitespace and comments in source order. Typed wrappers then expose operations such as “get this function’s name” without requiring callers to understand every raw node kind.

This is the broad pattern in rust-analyzer: a handwritten recursive-descent parser, Rowan syntax trees, and typed AST accessors. Its parser produces a tree plus errors for malformed input. The project’sungrammar description helps generate tree APIs; it should not be mistaken for the executable parsing grammar.The architecture guide separates these responsibilities.

That makes “Tree-sitter or Rowan?” an incomplete question. Tree-sitter supplies parsing machinery and its own tree representation. Rowan supplies a tree library that you can pair with a handwritten parser. Compare the whole toolchain you need, including diagnostics, tree fidelity, query APIs, and incremental updates.

09 / Open the reference without getting lost

Read a real Rust rule

The Rust Reference presents linked grammar fragments alongside explanatory prose. Its notation includes token names, named productions, repetition, and grouping. Read the legend first: unlike our unordered EBNF, the current legend describes ordered alternation and a hard-cut operator for committed matching.Keep the notation page openrather than assuming every grammar uses the same conventions.

Now open thefunction rule. It describes qualifiers, fn, a name, optional generic parameters, parenthesised parameters, an optional return type and where-clause, then a body or a semicolon. Here is an original example that exercises those parts:

async fn choose<'a, T>(value: &'a T) -> &'a T
where
    T: Copy,
{
    value
}

Use a pencil-and-paper cursor. Match the outer structure first. When you reach the parameter list, descend into just that rule. When it finishes at ), return to the function rule. You are manually doing recursive descent; you do not need to memorise every linked rule.

Then read the prose and footnotes. A semicolon appears as an alternative to a body, but bodyless functions are restricted to contexts such as traits and external blocks. A syntax alternative is not permission to use it everywhere. This distinction is part of reading the language specification, not an annoying exception to the grammar.

10 / Complexity has identifiable causes

Where Rust gets interesting

The same spelling can belong to different categories

(x, y)can be a tuple expression, whilelet (x, y) = pair; uses a tuple pattern.(i32, i32) in a type annotation is a tuple type. Dispatch according to the enclosing rule: parse a pattern afterlet and a type after its annotation colon. Do not create a universal “tuple” rule and assume every element has the same role.

Angle brackets need a context

let values: Vec<Vec<u8>> = Vec::new();
let n = size_of::<u64>();
let smaller = a < b;

In a type, angle brackets introduce generic arguments. In an expression path, the ::<...> spelling—the “turbofish”—distinguishes them from comparison operators. Closing nested generic arguments also means that>> cannot always be treated as an indivisible shift operator; the parser and token interface must support the appropriate interpretation.The path grammar describes the expression/type distinction.

A brace may start a value or a control-flow body

Rust uses braces for both struct expressions and blocks. Afterif ready, the next brace should start the branch body. A naive “parse any expression” routine could instead try to attach a struct literal to a preceding path. Rust restricts unparenthesised struct expressions in certain positions, including conditions. An implementation can pass an expression-context flag and use parentheses to enter an unrestricted expression context.The struct-expression reference documents these restrictions.

A semicolon is not just decoration

Rust allows block-like expressions such as if andmatch in statement positions with rules that differ from ordinary arithmetic expressions. It also distinguishes a block’s tail value from its statements. Our Sprout block algorithm is therefore a starting point, not a full Rust statement parser. Read thestatement rulesandblock-expression rulestogether.

Macros introduce another layer of syntax

A Rust macro invocation contains token trees: individual tokens or recursively balanced delimiter groups. The contents may use a macro-specific syntax rather than ordinary Rust expressions. For example, the semicolon in vec![0; 4] has a meaning assigned by that macro. Recognise the invocation and its balanced input, then let macro processing interpret it. Expanded output can need parsing again.The macro reference introduces token trees and invocation forms.

Finally, track edition and syntactic context where the language requires them. Whether a token acts as a keyword, which forms are allowed, and what a construct means are not all settled by one giant context-free production. Keep these restrictions explicit and tested. A parser that silently consults unrelated type-checker state is much harder to understand and reuse.

11 / The user is still typing

Design for unfinished code

An editor spends much of its life looking at invalid input. After let result =, the user has not necessarily made a mistake; they may be about to type the value. A useful parser returns the structure it can recognise and diagnostics for the missing pieces.

fn example() {
    let broken = ;
    let good = 2;
    good
}

At the first semicolon, report “expected an expression after=”. Record a missing expression or an error node according to your tree model, finish the binding, and continue. The second binding should still appear in the tree. Anerror node can preserve unexpected text; amissing token can represent expected punctuation with no source characters.

Synchronizationmeans resuming at a useful boundary. For a statement, that might be a semicolon, closing brace, or next let. Do not skip blindly to the next semicolon: it could be inside nested delimiters. Track nesting, and let the block parser own its closing brace.

while not at("}") and not at(EOF):
    before = cursor
    parse_statement_or_tail_with_recovery()
    if cursor == before:
        record_error_and_consume_one_token()
expect("}")

The progress check is a termination guarantee. A recovery routine must consume something, return to a caller that will consume something, or stop at a boundary. For a missing semicolon before the next let, you can record a missing token and keep that next keyword for the following statement. A parser should not destroy useful structure merely to make an error disappear.

Test the tree, not just “accepted”

Keep a corpus of source snippets and expected trees. Include each alternative, an empty and non-empty list, a trailing comma, and mixed precedence. Then remove or duplicate punctuation. Check where errors point, whether the following construct survives, and whether parsing terminates.

For a lossless tree, concatenating leaf text must reproduce the input, including malformed fragments. For an incremental parser, parse after an edit and compare its structure with a fresh parse of the same final text. These checks catch problems that a successful parse alone cannot reveal.

12 / Put the method to work

Your next grammar

Build outward from Sprout in small, inspectable steps. For each new construct, write an example, a rule, an expected tree, and a deliberately broken example. Decide which parser routine owns the opening and closing punctuation before writing the implementation.

1. Add tuple types.Permit (i32, &i32). Decide how(), (i32), and(i32,) differ before choosing your list rule.
2. Implement postfix expressions.Extend the workbench with f(1).x[0]. Draw the nested tree first, and make suffixes bind more tightly than unary minus.
3. Add generic types.Support Map<Key, Vec<Value>>. Make a generic argument a type, then test nested closing brackets.
4. Add recovery.Delete a closing parenthesis or an initializer. Preserve the next binding and require forward progress.

Type      = IDENT | "&" "mut"? Type | ParenType ;
ParenType = "(" ")"
          | "(" Type ")"
          | "(" Type "," (Type ("," Type)* ","?)? ")" ;

When reading a large grammar, use the same method in reverse. Identify the enclosing category, translate one rule into plain English, trace a concrete example, and follow only the nonterminals that example needs. Mark the places where prose adds a restriction. A complex language becomes approachable when each choice has a reason.