Compilers: A complete hand-written lexer

Write the whole lexer by hand, without the re module.

What to build

A program that tokenizes a line by scanning characters and prints every token.

Requirements

  • Kinds: NUMBER (digits, with an optional .digits), NAME, KEYWORD (if, else, while, print, return), STRING (double quotes, no quote inside), OP (==, !=, <=, >=, then + - * / = < > ( ) ,). Skip spaces and # comments.
  • Print KIND lexeme per token. On an unexpected character, or a string that never closes, print error at C (from 1) and stop.

Input

One line.

Output

One line per token, possibly ending with an error line.

Constraints

At most 100 characters; do not use the re module.

Example

Input:

if speed >= 60 print("fast")

Output:

KEYWORD if
NAME speed
OP >=
NUMBER 60
KEYWORD print
OP (
STRING "fast"
OP )

Why it works

Each branch consumes exactly one kind of token, and lookahead settles the cases where two kinds start the same way.

Examples

Example 1 · Input
if speed >= 60 print("fast")
Expected output
KEYWORD if
NAME speed
OP >=
NUMBER 60
KEYWORD print
OP (
STRING "fast"
OP )
Example 2 · Input
total = 2.5 * n # cost
Expected output
NAME total
OP =
NUMBER 2.5
OP *
NAME n

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

Hints

Hint 1

One loop with a branch per token kind; take each token as a slice from its start position.

Hint 2

Check keywords after reading a whole name, and two-character operators before one-character ones.

Solution

Show one correct solution (try it yourself first)
KEYWORDS = {"if", "else", "while", "print", "return"}
TWO = {"==", "!=", "<=", ">=", }
ONE = set("+-*/=<>(),")
text = input()
i = 0
while i < len(text):
    c = text[i]
    start = i
    if c == " ":
        i += 1
    elif c == "#":
        break
    elif c.isdigit():
        while i < len(text) and text[i].isdigit():
            i += 1
        if i + 1 < len(text) and text[i] == "." and text[i + 1].isdigit():
            i += 1
            while i < len(text) and text[i].isdigit():
                i += 1
        print("NUMBER", text[start:i])
    elif c.isalpha() or c == "_":
        while i < len(text) and (text[i].isalnum() or text[i] == "_"):
            i += 1
        word = text[start:i]
        print("KEYWORD" if word in KEYWORDS else "NAME", word)
    elif c == '"':
        end = text.find('"', i + 1)
        if end == -1:
            print("error at", start + 1)
            break
        print("STRING", text[start:end + 1])
        i = end + 1
    elif text[i:i + 2] in TWO:
        print("OP", text[i:i + 2])
        i += 2
    elif c in ONE:
        print("OP", c)
        i += 1
    else:
        print("error at", start + 1)
        break

Lesson: A hand-written lexer →