Unmasking the Backtracker: review and a tokenizer

Nine in the morning, and the office is packed. Detective Kang stands by the door, Ms. Jeong has her notebook open, and Reporter Oh has his laptop on his knees. The director turns the monitor so everyone can see. "Today we read it together. One character at a time."

Here's the coded message from the inbox.

\x46\N{HYPHEN-MINUS}\060\x32 \x3d \uc11c\uc9c4
\x34\x46 \060\063\x3a\060\x32
(a+)+$

Reporter Oh shakes his head. "Those aren't letters, they're just symbols." The director answers, "Symbols have rules too. Write the rules down one by one and the machine will read it for you."

A program that breaks long text into meaningful pieces (tokens) is called a tokenizer. Today you'll pull together everything you've learned to build one, and use it to crack this message.

12-1. A tokenizer: named groups joined with | (12 min)

First, for practice, let's break up an arithmetic expression like 3.5*(2 + x). It has the same structure as the "Writing a Tokenizer" example in the official Python docs. (The error message is in Korean: 모르는 글자 = unknown character, 위치 = position.)

import re

TOKEN_SPEC = [
    ("NUMBER",   r"\d+(?:\.\d*)?"),   # integer or decimal
    ("ID",       r"[A-Za-z_]\w*"),    # name
    ("OP",       r"[+\-*/]"),         # operator
    ("LPAR",     r"\("),
    ("RPAR",     r"\)"),
    ("SKIP",     r"[ \t]+"),          # throw spaces away
    ("MISMATCH", r"."),               # anything else: an unknown character
]
TOKEN = re.compile("|".join(f"(?P<{name}>{rx})" for name, rx in TOKEN_SPEC))

def tokenize(code):
    for m in TOKEN.finditer(code):
        kind, value = m.lastgroup, m.group()
        if kind == "SKIP":
            continue
        if kind == "MISMATCH":
            raise ValueError(f"모르는 글자 {value!r} (위치 {m.start()})")
        yield kind, value

print(list(tokenize("3.5*(2 + x)")))
# [('NUMBER', '3.5'), ('OP', '*'), ('LPAR', '('), ('NUMBER', '2'), ('OP', '+'), ('ID', 'x'), ('RPAR', ')')]

The whole structure comes down to three things.

• One named group per rule, (?P<name>rule), joined with |. Writing the rules as a list makes them easy to read and change.
• finditer catches tokens one at a time from the front, and m.lastgroup (Lesson 6) gives you the name of which rule caught it.
• The MISMATCH at the very end is a single .. It catches any character that fits none of the rules.

list(tokenize("3.5 $ 2"))
# ValueError: 모르는 글자 '$' (위치 4)

What happens without MISMATCH? finditer silently skips characters that don't match. Even if strange characters were slipped into the message, you'd never notice.

NO_GUARD = re.compile(r"(?P<NUMBER>\d+)|(?P<OP>[+*])")
[m.group() for m in NO_GUARD.finditer("3 $ 2")]   # ['3', '2']

| tries alternatives from the left, so order is priority. Put a broad rule first and the narrow rules never get a chance.

BAD = re.compile(r"(?P<ID>\w+)|(?P<NUMBER>\d+)")
[m.lastgroup for m in BAD.finditer("x 3")]   # ['ID', 'ID']

12-2. Character escapes inside patterns (8 min)

Things like \x46 and \uc11c in the message are called character escapes. re understands most of the escapes you know from Python strings directly inside a pattern. That's why even the raw string r"\t" finds a tab.

print(re.findall(r"\t|\n", "F-02\t03:02\n"))   # ['\t', '\n']
print(re.fullmatch(r"\\", "\\"))              # <re.Match object; span=(0, 1), match='\\'>

• Control characters: \t (tab), \n (newline), \r, \f, \v, \a (bell), and \\ for a backslash itself.
• Hexadecimal: \x41 (two digits), \u00e9 (four digits), \U0001F600 (eight digits).
• By name: a Unicode character name, like \N{EM DASH}.

print(re.findall(r"\x46-\x30\x32", "badge=F-02"))   # ['F-02']
print(re.fullmatch(r"caf\u00e9", "café"))           # <re.Match object; span=(0, 4), match='café'>
print(re.fullmatch(r"\N{EM DASH}", "—"))            # <re.Match object; span=(0, 1), match='—'>
print(len("\U0001F600"), "\U0001F600" == "\N{GRINNING FACE}")   # 1 True

There are octal escapes too. An escape becomes an octal character when it starts with \0 or has three digits (as you saw in Lesson 10, \10 is a group number). And \b is a backspace character only inside a class.

print(re.findall(r"\101|\0", "A\0B"))    # ['A', '\x00']
print(re.findall(r"[\b]", "F\b-02"))     # ['\x08']

On the other hand, an escaped Latin letter with no assigned meaning is an error. Those spots are kept free so new meanings can be added later.

re.compile(r"\q")
# re.PatternError: bad escape \q at position 0

12-3. Handling pattern errors: re.error (8 min)

The message you see when a red error box pops up in the lab comes from an exception called re.error. Since 3.13 it also goes by the name re.PatternError; the two are the same exception. The exception object tells you what went wrong and where.

print(re.PatternError is re.error)   # True

try:
    re.compile(r"[a-Z]")
except re.error as e:
    print(e.msg)       # bad character range a-Z
    print(e.pattern)   # [a-Z]
    print(e.pos)       # 1

For a pattern that spans several lines, lineno (which line) and colno (which column) come in handy. Both count from 1.

user_pattern = r'''(?x)
    (?P<badge> F-\d+ )
    (?P<time \d\d:\d\d )
'''
try:
    re.compile(user_pattern)
except re.PatternError as e:
    print(e.msg)                  # missing >, unterminated name
    print(e.pos, e.lineno, e.colno)   # 36 3 9

A pattern typed by a person can be wrong at any time. A program that accepts patterns, like a search box, should always wrap them in try/except. (패턴 오류 = pattern error.)

def safe_compile(text):
    try:
        return re.compile(text)
    except re.error as e:
        print(f"패턴 오류: {e.msg} (위치 {e.pos})")
        return None

safe_compile(r"(?P<SIGN>(a+)+$")   # 패턴 오류: missing ), unterminated subpattern (위치 0)

But try/except only protects you from syntax errors. A pattern like (a+)+$, which is perfectly valid but slow, just freezes without raising anything (Lesson 8). That's why the Evidence lab hands patterns to a separate worker and replaces that worker when time runs out.

12-4. bytes patterns (7 min)

Data read from a file or a network is sometimes bytes, not str. For bytes, use a bytes pattern like rb"...". You can't mix str and bytes.

data = "badge=F-02 서진".encode()
print(re.findall(rb"F-\d+", data))   # [b'F-02']

re.findall(r"F-\d+", data)
# TypeError: cannot use a string pattern on a bytes-like object
re.findall(rb"F-\d+", "badge=F-02")
# TypeError: cannot use a bytes pattern on a string-like object

In a bytes pattern, \w, \d and \s see ASCII only. Hangul is split across several bytes, so it doesn't look like letters. To work with Hangul, decode() it into a str first.

print(re.findall(rb"\w+", data))            # [b'badge', b'F', b'02']
print(re.findall(r"\w+", data.decode()))    # ['badge', 'F', '02', '서진']

The flags flip too. re.L works only with bytes patterns (Lesson 11), and re.U is an error with a bytes pattern.

print(re.compile(rb"\w", re.L).flags)   # 4
re.compile(rb"\w", re.U)
# ValueError: cannot use UNICODE flag with a bytes pattern

12-5. Warnings and hidden tools (5 min)

In Lesson 2 you were told to avoid [[, --, &&, ~~ and || inside a class. They're reserved for future "set operations", so for now they raise a FutureWarning. If you mean the characters literally, escape them.

re.compile(r"[[a-z]")
# FutureWarning: Possible nested set at position 1
re.compile(r"[a-z--]")
# FutureWarning: Possible set difference at position 4
re.compile(r"[\[a-z]")   # no warning

The re module also has internal tools that aren't in the official docs: re.Scanner (a class that builds a tokenizer for you), Pattern.scanner(), and Match.regs (the spans of every group). Just know they exist. Anything undocumented can change at any time, so in real code, use the finditer + lastgroup approach you built today.

m = re.search(r"(F)-(\d+)", "badge=F-02")
print(m.regs)   # ((6, 10), (6, 7), (8, 10))

Cracking the case (10 min)

Now write down the rules of the message: four kinds of character escape, the signature, spacing, and a MISMATCH to plug the gaps. As you learned in Lesson 11, spell it out with re.X and add comments. (The error message is the same Korean as before: 모르는 토큰 = unknown token.)

import unicodedata

CIPHER = re.compile(r'''
    (?P<HEX>   \\x [0-9a-fA-F]{2} )    # \x46    two hex digits
  | (?P<UNI>   \\u [0-9a-fA-F]{4} )    # \uc11c  four hex digits
  | (?P<NAME>  \\N \{ [A-Z -]+ \} )    # \N{...} a character name
  | (?P<OCT>   \\ [0-7]{3} )           # \060    three octal digits
  | (?P<SIGN>  \(a\+\)\+\$ )           # the signature, same as re.escape("(a+)+$")
  | (?P<SPACE> [ \n]+ )                # keep spaces and line breaks as they are
  | (?P<MISMATCH> . )                  # any other character is suspicious
''', re.X)

def decode(message):
    out = []
    for m in CIPHER.finditer(message):
        kind, value = m.lastgroup, m.group()
        if kind in ("HEX", "UNI"):
            out.append(chr(int(value[2:], 16)))
        elif kind == "OCT":
            out.append(chr(int(value[1:], 8)))
        elif kind == "NAME":
            out.append(unicodedata.lookup(value[3:-1]))
        elif kind == "SPACE":
            out.append(value)
        elif kind == "MISMATCH":
            raise ValueError(f"모르는 토큰 {value!r} (위치 {m.start()})")
    return "".join(out).strip()

print(decode(message))
# F-02 = 서진
# 4F 03:02

Remember that even under re.X, the spaces inside the classes [A-Z -] and [ \n] stay. The SIGN token is thrown away without printing anything.

You can also ask re itself whether the decoded text is right. The first line of the message is a valid regex in its own right, because re understands the same escapes.

first = message.splitlines()[0]
print(re.fullmatch(first, "F-02 = 서진"))   # <re.Match object; span=(0, 9), match='F-02 = 서진'>

F-02 = 서진. 서진 is a name written in Hangul: Seo Jin. Fourth floor, 3:02 a.m. Exactly the same time as the access log in Lesson 11.

Detective Kang asks, "Who's Seo Jin?" The director takes the frame she'd laid face down out of the drawer and stands it on the desk. It's a photo of two young people standing under this agency's sign.

"The man who started Grep & Co. with me. F-02 was his badge." The director touches the man in the photo with her fingertip. "He was a genius. He wrote everything as a one-line regex. Nobody could read that code, and nobody could fix it. So we spelled it out, piece by piece… and I suppose he thought we were erasing him. One day he walked out and left only his badge behind."

"Why didn't you cancel the badge?" Instead of answering, the director looks at the last line on the screen, (a+)+$. "The man who said an unreadable regex is the best regex sent us his own name in a form we could read. He wanted someone to read him all along."

Rereading the twelve cases

That afternoon, the director and the new detective go back through all twelve case files from the start. "How would we write it now?"

• CASE-001, the payment log: re.escape("$4.99") instead of adding backslashes by hand.
• CASE-002 and 003, number plates and phone numbers: shorten them with quantifiers, like \d{2,3}[가-힣]\d{4}, and validate with fullmatch.
• CASE-004, the fake sign-ups: not search but re.fullmatch(r"[a-z][a-z0-9_]{3,15}", user_id).
• CASE-005 and 010, dates: (?P<y>\d{4})(?P<sep>[-./])(?P<m>\d\d)(?P=sep)(?P<d>\d\d). With names, there's no need to count numbers.
• CASE-006, the access log: named groups and groupdict() to turn a line into a dict.
• CASE-007, the customer list: function replacement, and keyword arguments like count=.
• CASE-008, the Backtracker's challenge: ^a+$ instead of ^(a|aa)+$. Never write overlapping repeats.
• CASE-009, the safe's rules: one condition per lookahead, and one comment line per condition.
• CASE-011, the one-line regex: spell it out with re.X and give it a name with re.compile.
• CASE-012, the coded message: a tokenizer with its rules written as a list, and MISMATCH at the end.

Late that night, one more email arrives. This time it isn't in code.

The signature has changed. Its comment is in Korean: "no more backtracking." Out of habit, the new detective drops the signature into the lab. Without the outer repeat, the pattern doesn't hesitate even when it fails.

sign = r"(?x) a+ $   # 이제 되돌아가지 않는다"
print(re.fullmatch(sign, "a" * 30 + "b"))   # None

The director sets her worn notebook on the new detective's desk. From the first page on, every case is crammed with her handwriting. "It's yours now. Short regexes don't win. Readable regexes do. Don't ever forget that."

Exercises

1. Add = as ASSIGN and line breaks as NEWLINE to the tokenizer from 12-1, then tokenize two lines of code: x = 3.5 followed by y = x * 2 on the next line.
2. Add a token for \U followed by eight hex digits to the message decoder, and decode \U0000C11C\U0000C9C4.
3. Write a function that takes a pattern from the user and, if there's an error, shows the pattern with a ^ under position e.pos. That's exactly what the Evidence lab does.