Cheat Sheet

Lexical Analysis Quick Reference

Token definitions, regex patterns, DFA construction, and the lexer pipeline.

Token	Regex Pattern	Description
Keyword	`(if\|else\|while\|for\|return\|int\|void\|struct)`	Reserved words
Identifier	`[a-zA-Z_][a-zA-Z0-9_]*`	Variable/function names
Integer	`[0-9]+`	Decimal integer literal
Float	`[0-9]+\.[0-9]*`	Floating-point literal
String	`"[^"]*"`	String literal
Operator	`[+\-*/%=<>!&\|^~]`	Binary/unary operators
Punctuation	`[(){}\[\],;]`	Grouping and separator
Whitespace	`[ \t\n\r]+`	Ignored (not tokenized)
Comment	`//.` or `/\(.\|\n)?\/`	Single/multi-line

•1. Input Buffering: Read source file into memory (~4KB chunks for efficiency).
•2. Pattern Matching: Match input against regex rules using DFA or hand-written scanner.
•3. Token Emission: Produce (type, lexeme, line, col) tuples.
•4. Error Recovery: Skip to next known delimiter on invalid characters.
•5. Symbol Table Entry: Optionally intern identifiers at lexer level.

•∅ (empty): Two states, no transition.
•ε (epsilon): Two states, ε-transition.
•a (symbol): Two states, transition on character a.
•R|S (union): New start with ε-edges to R and S start states.
•RS (concatenation): ε-edge from R's accept to S's start.
•R* (Kleene star): ε-edges from accept back to start, and from new start to accept.
•Result: NFA with ε-transitions. Convert to DFA via subset construction.