LL(1) Predictive Parsing Table Construction & Conflict Analysis
“Table construction algorithm M[A, a], LL(1) necessary and sufficient conditions, and multi-entry conflicts.”
1.Predictive Non-Recursive LL(1) Parsing Engine
§ 2.1.An LL(1) parser operates using a pushdown stack, an input buffer containing the token string terminated with , and a two-dimensional parsing table M[A, a] where rows are non-terminals and columns are terminals (including ).
The name LL(1) denotes: Left-to-right scan of the input, Leftmost derivation, with 1 token of lookahead.
Parser Execution Cycle:
Let X be the symbol on top of the stack and a be the current input token.
1. If X = a = \$: Parsing halts and succeeds with acceptance.
2. If X = a \ne \: The parser pops X$ from the stack and advances the input pointer to the next token (match action).
3. If X is a terminal and X \ne a: Syntax error reported.
4. If X is a non-terminal: The parser consults table entry M[X, a].
- If M[X, a] = {X \to Y_1 Y_2 ... Y_k}, the parser pops X and pushes Y_k, Y_{k-1}, ..., Y_1 onto the stack (so Y_1 is on top).
- If M[X, a] is empty, a syntax error is raised.
- If M[X, a] contains ≥ 2 productions, the table construction failed because the grammar is NOT LL(1).
Removing left recursion and left factoring are NECESSARY steps, but they do NOT guarantee that the resulting grammar is LL(1). Disjointness of FIRST and FOLLOW must still be verified algebraically.
2. Worked Analysis: Proving a Grammar is NOT LL(1)
Even though the grammar has no left recursion and appears factored, check the intersection between FIRST and FOLLOW for nullable non-terminals.
Consider the grammar:
S -> A a | b
A -> a | epsilon
Determine if this grammar is LL(1). If not, identify the exact table cell collision.
Step 1: Compute FIRST sets:
- FIRST(A) = {a, epsilon}
- FIRST(S) = (FIRST(A) - {epsilon}) U {a} U {b} = {a, b}
Step 2: Compute FOLLOW sets:
- FOLLOW(S) = {$}
- In S -> A a: A is followed by terminal 'a'. Thus, FOLLOW(A) = {a}.
Step 3: Test LL(1) Condition on non-terminal A:
- Productions for A are: (1) A -> a, and (2) A -> epsilon.
- Let alpha = a, beta = epsilon.
- FIRST(alpha) = {a}.
- Since beta =>* epsilon, we must check if FIRST(alpha) ∩ FOLLOW(A) = ∅.
- Here, FIRST(alpha) = {a} and FOLLOW(A) = {a}.
- FIRST(alpha) ∩ FOLLOW(A) = {a} ∩ {a} = {a} ≠ ∅!
Step 4: Examine Table Cell M[A, a]:
- For production A -> a: since 'a' is in FIRST(a), place A -> a in M[A, a].
- For production A -> epsilon: since epsilon is in FIRST(epsilon), place A -> epsilon in M[A, b] for all b in FOLLOW(A). Since FOLLOW(A) = {a}, place A -> epsilon in M[A, a].
- Table entry M[A, a] contains BOTH {A -> a, A -> epsilon}.
Conclusion: The grammar is NOT LL(1) due to a multi-entry conflict in cell M[A, a].
Primary Academic References & Exam Sources
Every concept in Notes From a B.Tech Brain is synthesized from authoritative academic texts, seminal peer-reviewed research, verified exam archives, and renowned university lectures.
Curated for clarity, rigorous numerical solving, and semester excellence:
GATE-focused with worked FIRST/FOLLOW and LR parsing table numericals.
Exam-oriented explanations of ambiguous grammars and parser conflicts.
University-depth treatment of the full compiler pipeline — build a real compiler.