Cómo hacer coincidir una cadena de cierta longitud con una expresión regular

Question

Para un proyecto mío, estoy tratando de implementar una pequeña parte del protocolo BitTorrent, que se puede encontrar en here. Específicamente, quiero usar la parte de "Bencode", que es una forma de codificar de forma segura los datos para transferirlos a través de un socket. El formato es el siguiente:

8:a string => "a string" 
i1234e => 1234 
l1:a1:be => ['a', 'b'] 
d1:a1:b3:one3:twoe => {'a':'b', 'one':two} 

la parte de codificación fue bastante fácil, pero la decodificación se convierta en una molestia. Por ejemplo, si tengo una lista de cadenas, no tengo manera de separarlas en cadenas individuales. He intentado varias soluciones diferentes, incluyendo PyParsing y un analizador de tokens personalizado. Actualmente estoy tratando de usar expresiones regulares, y parece estar yendo bastante bien, pero todavía estoy pendiente del problema de la secuencia. Mi expresión regular actual es:

(?P<length>\d+):(?P<contents>.{\1}) 

Sin embargo, me parece que no puede utilizar el primer grupo que la longitud del segundo grupo. ¿Hay alguna buena manera de hacer esto? ¿O me estoy equivocando y la respuesta está frente a mí?

Answer 1

Cualquier analizador utiliza para esto va a tener que ser con estado (es decir, recordar cosas), y expresiones regulares son, por lo general, no con estado. Son la herramienta incorrecta para este trabajo.

Si esos son los únicos tipos de datos que debe preocuparse, creo que simplemente escribiría analizadores personalizados para cada tipo de datos, pasando el control al analizador apropiado después de leer el primer carácter.

De hecho, implementaría uno ahora, pero es tarde.

bien que decidí escribir una implementación:

from StringIO import StringIO 
import string 

inputs = ["10:a stringly", 
     "i1234e" , 
     "l1:a1:be", 
     "d1:a1:b3:one3:twoe"] 

# Constants 
DICT_TYPE = 'd' 
LIST_TYPE = 'l' 
INT_TYPE = 'i' 
TOKEN_EOF = '' 
TOKEN_END = 'e' 
COLON  = ':' 


class BadTypeIndicatorException(Exception):pass 


def read_int(stream): 

    s = "" 

    while True: 
     ch = stream.read(1) 
     if ch not in [TOKEN_EOF, TOKEN_END, COLON]: 
     s += ch 
     else: 
     break 

    return s 


def tokenize(stream): 

    s = "" 

    while True: 

     ch = stream.read(1) 

     if ch == TOKEN_END or ch == TOKEN_EOF: 
     return 

     if ch == COLON: 
     length = int(s) 
     yield stream.read(length) 
     s = "" 

     else: 
     s += ch 


def parse(stream): 

    TYPE = stream.read(1) 

    if TYPE in string.digits: 
     length = int(TYPE + read_int(stream)) 
     return stream.read(length) 

    elif TYPE is INT_TYPE: 
     return int(read_int(stream)) 

    elif TYPE is LIST_TYPE: 
     return list(tokenize(stream)) 

    elif TYPE is DICT_TYPE: 
     tokens = list(tokenize(stream)) 
     return dict(zip(tokens[0::2], tokens[1::2])) 

    else: 
     raise BadTypeIndicatorException 



for input in inputs: 
    stream = StringIO(input) 
    print parse(stream) 

Answer 2

Puede hacerlo si analiza la cadena dos veces. Aplica la primera expresión regular para obtener la longitud. Concatenar la longitud en su segunda expresión regular para formar una expresión válida.

No estoy seguro de cómo esto se puede hacer en Python, pero una muestra en C# sería:

string regex = "^[A-Za-z0-9_]{1," + length + "}$" 

para que coincida con 1 a longitud ningún de caracteres que puede ser alpanumeric o _ donde la longitud se determina a partir de una previa regex que recupera solo la longitud.

Espero que esto ayude :)

Answer 3

Está utilizando la herramienta equivocada para el trabajo ... Esto requiere algún tipo de mantenimiento de estado, y en general, las expresiones regulares son apátridas .

---

Un ejemplo de aplicación bdecoding (y bencoding) en Perl que hice se puede encontrar here.

Una explicación de cómo funciona esa función (ya que nunca tuvimos la oportunidad de comentar que [Uy]):

Básicamente lo que hay que hacer es configurar una función recursiva. Esta función toma una referencia de cadena (por lo que puede modificarse) y devuelve "algo" (la naturaleza de esto significa que podría ser una matriz, una tabla hash, una int o una cadena).

la propia función se limita a comprobar el primer carácter de la cadena y decide qué hacer basado de que:

• Si se trata de un i, a continuación, analizar todo el texto entre el i y la primera e, y tratar de analizarlo como un int de acuerdo con las reglas de lo permitido.
• Si es un dígito, entonces lea todos los dígitos hasta :, luego lea esos caracteres fuera de la cadena.

listas y diccionarios son donde empiezan las cosas que se ponen interesantes ... si hay un l o d como primer carácter, entonces usted necesita para quitarse el l/d, a continuación, pasar la corriente vuelva a la función para que pueda comenzar a analizar elementos en la lista o el diccionario. A continuación, solo almacene los valores devueltos en los lugares apropiados en una estructura adecuada hasta que llegue a e y devuelva la estructura que le queda.

Recuerde, la función como la implementé fue DESTRUCTIVA. La secuencia que se pasa está vacía cuando la función regresa debido a que se pasa por referencia, o más exactamente, estará desprovista de todo lo que se haya analizado y devuelto (por lo que puede usarse recursivamente: se deja todo lo que no se procesa intacto). Sin embargo, en la mayoría de los casos de la llamada inicial, esto debería procesar todo a menos que haya estado haciendo algo extraño, por lo que lo anterior es válido.

Answer 4

Querrá hacer esto en dos pasos. Las expresiones regulares son en realidad un poco exageradas para problemas de análisis tan simples como este. Así es como yo lo haría:

def read_string(stream): 
    pos = stream.index(':') 
    length = int(stream[0:pos]) 
    string = stream[pos+1:pos+1+length] 
    return string, stream[pos+1+length:] 

Es una forma de estilo funcional de análisis, se devuelve el valor analizado y el resto de la corriente.

Para las listas, tal vez:

def read_list(stream): 
    stream = stream[1:] 
    result = [] 
    while stream[0] != 'e': 
     obj, stream = read_object(stream) 
     result.append(obj) 
    stream = stream[1:] 
    return result 

Y entonces lo que define una READ_OBJECT que comprueba el primer carácter de la corriente y despacha de manera apropiada.

Answer 5

Pseudocódigo, sin comprobaciones de sintaxis:

define read-integer (stream): 
    let number 0, sign 1: 
     if string-equal ('-', (c <- read-char (stream))): 
      sign <- -1 
      else: 
      number <- parse-integer (c) 
     while number? (c <- read-char (stream)): 
      number <- (number * 10) + parse-integer (c) 
     return sign * number 

define bdecode-string (stream): 
    let count read-integer (stream): 
     return read-n-chars (stream, count) 

define bdecode-integer (stream): 
    ignore read-char (stream) 
    return read-integer (stream) 

define bdecode-list (stream): 
    ignore read-char (stream) 
    let list []: 
     while not string-equal ('e', peek-char (stream)): 
      append (list, bdecode (stream)) 
     return list 

define bdecode-dictionary (stream): 
    let list bdecode-list stream: 
     return dictionarify (list) 

define bdecode (stream): 
    case peek-char (stream): 
     number? => bdecode-string (stream) 
     'i' => bdecode-integer (stream) 
     'l' => bdecode-list (stream) 
     'd' => bdecode-dictionary (stream)