PARSING IS THE PROBLEM OF FINDING A DERIVATION TREE FOR A GIVEN STRING, OR REPORTING THAT NONE EXISTS. Note the direction of travel. The previous topic assumed the derivation was known and drew the tree; A PARSER IS GIVEN ONLY THE STRING AND MUST DISCOVER THE TREE. That is a search problem, and the two strategies are two ways to organise the search. ── TOP-DOWN PARSING ──────────────────────────────────────── START AT THE ROOT (the start symbol) AND WORK TOWARD THE LEAVES, expanding variables until the input is matched. It constructs a LEFTMOST DERIVATION, in the order the derivation is written. RECURSIVE DESCENT is the direct implementation: write ONE FUNCTION PER VARIABLE, each of which tries the productions for that variable. It is the parsing method most easily written by hand, and hand-written recursive descent parsers are used in several production compilers precisely because they are easy to read and to give good error messages. THE FUNDAMENTAL DIFFICULTY: WHICH PRODUCTION TO CHOOSE. On reaching a variable A with several productions, the parser must decide which to try. An LL(1) parser decides by looking at ONE lookahead token. LL(k) means: scan LEFT to right, produce a LEFTMOST derivation, using k tokens of lookahead. TWO OBSTACLES MUST BE REMOVED FIRST: 1. LEFT RECURSION — a production A → Aα causes recursive descent to call itself with no progress, giving infinite recursion. THE STANDARD ELIMINATION: A → Aα | β becomes A → β A′ A′ → α A′ | ε Applied to the expression grammar: E → E + T | T becomes E → T E′ E′ → + T E′ | ε NOTE THE PRICE: THE GRAMMAR IS NO LONGER LEFT-RECURSIVE, SO THE TREE NO LONGER DIRECTLY EXPRESSES LEFT ASSOCIATIVITY. The parser must reassemble associativity itself, which is a real cost of the top-down approach. 2. COMMON PREFIXES — A → αβ₁ | αβ₂ leaves the parser unable to choose after seeing only α. LEFT FACTORING fixes it: A → αβ₁ | αβ₂ becomes A → α A′ A′ → β₁ | β₂ ── BOTTOM-UP PARSING ─────────────────────────────────────── START AT THE LEAVES (the input tokens) AND WORK TOWARD THE ROOT, replacing right-hand sides by their left-hand variables. It constructs a RIGHTMOST DERIVATION IN REVERSE, which is the detail that surprises students and is frequently examined. SHIFT-REDUCE PARSING is the mechanism, using a STACK: SHIFT — push the next input token onto the stack REDUCE — when the top of the stack matches the right-hand side of a production, pop it and push the left-hand variable ACCEPT — the stack holds only S and the input is exhausted ERROR — no action applies THE HANDLE is the substring that should be reduced next — the right-hand side whose reduction is a step of the rightmost derivation in reverse. FINDING THE HANDLE IS THE ENTIRE PROBLEM, and an LR parser uses a table built from the grammar to decide. LR(k) means: scan LEFT to right, produce a RIGHTMOST derivation (reversed), with k lookahead tokens. The family in increasing power: LR(0) ⊂ SLR(1) ⊂ LALR(1) ⊂ LR(1). LALR(1) IS WHAT yacc AND bison GENERATE — a deliberate compromise, nearly as powerful as LR(1) with far smaller tables. ── A WORKED SHIFT-REDUCE PARSE ───────────────────────────── Grammar: E → E + T | T, T → T * F | F, F → id Input: id + id * id STACK INPUT ACTION ──────────────────────────────────────────────────────── $ id + id * id $ shift $ id + id * id $ reduce F → id $ F + id * id $ reduce T → F $ T + id * id $ reduce E → T $ E + id * id $ shift $ E + id * id $ shift $ E + id * id $ reduce F → id $ E + F * id $ reduce T → F $ E + T * id $ shift $ E + T * id $ shift $ E + T * id $ reduce F → id $ E + T * F $ reduce T → T * F $ E + T $ reduce E → E + T $ E $ ACCEPT ──────────────────────────────────────────────────────── NOTICE THE DECISION AT "$ E + T" WITH "* id" REMAINING: the parser could have reduced E → E + T immediately, but doing so would have made the multiplication apply to the whole sum. IT SHIFTS INSTEAD, because the lookahead * binds tighter. THIS IS A SHIFT-REDUCE CONFLICT RESOLVED BY PRECEDENCE, and it is exactly how yacc handles operator precedence declarations. READ THE REDUCTIONS BOTTOM TO TOP AND THEY ARE THE RIGHTMOST DERIVATION — which is what "rightmost in reverse" means.

── WHEN THE GRAMMAR IS NOT LL OR LR ──────────────────────── LL(1) and LR(1) grammars are restricted classes. For an ARBITRARY context-free grammar, general algorithms exist: THE CYK ALGORITHM (Cocke-Younger-Kasami) Requires the grammar in CHOMSKY NORMAL FORM. It fills an upper-triangular table where entry (i, j) holds every variable deriving the substring from position i of length j. FOR j = 1: X ∈ table[i,1] if X → wᵢ is a production FOR j > 1: X ∈ table[i,j] if there is a production X → YZ and a split point k with Y ∈ table[i,k] and Z ∈ table[i+k, j−k] ACCEPT if the start symbol appears in table[1, n]. RUNS IN O(n³ · |G|) TIME AND O(n²) SPACE — cubic, so it is not used for programming languages, but it WORKS FOR EVERY CFG including ambiguous ones, and it is a DYNAMIC PROGRAMMING algorithm of the same family as the ones in the algorithms subject. EARLEY'S ALGORITHM Handles any CFG in O(n³), improving to O(n²) for unambiguous grammars and O(n) for LR-parsable ones. NO NORMAL FORM REQUIRED, which makes it popular in natural language processing where grammars are large and messy. ── THE COMPARISON ────────────────────────────────────────── TOP-DOWN (LL) BOTTOM-UP (LR) ────────────────────────────────────────────────────────── direction root → leaves leaves → root derivation LEFTMOST RIGHTMOST, REVERSED basic action PREDICT which REDUCE when a handle production applies is complete needs NO left recursion, handles left recursion left factoring NATURALLY grammar class SMALLER LARGER — every LL(1) grammar is LR(1) hand-writing EASY (recursive impractical descent) error messages BETTER — the parser weaker: it knows only knows what it that nothing fits EXPECTED typical tool ANTLR, hand-written yacc, bison (LALR) ────────────────────────────────────────────────────────── THE ENGINEERING SUMMARY: LR PARSERS ACCEPT MORE GRAMMARS AND NEED A GENERATOR; LL PARSERS ACCEPT FEWER GRAMMARS AND CAN BE WRITTEN AND DEBUGGED BY HAND. Several major compilers — GCC among them — abandoned generated bottom-up parsers in favour of hand-written recursive descent, precisely for the error message and maintainability advantages in the last two rows. ── ERROR HANDLING ────────────────────────────────────────── A parser that stops at the first error is nearly useless, so real parsers RECOVER and continue: PANIC MODE — discard tokens until a SYNCHRONISING token (typically ; or }) is found, then resume. Simple and robust; may skip real errors. PHRASE-LEVEL RECOVERY — perform a local correction, such as inserting a missing semicolon. ERROR PRODUCTIONS — add productions to the grammar for common mistakes, so the parser recognises the error explicitly and reports it precisely. GLOBAL CORRECTION — find the minimal edit making the input parseable. Theoretically clean, too expensive in practice. THE PRACTICAL GOAL IS TO REPORT EVERY REAL ERROR ONCE AND INVENT NONE — and CASCADING ERRORS, where one mistake produces twenty messages, is the failure mode recovery exists to prevent.