The Role of the Parser

In Phase 1, the Lexical Analyzer grouped characters into a flat stream of tokens. In Phase 2, the Syntax Analyzer (Parser) takes that token stream and determines if it forms a valid sentence according to the rules of the programming language.

Why regular expressions aren't enough: Regular expressions (and the Finite Automata that run them) cannot count or remember unbounded information. This means they cannot verify matched structures like balanced parentheses ((())) or nested blocks { { } }. Because every modern programming language uses heavily nested structures (nested if statements, nested loops, nested math expressions), we require a more powerful mathematical tool: the Context-Free Grammar (CFG).

Formal Definition of a Context-Free Grammar

A Context-Free Grammar is a set of rules describing how to form valid sentences. Mathematically, it is defined as a 4-tuple: $G = (V, T, P, S)$

1. $V$ (Variables / Non-terminals): Syntactic variables that represent sets of strings (e.g., $expr$, $stmt$, $block$). They are placeholders that must be expanded further.
2. $T$ (Terminals): The basic symbols from which strings are formed. In a compiler, the terminals are the tokens returned by the lexer (e.g., id, +, while, int).
3. $P$ (Productions): The rules that define how non-terminals can be replaced. They always have the form: Non-terminal → Sequence of terminals and/or non-terminals (e.g., $E \to E + E$)
4. $S$ (Start Symbol): A special non-terminal in $V$ that represents the entire program or the root concept we are trying to parse.

The Classic "Dangling-Else" Ambiguity

The most famous ambiguity in computer science occurs with if-then-else statements. Consider this grammar: $Stmt \to \text{if } Expr \text{ then } Stmt$ $Stmt \to \text{if } Expr \text{ then } Stmt \text{ else } Stmt$

Now parse this code:

1if x > 0 then 
2    if y > 0 then print(y) 
3else print(x)

Does the else belong to the first (outer) if, or the second (inner) if? Both are perfectly valid derivations under this grammar!

Most languages (like C and Java) resolve this informally in their spec: An else always binds to the closest unmatched if. However, to build an actual parser, the grammar itself must be rewritten to mathematically prevent the outer-bind interpretation.

Proving Ambiguity Formally (A common assessment requirement): If asked to justify if a grammar like $S \to aS \mid Sa \mid a$ is ambiguous, you must pick a single test string (e.g., aaa) and draw two distinct Leftmost Derivations (or Parse Trees) for it.

Derivation 1 (Expanding Left first): $S \Rightarrow aS \Rightarrow aaS \Rightarrow aaa$

Derivation 2 (Expanding Right first): $S \Rightarrow Sa \Rightarrow Saa \Rightarrow aaa$

Because the exact same string aaa can be generated using two completely different leftmost derivations (resulting in two different parse trees), the grammar is formally proven to be ambiguous.

Push-Down Automata (PDA)

Just as Finite Automata are the theoretical machines that execute Regular Expressions, Push-Down Automata (PDA) are the theoretical machines that recognize Context-Free Grammars.

$\text{PDA} = \text{Finite Automaton} + \text{A Stack}$

The addition of a Last-In-First-Out (LIFO) stack gives the machine unbounded memory. When parsing balanced parentheses ((())), a PDA can push an item onto the stack for every (, and pop an item for every ). If the stack is empty at the end, the string is balanced.

Every parser generator (like Yacc or Bison) ultimately generates a deterministic Push-Down Automaton encoded as a transition table and a runtime stack.

CFG to PDA Conversion

There is a fundamental correspondence between Context-Free Grammars and Push-Down Automata: every CFG can be mechanically converted to an equivalent PDA, and every PDA defines a context-free language whose grammar can be reconstructed. This bi-directional equivalence is one of the most important theorems in formal language theory.

Construction Algorithm (CFG → PDA): Given a CFG $G = (V, T, P, S)$, we construct a PDA that accepts exactly $L(G)$ by empty stack. The PDA only needs a single state $q$, because the stack alone encodes the entire derivation state!

1. Expand (simulate a production): For each production $A \to \alpha$ in $P$, add a transition: $\delta(q, \varepsilon, A) = \{(q, \alpha)\}$ (When $A$ is on top of the stack, pop it and push $\alpha$. This simulates one derivation step without consuming any input.)

2. Match (verify a terminal): For each terminal $a \in T$, add a transition: $\delta(q, a, a) = \{(q, \varepsilon)\}$ (When the input symbol matches the top-of-stack terminal, pop it and consume the input.)

How it works: The PDA starts with the Start Symbol $S$ on the stack. It non-deterministically expands non-terminals using the grammar rules. When a terminal appears on top of the stack, it must match the current input symbol. If all input is consumed and the stack is empty, the string is accepted.