PadhaikoAll subjects

Lexical Analysis (part 2: 2.4–2.6)

Compiler Design (ENCT 326)

Open in the Padhaiko app

2.4 Finite automata and their relevance to compiler construction

A finite automaton (FA) is a mathematical model of a finite-state machine that reads an input string of symbols over an alphabet and either accepts or rejects the string. In compiler construction, finite automata serve as the theoretical and algorithmic backbone for automated lexical analyzer generators.

2.4.1 Formal Models: NFA vs. DFA

Definition

Nondeterministic and Deterministic Finite Automata

A Nondeterministic Finite Automaton (NFA) is a 5-tuple where:

A Deterministic Finite Automaton (DFA) is a special case of an NFA where:

AspectNondeterministic Finite Automata (NFA)Deterministic Finite Automata (DFA)
-TransitionsPermitted (-moves without consuming input)Strictly forbidden
Branching on Symbol Can have multiple next states for a single Exactly one deterministic transition per
String Acceptance Time simulating active state sets where each character takes exactly one step
Memory FootprintCompact; number of states is directly proportional to regular expression length ()Can experience worst-case exponential state explosion ()
ImplementationComplex software simulation with backtracking or set trackingSimple 2D lookup table: state = table[state][char]

2.4.2 Relevance to Compiler Construction

Compilers do not manually write nested loops and conditional statements to parse complex lexemes. Instead, the lexer pipeline follows a fully mechanized pipeline:

Diagram: from token patterns to a lexerText
Regular Expressions  --Thompson's construction-->  Combined NFA with e-moves
(token patterns)                                          |
                                                 Subset construction
                                                          v
Fast lexer driver    <--Table encoding--   Minimal DFA  <--Hopcroft's minimization--  DFA
yylex()                                    (smallest table)                      (deterministic)

2.4.3 Conversion Algorithms

1. Thompson's Construction (RE to NFA)

Thompson's algorithm recursively synthesizes an NFA with at most two transitions leaving any state and exactly one start and one accepting state:

2. Subset Construction (NFA to DFA)

The subset construction tracks the set of all NFA states reachable after reading each prefix of the input string:

3. DFA State Minimization (Hopcroft's Algorithm)

A minimal DFA contains the minimum possible number of states necessary to recognize a language. Hopcroft's algorithm repeatedly partitions the set of DFA states :

  1. Initial partition (accepting vs. non-accepting states).
  2. For each group and each input symbol , if states in transition to different groups in under , split into subgroups.
  3. Repeat until no group can be split further ().

2.5 Design of a lexical analyzer generator

A lexical analyzer generator (such as Lex or Flex) is a compiler-construction tool that takes a high-level declarative specification of regular expressions and corresponding actions, and automatically produces an efficient C scanner subroutine (yylex()).

2.5.1 Structure of a Lex Specification File

A Lex specification file (lexer.l) consists of three distinct sections separated by %%:

Text
%{
/* Section 1: Declarations */
#include <stdio.h>
#include "tokens.h"
int line_num = 1;
%}

/* Regular Definitions */
digit       [0-9]
letter      [a-zA-Z]
id          {letter}({letter}|{digit})*
number      {digit}+(\.{digit}+)?

%%
/* Section 2: Translation Rules */
"if"        { return IF; }
"else"      { return ELSE; }
"while"     { return WHILE; }
{id}        { yylval.str = strdup(yytext); return ID; }
{number}    { yylval.val = atof(yytext); return NUM; }
"<="        { return LE; }
"=="        { return EQ; }
[ \t]       { /* Ignore whitespace */ }
\n          { line_num++; }
.           { printf("Lexical Error at line %d: %s\n", line_num, yytext); }

%%
/* Section 3: User Auxiliary C Code */
int yywrap() {
    return 1; // Terminate scanning on EOF
}

2.5.2 Conflict Resolution in Lex

When an input string matches more than one regular expression rule in the specification, Lex resolves ambiguity using two universal rules:

  1. Longest Match (Maximal Munch): Lex always matches the longest possible prefix of the remaining input. For example, if both > and >= are valid patterns, the input string >= is recognized as token GE (>=), never as GT (>) followed by ASSIGN (=).
  2. First Rule Priority: If the longest matching prefix matches two or more patterns with identical length, Lex selects the rule that appears first in the specification file. For example, because "if" precedes {id} in the rules section, the lexeme if is emitted as token IF rather than token ID.

2.5.3 Architecture of the Generated Scanner

The compilation workflow of Lex:

  1. Lex reads lexer.l and constructs an NFA for each rule pattern with an accepting state labeled by the rule number.
  2. It unites all rule NFAs under a single master start state using -transitions.
  3. It converts the combined NFA into a DFA and encodes the transitions into static C lookup arrays (yy_nxt, yy_chk, yy_base, yy_def).
  4. The generated function yylex() tracks the longest match using variables:
    • yytext: A character pointer pointing to the current matching lexeme in the input buffer.
    • yyleng: The integer length of the lexeme (strlen(yytext)).
    • yylval: A global union storing semantic values passed to the parser.

2.6 Error handling in lexical analysis

A lexical analyzer has a localized view of the program text. It cannot detect syntactic or semantic anomalies (such as undeclared variables or mismatched parentheses), but it must reliably detect and recover from character-level mistakes.

2.6.1 Typical Lexical Errors

  1. Illegal / Unrecognized Characters: Characters not included in the source language alphabet (e.g., encountering an unexpected symbol like @ or ~ in pure ANSI C code outside of preprocessor lines).
  2. Unterminated String Literals: A string literal starting with " that encounters a newline or EOF before the closing quotation mark.
  3. Unclosed Multi-line Comments: A block comment /* that spans to the end of the file without a terminating */.
  4. Malformed Numerical Constants: Sequences that fail numeric regular expressions, such as 12.34.56 or 45e.
  5. Identifier Length Overflow: Identifiers exceeding implementation-defined character limits (e.g., exceeding characters).

2.6.2 Error Recovery Strategies

Lexical Error Recovery Strategies
Recovery StrategyOperational MechanismPros & Cons
Panic Mode RecoveryDeletes successive invalid characters from the input stream until a recognizable character or delimiter (e.g., whitespace, semicolon) is foundSimplest to implement; guaranteed to prevent infinite loops, but may cascade errors downstream
Character DeletionDeletes an isolated illegal character and resumes scanning at the very next characterHighly effective for accidental keystrokes (e.g., typing @int x;)
Character InsertionInserts a missing delimiter or expected character into the streamRepairs unterminated string literals by inserting a closing quote at newline
Character ReplacementSubstitutes an erroneous character with an adjacent valid candidateCorrects common visual confusions (e.g., substituting digit 0 for letter O)
TranspositionSwaps two adjacent transposed charactersRepaired misspelled keywords (e.g., correcting ti to it, or fi to if)

Minimum Edit Distance Error Correction

Theoretical compiler models apply Levenshtein distance algorithms to transform an invalid token string into the closest valid language token with the minimum number of character insertions, deletions, and substitutions. In commercial compilers, however, complex spelling correction is restricted to warning diagnostics to avoid misinterpreting programmer intent.


Worked Examples

Example 1

1

Using Thompson's construction and the Subset Construction algorithm, convert the regular expression into a Deterministic Finite Automaton (DFA). Tabulate the state transitions and draw the resulting transition table.

Thompson's Construction for :

  • NFA for : State , and State .
  • Kleene star : New start State transitions to State and State via ; State loops back to State and transitions to State via .
  • Concatenation with : State (accepting state).

The NFA has states ( through ), with start state and accepting state .

Subset Construction: Computing -closures:

  • State .

Transitions from :

  • .
  • .

Transitions from :

  • .
  • .

Transitions from :

  • .
  • .

Transitions from :

  • .
  • .

(Accepting state since ) Transitions from :

  • .
  • .

DFA Transition Table:

Answer:

The resulting DFA consists of states with initial state and accepting state . Any string ending in terminates in state .

Example 2

2

Apply Hopcroft's state minimization algorithm to the 5-state DFA obtained for : States: , Alphabet: , Start: , Accepting: . Determine whether any states can be merged, and construct the minimal DFA.

Initial Partition : Partition states into non-accepting and accepting sets:

Group is a singleton and cannot be split.

First Refinement on : Check transitions under inputs and :

  • Under input :
    • All states in transition to under .
  • Under input :
    • Notice that transitions to under , whereas transition to . Therefore, splits into and :

Second Refinement on :

  • Under input :
    • transitions to , whereas and transition to . Therefore, splits into and :
  • Testing :
    • (both go to ).
    • (both stay in ). States and are completely equivalent!
Answer:

States and are merged into a single state . The minimal DFA has states () and total transition edges across alphabet .

Example 3

3

Illustrate how Lex matches the input text if_count = 10; using its rule ordering and longest match principles against the following specification:

Text
"if"        { return IF; }
[a-z_][a-z0-9_]* { return ID; }
"="         { return ASSIGN; }
[0-9]+      { return NUM; }
";"         { return SEMI; }
[ \t\n]+    { /* ignore */ }

Matching if_count: The input begins with characters i, f, _, c, o, u, n, t.

  • The pattern "if" matches the -character prefix if.
  • The pattern [a-z_][a-z0-9_]* matches the entire -character sequence if_count.

Under the Longest Match (Maximal Munch) principle, the scanner selects the longest matching prefix ( characters vs. characters). Thus, it emits token ID with yytext = "if_count", ignoring the shorter rule "if".

Matching = 10;:

  • Whitespace ' ' matches [ \t\n]+ and is discarded.
  • = matches "=", emitting token ASSIGN.
  • Whitespace ' ' is discarded.
  • 10 matches [0-9]+, emitting token NUM with yytext = "10".
  • ; matches ";", emitting token SEMI.
Answer:

if_count is recognized as an identifier ID because Longest Match takes precedence over rule ordering. The full token stream is: ID("if_count"), ASSIGN, NUM("10"), SEMI.


Exercises

Practice Exercises — Finite Automata and Lexical Generation

Question 1

Explain Thompson's construction for converting a regular expression to an NFA. What are the key structural properties guaranteed by Thompson's algorithm regarding state count and transitions?

Thompson's Construction Principles: Thompson's algorithm constructs an NFA by structural induction on the syntax tree of a regular expression:

  • Every subexpression is mapped to an NFA with exactly one initial state and one distinct accepting state.
  • Transitions leaving any state are either at most two -transitions or at most one transition on an input symbol .
  • No transitions enter the initial state or leave the accepting state.

Structural Guarantees:

  1. Linear State Bound: For a regular expression of length (counting alphabet symbols and operators), the generated NFA has at most states.
  2. Linear Transition Bound: The total number of transitions is at most .
  3. Deterministic Composition: Sub-automata can be connected sequentially or in parallel without inspecting their internal state structure.
Answer:

Thompson's construction guarantees an NFA with exactly one start and one accepting state, at most states, at most transitions, and no state with more than two exiting transitions.

Question 2

Define the mathematical functions , , and . Explain how they are used to compute the next DFA state from a given NFA state subset.

Mathematical Definitions:

  • : The set of all NFA states reachable from state on transitions labeled only with (including state itself).
  • : The union of over all states :
  • : The set of all NFA states to which there is a transition labeled from any state :

DFA Transition Computation: Given a DFA state representing subset , the transition on symbol is computed as:

The algorithm first determines all states reachable on symbol , and then expands this set by including all states reachable via zero or more subsequent -moves.

Answer:

finds all states reachable via -transitions from any state in , while identifies states directly reached on symbol . The next DFA state is their composition: .

Question 3

Describe the internal operation of yylex() in a Lex-generated scanner. How does it track the longest matching lexeme and handle rule conflicts?

Execution Workflow of yylex():

  1. yylex() maintains two pointers, lexemeBegin and forward, in its character buffer.
  2. It advances forward, executing DFA transitions encoded in state tables.
  3. Whenever the DFA enters an accepting state, yylex() records the current position of forward and the matched rule ID as the most recent valid candidate match.
  4. If the DFA continues into further valid states, forward advances. Once the DFA reaches a dead state (no transition exists), yylex() retracts forward to the position of the most recent recorded accepting state.

Conflict Handling:

  • Longest Match: By attempting to continue past an accepting state until no transitions remain, it guarantees the longest match is detected.
  • Rule Ordering: If the recorded accepting state corresponds to multiple rules in the combined NFA, yylex() looks up the rule with the smallest line index in the Lex specification.
Answer:

yylex() tracks the longest match by advancing the DFA until a dead state is reached and retracting to the latest recorded accepting state. Multiple rule matches at that position are resolved by picking the rule that appeared earliest in the specification.

Question 4

A lexical specification generates an NFA with states over an ASCII alphabet of symbols.

  1. What is the theoretical maximum number of states in the resulting DFA after Subset Construction?
  2. If a state table uses per transition entry, calculate the maximum memory required by the uncompressed DFA transition table in kilobytes ().
  3. If Hopcroft's minimization reduces the actual DFA to states, calculate the memory required by the minimized DFA table.

Maximum Theoretical DFA States: Subset construction maps subsets of NFA states to DFA states. For NFA states, the power set size is:

Uncompressed Table Memory Size: Each state has an entry for all symbols, taking per pointer:

Converting to kilobytes ():

Minimized Table Memory Size ( states): With states:

Converting to kilobytes:

Answer:
  • Maximum theoretical DFA states: .
  • Maximum uncompressed table size: .
  • Minimized table size ( states): .
Question 5

Compare panic mode recovery with phrase-level character editing in lexical analysis. Explain how panic mode prevents the scanner from entering an infinite loop when encountering invalid characters.

Comparison of Recovery Techniques:

  • Panic Mode: When an unrecognized character is read, the scanner logs an error diagnostic and discards characters one by one until a recognizable prefix or delimiter (e.g., whitespace, semicolon) is reached. It is simple, deterministic, and fast.
  • Character Editing (Insertion/Deletion/Replacement): The scanner attempts localized transformations on the input buffer (e.g., replacing a semicolon with a colon, or inserting a quote). While it can repair minor typos, it incurs algorithmic complexity and risks creating cascading misinterpretations.

Preventing Infinite Loops: An infinite scanning loop occurs if the lexer continuously encounters an unhandled character and fails to advance the input buffer pointer. In panic mode, the error handler explicitly increments the forward pointer by at least one character during every error cycle:

C
// Panic mode ensures forward pointer always makes progress
report_error("Invalid character", *forward);
forward++;
lexemeBegin = forward;

Because the input file has a finite length , incrementing the pointer guarantees that the scanner strictly progresses toward EOF, eliminating the possibility of an infinite loop.

Answer:

Panic mode discards characters until a valid delimiter is found, while character editing attempts localized repairs. Panic mode guarantees termination because it explicitly advances the buffer pointer on every unrecognized character, preventing infinite loops.

← Lexical Analysis (part 1: 2.1–2.3)Syntax Analysis (Parsing) →