Token Specification, Regular Expressions to Lexical DFA & Longest Match
“Maximal munch rule, Thompson's construction, subset powerset simulation, and minimal state scanning.”
1.Converting Patterns to Deterministic Finite Automata
§ 1.1.Every token pattern in a programming language (identifiers, integers, floating-point numbers, operators, string literals) is specified formally using a Regular Expression.
To implement the scanner, these expressions are compiled into finite state automata. The classic tool pipeline (such as lex or flex) operates as follows:
1. Thompson's Construction: Transforms each regular expression r_i into an NFA N_i with \epsilon-transitions. A single global start state with \epsilon-transitions to each N_i is created.
2. Subset Construction: Converts the composite NFA into a single Deterministic Finite Automaton (DFA) where each DFA state represents a set of NFA states.
3. DFA State Minimization: Applies Hopcroft's partition-refinement algorithm to merge indistinguishable states, producing the smallest possible transition table.
Disambiguation Rules: Because multiple token patterns can match the same prefix of characters, the scanner enforces two strict disambiguation axioms:
- Rule 1 (Longest Match / Maximal Munch): The scanner continues looking ahead as long as the DFA remains in an accepting state or can reach one. It selects the token corresponding to the longest possible character sequence.
- Rule 2 (Rule Priority): If the longest match matches multiple patterns (for example, the lexeme if matches both the keyword IF and the identifier ID), the pattern listed first in the specification takes precedence.
2. Worked Analysis: Minimal DFA States for Token Recognition
Do not forget the trap/dead state when counting total states of a complete DFA over an alphabet Sigma.
Problem Statement (Modeled on GATE Pattern):
A lexical analyzer must recognize floating-point numeric constants over alphabet \Sigma = {d, .} where d \in {0, 1, ..., 9}.
A valid constant must contain at least one digit, an optional decimal point '.', and if a decimal point is present, it must be followed by at least one digit.
Formal regular expression: L = d^+ (\. d^+)?.
Determine the minimum number of states in a complete DFA that accepts L over \Sigma = {d, .}.
Step 1: Construct states based on prefix history:
- State q_0 (Start): Initial state (no characters read yet).
- On input d: Transition to state q_1 (integer digits accumulated).
- On input '.': Transition to dead state q_{trap} (cannot start with a dot according to d^+).
- State q_1 (Accepting): Has read one or more digits.
- On input d: Self-loop on q_1 (more integer digits).
- On input '.': Transition to state q_2 (decimal point seen, awaiting fraction digits).
- State q_2 (Non-accepting): Decimal point encountered, must see at least one digit.
- On input d: Transition to state q_3 (fraction digits read).
- On input '.': Transition to q_{trap} (two dots are invalid).
- State q_3 (Accepting): Valid complete floating point number.
- On input d: Self-loop on q_3 (more fraction digits).
- On input '.': Transition to q_{trap} (a second dot is invalid).
- State q_{trap} (Dead State): Invalid input sequence.
- On input d, .: Self-loop on q_{trap}.
Step 2: Verify state minimality:
- Accepting states: {q_1, q_3}. Notice q_1 transitions on '.' to non-accepting q_2, while q_3 transitions on '.' to q_{trap}. Since their transitions differ on input '.', q_1 and q_3 are distinguishable and cannot be merged!
- Non-accepting states: {q_0, q_2, q_{trap}}.
- From q_0, on input d, we reach accepting q_1.
- From q_2, on input d, we reach accepting q_3. But on input '.', q_0 goes to q_{trap} and q_2 goes to q_{trap}. Are q_0 and q_2 equivalent? No, because q_0 is the start state and can transition to q_1 which accepts, whereas reaching q_2 requires having already consumed a dot.
Total states in minimal complete DFA = 5 states (q_0, q_1, q_2, q_3, q_{trap}).
Primary Academic References & Exam Sources
Every concept in Notes From a B.Tech Brain is synthesized from authoritative academic texts, seminal peer-reviewed research, verified exam archives, and renowned university lectures.
Curated for clarity, rigorous numerical solving, and semester excellence:
GATE-focused with worked FIRST/FOLLOW and LR parsing table numericals.
Exam-oriented explanations of ambiguous grammars and parser conflicts.
University-depth treatment of the full compiler pipeline — build a real compiler.