Skip to content

Lab 2 · The LL(1) toolkit, and recursive descent vs the table

Chapter: 2 · Grammars & Top-Down Parsing · Lessons: 2.2, 2.3, 2.4, 2.5, 2.7 · Time: 12–16 hours · Tests: ./course test 2 (label ch02)

Goal

You build two things behind one small contract, include/ll1/LL1.h:

  1. The LL(1) toolkit (your code in src/, switch ll1-toolkit): nullable, FIRST and FOLLOW as least fixed points (Lesson 2.2), the LL(1) table with classified conflicts (Lesson 2.3), the table-driven predictive parser (Lesson 2.5) with panic-mode recovery (Lesson 2.7), and the two grammar transformations, SCC-restricted Paull and left factoring (Lesson 2.4). This is the technique pebblec's parser is built on.
  2. The comparison lab (your code in rd/, switch rd-compare): a hand-written predictive recursive-descent parser that must agree with your table-driven parser token for token, a left-associative AST built by loops, and a backtracking recognizer measured naive vs memoized.

You design every data structure and helper yourself. The provided code is infrastructure only: the grammar model and file reader, bounded language enumeration and random sentences (test oracles), the printers, the fixed grammar of the comparison lab, and the ll1 command-line tool.

Requirements

Symbols, grammars and the text format are those of include/ll1/Grammar.h (provided). Productions are indexed from 0 in the API and printed from 1. "Least fixed point" and the set definitions are those of Lesson 2.2, Definition 2.2.1.

  • R1 (nullable). analyze(G).Nullable[X] is true iff \(X \Rightarrow^{*} \varepsilon\); false for every terminal and for $ (symbol 0). The vector has size G.numSymbols().
  • R2 (FIRST). analyze(G).First[A] is \(\mathrm{FIRST}(A)\) without \(\varepsilon\) for every nonterminal; First[t] == {t} for every terminal and First[$] == {$}. Works on every grammar (left recursion, \(\varepsilon\), cycles, useless symbols).
  • R3 (FOLLOW). analyze(G).Follow[A] is \(\mathrm{FOLLOW}(A)\) (with $ in FOLLOW of the start symbol); empty for terminals.
  • R4 (table). buildLL1Table(G, A).Cells maps exactly the non-empty cells \((A, t)\) to the productions whose PREDICT set (Definition 2.3.1) contains \(t\), without duplicates. Conflicts has one entry per cell with \(\ge 2\) productions, Productions sorted, Kind per Definition 2.3.3 (FIRST/FIRST iff at least two of them have \(t\) in FIRST of their right side).
  • R5 (parser). parseLL1(G, M, Input) runs Algorithm 2.5.4 on Input (terminals, no $). On success: Derivation is the leftmost derivation; Tree is the concrete tree (contract comment on ParseTree); Steps has one entry per move including the final accept, with the stack before the move and the action texts of Formats. On failure: the first SyntaxError (position, found token, expected set sorted by symbol id: {top} for a terminal on top, {$} for $ on top, else every \(t\) with M.cell(top, t) non-empty). A cell with \(\ge 2\) productions counts as an error cell.
  • R6 (panic mode). parseWithRecovery(G, A, M, Input) runs the same driver with Algorithm 2.7.3 instead of stopping: terminal on top and mismatch → record, pop; nonterminal with an empty or conflicting cell → record, then pop it if the lookahead is $ or in FOLLOW, else skip the token; $ on top with input left → record once, skip the rest. It fills Errors, Skipped (0-based positions) and Popped, never pushes during recovery, and always ends with a step at position Input.size(). On a sentence it behaves exactly like parseLL1; on a non-sentence its first error equals parseLL1's error.
  • R7 (left recursion). eliminateLeftRecursion(G) implements SCC-restricted Paull (Algorithm 2.4.5) with the output conventions below. It fails with a pebble::Error whose message contains "derives no terminal string" if some nonterminal has only left-recursive alternatives, or contains "nullable" if the result is still left-recursive (hidden left recursion); otherwise the result has no left-recursive nonterminal and the same language.
  • R8 (left factoring). leftFactor(G) implements Algorithm 2.4.6 with the conventions below; the result has no two alternatives of one nonterminal with the same first symbol and the same language.
  • R9 (recursive descent). rd::parseTree(G, Input), for G = rd::exprGrammar(), is a hand-written predictive recursive-descent parser (one function per nonterminal is the natural design). On every input it returns exactly what parseLL1 returns for the same grammar: the same ParseTree on success, the same SyntaxError on failure.
  • R10 (AST). rd::parseAst(G, Input) returns the AST fully parenthesized, with + - * / left-associative and * / binding tighter: "((id-id)*num)"; a lone operand prints as itself ("id"). It detects every error at the same token as parseLL1.
  • R11 (backtracking). backtrackRecognize(G, Input, Memoize) is the list-of-successes recognizer (Algorithm 2.5.6, and 2.5.7 with Memoize). Accepted iff Input \(\in L(G)\), for every grammar without left recursion; Calls counts nonterminal invocations that run their alternatives (memo hits are not calls). If the recursion depth exceeds \(\lvert N \rvert \times (\lvert \mathit{Input} \rvert + 1)\) it fails with an error whose message contains "left-recursive".
  • R12 (performance). Every ch02 test finishes in under a second on a laptop with the reference design; the round-robin fixed points may take \(O(p \cdot \lvert G \rvert \cdot \lvert T \rvert)\), the parser must be linear in the input, and the memoized recognizer must make at most \(\lvert N \rvert (n + 1)\) calls.

Output conventions of the transformations (R7, R8)

The golden files tests/ch02/Inputs/*.transformed fix one canonical output, so the transformations must be deterministic in this way:

  • nonterminals are processed in grammar order (G.nonterminals());
  • a new nonterminal is named G.freshName(A) (A', A'', …) and is listed right after \(A\) and after \(A\)'s earlier primes;
  • alternatives keep their relative order; a rewritten group takes the place of its first member; duplicates are removed keeping the first;
  • Paull: for \(A_i\), substitute \(A_j\) (\(j < i\), same left-corner SCC, some alternative of \(A_i\) starts with \(A_j\)) in order \(j = 1, 2, \dots\); drop \(A_i \to A_i\); bases get \(A_i'\) appended; \(A_i' \to \alpha_1 A_i' \mid \cdots \mid \varepsilon\) with the tails in order and \(\varepsilon\) last;
  • left factoring: repeatedly take the first nonterminal (in the current order) that has a group, its first group (by the group's first member), the group's longest common prefix \(\alpha\); restart the scan after every rewrite.

The contract

// labs/ch02-ll1-toolkit/include/ll1/LL1.h  (provided; do not change; abridged)
namespace ll1 {
struct GrammarAnalysis { std::vector<bool> Nullable; std::vector<SymbolSet> First, Follow; };
GrammarAnalysis analyze(const Grammar &G);                                  // E1-E3
struct LL1Table { std::map<std::pair<Symbol, Symbol>, std::vector<unsigned>> Cells;
                  std::vector<Conflict> Conflicts;  /* cell(), isLL1() */ };
LL1Table buildLL1Table(const Grammar &G, const GrammarAnalysis &A);        // E4
std::expected<ParseResult, SyntaxError>
parseLL1(const Grammar &G, const LL1Table &M, std::span<const Symbol> Input);           // E5
ParseResult parseWithRecovery(const Grammar &G, const GrammarAnalysis &A,
                              const LL1Table &M, std::span<const Symbol> Input);        // E6
std::expected<Grammar, pebble::Error> eliminateLeftRecursion(const Grammar &G);         // E7
Grammar leftFactor(const Grammar &G);                                                   // E8
namespace rd {
Grammar exprGrammar();                                                      // provided
std::expected<ParseTree, SyntaxError> parseTree(const Grammar &G, std::span<const Symbol> Input);   // L1
std::expected<std::string, SyntaxError> parseAst(const Grammar &G, std::span<const Symbol> Input);  // L2
}
std::expected<BacktrackResult, pebble::Error>
backtrackRecognize(const Grammar &G, std::span<const Symbol> Input, bool Memoize);      // L3-L4
}

Read the header itself for the exact meaning of every field (ParseTree, ParseStep, SyntaxError, ParseResult, Conflict, BacktrackResult). The functions own nothing: they take references and spans and return values.

Where your code goes: any *.cpp under src/ (toolkit) and under rd/ (comparison lab); both directories start with a Stub.cpp that defines the contract with PEBBLE_TODO so the project builds. Delete the stub as you implement. Add as many files and private headers as you like; include them with a path relative to your file.

Input and output formats

Grammar files (tests/ch02/Inputs/*.grammar, parsed by the provided reader): one nonterminal per line, # comments, arrows ->, → or ::=, alternatives separated by |, ε (also eps, epsilon, '') for the empty string; a symbol is a nonterminal iff it appears on a left side; the start symbol is the first left side.

E  -> T E'
E' -> + T E' | ε
T  -> ( E ) | id

Parser step actions (R5; ll1 parse --trace prints them as a table):

move ParseStep::Action
expand output (N) <production> with N 1-based and <production> = G.productionString(i), e.g. output (3) E' -> ε
match match <token name>, e.g. match id
accept accept
recovery (R6) free text starting with error: (the reference prints e.g. error: M[T, *] is empty; skip *)
end of a recovering parse accept if there was no error, else free text (the reference prints stop after 2 error(s))

The ll1 tool (provided, build/<preset>/bin/ll1; run it without arguments for usage) prints: report (the golden format of tests/ch02/Inputs/*.expected: [grammar], [nullable], [first] with ε for nullable nonterminals, [follow], [table], [conflicts], ll1: yes|no), table (a Markdown matrix, !! marks conflicts), parse [--recover] [--trace] [--tree], transform [--no-left-recursion] [--no-factor], enumerate, rd and backtrack [--max-depth N]. Example:

$ ll1 report tests/ch02/Inputs/running.grammar      # abridged
[nullable]
S' E'
[follow]
S: e $
S': e $
…
[conflicts]
M[S', e]: FIRST/FOLLOW 3 4
ll1: no

Provided infrastructure

File What it gives you
include/ll1/Grammar.h, provided/Grammar.cpp Grammar, Symbol, SymbolSet, the text format reader, freshName, nonterminals()/terminals() order, productionString, toText, tokenize
include/ll1/Language.h, provided/Language.cpp enumerateLanguage (the bounded language, a test oracle), randomSentence, randomTokens
include/ll1/Print.h, provided/Print.cpp the golden report, the table matrix, leftmostDerivation, yield, treeToString, stepsToTable, describe
provided/ExprGrammar.cpp rd::exprGrammar(), the comparison lab's fixed grammar
tools/ll1.cpp the command-line driver
tests/ch02/Inputs/ 22 grammars with golden reports (*.expected) and transformations (*.transformed) produced by the Python oracles in tools/course/lib/grammar.py

What the tests check

Every test goes through the contract or the ll1 tool; none looks at your internals.

Test Checks
ch02.GrammarFormat.*, ch02.Language.* the provided code (these pass in the skeleton build)
ch02.AnalysisNullable.*, ch02.AnalysisFirst.*, ch02.AnalysisFollow.* R1–R3 on the Dragon expression grammar, the lesson's running example, a grammar that needs several passes, a nullable chain, and A -> a A (a FOLLOW self-reference)
ch02.AnalysisCrossCheck.* R1–R2 against the bounded language of every corpus grammar
ch02.Table.*, ch02.Golden/Corpus.ReportMatchesGolden/* R4: cell contents, conflict kinds on seven grammars, LL(1) verdicts, and formatReport of your results byte-for-byte equal to all 22 golden reports
ch02.PredictiveParser.* R5: the 17-step trace and derivation of Lesson 2.5 §3, tree ↔ derivation ↔ yield, first-error positions and expected sets, and acceptance = membership in the bounded language on every LL(1) corpus grammar
ch02.PanicMode.* R6: skipped positions and popped symbols on the lesson's inputs; agreement with parseLL1 on 800 random inputs; the last step is at the end of the input
ch02.TransformLeftRecursion.*, ch02.TransformLeftFactor.*, ch02.Corpus/TransformGolden.* R7–R8: exact output text on the Dragon examples, the SCC restriction on json.grammar, hidden left recursion reported, factoring over several rounds, and all golden *.transformed files
ch02.TransformProperties.* R7–R8: five grammars become LL(1) with the same language up to length 6; the whole corpus keeps its language; 400 random grammars either fail for a documented reason or produce a non-left-recursive, factored grammar with the same bounded language
ch02.RDCompare.* R9–R10: identical trees and errors to parseLL1 on hand-picked and 2 000 random inputs; left-associative ASTs; AST errors at the same token
ch02.Backtracking.* R11: acceptance = bounded-language membership on every non-left-recursive corpus grammar (naive and memoized); naive calls exactly \(3 \cdot 2^{d+1} - 3\) and memoized calls exactly \(2d + 2\) on \(d\) nested parentheses; rejection; left recursion reported
ch02.lit the ll1 tool on your code: report (golden diffs), table, parse (trace, error, recovery), transform, rd, backtrack, enumerate, and usage errors

The RDCompare tests compare with your parseLL1, so do E1–E5 first, or configure with -DPEBBLE_USE_SOLUTION=ll1-toolkit to compare against the reference toolkit while you work on rd/.

Milestones

  1. Sets (E1–E3): ctest --preset linux -L '^ch02$' -R 'ch02.Analysis' (macOS: --preset macos).
  2. Table (E4): -R 'ch02.(Table|Golden)'; then ll1 report works on any grammar file.
  3. Parser (E5): -R 'ch02.PredictiveParser'; ll1 parse tests/ch02/Inputs/expr-ll1.grammar --trace id + id '*' id prints Lesson 2.5's table.
  4. Recovery (E6): -R 'ch02.PanicMode'.
  5. Transformations (E7–E8): -R 'ch02.(Transform|Corpus)'.
  6. Recursive descent (L1–L2): -R 'ch02.RDCompare'.
  7. Backtracking (L3–L4): -R 'ch02.Backtracking', then measure.
  8. Everything: ./course test 2.

Measurement

Run build/<preset>/bin/ll1 backtrack --max-depth 12 and fill in the table; compare with Lesson 2.5 §3 and Proposition 2.5.14.

depth d tokens naive calls memoized calls naive ms
4 9
8 17
12 25

Then time ll1 rd against ll1 parse on a long random sentence of rd::ExprGrammarText and explain the difference (a switch per nonterminal vs a table lookup per step).

Hints

Hint 1 — where to start

Start with a helper that computes FIRST of a string of symbols and whether the string is nullable (Lesson 2.2's FirstOf); the FIRST loop, the FOLLOW loop and the table all use it. Keep per-symbol data in vectors indexed by Symbol (G.numSymbols() entries), which is exactly the shape the contract returns. For the parser, print Lesson 2.5's trace table first and make your step list match it before worrying about trees.

Hint 2 — the key ideas
  • Fixed points: repeat whole passes until a pass changes nothing (compare set sizes before and after inserting). When rule W3 copies FOLLOW(A) into FOLLOW(B) and B = A, copy the source set first.
  • Conflict kinds: classify after the table is complete, by counting how many of a cell's productions reach the lookahead through FIRST.
  • Parser: a stack of (symbol, pointer to the tree node it will fill). When you expand, size the node's Children once, then push pointers to them in reverse order; the vector is never resized again, so the pointers stay valid.
  • Recovery: never push. Share one driver between E5 and E6 (for example, a pointer to the analysis that is null when not recovering).
  • Paull: two nonterminals are in the same left-corner SCC iff each reaches the other in the left-corner graph (Definition 2.4.2); compute reachability once on the input grammar. Work on a copy ("alternatives per nonterminal" plus an output order) and build a fresh Grammar at the end.
  • Recursive descent: each function's cases are its row of the table; take ε only on FOLLOW tokens, or the error moves to the caller and R9 fails.
  • Backtracking: return sets of end positions, not booleans; a sequence threads a set of positions through its symbols.
Hint 3 — a design sketch

One reasonable split (the reference solution uses it): src/Analysis.cpp (three round-robin loops plus FirstOf), src/Table.cpp, src/PredictiveParser.cpp (one Driver class with a Recover flag), src/LeftCorner.cpp (nullable-aware left-corner reachability by Warshall's closure), src/Transform.cpp (a Rewrite working state: std::map<Symbol, std::vector<std::vector<Symbol>>> plus a std::vector<Symbol> order), a private src/Internal.h; rd/RecursiveDescent.cpp (an internal ExprParser class with parseE … parseF and parseSum/parseProduct/parseFactor over a small Ast struct) and rd/Backtracking.cpp (an internal recognizer with a std::map<std::pair<Symbol, size_t>, std::vector<size_t>> memo).

Bugs the tests catch most often: stopping the fixed point after one pass (NeedsSeveralPasses); forgetting W3 with ε (RunningExampleOfTheLesson); taking ε as a default: case in recursive descent (AgreesOnRandomInputs); counting terminal matches as calls, or stopping at the first successful alternative (that is ordered choice), in the backtracking recognizer (NaiveWorkDoublesWithEveryNestingLevel).

Stretch goals ★

  • Implement the worklist and digraph algorithms of Lesson 2.2 as alternatives inside analyze and check they give the same sets (the Python oracles in tools/course/lib/grammar.py do).
  • Add phrase-level routines (Algorithm 2.7.4) or single-token repair (Algorithm 2.7.5) as a third parsing mode and compare the error messages with panic mode on id + * id ).
  • Add ordered choice with memoization (packrat) to the backtracking recognizer and find an input that it rejects but the CFG accepts (\(S \to a \mid a\, b\)); Ch 4 builds on it.