LL(1) Parsing Tables
What You'll Learn
You'll learn how to construct a parsing table from FIRST and FOLLOW sets that drives a table-driven predictive parser, eliminating the need for hand-written recursive descent functions.
The Core Idea
An LL(1) parsing table is a two-dimensional lookup table that tells a predictive parser exactly which production to apply based on the current non-terminal and the next input token (lookahead). Instead of writing separate recursive functions for each non-terminal, you build one table and let a generic table-driven algorithm do all the parsing.
Think of it like a dispatch table: rows represent non-terminals, columns represent terminal symbols (tokens), and each cell contains the production rule to use—or remains empty if that combination is illegal.
Construction Algorithm
For each production A → α in your grammar:
- For each terminal
ain FIRST(α): PlaceA → αin table cell[A, a] - If ε is in FIRST(α): For each terminal
bin FOLLOW(A), placeA → αin cell[A, b] - **If ε is in FIRST(α) and ]` (end-of-input marker)
If any cell ends up with multiple entries, the grammar is not LL(1)—the parser wouldn't know which production to choose.
Using the Table
During parsing, the table-driven parser looks at:
- The current non-terminal on the stack
- The next input token
It consults table[non-terminal][token] to find which production to apply. This makes the parser fast, compact, and mechanical—no recursive calls needed.
Key Takeaway: LL(1) parsing tables convert FIRST and FOLLOW sets into a concrete lookup structure that drives predictive parsing, making it possible to parse LL(1) grammars efficiently with a simple table-driven algorithm.