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

Updated 31 Oct 20266 min read
Lexical Analysis Formula Sheet: Tokens, Regular Expressions and DFA Revision Notes

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

r | s

Union

Choose a string from either language

rs

Concatenation

Place an r string before an s string

r*

Zero or more copies

Repetition that may be empty

r+ = rr* = r*r

One or more copies

Repetition that must occur

r? = r | epsilon

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.

DFA diagram with start state q0, accepting identifier and integer states, dead state, loops, and example traces for if2 and 10.

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, IF and ID both match length 2, so priority emits IF("if").

  • Position 2 is a skipped space. At 3, IF matches length 2, but ID matches if2 with length 3, so emit ID("if2").

  • At 6, LT matches length 1, while LE matches length 2, so emit LE("<=").

  • At 8, emit NUM("10"). Skip the space at 10, then emit LT("<") at 11 and skip the space at 12.

  • At 13, IF and ID tie at length 2, so emit IF("if"). Emit ASSIGN("=") at 15 and NUM("7") at 16.

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.

Character-indexed maximal-munch trace for if if2<=10 < if=7 showing skipped spaces, tie comparisons, and eight emitted tokens.

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. epsilon is not empty set.

  • r* includes epsilon; r+ excludes it unless r itself can generate epsilon.

  • Maximal munch comes before rule priority.

  • 2^n is 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 attribute

  • A 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.