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

Building a Transition Table

Creating the DFA transition table structure that drives the lexical analyzer's token recognition logic.

Building a Transition Table

You'll learn how to construct the table that drives a lexical analyzer's token recognition engine.

What Is a Transition Table?

Once you've converted your token patterns (regular expressions) into a DFA, you need a practical way to execute that automaton. A transition table is a 2D data structure that encodes all the state transitions of your DFA in a format a program can efficiently traverse.

Think of it as a roadmap: each row represents a state, each column represents an input character (or character class), and each cell tells you "where to go next" when you're in that state and see that character.

Structure of the Table

The table has:

  • Rows = states (0, 1, 2, ... n)
  • Columns = input symbols or character classes (a-z, 0-9, whitespace, etc.)
  • Cells = next state number (or error/reject indicator like -1)

Additionally, you typically mark which states are accepting states and what token type they recognize.

Building Process

  1. List all states from your DFA (including the start state)
  2. List all possible input characters or meaningful character classes
  3. For each state-symbol pair, fill in the target state from your DFA's transition function
  4. Mark accepting states with their corresponding token types (IDENTIFIER, NUMBER, KEYWORD, etc.)

Example Snapshot

State | a-z | 0-9 | other | Accept?
------|-----|-----|-------|--------
  0   |  1  |  2  |  -1   | No
  1   |  1  |  1  |  -1   | Yes: ID
  2   |  -1 |  2  |  -1   | Yes: NUM

Key Takeaway: The transition table translates your DFA into a lookup structure that your lexical analyzer can efficiently query character-by-character to recognize tokens.