Scanning

Take big bites. Anything worth doing is worth overdoing.

Robert A. Heinlein, Time Enough for Love

The first step in any compiler or interpreter is scanning. The scanner takes in raw source code as a series of characters and groups it into a series of chunks we call tokens. These are the meaningful “words” and “punctuation” that make up the language’s grammar.

Scanning is a good starting point for us too because the code isn’t very hard—pretty much a match statement with delusions of grandeur. It will help us warm up before we tackle some of the more interesting material later. By the end of this chapter, we’ll have a full-featured, fast scanner that can take any string of Lox source code and produce the tokens that we’ll feed into the parser in the next chapter.

4 . 1The Interpreter Framework

Since this is our first real chapter, before we get to actually scanning some code we need to sketch out the basic shape of our interpreter, pylox. Everything starts with a module in Python.

# lox/__main__.py
import sys
from pathlib import Path

def main():
    if len(sys.argv) > 2:
        print("Usage: pylox [script]")
        exit(64)
    elif len(sys.argv) == 2:
        path = Path(sys.argv[1])
        run_file(path)
    else:
        run_prompt()

if __name__ == "__main__":
    main()

We call this module __main__ so that Python can run it as a script. If pylox is properly installed as a package, then the user can run it from the command line either with the command pylox or with python -m lox.

Stick that in a text file, and go get your IDE or Makefile or whatever set up. I’ll be right here when you’re ready. Good? OK!

Lox is a scripting language, which means it executes directly from source. Our interpreter supports two ways of running code. If you start pylox from the command line and give it a path to a file, it reads the file and executes it.

# lox/__main__.py at top-level
def run_file(path: Path):
    src = path.read_text(encoding=sys.getdefaultencoding())
    lox = Lox()
    lox.run(src)

If you want a more intimate conversation with your interpreter, you can also run it interactively. Fire up pylox without any arguments, and it drops you into a prompt where you can enter and execute code one line at a time.

# lox/__main__.py at top-level
def run_prompt():
    lox = Lox()

    while True:
        try:
            line = input("> ")
        except EOFError:
            break
        else:
            lox.run(line)

The input() function reads a line of input from the user on the command line and returns the result. To kill an interactive command-line app, you usually type Control-D. Doing so signals an “end-of-file” condition to the program. When that happens input() raises an EOFError exception, so we check for that to exit the loop.

Both the prompt and the file runner are thin wrappers around this core method:

# lox/__main__.py at top-level
class Lox:
    def run(self, source: str):
        tokens = tokenize(source)

        # For now, just print the tokens.
        for token in tokens:
            print(token)

It’s not super useful yet since we haven’t written the interpreter, but baby steps, you know? Right now, it prints out the tokens our forthcoming scanner will emit so that we can see if we’re making progress.

4 . 1 . 1Error handling

While we’re setting things up, another key piece of infrastructure is error handling. Textbooks sometimes gloss over this because it’s more a practical matter than a formal computer science-y problem. But if you care about making a language that’s actually usable, then handling errors gracefully is vital.

The tools our language provides for dealing with errors make up a large portion of its user interface. When the user’s code is working, they aren’t thinking about our language at all—their headspace is all about their program. It’s usually only when things go wrong that they notice our implementation.

When that happens, it’s up to us to give the user all the information they need to understand what went wrong and guide them gently back to where they are trying to go. Doing that well means thinking about error handling all through the implementation of our interpreter, starting now.

# lox/errors.py after the Lox class
class LoxSyntaxError(Exception):
    def __init__(self, line: int, message: str,
                 where: str | None = None):
        super().__init__(line, message, where)
        self.line = line
        self.message = message
        self.where = where

    def __str__(self):
        if self.where is None:
            where = ""
        else:
            where = " " + self.where
        return f"[line {self.line}] Error{where}: {self.message}"

This LoxSyntaxError exception and its __str__() renders it in a friendly manner. That is really the bare minimum to be able to claim you even have error reporting. Imagine if you accidentally left a dangling comma in some function call and the interpreter printed out:

Error: Unexpected "," somewhere in your code. Good luck finding it!

That’s not very helpful. We need to at least point them to the right line. Even better would be the beginning and end column so they know where in the line. Even better than that is to show the user the offending line, like:

Error: Unexpected "," in argument list.

    15 | function(first, second,);
                               ^-- Here.

I’d love to implement something like that in this book but the honest truth is that it’s a lot of grungy string manipulation code. Very useful for users, but not super fun to read in a book and not very technically interesting. So we’ll stick with just a line number. In your own interpreters, please do as I say and not as I do.

Notice our LoxSyntaxError class receives the parameters necessary to construct the error message instead of a fully formed string with said message and its __str__ method constructs the string message on the fly. This is to remind you that it’s good engineering practice to separate the code that generates the errors from the code that reports them.

Various phases of the front end will detect errors, but it’s not really their job to know how to present that to a user. In a full-featured language implementation, you will likely have multiple ways errors get displayed: on stderr, in an IDE’s error window, logged to a file, etc. You don’t want that code smeared all over your scanner and parser.

Ideally, we would have an actual abstraction, some kind of “ErrorReporter” interface that gets passed to the scanner and parser so that we can swap out different reporting strategies. For our simple interpreter here, I didn’t do that, but I did at least move the code for error reporting into a different class.

With some rudimentary error handling in place, our application shell is ready. Once we have a Scanner class with a scan_tokens() method, we can start running it. Before we get to that, let’s get more precise about what tokens are.

4 . 2Lexemes and Tokens

Here’s a line of Lox code:

var language = "lox";

Here, var is the keyword for declaring a variable. That three-character sequence “v-a-r” means something. But if we yank three letters out of the middle of language, like “g-u-a”, those don’t mean anything on their own.

That’s what lexical analysis is about. Our job is to scan through the list of characters and group them together into the smallest sequences that still represent something. Each of these blobs of characters is called a lexeme. In that example line of code, the lexemes are:

The lexemes are only the raw substrings of the source code. However, in the process of grouping character sequences into lexemes, we also stumble upon some other useful information. When we take the lexeme and bundle it together with that other data, the result is a token. It includes useful stuff like:

4 . 2 . 1Token type

Keywords are part of the shape of the language’s grammar, so the parser often has code like, “If the next token is while then do . . . ” That means the parser wants to know not just that it has a lexeme for some identifier, but that it has a reserved word, and which keyword it is.

The parser could categorize tokens from the raw lexeme by comparing the strings, but that’s slow and kind of ugly. Instead, at the point that we recognize a lexeme, we also remember which kind of lexeme it represents. We have a different type for each keyword, operator, bit of punctuation, and literal type.

# lox/tokens.py
from typing import Literal, Any

type TokenType = Literal[
    # Single-character tokens.
    "LEFT_PAREN", "RIGHT_PAREN", "LEFT_BRACE", "RIGHT_BRACE",
    "COMMA", "DOT", "SEMICOLON",
    "MINUS", "PLUS", "SLASH", "STAR",

    # One or two character tokens.
    "BANG", "BANG_EQUAL", "EQUAL", "EQUAL_EQUAL",
    "GREATER", "GREATER_EQUAL", "LESS", "LESS_EQUAL",

    # Literals.
    "IDENTIFIER", "STRING", "NUMBER",

    # Keywords.
    "AND", "CLASS", "ELSE", "FALSE", "FUN", "FOR", "IF",
    "NIL", "OR", "PRINT", "RETURN", "SUPER", "THIS", "TRUE",
    "VAR", "WHILE",

    # Special tokens.
    "EOF", "INVALID",
    "UNTERMINATED_STRING",
]

We use strings token types here for simplicity, but we declare the allowed strings values explicitly using Literal so the Language Server can catch (some) typos in our code.

We will also gather many utility types in the lox/types.py module. While we’re at it, let’s define a Literal type to represent any Lox value that may be present literally in the source code.

# lox/tokens.py

type LiteralValue = None | str | float | bool

4 . 2 . 2Literal value

There are lexemes for literal values—numbers and strings and the like. Since the scanner has to walk each character in the literal to correctly identify it, it can also convert that textual representation of a value to the living runtime object that will be used by the interpreter later.

4 . 2 . 3Location information

Back when I was preaching the gospel about error handling, we saw that we need to tell users where errors occurred. Tracking that starts here. In our simple interpreter, we note only which line the token appears on, but more sophisticated implementations include the column and length too.

We take all of this data and wrap it in a class.

# lox/tokens.py after the TokenType class
from dataclasses import dataclass

@dataclass
class Token:
    type: TokenType
    lexeme: str
    line: int
    literal: LiteralValue = None

    def __str__(self):
        return f"{self.type} {self.lexeme!r} {self.literal}"

Now we have an object with enough structure to be useful for all of the later phases of the interpreter.

4 . 3Regular Languages and Expressions

Now that we know what we’re trying to produce, let’s, well, produce it. The core of the scanner is a loop. Starting at the first character of the source code, the scanner figures out what lexeme the character belongs to, and consumes it and any following characters that are part of that lexeme. When it reaches the end of that lexeme, it emits a token.

Then it loops back and does it again, starting from the very next character in the source code. It keeps doing that, eating characters and occasionally, uh, excreting tokens, until it reaches the end of the input.

The part of the loop where we look at a handful of characters to figure out which kind of lexeme it “matches” may sound familiar. If you know regular expressions, you might consider defining a regex for each kind of lexeme and using those to match characters. For example, Lox has the same rules as C for identifiers (variable names and the like). This regex matches one:

[a-zA-Z_][a-zA-Z_0-9]*

If you did think of regular expressions, your intuition is a deep one. The rules that determine how a particular language groups characters into lexemes are called its lexical grammar. In Lox, as in most programming languages, the rules of that grammar are simple enough for the language to be classified a regular language. That’s the same “regular” as in regular expressions.

You very precisely can recognize all of the different lexemes for Lox using regexes if you want to, and there’s a pile of interesting theory underlying why that is and what it means. Tools like Lex or Flex are designed expressly to let you do this—throw a handful of regexes at them, and they give you a complete scanner back.

Since our goal is to understand how a scanner does what it does, we won’t be delegating that task. We’re about handcrafted goods.

4 . 4The Scanner Class

Without further ado, let’s make ourselves a scanner.

# lox/scanner.py
from dataclasses import dataclass, field
from typing import Any
from lox.tokens import Token

@dataclass
class Scanner:
    source: str
    tokens: list[Token] = field(default_factory=list)

def tokenize(source: str) -> list[Token]:
    scanner = Scanner(source)
    return scanner.scan_tokens()

The tokenize function is the main entry point to the scanner module. It initializes a scanner, reads the tokens and thow away any intermediary state. That way we do not need to reset the scanner state manually in the Lox class every time we analyze a new piece of code.

We store the raw source code as a simple string, and we have a list ready to fill with tokens we’re going to generate. The aforementioned loop that does that looks like this:

# lox/scanner.py Scanner method
def scan_tokens(self) -> list[Token]:
    while not self.is_at_end():
        # We are at the beginning of the next lexeme.
        self.start = self.current
        self.scan_token()
    self.tokens.append(Token("EOF", "", self.line))
    return self.tokens

The scanner works its way through the source code, adding tokens until it runs out of characters. Then it appends one final “end of file” token. That isn’t strictly needed, but it makes our parser a little cleaner.

This loop depends on a couple of fields to keep track of where the scanner is in the source code.

# lox/scanner.py Scanner attributes
    start: int = 0
    current: int = 0
    line: int = 1

The start and current fields are offsets that index into the string. The start field points to the first character in the lexeme being scanned, and current points at the character currently being considered. The line field tracks what source line current is on so we can produce tokens that know their location.

Then we have one little helper function that tells us if we’ve consumed all the characters.

# lox/scanner.py Scanner method
def is_at_end(self) -> bool:
    return self.current >= len(self.source)

4 . 5Recognizing Lexemes

In each turn of the loop, we scan a single token. This is the real heart of the scanner. We’ll start simple. Imagine if every lexeme were only a single character long. All you would need to do is consume the next character and pick a token type for it. Several lexemes are only a single character in Lox, so let’s start with those.

# lox/scanner.py Scanner method
def scan_token(self):
    match self.advance():
        case "(":
            self.add_token("LEFT_PAREN")
        case ")":
            self.add_token("RIGHT_PAREN")
        case "{":
            self.add_token("LEFT_BRACE")
        case "}":
            self.add_token("RIGHT_BRACE")
        case ",":
            self.add_token("COMMA")
        case ".":
            self.add_token("DOT")
        case "-":
            self.add_token("MINUS")
        case "+":
            self.add_token("PLUS")
        case ";":
            self.add_token("SEMICOLON")
        case "*":
            self.add_token("STAR")

Again, we need a couple of helper methods.

# lox/scanner.py Scanner methods
def advance(self) -> str:
    char = self.source[self.current]
    self.current += 1
    return char

def add_token(self, type: TT, literal: Any = None):
    text = self.source[self.start:self.current]
    self.tokens.append(Token(type, text, self.line, literal))

The advance() method consumes the next character in the source file and returns it. Where advance() is for input, add_token() is for output. It grabs the text of the current lexeme and creates a new token for it. We’ll use the other overload to handle tokens with literal values soon.

4 . 5 . 1Lexical errors

Before we get too far in, let’s take a moment to think about errors at the lexical level. What happens if a user throws a source file containing some characters Lox doesn’t use, like @#^, at our interpreter? Right now, those characters get silently discarded. They aren’t used by the Lox language, but that doesn’t mean the interpreter can pretend they aren’t there. Instead, we collect them as an error token.

# lox/scanner.py at Scanner.scan_token()'s match/case
    ...
    case _:
        self.add_token("INVALID")

Note that the erroneous character is still consumed by the earlier call to advance(). That’s important so that we don’t get stuck in an infinite loop.

Note also that we keep scanning. There may be other errors later in the program. It gives our users a better experience if we detect as many of those as possible in one go. Otherwise, they see one tiny error and fix it, only to have the next error appear, and so on. Syntax error Whac-A-Mole is no fun.

4 . 5 . 2Operators

We have single-character lexemes working, but that doesn’t cover all of Lox’s operators. What about !? It’s a single character, right? Sometimes, yes, but if the very next character is an equals sign, then we should instead create a != lexeme. Note that the ! and = are not two independent operators. You can’t write ! = in Lox and have it behave like an inequality operator. That’s why we need to scan != as a single lexeme. Likewise, <, >, and = can all be followed by = to create the other equality and comparison operators.

For all of these, we need to look at the second character.

# lox/scanner.py at Scanner.scan_token()'s match/case
    ...
    case "!" if self.match("="):
        self.add_token("BANG_EQUAL")
    case "!":
        self.add_token("BANG")
    case "=" if self.match("="):
        self.add_token("EQUAL_EQUAL")
    case "=":
        self.add_token("EQUAL")
    case "<" if self.match("="):
        self.add_token("LESS_EQUAL")
    case "<":
        self.add_token("LESS")
    case ">" if self.match("="):
        self.add_token("GREATER_EQUAL")
    case ">":
        self.add_token("GREATER")
    ...

Those cases use this new method:

# lox/scanner.py Scanner method
def match(self, expected: str) -> bool:
    if self.is_at_end() or self.source[self.current] != expected:
        return False
    self.current += 1
    return True

It’s like a conditional advance(). We only consume the current character if it’s what we’re looking for.

Using match(), we recognize these lexemes in two stages. When we reach, for example, !, we jump to its switch case. That means we know the lexeme starts with !. Then we look at the next character to determine if we’re on a != or merely a !.

4 . 6Longer Lexemes

We’re still missing one operator: / for division. That character needs a little special handling because comments begin with a slash too.

# lox/scanner.py at Scanner.scan_token()'s match/case
    ...
    case "/" if self.match("/"):
        # A comment goes until the end of the line.
        while self.peek() != '\n' and not self.is_at_end():
            self.advance()
    case "/":
        self.add_token("SLASH")
    ...

This is similar to the other two-character operators, except that when we find a second /, we don’t end the token yet. Instead, we keep consuming characters until we reach the end of the line.

This is our general strategy for handling longer lexemes. After we detect the beginning of one, we shunt over to some lexeme-specific code that keeps eating characters until it sees the end.

We’ve got another helper:

# lox/scanner.py Scanner method
def peek(self) -> str:
    if self.is_at_end():
        return ""
    return self.source[self.current]

It’s sort of like advance(), but doesn’t consume the character. This is called lookahead. Since it only looks at the current unconsumed character, we have one character of lookahead. The smaller this number is, generally, the faster the scanner runs. The rules of the lexical grammar dictate how much lookahead we need. Fortunately, most languages in wide use peek only one or two characters ahead.

Comments are lexemes, but they aren’t meaningful, and the parser doesn’t want to deal with them. So when we reach the end of the comment, we don’t call addToken(). When we loop back around to start the next lexeme, start gets reset and the comment’s lexeme disappears in a puff of smoke.

While we’re at it, now’s a good time to skip over those other meaningless characters: newlines and whitespace.

# lox/scanner.py at Scanner.scan_token()'s match/case
    ...
    case " " | "\r" | "\t":
        pass # Ignore whitespace.
    case "\n":
        self.line += 1
    ...

When encountering whitespace, we simply go back to the beginning of the scan loop. That starts a new lexeme after the whitespace character. For newlines, we do the same thing, but we also increment the line counter. (This is why we used peek() to find the newline ending a comment instead of match(). We want that newline to get us here so we can update line.)

Our scanner is getting smarter. It can handle fairly free-form code like:

// this is a comment
(( )){} // grouping stuff
!*+-/=<> <= == // operators

4 . 6 . 1String literals

Now that we’re comfortable with longer lexemes, we’re ready to tackle literals. We’ll do strings first, since they always begin with a specific character, ".

# lox/scanner.py at Scanner.scan_token()'s match/case
    ...
    case '"':
        self.string()
    ...

That calls:

# lox/scanner.py Scanner method
def string(self):
    while self.peek() != '"' and not self.is_at_end():
        if self.peek() == '\n':
            self.line += 1
        self.advance()

    if self.is_at_end():
        self.add_token("UNTERMINATED_STRING")
        return

    # The closing ".
    self.advance()

    # Trim the surrounding quotes.
    value = self.source[self.start + 1 : self.current - 1]
    self.add_token("STRING", value)

Like with comments, we consume characters until we hit the " that ends the string. We also gracefully handle running out of input before the string is closed and report an error for that.

For no particular reason, Lox supports multi-line strings. There are pros and cons to that, but prohibiting them was a little more complex than allowing them, so I left them in. That does mean we also need to update line when we hit a newline inside a string.

Finally, the last interesting bit is that when we create the token, we also produce the actual string value that will be used later by the interpreter. Here, that conversion only requires a substring() to strip off the surrounding quotes. If Lox supported escape sequences like \n, we’d unescape those here.

4 . 6 . 2Number literals

All numbers in Lox are floating point at runtime, but both integer and decimal literals are supported. A number literal is a series of digits optionally followed by a . and one or more trailing digits.

1234
12.34

We don’t allow a leading or trailing decimal point, so these are both invalid:

.1234
1234.

We could easily support the former, but I left it out to keep things simple. The latter gets weird if we ever want to allow methods on numbers like 123.sqrt().

To recognize the beginning of a number lexeme, we look for any digit.

# lox/scanner.py at Scanner.scan_token()'s match/case
    ...
    case "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9":
        self.number()
    ...

Once we know we are in a number, we branch to a separate method to consume the rest of the literal, like we do with strings.

# lox/scanner.py Scanner method
def number(self):
    while is_digit(self.peek()):
        self.advance()

    # Look for a fractional part.
    if self.peek() == '.' and is_digit(self.peek_next()):
        # Consume the "."
        self.advance()

    while (is_digit(self.peek())):
        self.advance()

    substring = self.source[self.start: self.current]
    self.add_token("NUMBER", float(substring))

This relies on this little utility:

#lox/scanner.py at top-level
def is_digit(char: str) -> bool:
    return char.isdigit() and char.isascii()

We consume as many digits as we find for the integer part of the literal. Then we look for a fractional part, which is a decimal point (.) followed by at least one digit. If we do have a fractional part, again, we consume as many digits as we can find.

Looking past the decimal point requires a second character of lookahead since we don’t want to consume the . until we’re sure there is a digit after it. So we add:

# lox/scanner.py Scanner method
def peek_next(self):
    if self.current + 1 >= len(self.source):
        return "\0"
    return self.source[self.current + 1]

Finally, we convert the lexeme to its numeric value. Our interpreter uses Python’s float type to represent numbers, so we produce a value of that type. We’re using Python’s own parsing method to convert the lexeme to a real Python float. We could implement that ourselves, but, honestly, unless you’re trying to cram for an upcoming programming interview, it’s not worth your time.

The remaining literals are Booleans and nil, but we handle those as keywords, which gets us to . . . 

4 . 7Reserved Words and Identifiers

Our scanner is almost done. The only remaining pieces of the lexical grammar to implement are identifiers and their close cousins, the reserved words. You might think we could match keywords like or in the same way we handle multiple-character operators like <=.

case "o":
    if self.match("r"):
        self.add_token("OR")

Consider what would happen if a user named a variable orchid. The scanner would see the first two letters, or, and immediately emit an or keyword token. This gets us to an important principle called maximal munch. When two lexical grammar rules can both match a chunk of code that the scanner is looking at, whichever one matches the most characters wins.

That rule states that if we can match orchid as an identifier and or as a keyword, then the former wins. This is also why we tacitly assumed, previously, that <= should be scanned as a single <= token and not < followed by =.

Maximal munch means we can’t easily detect a reserved word until we’ve reached the end of what might instead be an identifier. After all, a reserved word is an identifier, it’s just one that has been claimed by the language for its own use. That’s where the term reserved word comes from.

So we begin by assuming any lexeme starting with a letter or underscore is an identifier.

# lox/scanner.py at Scanner.scan_token()'s match/case
    ...
    case c if is_alpha(c):
        self.identifier()
    ...

The rest of the code lives over here:

# lox/scanner.py Scanner method
def identifier(self):
    while is_alpha_numeric(self.peek()):
        self.advance()
    self.add_token("IDENTIFIER")

We define that in terms of these helpers:

# lox/scanner.py at top-level
def is_alpha(char: str) -> bool:
    return char == "_" or char.isalpha() and char.isascii()

def is_alpha_numeric(char: str) -> bool:
    return is_alpha(char) or is_digit(char)

That gets identifiers working. To handle keywords, we see if the identifier’s lexeme is one of the reserved words. If so, we use a token type specific to that keyword. We define the set of reserved words in a map.

# lox/scanner.py after the imports
KEYWORDS = {
    "and", "class", "else", "false", "for", "fun", "if",
    "nil", "or", "print", "return", "super", "this",
    "true", "var", "while",
}

Then, after we scan an identifier, we check to see if it matches anything in the map.

# lox/scanner.py at Scanner.identifier()
# before the self.add_token(...) line
    ...
    text = self.source[self.start: self.current]
    kind = "IDENTIFIER"
    if text in KEYWORDS:
        kind = text.upper()
    ...

If so, we use that keyword’s token type. Otherwise, it’s a regular user-defined identifier.

And with that, we now have a complete scanner for the entire Lox lexical grammar. Fire up the REPL and type in some valid and invalid code. Does it produce the tokens you expect? Try to come up with some interesting edge cases and see if it handles them as it should.