Skip to content
Tutorials Center
My learning

Topics

Lesson 6 of 61 ยท Lexical Analysis

Tokens, Lexemes and Patterns

Learn the difference between tokens, lexemes and patterns, how keywords differ from identifiers, and hand-write a character-by-character scanner in Python.

The first job of a compiler is to read characters and make sense of them as words. When you read the sentence "the cat sat" you do not see eleven letters, you see three words. The lexical analyzer, also called the lexer, scanner or tokenizer, does the same for programs: it turns a long string of characters into a short list of meaningful units called tokens.

Doing this as a separate phase keeps the rest of the compiler simple. The parser then never worries about spaces, comments or whether >= is one symbol or two. In this lesson you learn the vocabulary of lexing and write a scanner by hand, character by character. The next lessons show how to describe tokens with regular expressions and how the machinery works underneath. We use the Tiny language from Meet Our Toy Language.

Token, lexeme, pattern

Three terms are easy to mix up, so fix them now.

  • A lexeme is the actual sequence of characters in the source: count, >=, 42.
  • A token is the category the lexeme belongs to, plus any extra information: "identifier", "number", "greater-or-equal".
  • A pattern is the rule that describes which lexemes belong to a token: "a letter or underscore followed by letters, digits or underscores" is the pattern for identifiers.

An analogy: the pattern is the definition of the word "noun", the token is the label "noun", and the lexeme is the particular word "table".

Lexeme Token Attribute (value)
while WHILE none
count IDENT the name "count"
42 NUMBER the integer 42
"tick" STRING the text tick
>= >= none
; ; none

The last column is the attribute. Several lexemes can share a token (x and count are both IDENT), so the parser needs the attribute to tell them apart. For numbers the lexer converts the text to a real integer, so later phases do not parse digits again. Many compilers also store a source position with every token so error messages can point to the right place.

What the lexer discards

Some text never becomes a token:

  • Whitespace separates tokens. In most languages it carries no other meaning. Python is an exception: it treats indentation as syntax, so its lexer produces extra INDENT and DEDENT tokens.
  • Comments are for humans. The lexer recognizes them and drops them.

Throwing these away is one of the reasons we have a lexer at all. The grammar can then say "a let statement is LET IDENT = expr ;" without mentioning where spaces may appear.

Keywords and identifiers

Keywords such as while and let look exactly like identifiers: a run of letters. There are two common strategies:

  1. Write a separate pattern for each keyword and make sure it wins over the identifier pattern.
  2. Scan any word with the identifier pattern, then look the lexeme up in a keyword table. If it is in the table, the token is the keyword; otherwise it is IDENT.

Almost every real lexer uses the second approach. It is shorter, and it makes adding a keyword a one-line change.

Python Keyword, identifier or number?

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.

Two results deserve a look. Print is an identifier, because Tiny is case sensitive and only lowercase print is a keyword. 1x is rejected as a single word: an identifier cannot start with a digit. Next you will see what a scanner does when it meets 1x in the middle of a program.

The longest-match rule

When several tokens could start at the same position, a lexer takes the longest one. At <= the lexer must not stop after <, even though < is a valid token by itself. The same rule explains iffy: it begins with the keyword if, yet the whole word is an identifier, because the scanner reads the entire run of letters before it decides what the word is.

This is also called maximal munch. It is simple to apply and almost always what programmers expect, though it has side effects. In C++ before C++11, vector<vector<int>> was read with >> as a shift operator, which is why older code wrote vector<vector<int> > with a space.

Python First match versus longest match

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.

Without longest match, a <= b falls apart into < and =, and n == 10 turns into two assignments. The last example, total=-1, shows the rule has limits: the lexer cannot know the programmer meant = -1, but the result is correct anyway, because =- is not a two-character token in Tiny.

flowchart LR
    A["Characters<br/>l e t _ x _ = _ 4 2 ;"] --> B["Scanner"]
    B --> C["LET"]
    B --> D["IDENT x"]
    B --> E["="]
    B --> F["NUMBER 42"]
    B --> G[";"]

The scanner turns eleven characters into five tokens; the underscores stand for spaces that are discarded.

Writing a scanner by hand

A hand-written scanner is a loop with a position i. At each step it looks at the current character and decides what kind of token starts there:

  1. Whitespace: skip it.
  2. //: skip to the end of the line.
  3. A digit: keep reading digits, then convert to an integer.
  4. A letter or underscore: keep reading letters, digits and underscores, then check the keyword table.
  5. A double quote: read until the closing quote.
  6. A two-character operator, then a one-character operator.
  7. Anything else: report a lexical error.

The pattern in rules 3 to 5 is always the same: look at the first character to choose the token, then consume as many matching characters as possible. Peeking at the next character without consuming it (a lookahead of one character) is how the scanner decides where a token ends.

The scanner below records, for each token, its kind, its lexeme, its attribute and the offset where it starts. It stops at the first error with an exception; the lesson on lexical errors and recovery improves on that.

Python A hand-written scanner for Tiny

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.

Read the table of output top to bottom. The comment // start leaves no trace, but the offsets jump over it (14 to 25), which proves the lexer saw it. The scanner ended with a special EOF token, which saves the parser from checking "have we run out of input?" everywhere.

The last three lines show errors. An unterminated string and a stray $ raise LexError. The input 12ab is more interesting: it does not fail at all. The scanner returns NUMBER 12 followed by IDENT ab, because each is individually valid. It is the parser, a phase later, that will notice two values in a row where a ; was expected. Lexers only detect what is wrong at the character level.

Notice that ch in " \t\r\n" and the sets of letters and digits were written out by hand. Python's str.isalpha() and str.isdigit() accept many Unicode characters (including digits from other scripts that int() converts), which is surprising in a lexer. If you want your language to be ASCII-only, as Tiny is, list the characters explicitly.

Design choices you will meet again

  • Token representation. A named tuple, a dataclass or a small class with kind, lexeme, value and a position. Use whatever keeps later phases readable.
  • Lazy or eager. Our scanner builds a whole list. Many real lexers are generators that produce one token at a time on request, so a parser never needs the whole file in memory.
  • Where to convert values. Converting digits to an integer in the lexer is convenient. Some compilers keep the lexeme and convert later, so that huge numbers or hexadecimal and floating-point forms can be handled in one place.
  • Hand-written or generated. Hand-written scanners, like this one, are fast and flexible. Tools such as Lex and Flex generate scanners from patterns. In the next lesson you use Python's re module for the same purpose.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. In the statement let total = 5;, what is total?

    total is the lexeme, the actual characters. The token (category) is IDENT, with the name total as its attribute. The pattern is the rule that describes all identifiers.
  2. 2. Why do most lexers read a whole word and then look it up in a keyword table?

    Keywords have the same shape as identifiers. Scanning one run of letters and checking a table is simpler than writing a separate pattern for every keyword.
  3. 3. How does the longest-match (maximal munch) rule tokenize a <= b?

    At < the scanner prefers the longest possible token, <=, over the shorter <.
  4. 4. What does the scanner above do with the input 12ab?

    Each piece is a valid token on its own, so the lexer accepts both. The parser later finds two values in a row where the grammar expects something else.
  5. 5. Why does the scanner return a final EOF token?

    An explicit end marker means the parser never has to test for 'no more tokens' before each peek.

Summary

  • A lexeme is the characters in the source, a token is its category plus an attribute, and a pattern is the rule describing a token's lexemes.
  • The lexer discards whitespace and comments and turns the rest into a stream of tokens, usually ending with an EOF token.
  • Keywords are found by scanning a word as an identifier and checking a keyword table.
  • Longest match (maximal munch) means the scanner always takes the longest token that fits.
  • A hand-written scanner is a loop: look at the first character to pick the token kind, then consume characters while they fit.
  • Lexers only report character-level errors; many mistakes, like 12ab, are left for the parser.

Next: Regular Expressions for Lexers