Course contentsShow
← Computer Science
Lesson 1959 of 2,87244. Lexical Analysis and ParsingFree lesson

LL(1) Parsing Tables

Constructing parsing tables from FIRST and FOLLOW sets to drive table-driven predictive parsers.

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:

  1. For each terminal a in FIRST(α): Place A → α in table cell [A, a]
  2. If ε is in FIRST(α): For each terminal b in FOLLOW(A), place A → α in cell [A, b]
  3. **If ε is in FIRST(α) and isinFOLLOW(A)∗∗:Place‘A→α‘incell‘[A,is in FOLLOW(A)**: Place `A → α` in cell `[A,]` (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.