Skip to content

Lab 4 · One expression grammar, four parsing paradigms (and incremental reparsing ★)

Chapter: 4 · Parsing in Practice · Lessons: 4.1, 4.2, 4.3, 4.6 · Time: 10–16 hours (6–8 without the ★ part) · Tests: ./course test 4 (label ch04)

Goal

You parse the expression language of Pebble — nine binary precedence levels with a non-associative comparison level, prefix - and !, the postfix-like as, indexing, field access and calls (pebble-spec §4.2) — with four algorithms from four paradigms:

  • Pratt parsing (binding powers, top-down operator precedence; Lesson 4.1, Algorithm 4.1.8),
  • Dijkstra's shunting-yard (two explicit stacks, no recursion; Algorithm 4.1.9),
  • a packrat parser for a parsing expression grammar (ordered choice + memoization; Lesson 4.2, Algorithm 4.2.7),
  • an Earley parser for a left-recursive context-free grammar (Lesson 4.3, Algorithm 4.3.3; Proposition 4.3.12 bounds its sets on this grammar).

The tests check that the four build the same tree on every valid input and reject the same invalid ones: Theorem 4.1.14 says the first two must agree with the layered grammar, and the PEG and the CFG below are written so that all four define the same language. You then measure what the paradigms cost on this grammar. The ★ milestone keeps a parsed Pebble module up to date under edits, reparsing only the function an edit touches (Lesson 4.6).

You design everything: the binding-power table, the stacks, the PEG rules and memo table, the Earley items, sets and back-pointers, and the tree type. The provided code is the contract header, a tokenizer, a random-expression generator, the command-line tool and the benchmark.

The language

2.1 Tokens (provided: exprlab::tokenize)

Integers [0-9]+, identifiers [A-Za-z_][A-Za-z0-9_]*, the keyword as, the type names int, float, bool (only meaningful after as), and the operators

||  &&  ==  !=  <  <=  >  >=  |  ^  &  <<  >>  +  -  &+  &-  *  /  %  &*  !  (  )  [  ]  .  ,

by maximal munch (a<=b is a, <=, b; x&-1 is x, &-, 1). Spaces are ignored. Any other character is a tokenizer error.

2.2 The PEG (for the packrat parser)

Expr    <- Or END
Or      <- And ('||' And)*
And     <- Cmp ('&&' Cmp)*
Cmp     <- BitOr (CmpOp BitOr)?                    # CmpOp: == != < <= > >=
BitOr   <- BitXor ('|' BitXor)*
BitXor  <- BitAnd ('^' BitAnd)*
BitAnd  <- Shift ('&' Shift)*
Shift   <- Sum (('<<' / '>>') Sum)*
Sum     <- Product (('+' / '-' / '&+' / '&-') Product)*
Product <- Cast (('*' / '/' / '%' / '&*') Cast)*
Cast    <- Unary ('as' Type)*
Unary   <- ('-' / '!') Unary / Postfix
Postfix <- Primary ('[' Or ']' / '.' Ident)*
Primary <- Ident '(' (Or (',' Or)*)? ')' / Ident / Int / '(' Or ')'

Terminals are tokens. A repetition (op X)* builds a left-nested tree. Note the order in Primary: with Ident first, ordered choice would commit to it and f(x) could never parse (prefix capture, Lesson 4.2, the example after Definition 4.2.2). A second comparison, as in a < b < c, leaves < c unconsumed, so Expr fails at END.

2.3 The CFG (for the Earley parser)

S  -> E1
E1 -> E1 '||' E2 | E2              E6 -> E6 '&' E7 | E7
E2 -> E2 '&&' E3 | E3              E7 -> E7 ShiftOp E8 | E8
E3 -> E4 CmpOp E4 | E4             E8 -> E8 AddOp E9 | E9
E4 -> E4 '|' E5 | E5               E9 -> E9 MulOp C | C
E5 -> E5 '^' E6 | E6               C  -> C 'as' Type | U
U  -> '-' U | '!' U | P            P  -> P '[' E1 ']' | P '.' Ident | A
A  -> Int | Ident | Ident '(' ')' | Ident '(' L ')' | '(' E1 ')'
L  -> E1 | L ',' E1

Left recursion is fine for Earley. The grammar is unambiguous (Lemma 4.1.4 generalized), so every accepted input has exactly one tree to read back.

3. Trees: the output format

One line, fully parenthesized, no spaces other than single separators; parentheses of the input leave no node:

Input Tree
1 + 2 * 3 (+ 1 (* 2 3))
-a as float (as (neg a) float)
!t (not t)
xs[i + 1] (idx xs (+ i 1))
p.x (. p x)
f(), f(a, b) (call f), (call f a b)
((x)) x

Operators are printed with their spelling (&+, <<, ==, …).

4. The contract

// labs/ch04-paradigms/include/exprlab/ExprParsers.h  (provided; do not change; comments abridged)
namespace exprlab {
enum class Algo { Pratt, Shunting, Peg, Earley };
struct ParseError { unsigned Column = 0; std::string Message; };   // 1-based column
struct Stats {                                                       // work counters (§6)
  uint64_t Steps = 0;        // Pratt/shunting: loop iterations
  uint64_t RuleCalls = 0;    // PEG: rule invocations that were not memo hits
  uint64_t MemoHits = 0;     // PEG
  uint64_t MemoEntries = 0;  // PEG: (rule, position) entries stored
  uint64_t EarleyItems = 0;  // Earley: items over all sets
};
std::expected<std::string, ParseError> parse(Algo A, std::string_view Input, Stats *S = nullptr);
}

and the command-line tool ch04-parse (provided, built on parse):

ch04-parse --algo=pratt|shunting|peg|earley [--stats] [EXPR]

which parses EXPR, or each line of standard input, and prints the tree or error: <column>: <message> per line (exit status 1 if any line failed).

Your code goes in any *.cpp under labs/ch04-paradigms/src/ (switch paradigms). It starts with Stub.cpp, whose parse stops with TODO(ch04). The provided tokenizer and generator are declared in include/exprlab/Tokens.h.

5. Requirements and what the tests check

  • R1 (Pratt). Algo::Pratt is one recursive function driven by binding powers (Algorithm 4.1.8), not one function per level.
  • R2 (shunting-yard). Algo::Shunting uses an operand stack and an operator stack and no recursion; it distinguishes prefix from infix - with an expecting-operand/expecting-operator state (Algorithm 4.1.9).
  • R3 (packrat). Algo::Peg implements the PEG of §2.2 with ordered choice and memoizes every (rule, position) result, so that no rule is evaluated twice at the same position (Theorem 4.2.10).
  • R4 (Earley). Algo::Earley implements the CFG of §2.3 with Earley sets (predict, scan, complete) and builds the tree from the chart.
  • R5 (same trees). On every input all four return the same result: the same tree, or an error. Error columns and messages may differ between algorithms, but a column must lie in 1…length+1.
  • R6 (errors). Every input outside the language is rejected: chained comparisons (a < b < c, a == b != c), missing operands, unbalanced brackets, trailing tokens, as without a type, a . without a name, trailing commas in calls, calls of anything but a name ((f)(x)), tokenizer errors.
  • R7 (linear work). On the random inputs of the benchmark, packrat rule calls stay below 32 per token and Earley items below 200 per token (for this grammar both are linear: Theorem 4.2.10 and Proposition 4.3.12).
Test Checks
ch04.Paradigms.L1to4_CorpusTrees R1–R4: 36 hand-picked inputs covering every level, associativity, prefix/postfix, casts, calls
ch04.Paradigms.L1to4_InvalidInputsAreRejected R6: 30 invalid inputs, for each algorithm, with a column in range
ch04.Paradigms.L1to4_RandomExpressionsGiveTheGeneratedTree R5: 400 random expressions per algorithm (generator trees built independently of any parser, printed with minimal parentheses plus random extra ones)
ch04.Paradigms.L5_AllFourAgreeOnRandomTokenSequences R5: 10 000 random token sequences (mostly invalid): same verdict and same tree
ch04.Paradigms.L5_WorkGrowsLinearlyOnThisGrammar R7 at 200, 2 000 and 8 000 tokens
ch04.lit (paradigms-cli.test) the ch04-parse output format on inputs/cases.txt for all four algorithms
ch04.lab.bench-smoke ch04-parsebench --quick runs and every algorithm returns the expected tree
ch04.Incremental.* ★ §7

6. Measurement

build/<preset>/bin/ch04-parsebench            # sizes 100, 1000, 10000, 50000 tokens
build/<preset>/bin/ch04-parse --algo=earley --stats 'a + b * c'

Fill in the table with your numbers (time per expression and work per token at each size). The reference solution on the course's Linux container gave, at about 28 500 tokens: Pratt 7.8 ms and 1.18 steps/token, shunting-yard 5.8 ms and 1.18 steps/token, packrat 11.5 ms and 4.46 (calls + hits)/token, Earley 157 ms and 25.3 items/token. Everything is linear; Earley's constant is about 20 times Pratt's.

Algorithm 100 tokens 1 000 10 000 work/token notes
Pratt
shunting-yard
packrat
Earley

7. ★ Milestone L6: incremental reparsing

Contract include/exprlab/Incremental.h, your code in labs/ch04-paradigms/incr/ (switch incremental):

struct Edit { size_t Offset = 0; size_t Length = 0; std::string Text; };
struct ReparseStats { unsigned ItemsReused = 0; unsigned ItemsReparsed = 0; };
class IncrementalParser {
public:
  virtual std::string open(std::string Text) = 0;   // AST dump (pebble-spec §14.2)
  virtual std::string edit(const Edit &E) = 0;      // dump after the edit
  virtual ReparseStats lastStats() const = 0;
};
std::unique_ptr<IncrementalParser> createIncrementalParser();
  • R8. After every edit, the returned dump equals the dump of a full parseModule of the edited text (use the Pebble parser of pebble/lib/Parse, yours or the reference one).
  • R9. An edit inside one top-level item (a function, struct or extern) reparses exactly that item and reuses the ASTs of all the others; adding an item reparses only it; deleting one reparses nothing. Edits in the whitespace between items reparse nothing.

Tests: ch04.Incremental.L6_OpenEqualsFullParse, L6_EditsInsideOneFunctionReparseOnlyIt (60 random insertions and deletions of statements), L6_AddingAndRemovingItems.

8. Milestones

  1. L1 Pratt — ctest --preset linux -R 'Paradigms.L1to4_CorpusTrees' with only Pratt implemented (return an error for the other three at first; the test names the failing algorithm).
  2. L2 shunting-yard, then L3 packrat, then L4 Earley — the same test, plus L1to4_InvalidInputsAreRejected and L1to4_RandomExpressionsGiveTheGeneratedTree.
  3. L5 — L5_* and the measurement table.
  4. L6 ★ — ctest --preset linux -R Incremental.

Hints

Hint 1 — where to start

Write the tree type first: a vector of nodes with child indices (the arena design of Lesson 4.7) and one printer. Then Pratt: Lesson 4.1's Algorithm 4.1.8 with the table of pebble-spec §4.2 turned into binding powers. as, [, . are postfix operators in the loop, with powers 10, 12, 12.

Hint 2 — the key ideas
  • Shunting-yard: postfix operators apply to the operand on top of the output stack immediately, except that as must first reduce stacked prefix operators (-a as float is (as (neg a) float)). Calls push a marker holding the callee name and an argument count; , and ) reduce down to the nearest marker.
  • Non-associativity: in Pratt, remember whether the left operand of the loop was built by a comparison in this same loop; in shunting-yard, a comparison that is about to pop another comparison is the error.
  • Packrat: a table indexed by (rule, token position) holding "failed" or (tree, end position).
  • Earley: store in every item the item it advanced from and the child (a token or a completed item) that advanced it; then the tree of a completed item is a walk back along those links.
Hint 3 — a design sketch
  • Pratt: int expr(int MinBP), returning a node index; errors in a member std::optional<ParseError>.
  • Shunting-yard: std::vector<int> operands, std::vector<OpEntry> operators with a kind (binary, prefix, (, [, call).
  • Packrat: std::vector<std::vector<std::optional<Result>>> Memo(NumRules, …); one member function per rule.
  • Earley: rules as data ({Lhs, Rhs, Action}), items {Rule, Dot, Origin, Prev, Child} in one vector, sets as index lists, a hash set per Earley set for duplicates, and per set and nonterminal the list of items waiting for it (used by complete).
  • ★ Incremental: cut the text into items at fn/struct/extern tokens at brace depth 0; cache parsed items by their text.

Stretch goals

  • Add Algo::Climb (precedence climbing, Algorithm 4.1.6) and Algo::Layered (one function per level, Algorithm 4.1.5) and check they agree too.
  • Give the Earley parser Leo's optimization (Algorithm 4.3.6) and measure a right-recursive grammar.
  • Make the PEG left-recursive (Sum <- Sum '+' Product / Product) and support it with seed growing (Algorithm 4.2.8).