Come abbinare una stringa di una certa lunghezza con una regex

Question

Per un mio progetto, sto cercando di implementare una piccola parte del protocollo BitTorrent, che può essere trovato here. In particolare, voglio utilizzare la parte "Bencoding" di esso, che è un modo per codificare in modo sicuro i dati per il trasferimento su un socket. Il formato è il seguente:

parte

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

La codifica è stato abbastanza facile, ma la decodifica è diventato piuttosto una seccatura. Ad esempio, se ho una lista di stringhe, non ho modo di separarle in stringhe individuali. Ho provato diverse soluzioni, tra cui PyParsing e un parser di token personalizzato. Attualmente sto tentando di usare espressioni regex e sembra che stia andando abbastanza bene, ma sono ancora bloccato dal problema delle stringhe. La mia espressione regolare è:

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

Tuttavia, non riesco a utilizzare il primo gruppo come la lunghezza del secondo gruppo. C'è un buon modo per farlo? O mi sto avvicinando a questo tutto sbagliato, e la risposta è seduta proprio di fronte a me?

Answer 1

Qualsiasi parser si utilizza per questo sta andando ad avere bisogno di essere stateful (cioè ricordare roba), e espressioni regolari sono, in generale, non è stateful. Sono lo strumento sbagliato per questo lavoro.

Se questi sono gli unici tipi di dati di cui preoccuparsi, penso che scriverei parser personalizzati per ogni tipo di dati, passando il controllo al parser appropriato dopo aver letto il primo carattere.

In realtà ne implementerò uno ora, ma è tardi.

Va bene ho deciso di scrivere un'implementazione:

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

È possibile farlo se si analizza la stringa due volte. Applicare la prima espressione regolare per ottenere la lunghezza. Concatena la lunghezza della seconda espressione regolare per formare un'espressione valida.

Non so come questo possa essere fatto in pitone, ma un campione in C# sarebbe:

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

per abbinare 1 alla lunghezza non di caratteri che può essere alpanumeric o _ in cui la lunghezza è determinata da una precedente regex che recupera solo la lunghezza.

Spero che questo aiuti :)

Answer 3

Si utilizza lo strumento sbagliato per il lavoro ... Questo richiede una sorta di mantenimento dello stato, e in generale, le espressioni regolari sono apolidi .

---

Un esempio di implementazione di bdecoding (e bencoding) in Perl che ho fatto può essere trovato here.

Una spiegazione di come funziona quella funzione (dal momento che non ho mai fatto arrivare a commentarlo [oops]):

Fondamentalmente quello che dovete fare è impostare una funzione ricorsiva. Questa funzione prende un riferimento di stringa (quindi può essere modificato) e restituisce "qualcosa" (la natura di questo significa che potrebbe essere un array, un hashtable, un int o una stringa).

La funzione stessa solo controlla il primo carattere della stringa e decide cosa fare in base di che:

• Se si tratta di un i, quindi analizzare fuori tutto il testo tra il i e la prima e e prova ad analizzarlo come un int secondo le regole di ciò che è permesso.
• Se è una cifra, quindi leggere tutte le cifre fino a :, quindi leggere che molti caratteri fuori dalla stringa.

Liste e dizionari sono dove iniziano le cose a farsi interessante ... se c'è un l o d come primo carattere, quindi è necessario togliere il l/d, quindi passare la corrente ricollegarsi alla funzione, in modo che possa iniziare l'analisi degli elementi nell'elenco o nel dizionario. Quindi basta memorizzare i valori restituiti nelle posizioni appropriate in una struttura appropriata fino a quando non si preme un e e si restituisce la struttura che vi rimane.

Ricordare, la funzione come ho implementato era DISTRUTTIVO. La stringa passata è vuota quando la funzione ritorna perché viene passata per riferimento, o più accuratamente, sarà priva di qualsiasi cosa sia stata analizzata e restituita (motivo per cui può essere utilizzata in modo ricorsivo: tutto ciò che non viene elaborato rimane intatto). Tuttavia, nella maggior parte dei casi della chiamata iniziale, questo dovrebbe elaborare tutto a meno che tu non stia facendo qualcosa di strano, quindi quanto sopra.

Answer 4

Avrai voglia di farlo in due passi. Le espressioni regolari sono in realtà un po 'esagerate per problemi di analisi così semplici come questo. Ecco come lo farei:

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:] 

E 'un modo funzionale, in stile di parsing, restituisce il valore analizzato e il resto del torrente.

Per le liste, forse:

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 

E allora si sarebbe definito un READ_OBJECT che controlla il primo carattere del flusso e invia in modo appropriato.

Answer 5

pseudo-codice, senza controlli di sintassi:

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)