Die Enttarnung des Backtrackers: Rückblick und ein Tokenizer

9 Uhr morgens. Die Detektei ist voll. Kommissar Kang steht an der Tür, Frau Jeong hat ihr Notizbuch aufgeschlagen, Reporter Oh balanciert seinen Laptop auf den Knien. Die Direktorin dreht den Monitor so, dass alle ihn sehen. „Heute lesen wir gemeinsam. Zeichen für Zeichen.“

Das ist die verschlüsselte Nachricht aus dem Postfach:

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

Reporter Oh schüttelt den Kopf. „Das sind doch keine Buchstaben, das sind nur Symbole.“ Die Direktorin antwortet: „Auch Symbole folgen Regeln. Schreib die Regeln eine nach der anderen auf, dann liest die Maschine für dich.“

Ein Programm, das langen Text in sinnvolle Stücke (Tokens) zerlegt, heißt Tokenizer. Heute baust du aus allem, was du bisher gelernt hast, einen Tokenizer und knackst damit diese Nachricht.

12-1. Der Tokenizer: benannte Gruppen mit | verbinden (12 Min.)

Zum Üben zerlegen wir erst einmal einen Rechenausdruck wie 3.5*(2 + x). Der Aufbau entspricht dem Beispiel „Writing a Tokenizer“ aus der offiziellen Python-Dokumentation.

import re

TOKEN_SPEC = [
    ("NUMBER",   r"\d+(?:\.\d*)?"),   # Ganzzahl oder Dezimalzahl
    ("ID",       r"[A-Za-z_]\w*"),    # Name
    ("OP",       r"[+\-*/]"),         # Operator
    ("LPAR",     r"\("),
    ("RPAR",     r"\)"),
    ("SKIP",     r"[ \t]+"),          # Leerraum wird verworfen
    ("MISMATCH", r"."),               # alles andere: unbekanntes Zeichen
]
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', ')')]

Die Fehlermeldung im Code ist koreanisch: 모르는 글자 heißt „unbekanntes Zeichen“, 위치 heißt „Position“. Der ganze Aufbau besteht aus drei Dingen:

• Für jede Regel eine benannte Gruppe (?P<name>regel), verbunden mit |. Weil die Regeln als Liste dastehen, sind sie leicht zu lesen und zu ändern.
• finditer fängt von vorn ein Token nach dem anderen, und m.lastgroup (Lektion 6) liefert den Namen der Regel, die getroffen hat.
• Das MISMATCH am Ende ist ein einzelner .. Hier bleibt jedes Zeichen hängen, auf das keine andere Regel passt.

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

Was passiert ohne MISMATCH? finditer überspringt Zeichen, die nicht passen, stillschweigend. Steckt ein merkwürdiges Zeichen in der Nachricht, merkst du es nicht einmal.

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

| probiert von links nach rechts, also ist die Reihenfolge die Priorität. Steht eine breite Regel vorn, kommt eine engere nie zum Zug.

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

12-2. Zeichen-Escapes im Muster (8 Min.)

Dinge wie \x46 oder \uc11c in der Nachricht heißen Zeichen-Escapes. Die meisten Escapes aus Python-Strings versteht auch re direkt im Muster. Deshalb findest du einen Tab auch mit dem Raw-String r"\t".

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

• Steuerzeichen: \t (Tab), \n (Zeilenumbruch), \r, \f, \v, \a (Klingel), und der Backslash selbst ist \\.
• Hexadezimal: \x41 (zwei Stellen), \u00e9 (vier Stellen), \U0001F600 (acht Stellen).
• Name: mit dem Unicode-Namen des Zeichens, etwa \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

Es gibt auch Oktalzahlen. Beginnt ein Escape mit \0 oder hat es drei Ziffern, wird es zu einem Oktalzeichen (wie in Lektion 10 gesehen, ist \10 eine Gruppennummer). Außerdem ist \b nur innerhalb einer Klasse ein Backspace-Zeichen.

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

Umgekehrt ist ein Escape mit einem Buchstaben ohne festgelegte Bedeutung ein Fehler. Diese Plätze sind freigehalten, damit sie später eine neue Bedeutung bekommen können.

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

12-3. Musterfehler behandeln: re.error (8 Min.)

Die Meldung im roten Fehlerfeld des Labors stammt von einer Ausnahme namens re.error. Seit 3.13 gibt es auch den Namen re.PatternError, beides ist dieselbe Ausnahme. Das Ausnahmeobjekt sagt dir, was falsch ist und wo.

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

Bei mehrzeiligen Mustern sind lineno (welche Zeile) und colno (welche Spalte) hilfreich. Gezählt wird ab 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

Von Menschen eingegebene Muster können jederzeit falsch sein. Programme, die Muster entgegennehmen, etwa ein Suchfeld, packen das immer in try/except.

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)

(패턴 오류 heißt „Musterfehler“.) try/except fängt allerdings nur Syntaxfehler ab. Ein Muster wie (a+)+$, dessen Syntax stimmt, das aber langsam ist, bleibt ohne jede Ausnahme einfach hängen (Lektion 8). Deshalb lässt das Beweislabor Muster von einem separaten Arbeiter ausführen und tauscht diesen Arbeiter aus, wenn die Zeit abläuft.

12-4. bytes-Muster (7 Min.)

Daten aus Dateien oder dem Netzwerk sind manchmal nicht str, sondern bytes. Für bytes nimmst du bytes-Muster wie rb"...". str und bytes lassen sich nicht mischen.

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

\w, \d und \s in bytes-Mustern beachten nur ASCII. Hangul ist auf mehrere Bytes verteilt und wird darum nicht als Buchstabe erkannt. Um mit Hangul zu arbeiten, machst du zuerst mit decode() einen str daraus.

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

Auch bei den Flags ist es umgekehrt. re.L geht nur mit bytes-Mustern (Lektion 11), und re.U ist bei bytes-Mustern ein Fehler.

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. Warnungen und versteckte Werkzeuge (5 Min.)

In Lektion 2 hieß es, du sollst [[, --, &&, ~~ und || in Klassen meiden. Diese Stellen sind für künftige „Mengenoperationen“ reserviert, deshalb gibt es heute eine FutureWarning. Meinst du die Zeichen wörtlich, escape sie.

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]")   # keine Warnung

Im Modul re gibt es auch interne Werkzeuge, die nicht in der offiziellen Dokumentation stehen: re.Scanner (eine Klasse, die dir einen Tokenizer baut), Pattern.scanner() und Match.regs (die spans aller Gruppen). Es reicht, dass du weißt, dass es sie gibt. Was nicht dokumentiert ist, kann sich jederzeit ändern. In echtem Code nimmst du den Weg über finditer + lastgroup, den du heute gebaut hast.

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

Den Fall lösen (10 Min.)

Jetzt schreibst du die Regeln der Nachricht auf: vier Arten von Zeichen-Escapes, die Signatur, Leerraum und das MISMATCH, das alle Lücken schließt. Wie in Lektion 11 gelernt, mit re.X aufgeschrieben und kommentiert.

import unicodedata

CIPHER = re.compile(r'''
    (?P<HEX>   \\x [0-9a-fA-F]{2} )    # \x46    zwei Hexadezimalstellen
  | (?P<UNI>   \\u [0-9a-fA-F]{4} )    # \uc11c  vier Hexadezimalstellen
  | (?P<NAME>  \\N \{ [A-Z -]+ \} )    # \N{...} Zeichenname
  | (?P<OCT>   \\ [0-7]{3} )           # \060    drei Oktalstellen
  | (?P<SIGN>  \(a\+\)\+\$ )           # Signatur, wie re.escape("(a+)+$")
  | (?P<SPACE> [ \n]+ )                # Leerzeichen und Zeilenumbrüche bleiben
  | (?P<MISMATCH> . )                  # alle anderen Zeichen sind verdächtig
''', 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

Denk daran: Auch unter re.X bleiben die Leerzeichen in den Klassen [A-Z -] und [ \n] erhalten. Die Signatur SIGN gibt nichts aus und wird verworfen. (모르는 토큰 heißt „unbekanntes Token“.)

Ob die entschlüsselten Zeichen stimmen, kannst du auch re direkt fragen. Die erste Zeile der Nachricht ist selbst ein gültiger regulärer Ausdruck, denn re versteht dieselben Escapes.

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

F-02 = 서진. 서진 ist ein koreanischer Name: Seo Jin. 4. Stock, 3:02 Uhr nachts. Genau die Uhrzeit aus dem Zutrittsprotokoll in Lektion 11.

Kommissar Kang fragt: „Wer ist Seo Jin?“ Die Direktorin holt den Bilderrahmen, der mit dem Bild nach unten in der Schublade lag, und stellt ihn auf den Schreibtisch. Zwei junge Menschen stehen auf dem Foto unter dem Schild dieser Detektei.

„Der Mann, mit dem ich Grep & Co. gegründet habe. F-02 war sein Ausweis.“ Mit der Fingerspitze tippt die Direktorin auf den Mann im Bild. „Er war ein Genie. Alles schrieb er als einzeiligen Regex. Niemand konnte seinen Code lesen, niemand konnte ihn reparieren. Also haben wir ihn Stück für Stück lesbar aufgeschrieben … und er hat das wohl so verstanden, als würden wir ihn auslöschen. Eines Tages ließ er nur seinen Ausweis zurück und ging.“

„Und warum haben Sie den Ausweis nicht gesperrt?“ Statt zu antworten, sieht die Direktorin auf die letzte Zeile auf dem Bildschirm, (a+)+$. „Ausgerechnet der, für den ein unlesbarer Regex der beste war, schickt seinen Namen so, dass man ihn lesen kann. Er wollte von Anfang an, dass ihn jemand liest.“

Die zwölf Fälle noch einmal gelesen

Am Nachmittag blättern die Direktorin und du alle zwölf Fallakten noch einmal von vorn durch. „Wie würden wir es heute schreiben?“

• CASE-001 Zahlungsdaten: statt Backslashes von Hand re.escape("$4.99").
• CASE-002 und 003 Kennzeichen und Telefonnummern: mit Quantoren kürzen wie in \d{2,3}[가-힣]\d{4}, prüfen mit fullmatch.
• CASE-004 Falsche Anmeldungen: nicht search, sondern re.fullmatch(r"[a-z][a-z0-9_]{3,15}", user_id).
• CASE-005 und 010 Datumsangaben: (?P<y>\d{4})(?P<sep>[-./])(?P<m>\d\d)(?P=sep)(?P<d>\d\d). Mit Namen muss man keine Nummern zählen.
• CASE-006 Zugriffslog: benannte Gruppen und groupdict(), um eine Zeile in ein dict zu verwandeln.
• CASE-007 Kundenliste: Ersetzen per Funktion und Schlüsselwortargumente wie count=.
• CASE-008 Die Herausforderung des Backtrackers: ^a+$ statt ^(a|aa)+$. Keine überlappenden Wiederholungen.
• CASE-009 Die Regeln des Tresors: ein Lookahead pro Bedingung und eine Kommentarzeile pro Bedingung.
• CASE-011 Der einzeilige Regex: mit re.X aufschreiben und mit re.compile benennen.
• CASE-012 Die verschlüsselte Nachricht: ein Tokenizer mit den Regeln als Liste, am Ende MISMATCH.

Spät in der Nacht kommt noch eine Mail. Diesmal ist sie nicht verschlüsselt.

Die Signatur hat sich geändert. Aus Gewohnheit steckst du sie ins Labor. Ohne die äußere Wiederholung zögert das Muster nicht einmal, wenn es scheitert.

sign = r"(?x) a+ $   # ich gehe nicht mehr zurück"
print(re.fullmatch(sign, "a" * 30 + "b"))   # None

Die Direktorin legt ihr altes Notizbuch auf deinen Schreibtisch. Von der ersten Seite an steht zu jedem Fall ihre Handschrift, dicht an dicht. „Das gehört jetzt dir. Nicht der kürzeste Regex gewinnt. Der lesbare gewinnt. Vergiss das nie.“

Übungen

1. Ergänze den Tokenizer aus 12-1 um = als ASSIGN und den Zeilenumbruch als NEWLINE, und zerlege damit zweizeiligen Code in Tokens: x = 3.5 und darunter y = x * 2.
2. Ergänze den Entschlüssler um ein Token aus \U mit acht Hexadezimalstellen und entschlüssle \U0000C11C\U0000C9C4.
3. Schreib eine Funktion, die ein Muster vom Benutzer entgegennimmt und bei einem Fehler unter dem Muster an der Stelle e.pos ein ^ anzeigt. Genau das macht das Beweislabor.