El Backtracker, desenmascarado: repaso y un tokenizador

Las nueve de la mañana. La agencia está llena. El inspector Kang espera de pie junto a la puerta, la señora Jeong ha abierto su libreta y el periodista Oh tiene la laptop sobre las rodillas. La directora gira el monitor para que todos lo vean. «Hoy lo leemos entre todos. Carácter a carácter».

Este es el mensaje cifrado que llegó al correo:

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

El periodista Oh niega con la cabeza. «Esto no son letras, son símbolos sin más». La directora responde: «Los símbolos también tienen reglas. Si las escribes una por una, la máquina lo lee por ti».

Un programa que parte un texto largo en trozos con significado (tokens) se llama tokenizador. Hoy vamos a reunir todo lo aprendido para construir un tokenizador y descifrar este mensaje.

12-1. Un tokenizador: grupos con nombre unidos con | (12 min)

Primero, para practicar, partamos una expresión de cálculo como 3.5*(2 + x). La estructura es la misma que la del ejemplo «Writing a Tokenizer» de la documentación oficial de Python.

import re

TOKEN_SPEC = [
    ("NUMBER",   r"\d+(?:\.\d*)?"),   # entero o decimal
    ("ID",       r"[A-Za-z_]\w*"),    # nombre
    ("OP",       r"[+\-*/]"),         # operador
    ("LPAR",     r"\("),
    ("RPAR",     r"\)"),
    ("SKIP",     r"[ \t]+"),          # los espacios se descartan
    ("MISMATCH", r"."),               # cualquier otro carácter: desconocido
]
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', ')')]

El mensaje de error está en coreano: 모르는 글자 significa «carácter desconocido» y 위치, «posición». La estructura se reduce a tres cosas:

• Un grupo con nombre por regla, (?P<nombre>regla), todos unidos con |. Como las reglas están escritas en una lista, es fácil leerlas y cambiarlas.
• finditer las va capturando de una en una desde el principio, y m.lastgroup (lección 6) te da el nombre de la regla que capturó.
• El MISMATCH del final es un solo .. Ahí se atrapa cualquier carácter que no encaje en ninguna regla.

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

¿Y si no hubiera MISMATCH? finditer se salta en silencio los caracteres que no coinciden. Aunque el mensaje tuviera un carácter extraño, pasaría sin que te enteraras.

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

| prueba de izquierda a derecha, así que el orden es la prioridad. Si pones delante una regla amplia, las reglas más estrechas nunca tienen su oportunidad.

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

12-2. Escapes de caracteres dentro del patrón (8 min)

Cosas como \x46 o \uc11c del mensaje se llaman escapes de caracteres. re entiende directamente dentro del patrón casi todos los escapes de las cadenas de Python. Por eso, aunque escribas la cadena raw r"\t", encuentra el tabulador.

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

• Caracteres de control: \t (tabulador), \n (salto de línea), \r, \f, \v, \a (campana), y la propia barra invertida, \\.
• Hexadecimal: \x41 (dos cifras), \u00e9 (cuatro), \U0001F600 (ocho).
• Por nombre: con el nombre Unicode del carácter, como \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

También hay octal. Es un carácter octal si empieza por \0 o tiene tres cifras (como viste en la lección 10, \10 es un número de grupo). Y \b solo es el carácter de retroceso (backspace) dentro de una clase.

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

En cambio, los escapes de letras que no tienen significado asignado son un error. Son huecos reservados para darles un significado nuevo en el futuro.

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

12-3. Gestionar errores de patrón: re.error (8 min)

Los mensajes que aparecen en el recuadro rojo de error del laboratorio vienen de una excepción llamada re.error. Desde la 3.13 también existe el nombre re.PatternError, y los dos son la misma excepción. El objeto de la excepción contiene qué está mal y dónde.

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

Si el patrón ocupa varias líneas, son útiles lineno (número de línea) y colno (número de columna). Se cuentan desde 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

Un patrón que escribe una persona puede estar mal en cualquier momento. Un programa que recibe patrones, como un buscador, siempre debe envolverlos en try/except. En la salida, 패턴 오류 significa «error de patrón».

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)

Eso sí, try/except solo te protege de los errores de sintaxis. Un patrón como (a+)+$, sintácticamente correcto pero lento, se queda colgado sin lanzar ninguna excepción (lección 8). Por eso el Laboratorio de pruebas ejecuta los patrones en un trabajador aparte y, si se pasa de tiempo, lo sustituye por otro.

12-4. Patrones bytes (7 min)

Los datos leídos de un archivo o de la red a veces no son str, sino bytes. Para bytes se usan patrones bytes, como rb"...". str y bytes no se pueden mezclar.

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

En un patrón bytes, \w, \d y \s solo ven ASCII. El hangul está repartido en varios bytes, así que no se reconoce como letras. Para trabajar con hangul, primero conviértelo en str con decode().

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

Con los flags pasa al revés: re.L solo se puede usar con patrones bytes (lección 11) y re.U da error con un patrón bytes.

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. Avisos y herramientas ocultas (5 min)

En la lección 2 te dije que evitaras [[, --, &&, ~~ y || dentro de una clase. Están reservados para futuras «operaciones de conjuntos» y, de momento, lanzan un FutureWarning. Si los quieres como caracteres literales, escápalos.

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]")   # sin aviso

El módulo re también tiene herramientas internas que no aparecen en la documentación oficial: re.Scanner (una clase que construye un tokenizador por ti), Pattern.scanner() y Match.regs (los span de todos los grupos). Basta con que sepas que existen. Lo que no está documentado puede cambiar en cualquier momento, así que en código real usa el método finditer + lastgroup que has construido hoy.

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

Caso resuelto (10 min)

Ahora escribe las reglas del mensaje cifrado: cuatro tipos de escape de caracteres, la firma, los espacios y el MISMATCH que tapa los huecos. Como aprendiste en la lección 11, despliégalo con re.X y ponle comentarios.

import unicodedata

CIPHER = re.compile(r'''
    (?P<HEX>   \\x [0-9a-fA-F]{2} )    # \x46    dos cifras hexadecimales
  | (?P<UNI>   \\u [0-9a-fA-F]{4} )    # \uc11c  cuatro cifras hexadecimales
  | (?P<NAME>  \\N \{ [A-Z -]+ \} )    # \N{...} nombre del carácter
  | (?P<OCT>   \\ [0-7]{3} )           # \060    tres cifras octales
  | (?P<SIGN>  \(a\+\)\+\$ )           # la firma; igual que re.escape("(a+)+$")
  | (?P<SPACE> [ \n]+ )                # espacios y saltos de línea, tal cual
  | (?P<MISMATCH> . )                  # cualquier otro carácter es sospechoso
''', 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

Recuerda que, incluso con re.X, se conservan los espacios dentro de las clases [A-Z -] y [ \n]. La firma, SIGN, se descarta sin imprimir nada. (모르는 토큰 significa «token desconocido».)

También puedes preguntarle directamente a re si los caracteres descifrados son correctos. La primera línea del mensaje es, por sí misma, una regex válida, porque re entiende los mismos escapes.

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

F-02 = 서진. 서진 es un nombre coreano: Seo Jin. 4.ª planta, las 3:02 de la madrugada. Exactamente la misma hora que el registro de accesos de la lección 11.

El inspector Kang pregunta: «¿Quién es Seo Jin?». La directora saca del cajón el marco que había dejado boca abajo y lo pone de pie sobre el escritorio. Es una foto de dos jóvenes bajo el cartel de esta misma agencia.

«El que fundó Grep & Co. conmigo. La F-02 era su tarjeta». La directora señala con la yema del dedo al hombre de la foto. «Era un genio. Lo escribía todo en regex de una sola línea. Nadie podía leer su código y nadie podía arreglarlo. Así que fuimos desplegándolo trozo a trozo… y él debió de pensar que lo estábamos borrando a él. Un día se fue y solo dejó la tarjeta».

«¿Y por qué no anuló la tarjeta?» En lugar de responder, la directora mira la última línea de la pantalla, (a+)+$. «El que decía que la mejor regex es la que nadie puede leer nos ha enviado su nombre de forma que se pueda leer. Desde el principio quería que alguien lo leyera».

Releyendo los doce casos

Esa tarde, la directora y tú repasan desde el principio los doce expedientes. «¿Cómo lo escribiríamos ahora?»

• CASE-001, el registro de pagos: en lugar de poner barras invertidas a mano, re.escape("$4.99").
• CASE-002 y 003, matrículas y teléfonos: acortar con cuantificadores, como \d{2,3}[가-힣]\d{4}, y validar con fullmatch.
• CASE-004, los registros falsos: no search, sino re.fullmatch(r"[a-z][a-z0-9_]{3,15}", user_id).
• CASE-005 y 010, las fechas: (?P<y>\d{4})(?P<sep>[-./])(?P<m>\d\d)(?P=sep)(?P<d>\d\d). Con nombres, no hace falta contar números.
• CASE-006, el log de accesos: cada línea a un dict con grupos con nombre y groupdict().
• CASE-007, la lista de clientes: reemplazo con función y argumentos con nombre como count=.
• CASE-008, el desafío del Backtracker: ^a+$ en lugar de ^(a|aa)+$. Nada de repeticiones solapadas.
• CASE-009, las reglas de la caja fuerte: un lookahead por condición, y un comentario por condición.
• CASE-011, la regex de una línea: desplegarla con re.X y ponerle nombre con re.compile.
• CASE-012, el mensaje cifrado: un tokenizador con las reglas en una lista y, al final, MISMATCH.

Ya de noche, llega otro correo. Esta vez no está cifrado.

La firma ha cambiado. Por costumbre, la metes en el laboratorio. Sin la repetición exterior, el patrón no titubea ni siquiera cuando falla.

sign = r"(?x) a+ $   # ya no vuelvo atrás"
print(re.fullmatch(sign, "a" * 30 + "b"))   # None

La directora deja su viejo cuaderno sobre tu escritorio. Desde la primera página, cada caso está lleno de su letra. «Ahora es tuyo. No gana la regex más corta. Gana la que se puede leer. No lo olvides».

Ejercicios

1. Añade al tokenizador de 12-1 el = como ASSIGN y el salto de línea como NEWLINE, y parte en tokens un código de dos líneas: x = 3.5 y, en la línea siguiente, y = x * 2.
2. Añade al descifrador un token para \U seguido de ocho cifras hexadecimales y descifra \U0000C11C\U0000C9C4.
3. Escribe una función que pida un patrón al usuario y, si hay un error, muestre una ^ debajo del patrón, en la posición e.pos. Es lo mismo que hace el Laboratorio de pruebas.