Skip to content
Tutorials Center
My learning

Topics

Lesson 7 of 61 ยท Lexical Analysis

Regular Expressions for Lexers

Use regular expressions to describe tokens, learn longest-match and priority rules, and build a complete tokenizer with Python's re module and named groups.

In the previous lesson you wrote a scanner by hand, and every token kind needed its own little loop. That works for a small language, but it is repetitive: the same idea ("read characters while they fit a shape") appears again and again. Compiler writers noticed long ago that the shapes of tokens can be described with a very small, precise notation, the regular expression, and that a tool can turn that notation into a working scanner.

This lesson shows how to write token patterns as regular expressions, how a lexer chooses between competing patterns, and how to build a complete tokenizer with Python's re module in about twenty lines. Along the way you will meet a Python-specific trap that catches nearly every beginner.

The three core operations

Theory first, because it is short. A regular expression is built from just three operations over an alphabet of characters:

Operation Notation Meaning
Concatenation ab an a followed by a b
Alternation a|b an a or a b
Repetition (Kleene star) a* zero or more as

Every other operator is shorthand for combinations of these three:

Shorthand Equivalent Meaning
a+ aa* one or more
a? (a|) zero or one (optional)
[abc] a|b|c one character from a set
[a-z] a|b|...|z one character from a range
[^"] any character except " negated set
. any one character (except newline) wildcard
\d [0-9] a digit
\w [A-Za-z0-9_] a word character
\s space, tab, newline... whitespace

The set of strings a regular expression describes is called a regular language. These are exactly the languages that a finite automaton can recognize, which is why lexers can run so fast: you will see the machine in Finite Automata and how to build it from a regex in From Regex to NFA to DFA.

In Python source code, write patterns as raw strings (r"\d+"). Without the r, Python treats \d and \n as escape sequences before the regex engine ever sees them. Also note that in Python 3, \d and \w match Unicode digits and letters by default. In a lexer for an ASCII language, write [0-9] and [A-Za-z0-9_], or compile with re.ASCII.

Patterns for Tiny's tokens

Here is each token kind of Tiny, written as a regular expression:

TEXT
identifier   [A-Za-z_][A-Za-z0-9_]*
integer      [0-9]+
string       "[^"\n]*"
comment      //[^\n]*
whitespace   [ \t\r\n]+
operator     <=|>=|==|!=|[-+*/%<>=]
punctuation  [(){};,]

Read the identifier pattern aloud: "one letter or underscore, then any number of letters, digits or underscores". The string pattern says: a quote, then any characters except a quote or a newline, then a quote. That is why "open (no closing quote) does not match. Try your own patterns in the table below, which tests several inputs against several patterns.

Python Which pattern accepts which text?

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Each sample is accepted by exactly one pattern, or by none. 3. and .5 are rejected by decimal because that pattern demands digits on both sides of the dot. Whether your language allows them is a design decision; to allow .5 you could write [0-9]*\.[0-9]+. Notice also that 007 matches integer: whether leading zeros are allowed is again a language rule.

Choosing between patterns

A lexer has many patterns and must pick one at each position in the source. The rules are:

  1. Longest match. Among all patterns that match at this position, choose the one that consumes the most characters. This makes <= beat < and iffy beat if.
  2. Priority. If two patterns match the same length, choose the one listed first. This makes the keyword if win over the identifier pattern for the text if, because both match two characters.

This is the rule set used by Lex and Flex, and by the hand-written scanner from the last lesson. Now the trap: Python's regular expression alternation does not use rule 1. The | operator tries the alternatives left to right and takes the first one that works, even if a later one would match more.

Python First alternative versus longest match

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The first part is the trap. <|<= matches only <, because it is tried first and succeeds. If you list multi-character operators before their prefixes, as in <=|<, you get the longest match. The same trick applies everywhere: put == before =, >= before >, and so on.

The second part implements the formal rule by brute force: try every pattern and keep the longest result. iffy is an IDENT, because its four characters beat the two of if, while plain if is a tie that listing order settles, so IF wins. The last example, 123abc, becomes NUMBER '123', and abc is left over for the next round, matching what you saw earlier.

In practice, a lexer built on re does not run every pattern separately. It orders the alternatives carefully in one big pattern. Keywords are usually not given patterns at all; as before, the lexer recognizes IDENT and checks a keyword table afterwards.

One master pattern with named groups

Python lets you name a group with (?P<name>...). Joining all token patterns into one master pattern with | gives you a complete scanner: ask the engine for the next match at the current position, and the lastgroup attribute tells you which pattern won.

flowchart LR
    A["Source text"] --> B["Master regex<br/>one named group per token kind"]
    B --> C{"m.lastgroup"}
    C -->|NUMBER| D["Token NUMBER"]
    C -->|IDENT| E["Token IDENT or keyword"]
    C -->|SPACE or COMMENT| F["Skip"]
    C -->|ERROR| G["Report error"]

The master regex picks the winning named group at each position; the lexer acts on its name.

The tokenizer below also tracks line and column numbers. A NEWLINE pattern bumps the line counter and remembers where the line started, so column = offset - line_start + 1. The final catch-all pattern ERROR (. matches any one character) guarantees that scanning never gets stuck: every character is matched by something, and the lexer decides what to do with unknown ones.

Python A tokenizer with named groups

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Check the details in the output. >= appears as a single OP token, thanks to listing it before the single-character class in the OP pattern. and is a KEYWORD, while n is an IDENT. The comment disappears and the second line starts counting from column 1 again. The @ hits the catch-all rule and produces a position in the error message: line 1, column 11.

Notice what we changed compared to the hand-written scanner. The whole lexer is now data (a list of name and pattern pairs) plus a ten-line driver. Adding a token means adding one line to TOKEN_SPEC. The order of that list encodes priority, and that is the one thing you must always think about.

Pitfalls to remember

  • Order matters. Put longer alternatives first (<= before <), and put the ERROR catch-all last.
  • Keywords. If you give each keyword its own pattern, it must come before IDENT, and you also need word boundaries so iffy is not split into if and fy. A keyword table avoids the problem.
  • Greedy repetition. .* eats as much as it can. A comment pattern //.* stops at the newline because . does not match \n, but "[^"]*" is preferred over ".*" for strings, since ".*" on "a" + "b" would swallow everything from the first quote to the last.
  • Performance. Python's engine backtracks, so a badly written pattern such as (a+)+b can take exponential time on some inputs. Token patterns are usually simple enough that this never matters, but be careful if the pattern comes from user input.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Which three operations are enough to build every regular expression?

    Concatenation, alternation and the Kleene star can express everything else, such as + (one or more), ? (optional) and character classes.
  2. 2. In Python, what does re.compile(r"<|<=").match("<= 3") return?

    Python alternation is ordered, not longest-match. Writing <=|< gives the longer match.
  3. 3. Two token patterns both match the text while with the same length. Which wins in a standard lexer?

    Priority goes to the rule listed first. That is why keyword patterns, or the keyword table check, take effect before plain identifiers.
  4. 4. What is the purpose of the final catch-all rule (?P<ERROR>.) in the master pattern?

    Without it, finditer would silently skip characters that no rule matches. With it, each unknown character becomes an ERROR token the lexer can report with a position.
  5. 5. Why is "[^"]*" a better pattern for strings than ".*"?

    .* is greedy and runs to the last quote it can find, so two strings on one line would be merged into one token. The negated set stops at the first closing quote.

Summary

  • Token patterns are regular expressions, built from concatenation, alternation and repetition; other operators are shorthand.
  • A lexer chooses the longest match at each position, and breaks ties by rule order (priority).
  • Python's | is ordered, not longest-match: list longer alternatives first.
  • A master pattern of named groups plus m.lastgroup makes a complete tokenizer, with line and column tracking added through a newline rule.
  • A catch-all ERROR rule keeps the scanner from getting stuck on unknown characters.
  • The scanner becomes data (a table of patterns), so adding a token is a one-line change.

Next: Finite Automata: DFA and NFA