Build a Finite Automaton (DFA) and Use It to Drive Your Lexer

DFAs Drive Lexers

A deterministic finite automaton (DFA) is a state machine that reads input symbols and transitions between states. Lex/Flex compiles regex patterns into DFAs; hand-written lexers implement the same logic implicitly. GCC's cpp and Clang's character classifier tables are DFAs in disguise.

States and Transitions

Each state represents progress in recognizing a pattern. From state S0, digit goes to S_NUMBER; letter goes to S_IDENT; / might go to S_DIV or S_COMMENT if next char is /. Accept states emit tokens; trap states report errors.

cCopy
Loading…

• Start state S0 handles every new token
• Accept states map to token types
• Trap/error states trigger recovery
• Transition table can be a 2D array indexed by (state, char class)

Connecting to real compilers

Production compilers embed this step inside a longer pipeline. GCC flows through cpp, cc1, assembly, and ld; Clang uses the driver, Sema, LLVM IR passes, and a target backend. LLVM bitcode, JVM bytecode, and WASM are other familiar IRs at the same layer. The exercise isolates one pass so you can test it alone before chaining it to the next stage.

Why for this exercise

You will build an explicit DFA transition table and use it to drive token recognition. This exercise requires encoding lexer states as integers, defining transitions for digits, letters, and operators, and emitting tokens when accept states are reached.