Compilers: A lexer from a rule list

Build a complete lexer with one master regular expression.

What to build

A program that tokenizes one line and prints each token, stopping at the first unexpected character.

Requirements

  • Rules in order: NUMBER \d+(\.\d+)?, NAME (then KEYWORD if it is if, else, while or print), OP (==, !=, <=, >=, then one of + - * / = < > ( )), comments from # to the end, whitespace.
  • Print KIND lexeme per token. On an unexpected character print error at column C (counting from 1) and stop.

Input

One line of source code.

Output

One line per token, possibly followed by an error line.

Constraints

At most 100 characters.

Example

Input:

if x>=10 print(x*2.5)

Output:

KEYWORD if
NAME x
OP >=
NUMBER 10
KEYWORD print
OP (
NAME x
OP *
NUMBER 2.5
OP )

Why it works

A single pattern of named rules finds the right token kind at each position, and its order gives two-character operators priority.

Examples

Example 1 · Input
if x>=10 print(x*2.5)
Expected output
KEYWORD if
NAME x
OP >=
NUMBER 10
KEYWORD print
OP (
NAME x
OP *
NUMBER 2.5
OP )
Example 2 · Input
a = b # a comment
Expected output
NAME a
OP =
NAME b

Prompts inside input() are ignored when checking, so input("n: ") is fine.

Hints

Hint 1

Join the rules with | into named groups, longest operators first, and use re.finditer.

Hint 2

Skip whitespace and # comments; the MISMATCH rule `.` catches anything else.

Solution

Show one correct solution (try it yourself first)
import re

KEYWORDS = {"if", "else", "while", "print"}
SPEC = [
    ("NUMBER", r"\d+(\.\d+)?"),
    ("NAME", r"[A-Za-z_]\w*"),
    ("OP", r"==|!=|<=|>=|[-+*/=<>()]"),
    ("COMMENT", r"#.*"),
    ("SKIP", r"\s+"),
    ("MISMATCH", r"."),
]
MASTER = re.compile("|".join(f"(?P<{n}>{p})" for n, p in SPEC))
for m in MASTER.finditer(input()):
    kind, value = m.lastgroup, m.group()
    if kind in ("COMMENT", "SKIP"):
        continue
    if kind == "MISMATCH":
        print("error at column", m.start() + 1)
        break
    if kind == "NAME" and value in KEYWORDS:
        kind = "KEYWORD"
    print(kind, value)

Lesson: Lexical analysis with regular expressions →