Seventeen characters, five words
A pricing script holds the line total = price * 12. To you it is five words. To the compiler it is seventeen characters, spaces included.
Before anything can check the grammar, something must group those characters into words and throw the spaces away. That part of a compiler is small, fast and easy to get subtly wrong.
By the end of this lesson
Note
I can turn source text into tokens.
Key words
| Word | What it means | Example |
|---|---|---|
| Token | one word of a program, with its kind | NUMBER 12 |
| Lexer | the part of a compiler that makes tokens | |
| Pattern | a rule for what one kind of token looks like | [0-9]+ |
| Longest match | take as many characters as the pattern allows | |
| Keyword | a word the language keeps for itself | if |
| Lexer generator | a tool that writes a lexer from patterns | flex |
The cells students fill in are left blank in this preview.
A token is a kind and some text
The lexer is the first part of the compiler proper. It reads characters from left to right and hands out tokens.
Each token has a kind, such as NUMBER or NAME, and the text it was made from. Spaces and comments make no token. They only mark where one token ends and the next begins.
Worked example: total = price * 12
| Characters | Kind | Text |
|---|---|---|
| t o t a l | NAME | total |
| = | OP | = |
| p r i c e | NAME | price |
| * | OP | * |
| 1 2 | NUMBER | 12 |
| The four spaces | No token | Skipped |
The cells students fill in are left blank in this preview.
A lexer in twenty lines
# A tiny lexer: numbers and the four signs, spaces skipped.
text = "12 + 30*2"
tokens = []
i = 0
while i < len(text):
ch = text[i]
if ch == " ":
i = i + 1
elif ch.isdigit():
start = i
# Keep going while there are digits: the longest match.
while i < len(text) and text[i].isdigit():
i = i + 1
tokens.append(["NUMBER", text[start:i]])
elif ch in "+-*/":
tokens.append(["OP", ch])
i = i + 1
else:
tokens.append(["ERROR", ch])
i = i + 1
print(tokens)
# Change text to "7 % 20" and run again.
flex writes the lexer for you
Writing a lexer by hand for a real language is slow. A lexer generator such as flex writes one from a list of patterns.
In calc.l, each line pairs a pattern with what to do when it matches. [0-9]+ means one or more digits. Its action turns the text into a number and returns the token NUMBER to the parser. The Runs show the rules, then build the calculator again from nothing.
Go into the compiler folder
cd ~/compilerShown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
The rules that return a token
grep -n "return" calc.lShown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
Remove everything make built
make cleanShown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
Build the calculator again
makeShown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
How long is the lexer flex wrote?
wc -l lex.yy.cShown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
Characters the lexer knows and does not
Each Run below pipes one line into the calculator. Watch which messages come from the lexer and which from the parser.
The lexer's last rule, a single dot, matches any character the others did not. It prints unexpected character and makes no token. The parser then sees what is left.
No spaces at all
echo "12+30" | ./calcShown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
Far too many spaces
echo " 7 * 6" | ./calcShown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
A character the lexer does not know
echo "4 # 2" | ./calcShown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
A letter stuck to a number
echo "40 + 2x" | ./calcShown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
Leading zeros
echo "007 + 1" | ./calcShown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
A common mistake
Warning
Many people think a lexer hands out one token per character, so 007 would be three numbers. A lexer takes the longest match: it keeps reading while the pattern still fits. So 007 is one NUMBER, and letter is one NAME, not the keyword let followed by ter.
Going further
Extend your tokenizer to read the two-character operators == and <= as one OP token each, and < and = alone as before.
Write three tests of your own first. Then say why a<=b must not become < and =, using the idea of the longest match.