Lexical Analysis (part 1: 2.1–2.3)
Open in the Padhaiko app2.1 The role of the lexical analyzer
The lexical analyzer (commonly known as the scanner) is the initial phase of the compiler front-end. Its primary function is to read the source program as a raw, unstructured stream of characters from secondary storage, group them into meaningful character sequences called lexemes, and emit a stream of tokens to the syntax analyzer (parser).
Source Program getNextToken()
(character stream) --> Lexical Analyzer <------------------ Syntax Analyzer
(Scanner) ------------------> (Parser)
| ^ token stream
| |
| +--(two-way)-- Symbol Table
v
Error Handler2.1.1 Scanner as a Subroutine to the Parser
In standard compiler architectures, the lexical analyzer does not run as a separate standalone batch pass that converts the entire file at once into disk tokens. Instead, it is organized as a subroutine invoked on demand:
- The parser calls a function such as
getNextToken(). - The scanner reads input characters until it identifies the next complete lexeme.
- The scanner packages the lexeme into a token tuple and returns control to the parser.
2.1.2 Reasons for Separating Lexical Analysis from Syntax Analysis
Separating lexical analysis from syntax analysis is a fundamental principle of compiler design:
| Aspect | Lexical Analysis | Syntax Analysis |
|---|---|---|
| Formal Model | Regular Expressions and Deterministic/Nondeterministic Finite Automata (DFA/NFA) | Context-Free Grammars (CFG) and Pushdown Automata (PDA) |
| Input Unit | Individual characters (bytes) | Discrete tokens emitted by the scanner |
| Primary Task | Stripping whitespace/comments, identifying keywords, constants, identifiers | Imposing hierarchical syntactic structure, validating expression/statement nesting |
| Efficiency Goal | Optimized for fast character-level I/O buffering and string matching | Optimized for recursive syntax tree generation and grammar shift/reduce tables |
| Portability | Confines character encoding quirks (ASCII, UTF-8, line-ending formats) to one module | Remains completely independent of hardware character sets and file reading mechanics |
2.1.3 Tokens, Patterns, and Lexemes
Understanding the distinctions among tokens, patterns, and lexemes is essential for lexical analysis:
Tokens, Patterns, and Lexemes
- Token: An abstract grammatical category (terminal symbol) recognized by the lexical analyzer and consumed by the parser. Examples:
id,num,if,while,relop,assign. - Lexeme: The concrete sequence of characters in the source code that matches the pattern for a given token. Examples:
total_sum,3.14159,while,<=. - Pattern: A formal descriptive specification (usually a regular expression) that defines the set of all possible character strings that can form a valid lexeme for a token.
| Token Name | Sample Lexemes | Informal Pattern Description |
|---|---|---|
if | if | Characters i, f |
else | else | Characters e, l, s, e |
relop | <, <=, ==, !=, >, >= | Comparison operators |
id | count, x, matrix_2 | Letter followed by letters, digits, and underscores |
number | 42, 3.1415, 6.02e23 | Any numeric constant (integer or floating-point) |
literal | "Compilation complete\n" | Any sequence of characters enclosed within double quotes |
When a token has multiple possible lexemes (such as id or number), it carries an attribute value to convey semantic data to downstream phases:
2.2 Specification and recognition of tokens
2.2.1 Mathematical Operations on Strings and Languages
Let an alphabet be a finite set of symbols (e.g., or the ASCII character set).
- A string (word) over is a finite sequence of symbols chosen from . The empty string is denoted , with length .
- The length is the number of symbol occurrences in .
- Prefix: Any leading segment of a string. If , prefixes are .
- Suffix: Any trailing segment of a string. Suffixes of are .
- Substring: Any contiguous segment obtained by removing a prefix and a suffix.
- Concatenation: If and , then . Identity: .
A language over is any countable set of strings over .
| Operation | Formal Notation | Mathematical Definition |
|---|---|---|
| Union | ||
| Concatenation | ||
| Kleene Closure | ||
| Positive Closure |
2.2.2 Regular Expressions and Regular Definitions
Regular Expressions (RE) provide a concise algebraic notation for describing patterns of tokens:
- Basis:
- is a regular expression denoting the language .
- If , then is a regular expression denoting .
- Inductive Steps: If and are regular expressions denoting and :
- Alternation (Choice): denotes .
- Concatenation: denotes .
- Kleene Star: denotes .
Precedence of Operators
Kleene star () has the highest precedence, followed by concatenation, and alternation () has the lowest precedence. For instance, parses as .
Regular Definitions
To simplify complex regular expressions, names are assigned to subexpressions:
where each is a distinct identifier and each is a regular expression over .
For standard C identifiers and numbers:
2.2.3 Transition Diagrams for Token Recognition
A transition diagram is a flowchart-like directed graph used to model the internal logic of a lexical analyzer:
- States: Represented as circles.
- Start State: The initial state marked with an incoming arrow labeled "start".
- Edges: Directed arrows labeled by input characters or character classes indicating state transitions.
- Accepting States (Final States): Represented by double concentric circles, indicating that a valid token has been recognized.
- Retract (): When an accepting state requires looking ahead at a character that is not part of the current lexeme, the accepting state is marked with an asterisk (). The scanner must retract the input pointer by one character (
retract()).
| State | On input | Next state | Action |
|---|---|---|---|
| 0 (start) | < | 1 | read next character |
| 0 | = | 5 | return EQ |
| 0 | > | 6 | read next character |
| 1 | = | 2 | return LE |
| 1 | > | 3 | return NE |
| 1 | other | 4 | retract, return LT |
| 6 | = | 7 | return GE |
| 6 | other | 8 | retract, return GT |
2.3 Input buffering
Character scanning is the most I/O-intensive task in the entire compilation pipeline. A compiler must examine millions of characters, often inspecting one or more lookahead characters before confirming the boundary of a token.
2.3.1 The Two-Buffer Scheme
Reading characters individually from secondary storage using system calls (such as C fgetc() or Unix read()) generates excessive context-switching overhead. To minimize system calls, the compiler utilizes a two-buffer scheme:
+-------------------+-------------------+
| Buffer 1 | Buffer 2 |
| [ N characters ] | [ N characters ] |
+-------------------+-------------------+
^ ^
| |
lexemeBegin forward- Two contiguous memory buffers of size (typically , matching the hardware disk sector/block size) are allocated.
- A single read system call fills an entire half-buffer of characters at once.
- Two pointers navigate the text:
lexemeBegin: Points to the first character of the lexeme currently being analyzed.forward: Advances through characters until a matching pattern is determined.
- If
forwardreaches the end of Buffer 1, Buffer 2 is populated with the next characters from disk, andforwardwraps around to Buffer 2. Ifforwardreaches the end of Buffer 2, Buffer 1 is reloaded.
2.3.2 Optimization Using Sentinels
In a naive two-buffer implementation, the scanner must execute two conditional tests for every single character inspected:
- Test whether
forwardhas reached the end of the current buffer. - Test which character is currently under
forwardto determine the automaton transition.
Because the buffer boundary check triggers millions of times, it substantially degrades scanning throughput. This overhead is eliminated by appending a sentinel character—the EOF (End of File) symbol—to the physical end of each buffer half:
+---------------------+---------------------+
| Buffer 1 | EOF | Buffer 2 | EOF |
+---------------------+---------------------+With sentinels, the inner scanning loop performs only one test per character in the common path:
switch (*forward++) {
case EOF:
if (forward == &buffer1[N]) {
// Reached end of Buffer 1; reload Buffer 2
reload_buffer(buffer2, N);
forward = &buffer2[0];
} else if (forward == &buffer2[N]) {
// Reached end of Buffer 2; reload Buffer 1
reload_buffer(buffer1, N);
forward = &buffer1[0];
} else {
// Reached true end of input file
return TOKEN_EOF;
}
break;
case ' ':
case '\t':
case '\n':
// Handle whitespace
break;
default:
// Perform standard automaton character transition
break;
}Worked Examples
1
Construct a transition diagram to recognize C-style identifiers and integer constants. Show how the input string speed_99 = 450; is decomposed into lexemes, tokens, and attribute values, explaining where pointer retraction occurs.
Designing Transition Diagrams:
- Identifier Transition Diagram:
- State (start): On receiving a letter or underscore
[A-Za-z_], transition to State . - State : On receiving a letter, digit, or underscore
[A-Za-z0-9_], loop in State . - State (accepting): On any other character, retract
forwardby and accept tokenid.
- State (start): On receiving a letter or underscore
- Integer Constant Transition Diagram:
- State (start): On receiving a digit
[0-9], transition to State . - State : On receiving a digit
[0-9], loop in State . - State (accepting): On any other character, retract
forwardby and accept tokennumber.
- State (start): On receiving a digit
Tracing Input String speed_99 = 450;:
- Scanning
speed_99: Characterss,p,e,e,d,_,9,9loop in State . The next character is space' '. The scanner transitions to State (accepting), retracts' ', inserts/looks up"speed_99"in the symbol table at entry , and emits . - Skipping whitespace: Space
' 'is stripped. - Scanning
=: State on'='transitions to State (accepting) without retraction, emitting . - Skipping whitespace: Space
' 'is stripped. - Scanning
450: Characters'4','5','0'loop in State . The next character is';'. The scanner transitions to State (accepting), retracts';', and emits . - Scanning
;: Matches single-character delimiter, emitting .
The string speed_99 = 450; yields the token stream:
- (retracted at space)
- (no retraction)
- (retracted at
;) - (no retraction)
2
A lexical analyzer scans a source file of size ().
- In a naive two-buffer implementation without sentinels, the scanner performs two conditional branches per character: one to check for buffer-end boundary and one to switch on the character.
- In a sentinel-based implementation with buffer block size , the scanner performs only one conditional branch per character in the normal path. An additional buffer-reload check occurs only when the
EOFsentinel is encountered at each buffer boundary.
Calculate:
- The total number of conditional branch evaluations in the naive scheme.
- The total number of conditional branch evaluations in the sentinel scheme.
- The absolute and percentage reduction in branch evaluations achieved by using sentinels.
Naive Scheme Branch Evaluations: In the naive scheme, each character requires checking both the pointer limit and character value:
Sentinel Scheme Branch Evaluations: In the sentinel scheme:
- Normal characters: Exactly branch evaluation (the
switch(*forward++)) per character:
- Sentinel boundary hits: A buffer boundary occurs every . The number of boundary transitions is:
At each boundary, an extra conditional test evaluates which buffer end was hit ( extra checks).
Total branches:
Reduction Analysis: Absolute branch reduction:
Percentage reduction:
- Naive scheme branches: .
- Sentinel scheme branches: .
- Reduction: branch evaluations (a computational reduction).
3
Construct the complete regular definition and transition diagram for recognizing signed and unsigned floating-point numbers with optional exponents (such as +12.45e-3, -0.5, 34E+2, 78).
Formulating Regular Definitions:
Transition Diagram Structure:
- State (start): On
+or-, move to State . Ondigit, move to State . - State : On
digit, move to State . - State : On
digit, loop in State . On.(decimal point), move to State . OnEore, move to State . On any other character, transition to State (accepting integer constant, retract). - State : On
digit, move to State . - State : On
digit, loop in State . OnEore, move to State . On any other character, transition to State (accepting float without exponent, retract). - State : On
+or-, move to State . Ondigit, move to State . - State : On
digit, move to State . - State : On
digit, loop in State . On any other character, transition to State (accepting full scientific float, retract).
The resulting transition diagram processes the optional sign in States , whole digits in State , fractional digits in States , and signed exponent powers in States , using retraction at accepting states to restore trailing non-numeric delimiters.
Exercises
Practice Exercises — Lexical Analysis and Input Buffering
Define the terms token, lexeme, and pattern. Using the C statement float average = sum / 10.0;, list each token, its matching lexeme, and its associated attribute value.
Definitions:
- Token: Abstract syntactic category recognized by the compiler front-end.
- Lexeme: The actual sequence of characters in the source text matching a token's pattern.
- Pattern: The descriptive rule (regular expression) defining valid lexeme structures.
Token Breakdown of float average = sum / 10.0;:
- Lexeme
float: Tokenfloat_kw(keyword, no attribute needed or pointer to keyword table). - Lexeme
average: Tokenid, attribute . - Lexeme
=: Tokenassign_op, attribute . - Lexeme
sum: Tokenid, attribute . - Lexeme
/: Tokenmult_op, attribute . - Lexeme
10.0: Tokennum, attribute (or pointer to literal table). - Lexeme
;: Tokensemicolon, attribute .
float matches float_kw; average and sum match id with symbol table pointers; = matches assign_op; / matches mult_op; 10.0 matches num with literal value ; ; matches semicolon.
Write formal regular definitions for:
- Valid variable identifiers in Python (cannot start with a digit, can contain letters, underscores, and digits).
- Relational operators in C (
<,<=,==,!=,>,>=). - String literals enclosed in double quotes containing arbitrary characters and escape sequences
\"and\\.
Regular Definitions:
- Python Identifiers:
- Relational Operators:
- String Literals with Escapes:
Identifiers: . Relational operators: . String literals: .
Explain why looking ahead is essential in lexical analysis. Describe a specific language construct where a scanner must look ahead multiple characters before deciding on a token.
Necessity of Lookahead: In many programming languages, the lexical analyzer cannot determine the identity or boundary of a token solely by reading characters belonging to the lexeme itself. A delimiter or subsequent operator character must be inspected to distinguish between valid language constructs.
Representative Lookahead Examples:
- Relational Operators: Upon encountering
>, the scanner cannot immediately emit tokenGT. It must inspect the next character; if=follows, the token isGE(>=); otherwise, the token isGT(>), requiring retraction of the lookahead character. - Fortran
DOLoop vs. Assignment: In classical Fortran, blanks are ignored:DO 5 I = 1.25is an assignment to variableDO5Iof the value1.25.DO 5 I = 1, 25is a loop statement with label 5. The scanner must look ahead past the digits and identifier until it sees either a comma,(loop) or a period.(assignment) before classifying the initialDOlexeme.
Lookahead is necessary because prefixes of distinct tokens often coincide. For example, > requires 1 character of lookahead to differentiate > from >=, and Fortran requires lookahead past the variable name to distinguish loop header DO 5 I = 1, 25 from assignment DO 5 I = 1.25.
A compiler implements a two-buffer input scheme where each buffer half has size , including a 1-byte sentinel at the end of each half.
- Determine the maximum length of a lexeme that can be guaranteed to fit completely within the buffer pair without overwriting unparsed characters.
- If the buffer size is doubled to with 1-byte sentinels, determine the new maximum safe lexeme length.
- What error condition arises if an identifier or string literal exceeds this maximum buffer length?
Maximum Safe Lexeme Length for : In a two-buffer system, while lexemeBegin is pinned at the start of a token in one buffer, forward can advance through the rest of that buffer and across the entire second buffer. However, once forward wraps past the second buffer, continuing further would require reloading the buffer where lexemeBegin is still pointing, which would destroy the beginning of the lexeme. Thus, the maximum safe lexeme length is bounded by the size of one buffer half:
If of header/control metadata are reserved per buffer half:
Doubled Buffer Size (): With and total reserved metadata:
Buffer Overflow Error Handling: If an unterminated string literal (e.g., missing closing quotation mark ") or an excessively long identifier exceeds , the scanner triggers a buffer overflow error: "Lexeme exceeds maximum buffer capacity." The error recovery routine truncates the identifier or flags the unterminated string and resynchronizes forward at the next line boundary.
Maximum safe lexeme length is for (or without header reserve), and for . Exceeding this triggers a buffer overflow error due to buffer wrap-around.
How does a lexical analyzer distinguish between language keywords (such as if, while, return) and user-defined identifiers? Compare the keyword table lookup method with the automaton hardcoding method.
The Keyword vs. Identifier Problem: Keywords (reserved words) have the exact same lexical pattern as identifiers (a letter followed by letters and digits). For instance, while matches the regular definition for an identifier.
Comparison of Approaches:
- Keyword Table Lookup (Symbol Table Initialization):
- The scanner uses a single generic transition diagram for all identifiers.
- The symbol table is pre-initialized with all reserved keywords and their corresponding token codes before scanning starts.
- When a string matching the identifier pattern is recognized, the scanner executes
lookup(lexeme):- If found in the keyword table, it returns the specific keyword token (e.g.,
WHILE). - If not found, it inserts the lexeme as a regular identifier and returns token
ID.
- If found in the keyword table, it returns the specific keyword token (e.g.,
- Automaton Hardcoding:
- The transition diagram contains explicit, dedicated state paths for every keyword (e.g., separate states for
w \to h \to i \to l \to e). - If a subsequent character is a letter/digit, the automaton transitions to the general identifier state.
- Highly fast (avoids table lookup), but drastically inflates the number of automaton states and makes grammar modifications difficult.
- The transition diagram contains explicit, dedicated state paths for every keyword (e.g., separate states for
Keywords are distinguished from identifiers either by pre-populating the symbol/keyword table and performing a lookup() on every scanned identifier, or by embedding dedicated transition paths in the finite automaton. Keyword table lookup is vastly preferred for its simplicity and maintainability.