The Software · Chapter 6.b
How does text become tokens?

Watch the opener · 1:19

Transcript

How does text become tokens? Every program starts as one flat row of characters, spaces and all.

I figured you'd just cut it at the spaces. But total equals twelve plus three can be written with no spaces at all, and it means the same.

So read it one character at a time, and group. A letter starts a name, so keep reading letters until they stop: total. An equals sign is one token on its own. A digit starts a number, so keep reading digits. Twelve is one number, not two. Then plus, then three. Five tokens, each with a kind: name, equals, number, plus, number. And a stray character that starts no token is refused, not guessed.

So text becomes tokens by grouping, not by spaces! The lexer cuts flat text into tokens, the pieces a parser reads.

Type a line into the lexer below, spaces or none, and watch the tokens come out whole.

Chapter 6’s assembler already did a first version of this job: it cut each line of assembly into a label, a mnemonic, and an operand. This chapter takes that cutting seriously as a stage of its own, because richer languages need more than a line-by-line split. The languages of the next chapters are described as trees, but a program does not arrive as a tree. It arrives as a line of flat text, a row of characters. Before anything can be parsed into a tree, that text has to be cut into the pieces a parser reads: the name total, an equals sign, the number 12, a plus, the number 3. That cutting is the job of the lexer, the very first stage of every compiler and interpreter.

6.b.1 Cutting text into tokens

The lexer scans the text left to right and groups it. Its one real subtlety is that grouping: 12 is a single number, not two separate tokens, and total is one name, not five letters. So when the lexer meets a digit it keeps reading digits as far as they go, and likewise for letters. Figure 6.b.2 shows a line cut up.

Example 6.b-1. Tokenizing a line of source

def tokenize(source: str) -> list:
    """Cut a line of source into tokens, grouping digit runs into numbers and
    letter runs into names. Raise on a character that begins no token."""
    tokens = []
    index = 0
    while index < len(source):
        char = source[index]
        if char.isspace():
            index += 1
        elif char.isdigit():
            start = index
            while index < len(source) and source[index].isdigit():
                index += 1
            tokens.append(Token("NUMBER", source[start:index]))1
        elif char.isalpha():
            start = index
            while index < len(source) and source[index].isalpha():
                index += 1
            tokens.append(Token("NAME", source[start:index]))2
        elif char in _SYMBOLS:
            tokens.append(Token(_SYMBOLS[char], char))
            index += 1
        else:
            raise ValueError(f"unexpected character {char!r}")3
    return tokens

• a run of digits is gathered into one number token
• a run of letters is gathered into one name token
• a character that begins no token is rejected at once

6.b.2 The front end

The lexer is the first of a short pipeline. It turns text into tokens; the parser of the next chapter turns tokens into a tree; the tree is then run or compiled. Each stage hands the next a tidier form of the program, as Figure 6.b.3 lays out.

The next two languages reuse this scanning idea with their own small lexers. Those return plain strings rather than this chapter’s Token(kind, value) pairs, and let digits follow the first letter of a name. Their parsers recognize the kind from the string. The representation changes; grouping characters before building a tree remains the same stage.

The interactive version needs the in-browser runtime.

6.b.3 The lexer, run

Running ftb.lexer tokenizes a couple of lines and then meets a character it cannot place.

'total = 12 + 3'
  NAME    total
  EQUALS  =
  NUMBER  12
  PLUS    +
  NUMBER  3

'y = (x + 40)'
  NAME    y
  EQUALS  =
  LPAREN  (
  NAME    x
  PLUS    +
  NUMBER  40
  RPAREN  )

a stray character is rejected:
  unexpected character '?'

Names and numbers come out whole however the spacing falls, and a stray character is refused rather than guessed at. With the text cut into tokens, the next chapter can build a tree of meaning from these pieces, and run it.

Exercises

• Add a token for times (the star) and tokenize an expression that uses it.
• Teach the lexer a two-character operator, such as ==. What has to change in the scan?