Syntax analysis: top-down and bottom-up parsing notes — Unit 2

The Parser is the heart of the compiler's front end. It receives a stream of tokens from the Lexical Analyzer and checks whether this stream conforms to the grammatical rules of the source language.

⇒1.1 The Output

If the syntax is correct, the parser typically produces a Parse Tree (or Abstract Syntax Tree), which represents the hierarchical structure of the program.

While Regular Expressions define tokens, they are not powerful enough to define nested structures like `if-else` blocks or matching parentheses. We use Context-Free Grammars for syntax.

⇒2.1 Components of a CFG (V, T, P, S)

• T (Terminals): The basic symbols (Tokens) from which strings are formed (e.g., `id`, `+`, `while`).
• V (Non-Terminals): Syntactic variables that denote sets of strings (e.g., `Expression`, `Statement`). Usually written in uppercase.
• P (Productions): Rules dictating how Non-Terminals can be replaced by other Non-Terminals and Terminals (e.g., `E -> E + E`).
• S (Start Symbol): A special Non-Terminal indicating where the derivation begins.

A derivation is a sequence of production rule applications that transform the Start Symbol into a string of terminal symbols.

⇒3.1 Leftmost vs Rightmost

• Leftmost Derivation (LMD): At each step, the leftmost non-terminal is replaced.
• Rightmost Derivation (RMD): At each step, the rightmost non-terminal is replaced.

Both LMD and RMD for the same string will produce the exact same Parse Tree.

A grammar is ambiguous if it can produce more than one valid Parse Tree (or more than one Leftmost Derivation) for the exact same input string.

⇒4.1 The Problem

If `E -> E + E | E E | id` parses the string `id + id id`, it could be grouped as `(id + id) id` or `id + (id id)`. Because mathematical precedence isn't baked into the grammar, the compiler doesn't know which one is correct. Compilers cannot handle ambiguity.

⇒4.2 Eliminating Ambiguity

We rewrite the grammar to enforce Precedence (multiplication before addition) and Associativity (left-to-right for addition).

A grammar is left-recursive if it has a production of the form `A -> Aα | β`. Top-down parsers will get stuck in an infinite loop if they encounter left recursion.

⇒5.1 The Transformation

We replace left recursion with right recursion. The standard formula:

`A -> Aα | β` becomes:

A  -> β A'
A' -> α A' | ε

This removes the immediate infinite loop while still generating the exact same language.

A predictive top-down parser cannot decide which production to choose if multiple productions share the same prefix.

⇒6.1 The Problem

`A -> αβ1 | αβ2`. When seeing `α`, the parser doesn't know whether to pick the first or second rule.

⇒6.2 The Transformation

We factor out the common prefix `α` to delay the decision until the parser has read past it.

A  -> α A'
A' -> β1 | β2

Parsers are broadly categorized into Top-Down and Bottom-Up.

⇒7.1 Characteristics

• Starts building the parse tree from the Root (Start Symbol) and grows down to the leaves (Tokens).
• Attempts to find a Leftmost Derivation.
• Can be implemented via Recursive Descent (using manual function calls) or table-driven (LL(1)).

Top-down parsers strictly require grammars that have no Left Recursion and no common prefixes (must be Left Factored).

To construct a predictive parsing table, we must compute two functions for all Non-Terminals.

⇒8.1 FIRST Set

`FIRST(X)` is the set of terminals that begin the strings derivable from X. If X can derive the empty string (`ε`), then `ε` is also in `FIRST(X)`.

⇒8.2 FOLLOW Set

`FOLLOW(A)` is the set of terminals that can appear immediately to the right of A in some valid derivation. `FOLLOW` sets never contain `ε`. A special end-of-input marker ` is placed in `FOLLOW(StartSymbol)`.

The most common table-driven top-down parser. It uses an explicit stack rather than recursive function calls.

⇒9.1 What does LL(1) mean?

• L: Scans input from Left to right.
• L: Produces a Leftmost derivation.
• (1): Uses 1 symbol of lookahead to make decisions.

⇒9.2 The Parsing Table

We use `FIRST` and `FOLLOW` sets to fill a 2D array. Rows are Non-Terminals, Columns are Terminals. If a cell contains more than one production, the grammar is NOT LL(1).

Starts from the leaves (Tokens) and builds the tree upward to the root (Start Symbol). It attempts to trace a Reverse Rightmost Derivation.

⇒10.1 Key Operations

• Shift: Push the next input token onto the top of the stack.
• Reduce: The parser finds a sequence on top of the stack matching the right side of a production (a Handle), and pops it, pushing the left-side Non-Terminal.
• Accept: Parsing successfully completes.
• Error: A syntax error is detected.

The most powerful class of bottom-up parsers. Used by modern tools like Yacc and Bison.

⇒11.1 What does LR(k) mean?

• L: Left-to-right scan.
• R: Reverse Rightmost derivation.
• k: Number of lookahead symbols (usually 1).

⇒11.2 The Hierarchy (Weakest to Strongest)

• LR(0): No lookahead. Too weak for real languages.
• SLR(1): Simple LR. Uses FOLLOW sets to resolve conflicts. Smallest table.
• LALR(1): Look-Ahead LR. Merges states to save memory. Used in Yacc.
• CLR(1) / Canonical LR: Most powerful. Massive parsing table.

If a grammar is not in the specific LR class, the parser generator will report conflicts in the parsing table cells.

⇒12.1 Shift/Reduce Conflict

The parser cannot decide whether to shift the next token onto the stack or reduce the current stack contents. (Classic example: The Dangling-Else problem).

⇒12.2 Reduce/Reduce Conflict

The parser knows it should reduce, but the top of the stack matches the right-hand side of two different productions, and it doesn't know which one to pick.

YACC (Yet Another Compiler Compiler) is a tool that automatically generates a LALR(1) parser from a CFG.

⇒13.1 Synergy with Lex

Lex generates `yylex()`, which reads characters and returns tokens. YACC generates `yyparse()`, which calls `yylex()`, receives tokens, and performs shift-reduce parsing. The two tools are designed to be tightly coupled.

⇒13.2 Structure of a YACC file

Like Lex, it has three sections separated by `%%`: Declarations (C code and token definitions), Grammar Rules (with C actions triggered upon Reduction), and Auxiliary C functions.