Skip to content
Tutorials Center
My learning

Topics

Lesson 10 of 61 Β· Lexical Analysis

Writing a Complete Lexer

Build a full hand-written lexer in Python: a Token class, line and column tracking, numbers, strings with escapes, comments, operators and EOF.

You already know what tokens and lexemes are, you have seen how regular expressions describe them, and you know that automata can recognize them. Now it is time to put it all together into a real lexer: a program that takes the source text of a language and returns a list of tokens, each with enough information to produce good error messages later.

We write it by hand, with no regular expressions. Hand-written lexers are what many production compilers use (Go, Rust and most JavaScript engines have one), because they are fast, easy to debug and easy to give precise error messages. They are also short: about a hundred lines of Python cover a language with numbers, strings, comments and a dozen keywords. The language we lex is the small toy language used throughout this track: let, print, if/else, while, fun/return, numbers, strings, booleans, arithmetic, comparisons and and/or/not.

What a token should carry

A token is more than a type name. A parser needs to know the kind of token, and an error message needs to know where it was. So our Token stores:

  • kind: NUMBER, STRING, IDENT, a keyword such as if, an operator such as <=, or EOF. For keywords and punctuation we use the text itself as the kind, which keeps parser code readable (expect("while") instead of expect(TokenKind.WHILE)).
  • lexeme: the exact source text, which is handy for error messages and for formatting code back.
  • value: the converted value for numbers (int or float) and strings (the text after processing escapes), otherwise None.
  • line and col: where the token starts, both counted from 1.

A frozen dataclass gives us a clean class with ==, repr and immutability for free.

Tracking lines and columns

Positions are easy to get wrong, so let us isolate the idea. Keep two counters. Every time you consume a character, add one to the column, except when the character is a newline: then add one to the line and reset the column to 1. Do this in one single place (an advance method) and every token gets correct positions automatically.

Python Line and column counters

Press Run (or Ctrl + Enter) to see the result here.

Program input Β· what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The x on line 2 is at column 9 because two spaces, print and one more space come before it. The final position (line 3, column 1) is where the EOF token will sit.

The shape of the lexer

The main loop is the same in nearly every hand-written lexer:

  1. Skip trivia: whitespace and comments.
  2. Remember the current line and column; this is where the token starts.
  3. Look at the first character and decide which kind of token follows (dispatch).
  4. Call a helper that consumes the whole lexeme and returns a token.
  5. At the end of input, return an EOF token.
flowchart TD
    S["next_token"] --> T["skip whitespace<br/>and comments"]
    T --> E{"first character"}
    E -->|"end of input"| EOF["EOF token"]
    E -->|"digit"| N["number()"]
    E -->|"letter or _"| W["word(): keyword or IDENT"]
    E -->|"double quote"| ST["string()"]
    E -->|"operator or punctuation"| O["one- or two-character operator"]
    E -->|"anything else"| ER["LexError"]

One character of lookahead is enough to choose the right helper.

The helper methods rely on two tiny functions: peek(offset) looks at a character without consuming it (returning "" past the end, so you never get an index error), and advance() consumes one character and updates the position.

The details that matter

Operators and longest match. At < you must look one character further: if the next character is =, the token is <=; otherwise it is <. This is the longest-match rule in action. We handle it by checking the two-character set first, then the one-character set.

Identifiers and keywords. Read a whole word ([A-Za-z_][A-Za-z0-9_]*), then look it up in the keyword set. if becomes an if token, while ifx stays an IDENT. Never test for keywords by checking prefixes.

Numbers. Read digits, then optionally a fraction (a . that is followed by a digit) and an optional exponent (e or E, an optional sign, and at least one digit). The "followed by a digit" check matters: in 1.x the 1 is a number and the dot is not part of it. Likewise 2e is the number 2 followed by an identifier e, not a broken number. Convert the text to int or float and store it in value.

Strings. After the opening quote, read characters until the closing quote. A backslash starts an escape sequence: \n, \t, \" and \\ become the single characters they stand for, so the token's value differs from its lexeme. A newline or end of input before the closing quote is an unterminated string error. An unknown escape is also an error, rather than being silently accepted.

Comments. // runs to the end of the line, and /* ... */ runs to the closing marker. They are skipped like whitespace and never reach the parser. An unterminated block comment is an error reported at the position where the comment started, which is far more useful than reporting end of file.

EOF. The final token is a real token of kind EOF, with a position. A parser that always finds a token under its cursor needs no special end-of-list checks.

The complete lexer

This is the whole thing. Read it top to bottom once, then run it. The test program at the bottom contains a line comment, a block comment across two lines, an escape in a string, a float with an exponent, keywords and operators. Afterwards a small loop feeds in tricky inputs and prints either the token kinds or the error.

Python A complete hand-written lexer for the toy language

Press Run (or Ctrl + Enter) to see the result here.

Program input Β· what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Study the edge-case table at the end. A few lines deserve a comment:

  • a=<b lexes as a, =, <, b: there is no =< operator, so the lexer correctly emits two tokens and leaves the mistake for the parser.
  • 1. is an error, not the number 1 followed by something, because our number leaves the dot alone and no token starts with a dot. Languages that want 1. to be a float need a different rule.
  • ifx if gives an identifier and then the keyword, which shows that keywords are matched on whole words.
  • 3.14.15 reports the second dot as unexpected, because 3.14 is already a complete number.

The lexer raises an exception at the first problem and stops. That is fine for a first version, but real compilers want to report many errors in one run. The next lesson, Lexical Errors and Recovery, shows how to keep going.

Design choices worth knowing

Return a list or produce tokens on demand? Our tokens() builds a list, which is simple and makes lookahead in the parser trivial. A streaming lexer (a generator, or a next_token() that the parser calls) uses less memory for huge files. For teaching and small languages the list is perfect.

Why store the lexeme if you have the value? Because the value loses information: 0x10, 16 and 1.6e1 may produce the same number, and an error message that says "unexpected 0x10" should quote what the user typed.

Whitespace significance. Python and Haskell care about indentation, so their lexers emit INDENT and DEDENT tokens. Our toy language ignores whitespace, so trivia never becomes a token.

Unicode. str.isalpha() accepts letters from any script, so identifiers like grâße work. A language specification should say exactly what it allows; many follow Unicode's identifier rules.

Performance. Hand-written lexers do one pass with constant work per character. If you need more speed in Python, the regex-based approach from the earlier lesson is usually faster because the matching runs in C.

Testing a lexer

Lexers are ideal for table-driven tests: a list of (source, expected token kinds) pairs. Test each token class, each boundary (< versus <=, 1.5 versus 1.x), each error, and the position of the first token on line 2 (it catches newline bugs). You will build a harness like this in Testing and Debugging a Compiler.

Check your understanding

Quick check Β· 5 questions

of 5 answered You scored / 5 Β· perfect!

  1. 1. Why does the lexer return an EOF token instead of just ending the list?

    An explicit EOF token removes special cases from the parser (no index errors) and gives 'unexpected end of input' errors a line and column.
  2. 2. In the number rule, why must the dot be followed by a digit before it joins the number?

    Looking one character past the dot avoids consuming a dot that does not start a fraction. The lexeme only grows when the longer form is valid.
  3. 3. How should the lexer turn the characters \n inside a string literal (backslash, then n) into a value?

    Escape sequences are decoded while reading the string, so value holds the real text. The lexeme still holds the source form for error messages.
  4. 4. Where should an unterminated block comment be reported?

    The start of the comment is where the user needs to look. The end of file is only where the lexer noticed the problem.
  5. 5. Why is the two-character operator set checked before the one-character set?

    If the shorter operator were tried first, <= would always split into two tokens. The longest-match rule takes the longest valid lexeme.

Summary

  • A good token carries a kind, the exact lexeme, a converted value and a line and column.
  • Update line and column in exactly one place, the advance method, resetting the column on newlines.
  • The lexer loop: skip whitespace and comments, record the start position, dispatch on the first character, call a helper, repeat until EOF.
  • Apply longest match for operators and numbers by looking ahead one or two characters with peek.
  • Decode string escapes while scanning, reject unknown escapes, and report unterminated strings and comments at their start.
  • Keywords are whole words found in a set after scanning an identifier.

Next: Lexical Errors and Recovery