Introduction
Before a compiler can understand while total <= 100, it must see that this line contains a keyword, a name, an operator and a number, and not just 23 characters. That job belongs to the lexer (or scanner). It is the simplest phase of a compiler, yet it makes every later phase easier: the parser never thinks about spaces, digits or comments again.
Many lexers are not written by hand at all. Tools such as lex, flex and the lexer generators in ANTLR take a list of regular expressions and build the lexer automatically. This lesson shows the same idea with Python's re module.
How it works
A token is a pair: its kind (NUMBER, NAME, OP…) and its lexeme, the characters themselves. Lexers usually record the position too, so that errors can point to the right place.
A lexer is a list of rules, each a token kind with a regular expression:
- numbers:
\d+(\.\d+)?; - names: a letter or underscore, then letters, digits or underscores;
- operators, with the two-character ones (
==,<=) listed before the one-character ones; - whitespace and comments, which are matched and then thrown away;
- a final catch-all rule for any other character, which is an error.
Joining the rules with |, each inside a named group such as (?P<NUMBER>…), gives one master pattern. re.finditer then walks through the text, and m.lastgroup names the rule that matched.
Order matters. Python's regular expressions try alternatives from left to right, so earlier rules win. That is why <= must come before <: otherwise <= would be read as < followed by =. Real lexers follow the longest match rule, and listing longer operators first achieves it here.
Keywords such as while match the NAME rule too. The usual approach is to lex them as names and then look them up in a set of keywords. That is simpler than writing one rule per keyword, and it makes whilex a name, not a keyword followed by x.
Syntax
SPEC = [("NUMBER", r"\d+(\.\d+)?"), ("NAME", r"[A-Za-z_]\w*"), ...]
MASTER = re.compile("|".join(f"(?P<{name}>{pattern})" for name, pattern in SPEC))
for m in MASTER.finditer(line):
kind, value = m.lastgroup, m.group()
Example
import re
KEYWORDS = {"if", "else", "while", "print"}
SPEC = [
("NUMBER", r"\d+(\.\d+)?"),
("NAME", r"[A-Za-z_]\w*"),
("OP", r"==|!=|<=|>=|[-+*/=<>()]"),
("COMMENT", r"#.*"),
("SKIP", r"[ \t]+"),
("MISMATCH", r"."),
]
MASTER = re.compile("|".join(f"(?P<{name}>{pattern})" for name, pattern in SPEC))
def tokenize(line):
for m in MASTER.finditer(line):
kind, value = m.lastgroup, m.group()
if kind in ("SKIP", "COMMENT"):
continue
if kind == "NAME" and value in KEYWORDS:
kind = "KEYWORD"
if kind == "MISMATCH":
raise SyntaxError(f"unexpected {value!r} at column {m.start() + 1}")
yield kind, value, m.start() + 1
try:
for kind, value, column in tokenize("while total <= 100: total = total * 1.5 # grow"):
print(f"{column:3} {kind:8} {value}")
except SyntaxError as error:
print("error:", error)Line by line
SPEClists the rules in priority order; COMMENT and SKIP are matched only to be thrown away.MASTERjoins them into one pattern with named groups.tokenizewalks through the line;m.lastgroupis the name of the rule that matched.- A NAME that is in
KEYWORDSbecomes a KEYWORD, sowhileis a keyword buttotalis a name. - Each token is printed with its column.
<=is one token because it is listed before<. The:is not in this small language, so the lexer stops there and the error, with its column, is printed last.
Expected result
1 KEYWORD while
7 NAME total
13 OP <=
16 NUMBER 100
error: unexpected ':' at column 19
In the real world
Python's own tokenize module turns source code into tokens, and tools such as Black and syntax highlighters use it. Lexer generators (flex, ANTLR, re2c) compile rule lists like this one into fast DFAs. Editors highlight code with similar rule lists, which is why highlighting sometimes goes wrong on unusual code: the lexer's rules are only an approximation of the language.
Common mistakes
- Putting short operators first, so
<=becomes<and=. - Matching keywords with their own rules after NAME, so they are never reached.
- Forgetting a catch-all rule, so unknown characters are silently skipped.
- Losing positions, which makes error messages useless.
Best practices
- Keep the rules in a list, in priority order, with a comment for anything subtle.
- Lex keywords as names, then look them up in a set.
- Record the line and column of every token.
Summary
A lexer turns characters into tokens, each with a kind, a lexeme and a position. A list of regular expressions joined into one master pattern with named groups makes a compact lexer, as long as longer rules come first. Keywords are names found in a keyword set, and an unexpected character is reported with its position.
Quick check
Key takeaways
- A lexer is a list of token rules; order sets priority when two rules match the same text.
- Named groups and m.lastgroup tell you which rule matched.
- Keywords are usually lexed as names, then recognised by looking them up.
Practice problems for this lesson
My notes
Write down what you want to remember from this lesson. Notes are saved on this device as you type, and appear on your dashboard.