Building a Tokenizer from Scratch [part 2]

From FSM to PDA: Q/A with Claude Opus In part 1 , we built a working FSM that recognizes <div>text</div> using just 7 primitives mapped 1:1 to assembly opcodes. But FSMs have a hard limit: they can't handle nested structures like <div><div>hello</div></div> . In this post, we climb the Chomsky hierarchy from finite state machines to pushdown automata , build a PDA that recognizes nested <div> tags, and then turn it into a transducer that emits tokens. In other words we are building the core of a lexer . Q: Why can't FSMs handle nested structures? Because an FSM has a fixed number of states , and that's all the memory it has. Consider nested divs: <div><div><div>hello</div></div></div> To correctly match closing tags, you need to count how many <div> s you've opened so you know how many </div> s to expect. An FSM with, say, 12 states can handle nesting up to some fixed depth — but someone can always write HTML nested one level deeper than your states can track. Put simply: 1 level deep