2.2 Regular Languages and Regular Expressions

A regular language is a language that can be recognized by a finite automaton. Equivalently, it can be described by a regular expression in the formal-language sense. This equivalence is the reason lexer generators exist: users write token patterns as regular expressions, and the tool turns those patterns into an automaton that scans characters efficiently.

Regular languages are powerful enough for many local character patterns: identifiers, integers, whitespace, line comments, operators, string delimiters, keywords, and simple escape sequences. They are not powerful enough for arbitrary recursive structure. Matching nested parentheses, checking that every begin has a corresponding end, or proving that an expression is type-correct requires later compiler phases.

Operations on Languages

Languages are sets, so set operations apply to them. Let:

A = {good, bad}
B = {boy, girl}

The union of two languages contains strings from either language:

A ∪ B = {good, bad, boy, girl}

The concatenation of two languages combines every string from the first with every string from the second:

A ∘ B = {goodboy, goodgirl, badboy, badgirl}

The Kleene closure of a language contains all finite concatenations of strings from that language:

These operations are not just mathematical exercises. Regular expressions are built from exactly these ideas: choice, concatenation, and repetition.

Formal Regular Expressions

At the formal core, regular expressions are constructed recursively:

• ∅ denotes the empty language.
• ε denotes the language containing only the empty string.
• A symbol a in Σ denotes the language {a}.
• If r and s are regular expressions, then r | s denotes union.
• If r and s are regular expressions, then rs denotes concatenation.
• If r is a regular expression, then $r^*$ denotes Kleene closure.

Programming tools add convenient abbreviations:

• $r^+$ means one or more repetitions: $rr^*$.
• $r^?$ means optional: r | ε.
• [0-9] means a choice among digit characters.
• [A-Za-z_] means a choice among letters and underscore.
• . often means any character except newline, depending on the engine.

Compiler courses often use formal regex syntax, while production tools use extended syntax. The theory still drives the implementation. Character classes are expanded into choices or represented as compact transition classes. + and ? are lowered into combinations of concatenation, union, and star. The final result can still become an automaton.

Precedence and Ambiguity

Regular expression operators have precedence. In the usual convention, Kleene star binds most tightly, concatenation comes next, and union has the lowest precedence. Therefore:

means:

not:

This matters when writing token specifications. The expression $[0-9]^+$ means one or more digits. The expression $[0-9]^+ "." [0-9]^+$ can describe decimal literals such as 3.14, depending on notation. But an expression like $[0-9] | [0-9][0-9]^*$ may be redundant because the right side already covers the one-digit case.

Good lexer specs avoid cleverness. They name token rules, test boundary cases, and separate lexical rules from parsing rules. For example, a lexer might recognize - as an operator rather than part of a negative integer. The parser or semantic analyzer can decide whether -42 is unary negation applied to 42.

The Boundary of Regular Languages

Regular expressions cannot count without bound. The classic non-regular language is:

The language contains ε, ab, aabb, aaabbb, and so on. To recognize it, a machine must remember how many a symbols appeared so it can require exactly the same number of b symbols. A finite automaton has only finitely many states, so it cannot store an unbounded count.

Balanced parentheses have the same problem. Recognizing ((())) requires remembering nesting depth. Since nesting depth is unbounded in the language definition, finite state is not enough. This is the line between lexical analysis and parsing. Lexers handle regular local patterns; parsers handle recursive structure using context-free grammars and stacks.

There are practical caveats. Real-world regex engines often support backreferences or lookaround features that go beyond regular languages. Those features are useful in text processing, but they are usually avoided in lexer generators because they can break the clean automaton model and predictable linear scanning.

Read Regex as an Algebra, Not Punctuation

The expression $(ab|c)^*d$ means zero or more choices of either the two-character string ab or the one-character string c, followed by d. It accepts d, abd, cd, and abcabd; it does not accept ad. Parentheses change the language, and precedence matters: ab|cd conventionally means (ab)|(cd), while a(b|c)d shares the outer a and d.

Regex syntax in programming tools adds conveniences such as character classes, reluctant quantifiers, captures, and backreferences. Those features are not all regular. Classical lexer regexes deliberately avoid backreferences because a finite automaton cannot generally remember and compare an unbounded captured substring. When designing a scanner, use regular patterns for token shape and leave nesting, declarations, and type-dependent rules to later phases.

Construction Tips

• Name subpatterns by intent: digit, hexDigit, identifierStart, and identifierContinue are easier to audit than one enormous pattern.

• Test shortest, longest-looking, and almost-valid strings, especially around alternation and optional suffixes.

• Decide whether matching is anchored. A lexer matches at its current cursor; a search API may find a match in the middle of text, which is a different operation.