Lexical Analysis

Learning Objectives

• Define lexical analysis and its role in the compilation pipeline
• Identify the different categories of tokens produced by a scanner
• Use regular expressions to describe patterns for common token types
• Trace a code snippet through the lexical analysis process step by step
• Explain how errors are detected and reported during lexical analysis

Quick Answer

Lexical analysis, also called scanning or tokenization, is the first phase of compilation. The scanner reads source code character by character and groups characters into tokens — the smallest meaningful units of a programming language. Tokens fall into categories such as keywords, identifiers, literals, operators, and punctuation. The scanner uses regular expressions and finite automata to recognize these patterns. Its output is a stream of labeled tokens that the parser then uses in the next phase.

Overview

Compiler design is a crucial aspect of computer science that deals with the creation of programs that translate source code written in one programming language into machine code or low-level assembly language. The process involves several stages, with lexical analysis being the first step in the compilation process.

Introduction to Compiler Design

A compiler is a program that translates source code written in a high-level programming language into machine code that can be executed directly by the computer's processor. The compilation process involves several stages, each serving a specific purpose in transforming the source code into executable machine code.

Key Components of Compiler Design

1. Lexical Analyzer (Scanner): Reads the source code character by character and groups them into tokens.
2. Syntax Analyzer (Parser): Analyzes the tokens produced by the lexical analyzer to ensure the source code adheres to the language's syntax rules.
3. Semantic Analyzer: Checks the meaning of the source code, ensuring that it complies with the language's semantics.
4. Intermediate Code Generator: Translates the parsed syntax tree into intermediate code.
5. Optimizer: Improves the efficiency of the generated code.
6. Code Generator: Converts the optimized intermediate code into machine-specific instructions.

Lexical Analysis

Lexical analysis, also known as scanning or tokenization, is the process of breaking down the source code into a series of tokens. These tokens represent keywords, identifiers, symbols, and other basic elements of the programming language.

Key Concepts in Lexical Analysis

1. Token Types:

   • Keywords (e.g., if, while)
   • Identifiers (variable names)
   • Literals (numbers, strings)
   • Symbols (operators, punctuation)

2. Regular Expressions:

   • Used to define patterns for matching tokens
   • Examples:
     • Keywords: if|while|return
     • Identifiers: [a-zA-Z_][a-zA-Z0-9_]*
     • Numbers: \d+
     • Strings: \".*?\"

Lexical Analysis Process

The lexical analysis process involves the following steps:

1. Reading Input: The source code is read character by character.
2. Pattern Matching: Regular expressions are used to identify tokens based on predefined patterns.
3. Token Generation: For each recognized pattern, a corresponding token is created and added to the token stream.
4. Error Handling: Any invalid characters or patterns are reported as lexical errors.

Example of Lexical Analysis

Let's consider a simple example of lexical analysis for the following source code:

if (x > 10) {
    return "Value is greater";
}

The tokens generated from this source code would be:

Token Type	Token
Keyword	if
Symbol	(
Identifier	x
Symbol	>
Number	10
Symbol	)
Symbol	{
Keyword	return
String	"Value is greater"
Symbol	}

Key Terms

Term	Definition	Related Concept
Token	A labeled unit of source text (keyword, identifier, literal, operator)	Lexeme
Lexeme	The actual character sequence matched to produce a token	Token
Scanner / Lexer	The component that performs lexical analysis	Compiler front end
Regular Expression	A pattern that describes a set of strings, used to match token types	Finite automaton
Finite Automaton	A state machine used to implement token recognition	DFA, NFA
Keyword	A reserved word with special meaning in the language (if, while, return)	Identifier
Identifier	A name chosen by the programmer for a variable, function, or type	Symbol table
Lexical Error	An invalid character or pattern that cannot form a valid token	Error recovery

Common Mistakes

Misconception: Lexical analysis checks whether the program is grammatically correct. Why it's wrong: Lexical analysis only identifies individual tokens — it says nothing about whether those tokens are in a valid sequence. Grammar checking is the job of the syntax analyzer (parser). Correct understanding: The lexer asks "what kind of thing is this character sequence?" The parser asks "are these things in the right order?"

---

Misconception: Keywords and identifiers are detected differently by the programmer's scanner code. Why it's wrong: Most lexers recognize keywords using the same pattern as identifiers — a word starting with a letter followed by letters and digits. The scanner then checks a keyword table to see if the matched string is reserved. Correct understanding: The scanner matches the identifier pattern, then looks up the lexeme in a keyword table. If found, it emits a keyword token; otherwise, it emits an identifier token.

---

Misconception: Lexical errors stop compilation immediately. Why it's wrong: Many production compilers use error recovery to skip or substitute the invalid character and continue scanning so they can report multiple errors in one pass. Correct understanding: Modern scanners often report the error, discard the offending character, and continue to find more lexical errors in the same compilation.

Comparison and Connections

Concept	Lexical Analysis	Syntax Analysis
Input	Raw source characters	Token stream
Output	Token stream	Parse tree
Tool used	Regular expressions / DFA	Context-free grammars
Errors detected	Invalid characters, malformed tokens	Invalid token sequences
Runs	First phase	Second phase

Practice Questions

Recall

1. What are the four main categories of tokens in most programming languages? Answer guidance: Keywords, identifiers, literals (numbers and strings), and symbols/operators. Some definitions also include punctuation as a separate category.

2. What does the scanner use to recognize token patterns? Answer guidance: Regular expressions, which are implemented as finite automata (typically DFAs) for efficient matching.

Understanding

3. Why are regular expressions sufficient for describing tokens but not for describing a full programming language? Answer guidance: Regular expressions describe regular languages — patterns with no nesting. Programming languages require nested structures (balanced parentheses, nested function calls) which need context-free grammars.

4. A scanner encounters the text whileTrue. Should it emit a while keyword token and a True identifier token? Answer guidance: No. Scanners use maximal munch — they consume the longest possible match. whileTrue matches the identifier pattern and should be emitted as a single identifier token.

Application

5. Write the token stream for: int count = 0; Answer guidance: int (keyword), count (identifier), = (operator), 0 (integer literal), ; (punctuation). Five tokens.

6. What regular expression pattern would match a valid C-style identifier? Answer guidance: [a-zA-Z_][a-zA-Z0-9_]* — starts with a letter or underscore, followed by zero or more letters, digits, or underscores.

Analysis

7. Why is it efficient to implement the lexer as a deterministic finite automaton (DFA) rather than testing each token type's regular expression one by one? Answer guidance: A DFA can scan input in one pass, making a single state transition per character. Testing each regex separately would be O(n * k) where k is the number of token types. A combined DFA reduces this to O(n).

8. Compare how lexical analysis and semantic analysis each contribute to catching programmer mistakes. Answer guidance: Lexical analysis catches character-level mistakes — illegal characters or malformed literals. Semantic analysis catches meaning-level mistakes — using a variable before declaring it or passing the wrong type to a function.

FAQ

What is the difference between a token and a lexeme? A lexeme is the actual string of characters found in the source code — for example, the characters while. A token is a pair consisting of the token type (keyword) and the lexeme. The scanner produces tokens; the parser works with token types and does not usually need the original character string.

Can the same string produce different tokens in different contexts? Yes, in some languages. For example, * in C could be a multiplication operator or a pointer dereference operator depending on context. Most lexers emit the same token type and leave disambiguation to the parser, which has more context.

What happens when the scanner hits an unrecognized character like @ in C? The scanner reports a lexical error (usually including line and column numbers) and then applies some form of error recovery — typically discarding the character and continuing. The error is added to an error list, and the compiler reports all errors at the end rather than stopping at the first one.

How does the scanner know where one token ends and the next begins? It uses the maximal munch rule — always match the longest string that forms a valid token. When the next character can no longer extend the current match, the scanner emits the current token and starts a new match. Whitespace and comments are typically discarded as delimiters.

Why do some languages like Python care about whitespace while most do not? In Python, indentation is syntactically meaningful — it defines block structure. The scanner must emit special INDENT and DEDENT tokens when indentation increases or decreases. Most languages use braces or explicit keywords for block structure, so whitespace is just a separator that the scanner discards.

Quick Revision

• Lexical analysis is the first compiler phase; it converts source characters into tokens
• Tokens are labeled units: keyword, identifier, literal, operator, punctuation
• A lexeme is the actual matched string; a token is the type-plus-lexeme pair
• Regular expressions describe token patterns; finite automata implement them efficiently
• Maximal munch: always match the longest valid token
• Keywords are recognized by matching the identifier pattern and then looking up a keyword table
• Lexical errors involve individual characters; syntax errors involve token sequences
• The scanner outputs a token stream that becomes the parser's input

Related Topics

Prerequisites: Regular expressions, finite automata, basic compiler structure

Related Topics: Syntax analysis, formal language theory, text processing

Next Topics: Syntax analysis and parsing, context-free grammars, LL and LR parsers