PEG Parser in DuckDB 2.0

DuckDB 2.0 is coming soon. I’m most interested in the new PEG parser, which allows extensions to add new grammar rules at runtime. Here is my chat with AI.

PEG

DuckDB 1.5 uses a modified PostgreSQL-derived LALR(1) parser generated with Flex/Bison from Bison grammar files (.y). Given my limited PL knowledge, I focus on these questions:

How are the grammar rules written?
How is the parser generated from the grammar rules?
How does the parsing process work?
Is PEG as expressive as LALR(1) or LL(1)?

PEG Grammar

DuckDB implements its own PEG parser, allowing it to express grammar more flexibly. Consider the DELETE statement:

Bison style:

DeleteStmt:
    opt_with_clause DELETE_P FROM relation_expr_opt_alias
    using_clause where_or_current_clause returning_clause
    ;

using_clause:
    USING from_list_opt_comma
    | /* EMPTY */
    ;

(DuckDB’s) PEG style:

DeleteStatement <- WithClause? 'DELETE' 'FROM' TargetOptAlias
                   DeleteUsingClause? WhereClause? ReturningClause?
DeleteUsingClause <- 'USING' List(TableRef)

DuckDB’s PEG syntax supports ? for inline optional expressions and parameterized rules such as List(...). Most grammar rules look the same except DuckDB-chosen operators <-, /, ?, *, +. Python’s PEG grammar, for example, looks closer to Bison.

PEG Parser

A PEG parser processes tokens with recursive, DFS-like matching. Conceptually, every matcher returns either success(end, result) or failure.

A sequence A B tries to match A at the given pos, then tries to match B where A ends. If either match fails, the complete sequence fails without consuming input:

Match(A B, pos):
    a = Match(A, pos)
    if a failed:
        return failure

    b = Match(B, a.end)
    if b failed:
        return failure

    return success(b.end, [a.result, b.result])

An alternative A / B tries to match A first and, if it fails, tries to match B.

Match(A / B, pos):
    a = Match(A, pos)
    if a succeeded:
        return a
    return Match(B, pos)

A? tries to match A; if it fails, the expression succeeds without consuming input.

Match(A?, pos):
    a = Match(A, pos)
    if a succeeded:
        return a
    return success(pos, empty)

A+ matches A once, then continues matching A until the next attempt fails.

Match(A+, pos):
    first = Match(A, pos)
    if first failed:
        return failure

    results = [first.result]
    pos = first.end
    while Match(A, pos) succeeds as a:
        results.append(a.result)
        pos = a.end

    return success(pos, results)

Given the parsing process, I have questions:

Backtracking might take time. Does that mean PEG is theoretically slower than LALR(1)? What is the time complexity of DuckDB’s PEG parser?

LALR(1) is ; full packrat PEG is for a fixed grammar; DuckDB’s selective packrat has no general linear-time guarantee.

A PEG without memoization can take exponential time. After a branch fails, backtracking may evaluate the same rule again at the same token position, and nested choices can multiply that repeated work.
Full packrat parsing caches every (matcher, token position) result. Given matchers and tokens, each pair is evaluated at most once, giving time. Because the grammar is fixed, is constant and this becomes .
DuckDB memoizes only certain expression and identifier rules. Those cached rules avoid repeated evaluation, but uncached rules can still backtrack. The standard full-packrat proof therefore does not establish an bound for the complete DuckDB parser. Its exact worst-case complexity depends on the current grammar; proving an exponential input family would require a separate analysis.

Parser Worst-case time
LALR(1)
PEG without memoization potentially exponential
Full packrat PEG , or for a fixed grammar
DuckDB PEG grammar-dependent; no documented general guarantee
Since it might backtrack later, must PEG retain all tokens instead of just the next token? Does that rule out streaming parsing?

Not necessarily, but a general PEG cannot guarantee a fixed-size token buffer. DuckDB currently tokenizes the full query once.

If an alternative consumes a long prefix and then fails, the parser must rewind to the beginning of that alternative. It must retain those tokens or be able to read them again. Packrat parsing also stores results indexed by token position, normally requiring memory proportional to the input.
DuckDB’s ParseIterator::EnsureTokenized() explicitly tokenizes the complete query into a token vector once. It parses multi-statement input one statement at a time, but it does not provide bounded-memory token streaming.
PEG can support bounded buffering when a grammar has bounded backtracking, provides commit points, or divides input into independent units. LALR is more naturally streaming because it generally needs only one lookahead token, although its parse stack and resulting AST can still grow with the input.
In Bison, we can run an action upon reduction. Is that impossible in PEG because of backtracking?

Yes. PEG has no LR reduce step. DuckDB builds the AST after matching succeeds.

Bison actions run when the LR parser reduces a production. PEG has no equivalent reduction event. Running externally visible actions during speculative matching is unsafe because the current branch may later fail and backtrack.
DuckDB instead lets matchers produce a ParseResult tree. After the statement matches, PEGTransformer walks that result and constructs the DuckDB AST.
Does PEG have shift-reduce or reduce-reduce conflicts? Is left recursion allowed?
PEG has no LR conflicts. DuckDB’s PEG parser does not support left recursion, although some PEG implementations do.
PEG has no shift-reduce or reduce-reduce conflicts because it has no LR parse table. Choice is ordered:
```
Value <- FunctionCall / Identifier
```
The first successful alternative wins. This removes table conflicts, but ordering mistakes can silently shadow later alternatives; specific alternatives generally need to come before their prefixes.
DuckDB’s recursive matcher cannot process direct left recursion:
```
Expression <- Expression '+' Term / Term
```
It would recurse at the same token position forever. It is normally rewritten as:
```
Expression <- Term ('+' Term)*
```
The AST transformer then folds the sequence from the left to preserve associativity.
Is PEG language “greater than” LALR(1) or LL(1)?

Here means the set of languages for which some grammar in class exists.
LL(1) must select a production using one lookahead token, so it recognizes a proper subset of the deterministic context-free languages recognized by LALR(1). LALR’s bottom-up state and parse stack retain more context than an LL(1) parser’s single predictive choice.
Standard PEGs contain the deterministic context-free languages and can also recognize some non-context-free languages through syntactic predicates. This makes the second inclusion strict as well.
This comparison concerns language families, not whether the same grammar text works with each parser. Converting an EBNF or LALR grammar to PEG may require ordering overlapping alternatives, removing left recursion, and rewriting greedy repetition.
It also concerns the theoretical PEG formalism with syntactic predicates and full-input matching, not necessarily DuckDB’s currently restricted PEG implementation.

Parser	Worst-case time
LALR(1)
PEG without memoization	potentially exponential
Full packrat PEG	, or for a fixed grammar
DuckDB PEG	grammar-dependent; no documented general guarantee

Extensible Grammar

Although a PEG parser might not appear to perform as well as Bison’s LALR(1) parser, Hannes and Mark’s paper proposes a runtime-extensible parser design.

In DuckDB 2.0, grammar rules are stored as a recursive ADT rather than as a compiled finite-state machine (FSM), allowing extensions to modify these rules at runtime. A simplified representation:

enum class MatcherType {
    KEYWORD,
    LIST,       // sequence: A B
    CHOICE,     // ordered choice: A / B
    OPTIONAL,   // A?
    REPEAT      // A+; A* is Optional(Repeat(A))
};

class Matcher {
    MatcherType type;
};

class ListMatcher : public Matcher {
    vector<reference<Matcher>> children;
};

class ChoiceMatcher : public Matcher {
    vector<reference<Matcher>> alternatives;
};

class OptionalMatcher : public Matcher {
    reference<Matcher> child;
};

class RepeatMatcher : public Matcher {
    reference<Matcher> child;
};

The matchers can be rebuilt after grammar changes. In the following example, the statement iterator deliberately executes LOAD before parsing the next statement, so an extension can register its syntax and use it later in the same query string.

LOAD 'loadable_extension_demo'; -- load parser extension
quack quack quack;

This is a significant step for database extensibility. In pg_ducklake, for example, we expose DuckLake tables in the Postgres catalog and would like to support syntax such as CREATE TABLE t (...) USING ducklake WITH (path='...'). In PostgreSQL (and most DBMSs), we must either replace the built-in parser or modify the database source to add such syntax.