Introduction to Lexical Analysis

Overview

Lexical analysis is the first phase of a compiler. The lexical analyzer (also called a scanner or tokenizer) reads the stream of characters making up the source program and groups them into meaningful sequences called lexemes. For each lexeme, the lexical analyzer produces a token that it passes to the subsequent phase, the syntax analyzer (parser).

Role of the Lexical Analyzer

The lexical analyzer performs several important functions:

Primary Functions

1. Reading input characters: Scans the source program from left to right
2. Grouping into lexemes: Identifies meaningful character sequences
3. Producing tokens: Maps lexemes to token classes
4. Stripping comments and whitespace: Removes non-essential characters
5. Maintaining line numbers: For error reporting

Secondary Functions

• Macro expansion: In some systems, handled during scanning
• Including files: Processing include directives
• Correlating error messages: Tracking source positions

Why Separate Lexical Analysis?

There are practical reasons for separating lexical analysis from parsing:

Interaction with Parser

The parser calls getNextToken() whenever it needs the next token. This demand-driven approach means the scanner doesn't need to store all tokens in memory.

Key Terminology

Token

A token is a pair consisting of a token name and an optional attribute value:

Token names are abstract symbols representing a kind of lexical unit (keyword, identifier, operator, etc.).

Lexeme

A lexeme is the actual character sequence in the source program that matches the pattern for a token.

Pattern

A pattern describes the form that lexemes of a token may take. Patterns are typically specified using regular expressions.

Example

For the statement: float count = 5;

Input Buffering

Since the lexical analyzer must process characters one at a time, efficient buffering is crucial:

Buffer Pairs Technique

Two pointers are maintained:

• lexemeBegin: Points to the start of the current lexeme
• forward: Scans ahead to find the end of the lexeme

Sentinels

To avoid checking for buffer boundaries on every character advance, a sentinel character (EOF) is placed at the end of each buffer half.

Specification of Tokens

Tokens are specified using regular expressions:

Errors in Lexical Analysis

The lexical analyzer can detect a limited set of errors:

• Invalid characters not belonging to the language alphabet
• Malformed numbers (e.g., 12.34.56)
• Unterminated strings or comments
• Identifiers exceeding maximum length

Error Recovery Strategies

1. Panic mode: Delete characters until a valid token is found
2. Character insertion: Insert a missing character
3. Character deletion: Remove an extraneous character
4. Character transposition: Swap two adjacent characters

Interview Questions

1. What is the role of a lexical analyzer in a compiler?

The lexical analyzer reads source code characters, groups them into lexemes, produces tokens for the parser, strips whitespace and comments, and reports lexical errors. It interfaces with the parser through a getNextToken() function.

1. What is the difference between a token, a lexeme, and a pattern?

A token is an abstract symbol representing a class of strings (like IDENTIFIER). A lexeme is the actual string in the source code (like "count"). A pattern is the rule describing valid lexemes for a token (like letter followed by letters/digits).

1. Why is lexical analysis separated from syntax analysis?

For simplicity (each component is simpler alone), efficiency (specialized buffering), portability (input handling isolated), and clean theoretical separation (regular expressions for tokens, context-free grammars for syntax).

1. What is input buffering and why is it needed?

Input buffering uses two alternating buffers to efficiently read source code characters. It's needed because reading one character at a time from disk is extremely slow, and sometimes we need to look ahead several characters to determine a token.

1. What errors can a lexical analyzer detect?

Invalid characters, malformed numbers, unterminated strings/comments, and identifiers exceeding maximum length. It cannot detect syntactic or semantic errors.