Parsers and ASTs: Recursive Descent, Operator Precedence and Pratt Parsing

Version note: The code in this post was built with .NET 10 (SDK 10.0.404) and C# 14 and verified with xUnit v3 4.0.3 tests.

Guess First

The lexer for the filter language we write for Bookstore, the online bookstore used as the shared example across this site's series, is ready; now we arrange the tokens into a tree. Two questions. First: which operator sits at the root of the tree for the filter stock = 0 or price < 300 and year < 1900, or or and? The operator at the root decides which books the filter returns.

Second: someone pastes 100,000 opening parentheses, price < 300 and 100,000 closing parentheses into the search box. What does a parser derived one-to-one from the grammar do with that input: slow down, report an error, or take the process down?

Grammar, Ambiguity, Precedence and Associativity

In post 01 we wrote the language's grammar in EBNF. We could have written it more briefly:

expr = expr , op , expr | field | literal | "(" , expr , ")" ;
op   = "or" | "and" | "=" | "<" | "contains" ;

This grammar accepts the right sentences but it is ambiguous: for a or b and c two different trees can be built, (a or b) and c and a or (b and c). Both fit the grammar, but they return different books. For a parser to produce a single tree it needs two pieces of information. Precedence says which of two different operators binds tighter: and binds tighter than or. Associativity says which way to group when the same operator repeats: a and b and c reads as (a and b) and c, so and is left-associative.

The grammar from post 01 builds both into the structure of its rules: the or_expr rule is made of and_exprs, and and_expr is made of not_exprs. The lower a rule sits, the tighter its operator binds. The repetition in the form { "and" , not_expr } gives left-associativity. Comparison has no repetition: comparison = primary , [ comp_op , primary ]. That is a deliberate choice; the language does not accept a chain such as price < 300 < 400. It also gives the answer to the first guess: or is at the root, and the filter means "books that are out of stock, or cheap books from before 1900".

Building the AST with C# Records

Let's design the tree the parser will produce first. A tree that mirrors the grammar one-to-one (a parse tree) carries a node for every rule. Even price < 300 goes through the chain or_expr → and_expr → not_expr → comparison → primary; parentheses and EndOfInput also have a place in the tree. The later stages need none of this. The AST keeps only the meaning: a comparison, its two sides and its operator.

namespace Bookstore.Filter.Syntax;

public enum ComparisonOperator { Equal, NotEqual, Less, LessOrEqual, Greater, GreaterOrEqual, Contains }

public enum LogicalOperator { And, Or }

// Position points at the token that best explains the node: the operator for binary nodes.
public abstract record Expr(SourcePosition Position);

public sealed record Identifier(string Name, SourcePosition Position) : Expr(Position);

// Value is decimal, string or bool
public sealed record Literal(object Value, SourcePosition Position) : Expr(Position);

public sealed record ComparisonExpr(Expr Left, ComparisonOperator Operator, Expr Right, SourcePosition Position)
    : Expr(Position);

public sealed record BinaryExpr(Expr Left, LogicalOperator Operator, Expr Right, SourcePosition Position)
    : Expr(Position);

public sealed record NotExpr(Expr Operand, SourcePosition Position) : Expr(Position);

// stands in for a part of the input that could not be parsed; the error is already reported
public sealed record ErrorExpr(SourcePosition Position) : Expr(Position);

public sealed record ParseResult(Expr Root, IReadOnlyList<Diagnostic> Diagnostics)
{
    public bool Success => Diagnostics.Count == 0;
}

Choosing records brings three benefits. The nodes are immutable; a stage cannot modify the tree, it produces a new one. Equality works on values; a single Assert.Equal can test that two parsers produce the same tree. And since the hierarchy is closed, the code that walks the tree is written with switch pattern matching; there is no need for separate classes for the visitor pattern. ErrorExpr is part of error recovery: the parser does not stop at a broken spot, it puts a placeholder there and carries on.

From Grammar to a Recursive Descent Parser

Recursive descent means turning each grammar rule into a method. If a rule mentions another rule, the method calls it; a { ... } repetition becomes a while, a [ ... ] option becomes an if. The mapping between grammar and code is so direct that we wrote each rule as a comment above its method:

// or_expr = and_expr , { "or" , and_expr } ;
private Expr ParseOr()
{
    Expr left = ParseAnd();
    while (Current.Kind == TokenKind.Or)
    {
        Token op = Advance();
        left = new BinaryExpr(left, LogicalOperator.Or, ParseAnd(), op.Position);
    }
    return left;
}

// not_expr = "not" , not_expr | comparison ;
private Expr ParseNot()
{
    if (Current.Kind != TokenKind.Not)
        return ParseComparison();
    Token not = Advance();
    return new NotExpr(ParseNot(), not.Position);
}

// comparison = primary , [ comp_op , primary ] ;
private Expr ParseComparison()
{
    Expr left = ParsePrimary();
    if (Operators.Comparison(Current.Kind) is not ComparisonOperator op)
        return left;
    Token opToken = Advance();
    return new ComparisonExpr(left, op, ParsePrimary(), opToken.Position);
}

The loop in ParseOr is the code for left-associativity: every new or makes the tree built so far its left child. ParseAnd calls ParseNot the same way (not shown to save space), and ParsePrimary reads a field, a literal or a parenthesized expression. Inside the parentheses it goes back to ParseOr; that is where the "recursive" in recursive descent comes from.

There is one thing to watch before coding a grammar. It seems natural to express left-associativity with the rule itself: or_expr = or_expr , "or" , and_expr | and_expr. This rule is left-recursive: its first element is itself. Write the code one-to-one and the first line of ParseOr is ParseOr() again, which keeps calling itself without consuming a single token. When we ran that in a small experiment, the process printed Stack overflow. and Repeated 40192 times: at LeftRec.ParseOr() and exited. The fix is to turn left recursion into repetition; the { ... } in EBNF does exactly that.

Pratt Parsing: Moving Precedence into a Table

In recursive descent, precedence is hidden in the order in which the methods call each other. Adding a new precedence level (say, xor) means a new method and changing the calls of two others; in a language with ten levels, parsing a comparison goes through ten methods. The idea Vaughan Pratt published in 1973, "Top Down Operator Precedence", moves precedence into a table. Every infix operator has a left and a right binding power; in a single loop, the parser collects the operators that bind more strongly than the minimum it was given:

// (left, right) binding power; left < right means left-associative
private static (int Left, int Right)? BindingPower(TokenKind kind) => kind switch
{
    TokenKind.Or => (10, 11),
    TokenKind.And => (20, 21),
    TokenKind.Equal or TokenKind.NotEqual or TokenKind.Less or TokenKind.LessOrEqual
        or TokenKind.Greater or TokenKind.GreaterOrEqual or TokenKind.Contains => (40, 41),
    _ => null,
};

private Expr ParseExpression(int minBindingPower)
{
    if (++_depth > MaxDepth)
    {
        Error(Current.Position, $"filter is nested too deeply (limit {MaxDepth})");
        // skip to EndOfInput and stay quiet: the missing ')' errors would only repeat this one
        _tooDeep = true;
        _pos = _tokens.Count - 1;
        _depth--;
        return new ErrorExpr(Current.Position);
    }

    Expr left = ParsePrefix();
    while (BindingPower(Current.Kind) is (int leftPower, int rightPower) && leftPower >= minBindingPower)
    {
        Token op = Advance();
        Expr right = ParseExpression(rightPower);
        left = MakeInfix(left, op, right);
    }

    _depth--;
    return left;
}

private Expr MakeInfix(Expr left, Token op, Expr right)
{
    if (op.Kind == TokenKind.And)
        return new BinaryExpr(left, LogicalOperator.And, right, op.Position);
    if (op.Kind == TokenKind.Or)
        return new BinaryExpr(left, LogicalOperator.Or, right, op.Position);

    if (left is ComparisonExpr)
        Error(op.Position, "comparisons cannot be chained; combine them with 'and'");
    return new ComparisonExpr(left, Operators.Comparison(op.Kind)!.Value, right, op.Position);
}

Let's trace the algorithm on stock = 0 or price < 300 and year < 1900. ParseExpression(0) builds stock = 0 and sees or: its left power is 10, greater than the minimum 0, so it continues. It reads the right side with ParseExpression(11). That call builds price < 300, then sees and: its left power is 20, greater than 11, so and stays inside this call and takes year < 1900 as well. The result is stock = 0 or (price < 300 and year < 1900). For left-associativity it is enough for the right power to be one more than the left: in a and b and c, the second and has a left power of 20 and the inner call's minimum is 21; the inner call does not take it, the outer loop does, and the result is (a and b) and c. If you want to add a right-associative operator (such as exponentiation), you just give it a right power lower than its left.

The prefix side lives in ParsePrefix: fields, literals, parentheses and not. not reads its operand with a power of 30; comparison (40) stays inside, and (20) stays outside. So not stock = 0 and price < 300 becomes (not (stock = 0)) and price < 300, which is what the grammar in post 01 said too.

A test pins down that both parsers really recognize the same language. Thanks to value equality on records, the test is a single line:

[Theory]
[InlineData("price < 300 and author = \"Jane Austen\"")]
[InlineData("stock = 0 or price < 300 and year < 1900")]
[InlineData("not not (title contains \"Dune\" or price >= 100.50) and stock != 0")]
[InlineData("true")]
public void Parse_PrattAndRecursiveDescent_ProduceTheSameAst(string text)
{
    Assert.Equal(RecursiveDescentParser.Parse(text), ParseOk(text));
}

$ dotnet run --project src/Bookstore.Filter.Cli -- ast 'price < 300 and author = "Jane Austen"'
BinaryExpr And @1:13
├─ ComparisonExpr < @1:7
│  ├─ Identifier price @1:1
│  └─ Literal 300 @1:9
└─ ComparisonExpr = @1:24
   ├─ Identifier author @1:17
   └─ Literal "Jane Austen" @1:26

Error Recovery: Panic Mode and Multiple Errors

Our recursive descent parser throws an exception at the first error. That may look enough for a filter box, but a user with three mistakes in a filter has to submit it three times. The Pratt parser uses panic mode instead: when it sees an unexpected token it records the error, skips ahead to a token that can continue the filter (and, or, ) or the end of input), puts an ErrorExpr there and carries on:

default:
    string found = token.Kind == TokenKind.EndOfInput ? "end of input" : $"'{token.Text}'";
    Error(token.Position, $"expected a field, a value or '(' but found {found}");
    Synchronize();
    return new ErrorExpr(token.Position);

// panic mode: skip tokens until one that can continue the filter
private void Synchronize()
{
    while (Current.Kind is not (TokenKind.EndOfInput or TokenKind.And or TokenKind.Or or TokenKind.CloseParen))
        Advance();
}

$ dotnet run --project src/Bookstore.Filter.Cli -- ast 'price < and stock > or (title = "Dune"'
BinaryExpr Or @1:21
├─ BinaryExpr And @1:9
│  ├─ ComparisonExpr < @1:7
│  │  ├─ Identifier price @1:1
│  │  └─ ErrorExpr @1:9
│  └─ ComparisonExpr > @1:19
│     ├─ Identifier stock @1:13
│     └─ ErrorExpr @1:21
└─ ComparisonExpr = @1:31
   ├─ Identifier title @1:25
   └─ Literal "Dune" @1:33
price < and stock > or (title = "Dune"
        ^ error at 1:9: expected a field, a value or '(' but found 'and'
price < and stock > or (title = "Dune"
                    ^ error at 1:21: expected a field, a value or '(' but found 'or'
price < and stock > or (title = "Dune"
                                      ^ error at 1:39: expected ')' to close '(' at 1:24

Three errors in a single pass, each at the right column. The tree is complete despite the broken parts; an editor could still do highlighting or completion on it. The unclosed-parenthesis error also naming the opening position is a small detail that helps. In a long filter, finding which opening a missing parenthesis belongs to is not left to the user. We do not write a second error for the Bad tokens the lexer produced; ParsePrefix quietly turns them into ErrorExpr, because the user should not see two messages for the same character.

A Tree-Walking Interpreter

The tree is ready; the shortest way to run it is to walk it for each book and compute the value. This is called a tree-walking interpreter, and with C# pattern matching it fits into a single switch expression:

public sealed class FilterRuntimeException(string message) : Exception(message);

// Tree-walking interpreter: evaluates the AST directly, once per book. Values are checked at run time.
public static class Interpreter
{
    public static IEnumerable<Book> Filter(IEnumerable<Book> books, Expr filter) =>
        books.Where(book => AsBool(Evaluate(filter, book), filter));

    public static object Evaluate(Expr expr, Book book) => expr switch
    {
        Literal literal => literal.Value,
        Identifier id => ReadField(id, book),
        NotExpr not => !AsBool(Evaluate(not.Operand, book), not),
        // && and || keep the short-circuit behaviour of the filter language
        BinaryExpr { Operator: LogicalOperator.And } and =>
            AsBool(Evaluate(and.Left, book), and.Left) && AsBool(Evaluate(and.Right, book), and.Right),
        BinaryExpr or =>
            AsBool(Evaluate(or.Left, book), or.Left) || AsBool(Evaluate(or.Right, book), or.Right),
        ComparisonExpr comparison => Compare(comparison, Evaluate(comparison.Left, book), Evaluate(comparison.Right, book)),
        _ => throw new FilterRuntimeException($"cannot evaluate a filter that has syntax errors (at {expr.Position})"),
    };

    private static object ReadField(Identifier id, Book book) => id.Name.ToLowerInvariant() switch
    {
        "isbn" => book.Isbn,
        "title" => book.Title,
        "author" => book.Author,
        "price" => book.Price,
        "year" => (decimal)book.Year,
        "stock" => (decimal)book.Stock,
        _ => throw new FilterRuntimeException($"unknown field '{id.Name}' at {id.Position}"),
    };

    private static bool Compare(ComparisonExpr c, object left, object right) => (left, c.Operator, right) switch
    {
        (decimal l, ComparisonOperator.Equal, decimal r) => l == r,
        (decimal l, ComparisonOperator.NotEqual, decimal r) => l != r,
        (decimal l, ComparisonOperator.Less, decimal r) => l < r,
        (decimal l, ComparisonOperator.LessOrEqual, decimal r) => l <= r,
        (decimal l, ComparisonOperator.Greater, decimal r) => l > r,
        (decimal l, ComparisonOperator.GreaterOrEqual, decimal r) => l >= r,
        (string l, ComparisonOperator.Equal, string r) => string.Equals(l, r, StringComparison.Ordinal),
        (string l, ComparisonOperator.NotEqual, string r) => !string.Equals(l, r, StringComparison.Ordinal),
        (string l, ComparisonOperator.Contains, string r) => l.Contains(r, StringComparison.Ordinal),
        (bool l, ComparisonOperator.Equal, bool r) => l == r,
        (bool l, ComparisonOperator.NotEqual, bool r) => l != r,
        _ => throw new FilterRuntimeException(
            $"operator '{Operators.Symbol(c.Operator)}' at {c.Position} cannot compare {TypeName(left)} with {TypeName(right)}"),
    };
}

$ dotnet run --project src/Bookstore.Filter.Cli -- run 'price < 300 and author = "Jane Austen"'
Emma                   Jane Austen       199.00 TRY  stock 7
Persuasion             Jane Austen       185.00 TRY  stock 3
Sense and Sensibility  Jane Austen       210.00 TRY  stock 5

Book is a six-field record in the Bookstore.Catalog namespace; the sample data is Dune, The Hobbit, Middlemarch and three Jane Austen novels. The interpreter's idea of types is dynamic: every value is an object and types are checked at the moment of comparison. Let's see what that leads to:

$ dotnet run --project src/Bookstore.Filter.Cli -- run 'stock > 0 or price = "abc"'
Dune                   Frank Herbert     349.90 TRY  stock 12
runtime error: operator '=' at 1:20 cannot compare number with string

The filter is plainly wrong, but the interpreter returned Dune first. Because or short-circuits, the right side was never evaluated for books in stock; the error only surfaced at the first book with zero stock, The Hobbit. With an empty catalog, or if every book were in stock, the error would never appear; one of the tests verifies exactly that. This is typical behavior of dynamic type checking, and it is the topic of the next post: catching the type error at compile time, before the filter touches any book.

In Production

The answer to the second guess. The recursive descent parser derived one-to-one from the grammar has no depth limit, and every level of parentheses means five method calls on the call stack:

$ dotnet run --project src/Bookstore.Filter.Cli -- nest 100000 rd
Stack overflow.
Repeated 6294 times:
--------------------------------
   at Bookstore.Filter.Syntax.RecursiveDescentParser.ParseNot()
   at Bookstore.Filter.Syntax.RecursiveDescentParser.ParseAnd()
   at Bookstore.Filter.Syntax.RecursiveDescentParser.ParseOr()
   at Bookstore.Filter.Syntax.RecursiveDescentParser.ParsePrimary()
   at Bookstore.Filter.Syntax.RecursiveDescentParser.ParseComparison()
--------------------------------

$ dotnet run --project src/Bookstore.Filter.Cli -- nest 100000 pratt
pratt: 1 diagnostic(s)
error at 1:65: filter is nested too deeply (limit 64)

In .NET a StackOverflowException cannot be caught; the runtime terminates the process. So a single request from a search box can take down the whole API. The level at which it overflows depends on the thread's stack size: the default for the main thread on Windows is 1 MB, on Linux it is usually larger, and frames are larger in a Debug build. "It worked up to 6,000 levels on our machine" is no guarantee. The Pratt parser counts depth, and once it goes past 64 it writes a single error and skips to the end of the input. 64 is more than enough for any filter a human will write.

A depth limit alone is not enough. A flat chain such as a and b and c ... does not make the parser go deeper (the Pratt loop collects it on one level), but the resulting AST grows deeper to the left, and the same risk comes back for an interpreter that walks the tree recursively. For that we will also put a limit on the input length; we will measure it and set the limit in post 04.

The interpreter walks the tree from the top for every book; every field read is a string switch and every number is boxed. With 10 books that does not matter; with a list of 100,000 rows, or thousands of requests per second, it does. Turning the tree into executable code once removes that cost, and we will do it in the next post by compiling it to an Expression Tree.

Common Pitfalls

Translating left recursion into code as it is. A rule of the form A = A , "x" | "y" sends a recursive descent parser into infinite recursion without consuming a token. Write it with repetition ({ }) or use the Pratt loop.

Leaving depth unbounded. Put a depth limit on every piece of recursive code that parses user input (JSON, XML, your own language). The default MaxDepth of System.Text.Json is 64; ours is the same.

Not testing precedence. Swapping and and or raises no error; it silently returns the wrong books. Write tests that check the root operator and associativity; if you have a second implementation (here, recursive descent), compare the two on the same inputs.

Moving to a parser generator too early, or never. Tools such as ANTLR pay off for large grammars like SQL or a full programming language, when the grammar changes often and when you need several target languages. For a small language like ours, a hand-written parser is shorter and gives full control over error messages. The parsers of Roslyn and TypeScript are hand-written recursive descent parsers too.

A Small Experiment

★☆☆ Add an xor operator with a precedence between and and or. How many lines changed in the Pratt parser, and how many methods in the recursive descent parser? Write a test that checks the precedence.

★★☆ Add the syntax price between 100 and 300. How does the parser tell the two meanings of the and keyword apart (logical, and part of between)? Print the AST for price between 100 and 300 and stock > 0.

★★★ Rewrite Interpreter.Evaluate without recursion, with an explicit Stack<T>, and compare the two versions on an and chain of 200,000 conditions. What do you need to keep on the stack to preserve short-circuit behavior?

We have a tree now, but we only see a mistake like price = "abc" while the filter runs, and only if we are lucky. In the next post we move on to semantic analysis: we bind fields to Book's properties with a symbol table, check types, then compile the verified tree to an Expression<Func<Book, bool>>, run it in memory and watch EF Core translate it to SQL.