Introduction
Regular-expression lexers are quick to write, but the lexers inside GCC, Clang, Go, Rust and CPython are written by hand. A hand-written lexer is just a loop over characters with a few if branches. It is easy to make fast, it can handle awkward cases that regular expressions make clumsy (such as nested comments or indentation), and its error messages can say exactly what was expected. This lesson builds one.
How it works
The lexer keeps a position in the text and two small helpers:
- peek returns the character at the position, or a few characters ahead, without moving;
- advance moves the position forward.
The main loop looks at the current character and chooses a branch:
- whitespace: skip it;
- a digit: consume digits; then, if the next character is a dot and the one after it is a digit, consume the dot and more digits. That second check is lookahead: it keeps
1.(a number followed by a dot) different from1.5; - a letter or underscore: consume letters, digits and underscores, giving a name;
- an operator: first check whether this character and the next form a two-character operator such as
<=; only if not, take a single character. This is the longest-match rule; - anything else: report an error with its position.
Each branch records the token's kind and its text, the slice from where it started to where it stopped. Because each character is looked at a fixed number of times, the lexer runs in time proportional to the length of the input.
Compared with the regular-expression lexer, the rules are the same; only the way they are written changes. In fact a hand-written lexer is a DFA written as code: each branch is a state, and each loop is a state looping on itself.
Syntax
def peek(self, ahead=0):
i = self.pos + ahead
return self.text[i] if i < len(self.text) else "" # "" at the end
start = self.pos
while self.peek().isdigit():
self.pos += 1
token = self.text[start:self.pos]
Example
class Lexer:
def __init__(self, text):
self.text, self.pos, self.tokens = text, 0, []
def peek(self, ahead=0):
i = self.pos + ahead
return self.text[i] if i < len(self.text) else ""
def run(self):
while self.pos < len(self.text):
c = self.peek()
start = self.pos
if c.isspace():
self.pos += 1
elif c.isdigit():
while self.peek().isdigit():
self.pos += 1
if self.peek() == "." and self.peek(1).isdigit():
self.pos += 1
while self.peek().isdigit():
self.pos += 1
self.tokens.append(("NUMBER", self.text[start:self.pos]))
elif c.isalpha() or c == "_":
while self.peek().isalnum() or self.peek() == "_":
self.pos += 1
self.tokens.append(("NAME", self.text[start:self.pos]))
elif c + self.peek(1) in ("==", "<=", ">=", "!="):
self.pos += 2
self.tokens.append(("OP", c + self.peek(-1)))
elif c in "+-*/=<>()":
self.pos += 1
self.tokens.append(("OP", c))
else:
raise SyntaxError(f"unexpected {c!r} at {self.pos}")
return self.tokens
lexer = Lexer("rate2 = 3.75*(hours>=40) - 1.")
try:
lexer.run()
problem = None
except SyntaxError as error:
problem = error
for kind, value in lexer.tokens:
print(kind, value)
if problem:
print("error:", problem)Line by line
peekreturns the empty string past the end, so the loops stop naturally at the end of the text.- The number branch consumes digits, then takes a dot only if a digit follows it.
- The name branch accepts letters, digits and underscores after the first character, so
rate2is one name. - The operator branch tries two characters first, so
>=is one token. - The last characters
1.show the lookahead: the dot is not followed by a digit, so1is a number and the dot is unexpected. The lexer stops with an error there; the tokens found before it are printed, then the error.
Expected result
NAME rate2
OP =
NUMBER 3.75
OP *
OP (
NAME hours
OP >=
NUMBER 40
OP )
OP -
NUMBER 1
error: unexpected '.' at 28
In the real world
CPython's tokenizer is hand-written C that also tracks indentation, producing INDENT and DEDENT tokens. Clang's lexer is hand-written for speed and for its detailed error messages. Go's scanner inserts semicolons automatically at the ends of lines, something a pure regular-expression lexer would struggle with.
Common mistakes
- Reading past the end of the text: make peek return an empty string there.
- Forgetting the lookahead for decimals, so
1.and1.5are confused. - Checking one-character operators first, which breaks the longest-match rule.
- Forgetting to advance in a branch, which makes the loop run forever.
Best practices
- Give every branch a clear start position and take the token as a slice.
- Keep peek and advance as tiny helpers, so the branches read like the rules.
- Test edge cases: empty input, a token at the very end, and every operator next to another.
Summary
A hand-written lexer scans characters with peek and advance, choosing a branch for each kind of token. Lookahead decides two-character operators and decimal points, giving the longest match. It is a DFA written as code: fast, flexible and able to give precise errors, which is why many production compilers use one.
Quick check
Key takeaways
- A hand-written lexer is a loop with one branch per kind of token.
- Lookahead decides cases such as <= versus <, and 1.5 versus 1 followed by a dot.
- It is fast, flexible and gives precise error messages.
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.