Wie man einen String einer bestimmten Länge mit einem Regex vergleicht

Question

Für ein Projekt von mir versuche ich, einen kleinen Teil des BitTorrent-Protokolls zu implementieren, das here gefunden werden kann. Insbesondere möchte ich den "Bencoding" -Teil verwenden, der eine Möglichkeit bietet, Daten für die Übertragung über einen Socket sicher zu verschlüsseln. Das Format ist wie folgt:

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

Der kodierende Teil leicht genug war, aber Decodierung ziemlich lästig werden. Zum Beispiel, wenn ich eine Liste von Strings habe, habe ich keine Möglichkeit, sie in einzelne Strings zu trennen. Ich habe mehrere verschiedene Lösungen ausprobiert, einschließlich PyParsing und einen benutzerdefinierten Token-Parser. Ich versuche gerade, Regexes zu benutzen, und es scheint ziemlich gut zu laufen, aber ich bin immer noch am String Problem hängen. Meine aktuelle Regex ist:

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

Allerdings kann ich nicht scheinen, die erste Gruppe als die Länge der zweiten Gruppe zu verwenden. Gibt es einen guten Weg, dies zu tun? Oder gehe ich das alles falsch an, und die Antwort sitzt direkt vor mir?

Answer 1

Jeder Parser Sie für diesen Einsatz wird gehen zu müssen, Stateful sein (das heißt Sachen erinnern), und reguläre Ausdrücke sind, im Großen und Ganzen nicht Stateful. Sie sind das falsche Werkzeug für diesen Job.

Wenn dies die einzigen Datentypen sind, um die Sie sich Gedanken machen müssen, würde ich einfach benutzerdefinierte Parser für jeden Datentyp schreiben und die Kontrolle an den entsprechenden Parser übergeben, nachdem ich das erste Zeichen gelesen habe.

Ich würde tatsächlich eine jetzt implementieren, aber es ist spät.

Okay habe ich beschlossen, eine Implementierung zu schreiben:

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

Sie können es tun, wenn Sie die Zeichenfolge zweimal analysieren. Übernehmen Sie die erste Regex, um die Länge zu erhalten. Verketten Sie die Länge in Ihrer zweiten Regex, um einen gültigen Ausdruck zu bilden.

nicht sicher, wie das in Python getan werden, aber eine Probe in C# wäre:

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

1 ohne von Zeichen auf Länge entsprechen, die alpanumeric sein kann oder _ wobei die Länge von einem frühen bestimmt wird Regex, die nur die Länge abruft.

this helps :)

Answer 3

Sie sind das falsche Werkzeug für den Job ... Diese eine Art Zustand zu halten erfordert, und allgemein gesprochen, reguläre Ausdrücke sind staatenlos .

---

Eine beispielhafte Implementierung von bdecoding (und bencoding) in PERL, die ich here gefunden haben kann.

Eine Erklärung, wie diese Funktion arbeitet (da ich nie bekommen habe zu kommentieren [oops]):

Im Grunde, was Sie tun müssen, ist Setup eine rekursive Funktion. Diese Funktion benötigt eine String-Referenz (damit sie geändert werden kann) und gibt "something" zurück (das bedeutet, dass es ein Array, eine Hashtable, ein int oder eine Zeichenkette sein könnte).

Die Funktion selbst nur das erste Zeichen in der Zeichenfolge prüft und entscheidet, was davon zu tun basiert:

• Wenn es ein i ist, dann den Text all zwischen den i analysieren und den ersten e, und versuchen Sie es als int nach den Regeln zu analysieren, was erlaubt ist.
• Wenn es eine Ziffer ist, dann lesen Sie alle Ziffern bis :, dann lesen Sie, dass viele Zeichen aus der Zeichenfolge.

Listen und Wörterbücher werden, wo die Dinge beginnen, interessant zu werden ... wenn es eine ist l oder d als erstes Zeichen, dann müssen Sie die l/d abzustreifen, dann den Strom passieren String zurück in die Funktion, damit es Elemente in der Liste oder im Wörterbuch analysieren kann. Dann speichern Sie einfach die zurückgegebenen Werte an den entsprechenden Stellen in einer geeigneten Struktur, bis Sie eine e treffen, und geben Sie die Struktur zurück, die Sie übrig haben.

Denken Sie daran, die Funktion, wie ich es implementierte, war DESTRUCTIVE. Die übergebene Zeichenkette ist leer, wenn die Funktion zurückkehrt, weil sie als Referenz übergeben wird, oder genauer gesagt, sie wird nichts geparst und zurückgegeben (weshalb sie rekursiv verwendet werden kann: alles, was sie nicht verarbeitet, bleibt übrig unberührt). In den meisten Fällen des ersten Anrufs sollte dies jedoch alles verarbeiten, es sei denn, Sie haben etwas Seltsames gemacht, also gilt das obige.

Answer 4

Sie möchten dies in zwei Schritten tun. Reguläre Ausdrücke sind eigentlich ein wenig übertrieben für so einfache Parsing-Probleme. Hier ist, wie ich es tun würde:

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 ist ein funktionaler Stil Art und Weise des Parsing, es gibt den analysierten Wert und den Rest des Stroms.

Für Listen, vielleicht:

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 

Und dann würden Sie einen read_object definieren, die das erste Zeichen des Stroms überprüft und die Versendungen in geeigneter Weise.

Answer 5

Pseudo-Code, ohne Syntaxprüfung:

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)