Compiler Phases and Token Classification

The Anatomy of a Compiler

At its core, a compiler is a program that translates code written in a high-level programming language (like C, Java, or Python) into a low-level language (like assembly or machine code) that the computer's processor can directly execute. This translation is not a single, monolithic action but a multi-stage process, often visualized as a pipeline. Each stage, or phase, takes the output of the previous one, performs a specific transformation, and passes its result to the next.

This phased approach offers significant engineering advantages: it modularizes the complex task of compilation, simplifies development and testing, and allows parts of the compiler (like the code-generation phase) to be adapted for different target machines without rewriting the entire program.

The six primary phases of a compiler are:

1. Lexical Analysis
2. Syntax Analysis
3. Semantic Analysis
4. Intermediate Code Generation
5. Code Optimization
6. Target Code Generation

The first four phases are often grouped into the front-end, which deals with the source language, while the last two form the back-end, which handles aspects related to the target machine architecture. A symbol table is a data structure used across all phases to store information about identifiers like variable names, function names, etc.

To get a clear overview of this entire process, we'll watch a video that walks through each phase using a simple C expression.

This walkthrough gives you a complete mental model of the compiler's pipeline. Now, let's dive deep into the first and foundational phase.

Phase 1 in Detail: Lexical Analysis

The lexical analysis phase, also known as scanning, is the first point of contact between the compiler and your source code. Its primary job is to read the sequence of characters that make up the program and group them into meaningful units called lexemes. For each lexeme, the lexical analyzer generates a token.

Let's clarify these terms:

• Lexeme: The actual sequence of characters in the code. For example, in int count = 0;, the lexemes are int, count, =, 0, and ;.
• Token: An abstract symbol representing a class of lexemes. A token is typically represented as a pair: ⟨token_name, attribute_value⟩. For instance, the lexeme count would be mapped to a token like ⟨id, pointer_to_symbol_table_entry_for_count⟩. The lexeme 0 would become ⟨number, 0⟩.
• Pattern: A rule that describes the set of strings that can form a lexeme for a particular token. This is where regular expressions come in.

The lexical analyzer performs several crucial functions:

• Tokenization: The core task of converting the character stream to a token stream.
• Stripping Whitespace and Comments: It removes non-essential parts of the code like spaces, tabs, newlines, and comments.
• Symbol Table Management: It inserts new identifiers (like variable and function names) into the symbol table.
• Error Reporting: It can report basic errors, like an illegal character.

Using Regular Expressions to Define Tokens

How does the lexical analyzer know that count is an identifier and 0 is a number? It uses patterns defined by regular expressions, a concept you mastered in the Theory of Computation module. Each class of token has an associated regular expression.

Here are some examples for a C-like language:

• Keyword: if | else | while | int | ...
• Identifier: [a-zA-Z_][a-zA-Z0-9_]* (A letter or underscore, followed by zero or more letters, digits, or underscores)
• Integer Constant: [0-9]+ (One or more digits)
• Relational Operator: == | != | < | <= | > | >=

The lexical analyzer's engine is essentially a Deterministic Finite Automaton (DFA). The regular expressions for all token types are combined into one large NFA, which is then converted into an equivalent DFA (using the subset construction algorithm you've learned). This DFA reads the source code character by character and transitions between states. When it reaches a final state, it has recognized a lexeme and emits the corresponding token.

The following video provides a detailed look at this process.

Handling Ambiguity

An interesting challenge arises when a lexeme could match multiple patterns. For instance, if matches both the pattern for the keyword if and the pattern for an identifier. How does the lexical analyzer decide? Two principles are commonly used:

1. Longest Match Rule: The lexical analyzer always tries to find the longest possible lexeme starting from the current position. For example, when it sees ==, it matches the token for the equality operator, not two separate = tokens.
2. Rule Priority: When a lexeme matches multiple patterns of the same length (like if), rules are given priority. Typically, keywords are given higher priority than identifiers. Thus, if is always recognized as a keyword. The DFA in the video you just watched demonstrates this: the state for recognizing if is distinct from the general-purpose identifier-recognizing states.

Conclusion

In this lesson, we mapped out the terrain of compiler design. You now have a high-level understanding of the transformative journey a program takes, from human-readable text to machine-executable code.

Here are the key takeaways:

• A compiler is structured as a pipeline of six main phases: Lexical Analysis, Syntax Analysis, Semantic Analysis, Intermediate Code Generation, Code Optimization, and Target Code Generation.
• The front-end is source-language dependent, while the back-end is target-machine dependent.
• The lexical analyzer is the first phase, responsible for converting a stream of characters into a stream of tokens.
• Regular expressions are used to define the patterns for tokens, and a DFA is used to perform the recognition. This is a direct practical application of finite automata theory.

We've seen what the lexical analyzer does. Now, the stream of tokens it produces—⟨id, x⟩, ⟨assign_op⟩, ⟨id, a⟩, ⟨plus_op⟩, ⟨id, b⟩, etc.—is ready for the next phase. The syntax analyzer, or parser, must determine if this sequence of tokens forms a grammatically valid "sentence."

In our next lesson, we will begin our exploration of syntax analysis by learning to compute FIRST and FOLLOW sets. These are fundamental tools that help a type of parser, called a top-down parser, to predict the grammatical structure of the code without guesswork.