Comment faire correspondre une chaîne d'une certaine longueur avec une expression régulière

Question

Pour un de mes projets, j'essaye d'implémenter une petite partie du protocole BitTorrent, qui peut être trouvé here. Plus précisément, je veux utiliser la partie "Bencoding", qui est un moyen de coder en toute sécurité des données pour un transfert sur une socket. Le format est le suivant:

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

La partie de codage était assez facile, mais le décodage est devenu un problème. Par exemple, si j'ai une liste de chaînes, je n'ai aucun moyen de les séparer en chaînes individuelles. J'ai essayé plusieurs solutions différentes, y compris PyParsing et un analyseur de jeton personnalisé. J'essaie actuellement d'utiliser des regex, et ça semble aller plutôt bien, mais je suis toujours accroché au problème des cordes. Mon regex actuel est:

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

Cependant, je ne peux pas sembler utiliser le premier groupe comme la longueur du deuxième groupe. Y a-t-il un bon moyen de le faire? Ou est-ce que je m'approche de tout cela, et la réponse est assise juste en face de moi?

Answer 1

Tout analyseur que vous utilisez pour cela va devoir être stateful (à savoir se souvenir des choses), et regexes sont, en gros, pas stateful. Ils sont le mauvais outil pour ce travail. Si ce sont les seuls types de données dont vous avez à vous soucier, je pense que j'écrirais simplement des analyseurs personnalisés pour chaque type de données, en passant le contrôle à l'analyseur approprié après avoir lu le premier caractère.

Je l'implémenterais en ce moment, mais il est tard.

Bon j'ai décidé d'écrire une implémentation:

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

Vous pouvez le faire si vous analysez deux fois la chaîne. Appliquez la première regex pour obtenir la longueur. Concaténer la longueur dans votre deuxième regex pour former une expression valide.

Je ne sais pas comment cela peut être fait en python, mais un échantillon en C# serait:

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

Pour correspondre 1 à longueur non de caractères qui peut être alpanumeric ou _ où la longueur est déterminée à partir d'une précédente regex qui récupère seulement la longueur.

Hope this helps :)

Answer 3

Vous utilisez le mauvais outil pour le travail ... Cela exige une sorte de maintien de l'Etat, et d'une manière générale, les expressions régulières sont apatrides .

---

Un exemple de mise en œuvre bdecoding (et bencoding) en PERL que je l'ai peut être trouvé here.

Une explication de la façon dont fonctionne cette fonction (puisque je ne ai jamais eu à le commenter [oups]):

Fondamentalement, ce que vous devez faire est de configurer une fonction récursive. Cette fonction prend une référence de chaîne (donc elle peut être modifiée) et retourne "quelque chose" (la nature de ceci signifie qu'il peut s'agir d'un tableau, d'une table de hachage, d'un int ou d'une chaîne).

La fonction elle-même vérifie que le premier caractère de la chaîne et décide quoi faire en fonction de ce qui suit:

• Si c'est un i, puis analyser tout le texte entre les i et le premier e, et essayez de l'analyser comme un int selon les règles de ce qui est autorisé.
• S'il s'agit d'un chiffre, lisez tous les chiffres jusqu'à :, puis lisez autant de caractères de la chaîne.

listes et les dictionnaires sont où les choses commencent à devenir intéressantes ... s'il y a un l ou d comme premier caractère, alors vous devez dépouiller le l/d, puis passer le courant renvoyer la chaîne dans la fonction, afin qu'elle puisse commencer à analyser les éléments de la liste ou du dictionnaire. Ensuite, il suffit de stocker les valeurs retournées dans les endroits appropriés dans une structure appropriée jusqu'à ce que vous frappez un e, et renvoyez la structure qui vous reste. Rappelez-vous, la fonction que j'ai implémentée était DESTRUCTIVE. La chaîne transmise est vide quand la fonction retourne parce qu'elle est passée par référence, ou plus exactement, elle sera dépourvue de tout ce qu'elle a analysé et retourné (c'est pourquoi elle peut être utilisée récursivement: tout ce qu'elle ne traite pas est laissé intacte). Cependant, dans la plupart des cas, l'appel initial devrait tout traiter à moins que vous n'ayez fait quelque chose d'étrange.

Answer 4

Vous aurez besoin de faire cela en deux étapes. Les expressions régulières sont en fait un peu exagérées pour des problèmes d'analyse aussi simples que celui-ci. Voici comment je le ferais:

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

C'est un moyen de style fonctionnel de l'analyse syntaxique, elle renvoie la valeur et le reste analysable du cours d'eau.

Pour les listes, peut-être:

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 

Et alors vous définissez un READ_OBJECT qui vérifie le premier caractère du flux et envoie de manière appropriée.

Answer 5

pseudo-code, sans vérification de syntaxe:

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)