← CSC 414 Compiler Construction
Lexical Analysis and Finite Automata
Notes
Overview of Lexical Analysis
Lexical analysis serves as the introductory phase of a modern compiler. Often termed scanning, this stage reads a continuous stream of source characters and groups them into meaningful sequences known as lexemes. For each lexeme, the lexical analyzer yields an internal representation called a token, typically formatted as a tuple containing a token name and an optional attribute value. In Kenyan software engineering environments, building customized domain-specific parsers requires an intimate appreciation of how lexical analyzers strip whitespace, eliminate source comments, and manage line numbers to aid descriptive compile-time diagnostic reporting.
Role of the Lexical Analyzer
The scanner bridges raw human-written code with the syntax analyzer. Instead of forcing the parser to negotiate individual ASCII or UTF-8 characters, the scanner provides clean, discrete token streams. Tokens represent terminal symbols in programming language grammars, such as keywords, operators, identifiers, punctuation, and numeric literals. Behind the scenes, the scanner communicates with the symbol table, entering encountered identifiers and retrieving existing attributes. Additionally, scanners must implement lookahead mechanisms to resolve ambiguous prefix scenarios, such as distinguishing between assignment operators and equality tests.
Regular Expressions and Finite State Automata
To formalize how tokens are detected, compiler architects specify patterns using regular expressions. These patterns translate mathematically into Finite Automata, which can be Non-deterministic Finite Automata (NFA) or Deterministic Finite Automata (DFA). Thomson's construction algorithm converts regular expressions into equivalent NFAs, and the subset construction algorithm converts these NFAs into DFAs suitable for direct execution through driver routines and state transition tables.
Practical example
Consider constructing a custom parser for processing mobile payment notification logs from Safaricom M-Pesa at a Kenyan commercial bank. The incoming transaction text contains data such as: QK78RT12DE Confirmed. Ksh 2500 paid to Naivas Supermarket.
The lexical analyzer must isolate transaction tokens using tailored regular expressions:
Transaction ID Pattern: [A-Z0-9]{10}
Currency Marker: Ksh
Amount Pattern: [0-9]+(\.[0-9]{2})?
During scanning, the lexeme QK78RT12DE is recognized by a DFA transitioning across ten alphanumeric states, emitting the token tuple (TOKEN_TXN_ID, QK78RT12DE). The keyword Confirmed is detected and matches an internal keyword list, emitting (TOKEN_CONFIRM, null). The lexeme Ksh matches the exact prefix DFA, yielding (TOKEN_CURRENCY, KES). Next, whitespace is ignored, and the scanner processes 2500 through digit-loop states until encountering space, outputting (TOKEN_AMOUNT, 2500.00). This token stream passes cleanly to syntax analyzers for ledger processing without raw string slicing overhead.
Quiz
1. What primary data structure does a lexical analyzer produce for downstream consumption by the parser?
2. Why are Non-deterministic Finite Automata (NFAs) generally converted to Deterministic Finite Automata (DFAs) in practical scanners?
3. In the context of lexical analysis, what is a lexeme?
Sign in to submit and securely grade your quiz.