From source to tokens

What a compiler is made of, and its first phase: turning characters into tokens, with regular expressions and with a hand-written scanner.

About 4 hours of study

Learning objectives

Lessons

  1. 1

    How a compiler works Intermediate

    A compiler turns source code into something a machine can run, in phases: lexing, parsing, checking, intermediate code, optimisation and code generation. Build a whole tiny compiler for arithmetic in 60 lines of Python.

  2. 2

    Lexical analysis with regular expressions Intermediate

    A lexer turns characters into tokens: numbers, names, keywords and operators, with their positions. Build one from a table of regular expressions combined into a single pattern, the way many real lexers are generated.

  3. 3

    A hand-written lexer Intermediate

    Write a lexer the way production compilers often do: one character at a time, with peek and advance, longest match, and lookahead for two-character operators and decimal numbers.

Module practice

Module quiz

1. Which phase turns characters into tokens?
2. What does the parser produce?
3. Which rule decides between the tokens = and == when the input is ==?
4. Two rules match the same longest text, such as the keyword if and an identifier. Which wins?
5. Why does a lexer keep the line and column of each token?
6. A hand-written lexer sees the digit 4 followed by 2 and a space. What does it do?

Parsing ›