Introduction

Packrat parsing is a top-down parsing technique that trades memory for predictable speed. It looks similar to recursive descent, but it memoizes parsing results so the parser does not repeat the same work over and over when backtracking.

The Core Idea

A normal backtracking recursive-descent parser can become slow because the same rule may be tried repeatedly at the same input position. Packrat parsing fixes that by caching the result of each rule at each position.

The cache key is usually:

• the rule name
• the current input index

The cached value is usually:

• success or failure
• the parsed result
• the next input position

That means each rule-position pair is computed at most once. For grammars written as Parsing Expression Grammars, usually shortened to PEGs, this gives linear-time parsing with respect to input length.

Why Packrat Parsing Is Associated with PEGs

Packrat parsing is most commonly used with PEGs because PEGs define ordered choice. Ordered choice means "try the first alternative, and only if it fails, try the next one." That removes ambiguity in a way that is convenient for top-down parsers.

For example, a PEG rule might conceptually mean:

identifier / keyword

That does not mean "either, in any parse tree." It means "try identifier first, and only try keyword if that fails."

Memoization makes this style practical even when the grammar backtracks often.

A Small Packrat Parser in Python

The following example parses sums of integers such as 12+7+3. It is intentionally tiny, but it demonstrates the memo table clearly.

1class PackratParser:
2    def __init__(self, text):
3        self.text = text
4        self.memo = {}
5
6    def parse_number(self, pos):
7        key = ("number", pos)
8        if key in self.memo:
9            return self.memo[key]
10
11        start = pos
12        while pos < len(self.text) and self.text[pos].isdigit():
13            pos += 1
14
15        if start == pos:
16            result = None
17        else:
18            result = (int(self.text[start:pos]), pos)
19
20        self.memo[key] = result
21        return result
22
23    def parse_expr(self, pos=0):
24        key = ("expr", pos)
25        if key in self.memo:
26            return self.memo[key]
27
28        left = self.parse_number(pos)
29        if left is None:
30            self.memo[key] = None
31            return None
32
33        value, pos = left
34        while pos < len(self.text) and self.text[pos] == "+":
35            right = self.parse_number(pos + 1)
36            if right is None:
37                self.memo[key] = None
38                return None
39            number, pos = right
40            value += number
41
42        result = (value, pos)
43        self.memo[key] = result
44        return result
45
46
47parser = PackratParser("12+7+3")
48parsed = parser.parse_expr()
49print(parsed)

Output:

(22, 6)

The memo table is the important part. If parse_expr or parse_number are asked to parse from the same position again, the parser reuses the saved result instead of re-scanning the same characters.

What You Gain and What You Pay

The main advantage is time predictability. Backtracking becomes much less scary because repeated failures do not cause exponential blowups in the same way as a naive parser.

The main cost is memory. A packrat parser stores an entry for many rule-position pairs, so memory usage is often proportional to the grammar size times the input length. That is acceptable for many programming-language parsers, but it can be expensive for huge inputs.

In other words:

• time is usually linear
• memory is often also linear, but with a large constant factor

That tradeoff is exactly why packrat parsing is attractive in some tools and inappropriate in others.

Left Recursion Still Matters

Classic recursive-descent parsers do not handle direct left recursion well, and neither do simple packrat parsers. A rule like:

expr <- expr "+" number / number

would recurse forever in a straightforward top-down implementation.

The usual fix is to rewrite the grammar into a non-left-recursive form or use a more advanced parser implementation that explicitly handles left recursion. For many practical PEG grammars, rewriting is the simplest option.

When Packrat Parsing Is a Good Fit

Packrat parsing is a strong choice when:

• the grammar is naturally expressed as a PEG
• grammar clarity matters more than absolute memory efficiency
• the parser needs heavy lookahead or backtracking
• predictable parse time is valuable

It is less attractive when inputs are huge and memory is tight. In those cases, an LR parser or a hand-written deterministic parser may be more appropriate.

Common Pitfalls

The first mistake is assuming packrat parsing magically handles every grammar form. Left recursion still needs special treatment.

Another mistake is ignoring memory growth. Memoization is the whole reason the technique is fast, but it is also the reason it can become memory-hungry.

Developers also confuse PEG ordered choice with context-free grammar alternation. PEG alternatives are tried in order, so grammar rule ordering changes behavior.

Finally, memoizing the wrong thing can quietly break the parser. The cache must include both the rule and the input position, not just one of them.

Summary

• Packrat parsing is recursive descent plus memoization.
• It is commonly used with PEGs to get linear-time parsing.
• Each rule at each input position is computed at most once.
• The speed benefit comes at the cost of substantial memo-table memory.
• Grammar ordering and left recursion still matter in real implementations.