Turning Text Into Instructions
Before It Can Read Your Program It Has to Decide Where the Words End
Source code is one long run of characters. Something has to cut it into pieces, and the cutting rules decide what your program means before anything has parsed it.
What a token is
A source file is a run of characters. Your editor shows it with colours and
indentation, which makes it look structured, but the bytes on disk are one
sequence with no more shape than a shopping list written without spaces.
The first thing a compiler does is cut that sequence into pieces. Each piece is
a token, and a token is three things: a category, the exact characters, and the
position in the file where they started.
source text:
total = count * 2 + 1;
tokens produced:
identifier total line 7 column 5
operator = line 7 column 11
identifier count line 7 column 13
operator * line 7 column 19
number 2 line 7 column 21
operator + line 7 column 23
number 1 line 7 column 25
semicolon ; line 7 column 26
note: the spaces are gone, and nothing above says
which operation happens firstThree observations about that list. The categories are few, perhaps forty in a
large language, and fixed before anybody wrote a line of your program. The
text is kept, because later stages need the actual name and the actual digits.
And the position is kept, which is what makes every downstream error message
able to point at a line.
Taking the longest bite
Now the only rule that matters. Reading left to right, keep consuming
characters while what you have so far could still be the start of a valid
token, and cut when it could not. In other words, take the longest match.
It sounds trivial until it is applied to operators, which in most languages
come in families where the short ones are prefixes of the long ones.
| characters consumed | forms a valid operator | what the splitter choose | |
|---|---|---|---|
| stop after one character | 1 | 1 | 0 |
| stop after two character | 2 | 1 | 0 |
| stop after three charact | 3 | 1 | 1 |
Two consequences follow immediately, and both are things programmers encounter
without knowing why.
The first is that whitespace sometimes matters and sometimes does not. Between
two identifiers it is required, because without it the longest match swallows
both into one name. Between an identifier and a bracket it is optional, because
a bracket cannot extend a name. People develop an intuition for this and the
intuition is just the longest-match rule felt from the outside.
The second is the classic nested-template problem. In languages where angle
brackets close a type, two of them in a row at the end of a nested type are
consumed as a shift operator, and the program is rejected for a reason that
appears to have nothing to do with what you wrote. Several languages have
special-cased this, which is a language designer paying a permanent complexity
cost to hide one consequence of the rule.
| step | position | character seen | state of the current piece | token emitted | what happened |
|---|---|---|---|---|---|
| 1 | 1 | t | building an identifier | none yet | A letter can start a name, so the splitter begins collecting and will keep going while letters and digits arrive. |
| 2 | 6 | space | the name ended | identifier total | A space cannot extend a name, so the longest match is over. The token is emitted and the space is consumed and discarded. |
| 3 | 7 | equals | building an operator | none yet | An equals sign could be the whole operator or the start of a longer one, so the splitter looks at the next character before deciding. |
| 4 | 8 | space | the operator ended at one character | operator equals | The next character cannot extend it, so the short form wins by default. Nothing here required backtracking: one pass, one character of lookahead. |
The cases that need a decision
The rule handles ordinary text. Four situations need a decision made in advance
by whoever designed the language.
Comments and whitespace are recognised like any other token and then thrown
away rather than emitted. That throwing away is why a comment can go almost
anywhere, and why the tools that need comments, such as documentation
generators and formatters, have to run their own splitter that keeps them.
Strings suspend the normal rules entirely. Inside quotes, a space is not a
separator and a semicolon is not punctuation. The splitter enters a different
mode at the opening quote and leaves it at the closing one, which is also why
an unterminated string produces such strange errors: everything after it is
being read in the wrong mode until the next quote, possibly pages later.
Numbers run into the question of where a dot belongs. In a language with both
decimals and member access, a dot after digits is ambiguous, and the answer is
a rule written down once and then half remembered by everyone who uses the
language.
Keywords are the one that surprises people. There is no keyword category in the
splitter. A keyword is an identifier that matched a fixed list after it was
collected, which is why keywords follow identifier rules exactly, and why
adding a keyword to a language breaks every existing program that used that
word as a name.
What it hands to the next stage
The flatness is worth holding on to. This stage cannot tell you that a bracket
is unmatched, because it has no idea that brackets come in pairs. It cannot
tell you a name is undefined, because it has no idea what names exist. It can
only tell you that some run of characters is not a valid piece of anything, and
that is the entire category of error it produces.
That is also why its errors are the most useful ones in the compiler. They
point at exactly one position, they are never cascading, and they are almost
always a typo. Every later stage produces errors with a degree of guesswork in
them, because every later stage is trying to reconstruct an intent.
The next lesson takes this flat list and builds a tree from it, and the
interesting part is that precedence, the thing everyone memorises as a table,
turns out to be a property of how the tree is built rather than a separate rule
applied afterwards.
Recap
- The first stage turns a run of characters into a flat list of tokens, each one a category, the exact text, and a position in the file.
- Where a token ends is decided by taking the longest run of characters that forms a valid token, which is why adding one character to an operator can change the meaning of the line.
- Whitespace and comments are consumed and thrown away, keywords are identifiers that matched a fixed list, and every error message you have seen points at a position this stage recorded.
This is the reading half
Starting the course gives you your own copy of it. Every idea on every page has problems standing under it, marked with a reason rather than a tick, and any sentence you do not believe can be opened and argued with. None of that can happen on a page nobody owns.
The contents