Regular Expressions in Compiler Design

Introduction

Regular expressions (regex) are a fundamental notation for specifying patterns of strings. In compiler design, they serve as the primary mechanism for defining token patterns. Every token in a programming language can be described by a regular expression, and these expressions can be systematically converted into finite automata for efficient pattern matching.

Basic Operations

1. Concatenation

Two regular expressions joined together match strings that are concatenations of strings matched by each.

2. Alternation (Union)

The | operator matches strings matched by either operand.

3. Kleene Closure (Star)

The * operator matches zero or more repetitions.

4. Positive Closure

The + operator matches one or more repetitions.

5. Optional (Question Mark)

The ? operator matches zero or one occurrence.

Operator Precedence

From highest to lowest:

Example

Extended Notation

Character Classes

Predefined Classes

Quantifiers

Regular Definitions

A regular definition gives names to regular expressions for readability:

Important: Regular definitions must not be recursive (no self-reference).

Token Patterns Using Regular Expressions

Complete Token Specification Example

Algebraic Laws of Regular Expressions

Converting Regular Expressions to Token Recognizers

The process of building a lexical analyzer:

Practical Examples

Example 1: Email Pattern (Simplified)

Example 2: C Integer Constants

Example 3: C Comments

Limitations of Regular Expressions

Regular expressions cannot describe:

1. Nested structures: Balanced parentheses (()()) — requires counting
2. Cross-references: Matching brackets a^n b^n
3. Context-dependent patterns: Some token ambiguities

These require context-free grammars (handled by the parser).

Interview Questions

1. What are the three fundamental operations of regular expressions?

Concatenation (ab — a followed by b), alternation (a|b — a or b), and Kleene closure (a* — zero or more repetitions of a). All other operations can be derived from these three.

1. Why are regular expressions sufficient for lexical analysis but not parsing?

Regular expressions can describe flat, non-nested patterns (identifiers, numbers, operators) but cannot describe recursive structures (nested parentheses, matching brackets). Programming language syntax requires context-free grammars for describing nesting and recursion.

1. What is a regular definition? Give an example.

A regular definition names a regular expression for use in other definitions. Example: digit = [0-9], integer = digit+, float = digit+ . digit+. This makes complex patterns readable and maintainable.

1. **Explain the difference between a*, a+, and a?.**

a* matches zero or more a's (ε, a, aa, ...), a+ matches one or more a's (a, aa, ...), and a? matches zero or one a (ε or a). Note: a+ = aa* and a? = a|ε.

1. How do you convert a regular expression into a recognizer?

Using Thompson's construction to build an NFA, then the subset construction algorithm to convert the NFA into a DFA, and optionally DFA minimization. The resulting DFA is implemented as a transition table for efficient pattern matching.