Lexical Analysis Formula Sheet: Tokens, Regular Expressions and DFA Revision Notes
Keep the rules that matter under time pressure in one place, then apply them to regex counting, DFA construction, a 17-character scanner trace, and fallback.
KnowledgeGate Team
Exam prep & CS education

Token, lexeme, regular-expression and DFA distinctions become easier to revise when each rule is tied to a scanner decision. A useful revision sequence is definitions first, then counting identities, maximal munch, and fallback on the last accepting state.
Lexical analysis in one page: token, lexeme and pattern
The compiler front end begins with this flow:
source characters -> lexical analyser -> token stream -> parser
A token has the form <token-name, optional attribute>. A lexeme is the exact source substring matched. A pattern describes all lexemes that belong to one token class. Whitespace and comments are normally skipped. An identifier may carry a symbol-table pointer, while a numeral may carry its value.
For total2 = 37, the lexemes are total2, = and 37. The analyser emits ID(pointer-to-total2), ASSIGN and NUM(37). Here, ID is the token name, total2 is the lexeme, and letter(letter|digit)* is the pattern.
The earlier Lexical Analysis: Tokens, Patterns and DFA Scanning explains the full compiler pipeline and first-pass scanner construction; regex identities, counting formulas, tie handling and retraction form a compact revision checklist. For related topics, use CS Fundamentals for Exams & Placements.
Regular expression formula sheet and counting rules
Rule | Meaning | When to use |
|---|---|---|
| Union | Choose a string from either language |
| Concatenation | Place an r string before an s string |
| Zero or more copies | Repetition that may be empty |
| One or more copies | Repetition that must occur |
| Zero or one copy | An optional part |
Precedence is closure (*, +, ?), concatenation, then union (|). epsilon has length zero; empty set contains no strings.
Use r|empty set = r, r epsilon = epsilon r = r, r empty-set = empty-set r = empty-set, r|r = r, (r*)* = r*, r*r* = r*, and r* = epsilon|rr*. But (r|s)* != r*|s* because the left side permits mixed strings. Arden's theorem gives R = Q|RP => R = QP* and R = Q|PR => R = P*Q, uniquely when epsilon is not in P.
For alphabet size k, exactly length n gives k^n. For k > 1, lengths 0 through n give (k^(n+1)-1)/(k-1); for k > 1, non-empty lengths 1 through n give (k^(n+1)-k)/(k-1). For k = 1, lengths 0 through n give n+1, while non-empty lengths 1 through n give n. With alphabet = {a,b,c}, k = 3, n = 4: 3^4 = 81, and at most length four including epsilon gives 1+3+9+27+81 = 121.
From token regex to a working DFA
Regular definitions are letter = A|...|Z|a|...|z, digit = 0|...|9, ID = letter(letter|digit)*, and NUM = digit+.
epsilon-closure(T) is T plus NFA states reached only through epsilon transitions. move(T,a) is the states reached on a. Compute U = epsilon-closure(move(T,a)) for each input symbol. A DFA subset is accepting if it contains at least one NFA final state.
An n-state NFA can produce at most 2^n DFA subsets, but we build only reachable subsets. A table-driven DFA scans m characters in O(m) time because each character causes one transition. The Compiler Design course connects regex construction to scanner implementation.

Maximal munch and rule priority: complete scanner trace
Use this exact rule order: 1 IF -> if, 2 ID -> [A-Za-z][A-Za-z0-9]*, 3 LE -> <=, 4 LT -> <, 5 ASSIGN -> =, 6 NUM -> [0-9]+, and 7 WS -> [ \t\n]+, whose action is skip.
First compute Lmax, the longest accepted prefix length. Then choose the lowest-numbered rule among the rules matching Lmax. Priority never defeats a strictly longer match.
Trace the 17-character input if if2<=10 < if=7 from zero-based position 0:
At
0,IFandIDboth match length2, so priority emitsIF("if").Position
2is a skipped space. At3,IFmatches length2, butIDmatchesif2with length3, so emitID("if2").At
6,LTmatches length1, whileLEmatches length2, so emitLE("<=").At
8, emitNUM("10"). Skip the space at10, then emitLT("<")at11and skip the space at12.At
13,IFandIDtie at length2, so emitIF("if"). EmitASSIGN("=")at15andNUM("7")at16.
The exact stream is IF("if"), ID("if2"), LE("<="), NUM("10"), LT("<"), IF("if"), ASSIGN("="), NUM("7"). Lexeme lengths total 2+3+2+2+1+2+1+1 = 14; three spaces at positions 2, 10, 12 give 14+3 = 17 source characters. Exactly 8 tokens are emitted.

Lookahead, retraction, buffering and token attributes
A practical scanner maintains lexemeBegin, forward, lastAcceptState, and lastAcceptPosition. Whenever it reaches an accepting state, it updates the last-accept pair. On a dead transition, it resets forward to lastAcceptPosition and emits that token. If it never reached an accepting state, it reports a lexical error and advances so scanning can continue.
For REAL -> [0-9]+\.[0-9]+, INT -> [0-9]+, and DOT -> \. on input 12., the scanner consumes 3 characters while trying REAL. Its last acceptance was after the second digit, at offset 2. It retracts 3-2 = 1 character, emits INT("12"), then rescans and emits DOT("."). Retraction returns to the last accepting position, not always by one character.
Two-buffer input alternates buffers of B characters with sentinels and refills at a sentinel. A token attribute may be a symbol-table pointer, literal value, or absent.
What the lexical analyser can and cannot decide
A lexer recognises identifiers, numbers, keywords, operators and regular comment forms. The parser checks grammar, including balanced delimiters. Semantic analysis checks declarations and types. In a + (b * c, every character can form a valid token, but the parser must report the missing closing parenthesis.
Keywords can use higher-priority rules than ID, as in the trace. Alternatively, the scanner can recognise an identifier first and look up its lexeme in a reserved-word table. Either method must classify if as a keyword and if2 as an identifier.
Comments are often removed by the lexer, but that does not make every nested construct automatically lexical. The specification and implementation determine whether extra machinery is required.
High-frequency traps and how questions test them
Correct these common mistakes quickly:
A token is not a lexeme.
epsilonis notempty set.r*includesepsilon;r+excludes it unlessritself can generateepsilon.Maximal munch comes before rule priority.
2^nis an upper bound, not a required DFA size.A dead transition does not erase the last accepting prefix.
A lexer does not prove that the token stream is grammatically valid.
For scanner questions: write rules and priority, mark every accepting prefix, select the longest, then break only equal-length ties by priority. For regex or automata questions, expand shorthand, apply precedence, and build only reachable DFA subsets.
Use Lexical Analysis and Tokens: 12 Solved MCQs to practise these distinctions on complete questions rather than memorising the correction list alone.
The short version and next step
token = name + optional attributeA lexeme is the matched text.
A pattern describes the token class.
*means zero or more.+means one or more.DFA scanning uses the longest accepted prefix.
Equal-length ties use rule priority.
Fallback returns to the last accepting position.
Reproduce the 17-character scan from the first character to the last without help, and confirm the same eight-token output. For a broader guided revision path, continue with GATE Guidance by Sanchit Sir.
Keep learning
Regular Expressions Formula Sheet: Rules, Worked Examples and Revision Notes
Remembering the symbols is only the first step. Use these identities, language templates and a complete ending-01 DFA example to check what a regular expression actually generates.
Lexical Analysis in Compiler Design: Tokens, Patterns, and DFA-Based Scanning with Worked Examples
Learn how a scanner turns source characters into tokens, how token patterns become DFAs, and how longest match, lookahead, and token-counting questions work.
Regular Language Properties: Formula Sheet and Revision Notes for GATE CS
Keep each regular-language rule beside its conditions. Revise identities, trace a product DFA and practise the quantifier order that makes a pumping-lemma proof work.
Semantic Analysis and SDT Formula Sheet and Revision Notes: Attributes, Type Rules and Worked Trace
Keep SDD, SDT, attribute flow, dependency order and type coercion straight with one worked assignment that ends at total = 13.0 and five TAC instructions.





