In the previous tutorial, you learned that lexical analysis breaks a program down into tokens based on patterns, but a natural question follows immediately: how does a compiler actually describe those patterns in a precise, unambiguous way? Saying that an identifier "starts with a letter and can be followed by letters or digits" is fine for a human reader, but a compiler needs something far more exact and mechanical to work with. That precise description comes from regular expressions, a compact mathematical notation for describing sets of strings that follow a particular pattern.
Regular expressions are not unique to compilers. Anyone who has used search-and-replace in a text editor, validated an email address on a web form, or searched log files for a specific pattern has almost certainly used regular expressions, even if they did not think of it in those terms. What makes regular expressions especially important in Compiler Design is that they provide the theoretical foundation for how a lexical analyzer recognizes valid tokens, connecting directly back to the finite automata studied in Theory of Computation.
In this tutorial, you will learn what regular expressions are, the basic notation used to write them, how they are used to define patterns for different token types, the close relationship between regular expressions and finite automata, how a regular expression is converted step by step into something a lexical analyzer can actually use, and some common pitfalls beginners run into when writing patterns for real programming languages.
A regular expression is a formal notation used to describe a set of strings that share a common pattern. Rather than listing out every possible valid string one by one, which would be impossible for something like "all valid identifiers," a regular expression provides a compact rule that any string can be checked against to determine whether it belongs to that set.
In the context of lexical analysis, each token type in a programming language is associated with its own regular expression. When the lexical analyzer scans the source code, it is essentially trying to match the upcoming characters against these regular expressions to figure out which token type, if any, the next lexeme belongs to.
Informal Description: A valid identifier starts with a letter and may be followed by any number of letters or digits. Regular Expression: letter (letter | digit)*
This single line precisely captures every valid identifier in a way that leaves no room for ambiguity, which is exactly what a compiler needs, since it cannot rely on the kind of common sense a human reader would use to interpret a vague description.
Regular expressions are built from a small set of basic operations, and understanding these operations is enough to construct patterns for almost any token type found in typical programming languages.
| Operation | Symbol | Meaning |
|---|---|---|
| Union (Alternation) | | | Matches either the expression on the left or the expression on the right. |
| Concatenation | (written side by side) | Matches the first expression immediately followed by the second expression. |
| Kleene Star | * | Matches zero or more repetitions of the expression it follows. |
| Kleene Plus | + | Matches one or more repetitions of the expression it follows. |
| Optional | ? | Matches zero or one occurrence of the expression it follows. |
| Grouping | ( ) | Groups part of an expression together so operators can be applied to the group as a whole. |
These six building blocks might look limited at first glance, but they are surprisingly expressive when combined. Nearly every token pattern found in real programming languages, from identifiers to numeric literals to string constants, can be constructed using just these operations applied to individual characters or character classes.
Let us walk through how regular expressions are used to describe some of the most common token categories found in programming languages, building each pattern up piece by piece.
digit = 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 integer = digit digit* Equivalent shorthand: integer = digit+
Here, a single digit is defined as a choice between ten individual characters. An integer is then defined as one digit followed by zero or more additional digits, which is exactly what the Kleene plus operator expresses in a single, compact symbol.
letter = a | b | ... | z | A | B | ... | Z identifier = letter (letter | digit)*
This pattern states that an identifier must begin with a letter, and after that first letter, it may contain any combination of letters and digits, repeated any number of times, including zero additional characters.
real_number = digit+ . digit+
This pattern requires at least one digit, followed by a literal decimal point character, followed by at least one more digit, correctly describing numbers such as 3.14 while rejecting malformed input such as a number with no digits after the decimal point.
signed_integer = ( + | - )? digit+
The optional operator here allows a number to be preceded by an optional plus or minus sign, correctly matching both "42" and "-42" using a single, unified pattern.
Regular expressions describe patterns in a compact, human-readable notation, but a lexical analyzer needs something it can actually execute step by step while scanning characters. This is where finite automata come in. It is a well-established result in formal language theory that every regular expression can be systematically converted into an equivalent finite automaton, and every finite automaton can likewise be described by an equivalent regular expression. This equivalence is exactly why Theory of Computation and Compiler Design are so closely linked.
In practice, building a lexical analyzer from a regular expression typically follows a well-defined sequence of transformations, moving from an abstract mathematical description toward something that can be directly implemented in code.
| Step | Description |
|---|---|
| 1. Write the Regular Expression | Define the pattern for a token type using regular expression notation. |
| 2. Convert to an NFA | Translate the regular expression into a non-deterministic finite automaton using a systematic construction method. |
| 3. Convert the NFA to a DFA | Apply subset construction to eliminate non-determinism, producing a deterministic finite automaton. |
| 4. Minimize the DFA | Reduce the number of states in the DFA while preserving the exact same matching behavior, improving efficiency. |
| 5. Implement the DFA | Translate the minimized DFA into executable code, often represented internally as a transition table. |
This pipeline should feel familiar if you have already studied finite automata in Theory of Computation, since it directly reuses the NFA to DFA conversion and DFA minimization techniques from that subject. Compiler Design does not require you to relearn these ideas from scratch; instead, it shows you how to apply them to solve a concrete, practical problem.
Regular Expression:
(a | b)* a b
Meaning:
Any string over the alphabet {a, b} that ends specifically with the sequence "a b".
Simplified Automaton Behavior:
Stay in a starting state while reading a or b.
Move toward an accepting state only after reading an a immediately followed by a b at the end of the string.
Once such an automaton is built, checking whether a given lexeme matches the pattern becomes a simple matter of feeding its characters into the automaton one at a time and observing whether the automaton ends in an accepting state.
Real lexical analyzers do not just need to recognize a single pattern in isolation. They need to scan source code and determine, at every point, which one of many possible token patterns, such as keywords, identifiers, numbers, and operators, the upcoming characters match. This is typically handled by combining the regular expressions for every token type into a single combined automaton, often built using the union operation.
When multiple patterns could match the same input, such as when the letters "if" match both the pattern for the keyword "if" and the more general pattern for identifiers, lexical analyzers typically apply a priority rule, usually preferring keywords over identifiers when both match exactly. Combined with the longest match rule discussed in the previous tutorial, these priority rules allow a single combined automaton to correctly and unambiguously tokenize real source code.
Patterns: KEYWORD_IF = "if" IDENTIFIER = letter (letter | digit)* Input Lexeme: if Result: Matches both patterns, but KEYWORD_IF is given priority, so the token produced is KEYWORD_IF rather than IDENTIFIER.
Students sometimes wonder how regular expressions relate to regular grammars, another topic covered in Theory of Computation. Both are ways of describing the same class of languages, known as regular languages, but they express these descriptions differently.
| Aspect | Regular Expression | Regular Grammar |
|---|---|---|
| Notation Style | An algebraic notation built from union, concatenation, and repetition. | A set of production rules similar to those used in context-free grammars, but restricted in form. |
| Typical Usage in Compilers | Directly used to define token patterns for lexical analysis. | Used more often in formal proofs and theoretical discussions than in practical lexical analyzer construction. |
| Readability for Token Definitions | Generally more compact and convenient for describing token patterns. | Can be more verbose for simple patterns but useful for illustrating the connection to grammars. |
In practice, when building a real lexical analyzer, regular expressions are almost always the preferred notation, since tools like Lex are built specifically around regular expression syntax rather than grammar-style production rules.
Writing correct regular expressions for a real programming language involves a few practical considerations that go beyond the basic notation itself.
| Mistake | Correct Understanding |
|---|---|
| Assuming regular expressions can describe any pattern, including nested or balanced structures. | Regular expressions can only describe regular languages and cannot express patterns requiring unbounded nesting, such as balanced parentheses, which require context-free grammars instead. |
| Writing a pattern for identifiers that accidentally also matches reserved keywords without any priority handling. | Keyword and identifier patterns often overlap, so lexical analyzers typically apply priority rules to correctly resolve such conflicts. |
| Believing regular expressions and finite automata are unrelated, separate topics. | Every regular expression can be systematically converted into an equivalent finite automaton, and this conversion is exactly how lexical analyzers are built in practice. |
| Forgetting to account for the longest match rule when designing overlapping patterns. | Even with correct patterns, a lexical analyzer must apply the longest match rule to correctly group characters into the intended tokens. |
Regular expressions provide the precise, mathematical notation that a compiler needs to describe what a valid token looks like, replacing vague human descriptions with unambiguous, checkable rules. Built from a small set of operations, including union, concatenation, and repetition, regular expressions can describe nearly every token pattern found in real programming languages. Because every regular expression corresponds to an equivalent finite automaton, these patterns can be systematically converted into an NFA, simplified into a DFA, minimized for efficiency, and finally implemented as the working core of a lexical analyzer.
In this tutorial, you learned what regular expressions are, the basic notation used to construct them, how they are used to define patterns for common token types, the step-by-step process of converting a regular expression into a usable automaton, how multiple overlapping token patterns are handled together, and how regular expressions compare to regular grammars. With this theoretical foundation in place, you are ready to move on to syntax analysis, where the tokens produced using these patterns are checked against the grammatical rules of the programming language.