PadhaikoAll subjects

Lexical Analysis (part 1: 2.1–2.3)

Compiler Design (ENCT 326)

Open in the Padhaiko app

2.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).

Diagram: scanner, parser and helpersText
Source Program                         getNextToken()
(character stream) --> Lexical Analyzer <------------------ Syntax Analyzer
                       (Scanner)        ------------------> (Parser)
                          |   ^             token stream
                          |   |
                          |   +--(two-way)-- Symbol Table
                          v
                     Error Handler

2.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:

  1. The parser calls a function such as getNextToken().
  2. The scanner reads input characters until it identifies the next complete lexeme.
  3. 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:

AspectLexical AnalysisSyntax Analysis
Formal ModelRegular Expressions and Deterministic/Nondeterministic Finite Automata (DFA/NFA)Context-Free Grammars (CFG) and Pushdown Automata (PDA)
Input UnitIndividual characters (bytes)Discrete tokens emitted by the scanner
Primary TaskStripping whitespace/comments, identifying keywords, constants, identifiersImposing hierarchical syntactic structure, validating expression/statement nesting
Efficiency GoalOptimized for fast character-level I/O buffering and string matchingOptimized for recursive syntax tree generation and grammar shift/reduce tables
PortabilityConfines character encoding quirks (ASCII, UTF-8, line-ending formats) to one moduleRemains 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:

Definition

Tokens, Patterns, and Lexemes

Tokens, Lexemes, and Patterns
Token NameSample LexemesInformal Pattern Description
ififCharacters i, f
elseelseCharacters e, l, s, e
relop<, <=, ==, !=, >, >=Comparison operators
idcount, x, matrix_2Letter followed by letters, digits, and underscores
number42, 3.1415, 6.02e23Any 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 language over is any countable set of strings over .

Language Operations
OperationFormal NotationMathematical 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:

  1. Basis:
    • is a regular expression denoting the language .
    • If , then is a regular expression denoting .
  2. 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:

Transition diagram for relational operators
StateOn inputNext stateAction
0 (start)<1read next character
0=5return EQ
0>6read next character
1=2return LE
1>3return NE
1other4retract, return LT
6=7return GE
6other8retract, 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:

Text
+-------------------+-------------------+
|     Buffer 1      |     Buffer 2      |
|  [ N characters ] |  [ N characters ] |
+-------------------+-------------------+
  ^           ^
  |           |
lexemeBegin  forward

2.3.2 Optimization Using Sentinels

In a naive two-buffer implementation, the scanner must execute two conditional tests for every single character inspected:

  1. Test whether forward has reached the end of the current buffer.
  2. Test which character is currently under forward to 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:

Text
+---------------------+---------------------+
| Buffer 1      | EOF | Buffer 2      | EOF |
+---------------------+---------------------+

With sentinels, the inner scanning loop performs only one test per character in the common path:

Sentinel-Based Buffer AdvanceC
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

Example 1

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:

  1. 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 forward by and accept token id.
  2. 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 forward by and accept token number.

Tracing Input String speed_99 = 450;:

  • Scanning speed_99: Characters s, p, e, e, d, _, 9, 9 loop 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 .
Answer:

The string speed_99 = 450; yields the token stream:

  1. (retracted at space)
  2. (no retraction)
  3. (retracted at ;)
  4. (no retraction)
Example 2

2

A lexical analyzer scans a source file of size ().

  1. 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.
  2. 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 EOF sentinel is encountered at each buffer boundary.

Calculate:

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:

Answer:
  • Naive scheme branches: .
  • Sentinel scheme branches: .
  • Reduction: branch evaluations (a computational reduction).
Example 3

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 . On digit, move to State .
  • State : On digit, move to State .
  • State : On digit, loop in State . On . (decimal point), move to State . On E or e, 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 . On E or e, move to State . On any other character, transition to State (accepting float without exponent, retract).
  • State : On + or -, move to State . On digit, 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).
Answer:

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

Question 1

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;:

  1. Lexeme float: Token float_kw (keyword, no attribute needed or pointer to keyword table).
  2. Lexeme average: Token id, attribute .
  3. Lexeme =: Token assign_op, attribute .
  4. Lexeme sum: Token id, attribute .
  5. Lexeme /: Token mult_op, attribute .
  6. Lexeme 10.0: Token num, attribute (or pointer to literal table).
  7. Lexeme ;: Token semicolon, attribute .
Answer:

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.

Question 2

Write formal regular definitions for:

  1. Valid variable identifiers in Python (cannot start with a digit, can contain letters, underscores, and digits).
  2. Relational operators in C (<, <=, ==, !=, >, >=).
  3. String literals enclosed in double quotes containing arbitrary characters and escape sequences \" and \\.

Regular Definitions:

  1. Python Identifiers:
  1. Relational Operators:
  1. String Literals with Escapes:
Answer:

Identifiers: . Relational operators: . String literals: .

Question 3

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:

  1. Relational Operators: Upon encountering >, the scanner cannot immediately emit token GT. It must inspect the next character; if = follows, the token is GE (>=); otherwise, the token is GT (>), requiring retraction of the lookahead character.
  2. Fortran DO Loop vs. Assignment: In classical Fortran, blanks are ignored:
    • DO 5 I = 1.25 is an assignment to variable DO5I of the value 1.25.
    • DO 5 I = 1, 25 is 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 initial DO lexeme.
Answer:

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.

Question 4

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.

  1. Determine the maximum length of a lexeme that can be guaranteed to fit completely within the buffer pair without overwriting unparsed characters.
  2. If the buffer size is doubled to with 1-byte sentinels, determine the new maximum safe lexeme length.
  3. 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.

Answer:

Maximum safe lexeme length is for (or without header reserve), and for . Exceeding this triggers a buffer overflow error due to buffer wrap-around.

Question 5

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:

  1. 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.
  2. 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.
Answer:

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.

← IntroductionLexical Analysis (part 2: 2.4–2.6) →