Как сопоставить строку определенной длины с регулярным выражением

Question

Для моего проекта я пытаюсь реализовать небольшую часть протокола BitTorrent, которую можно найти здесь . В частности, я хочу использовать часть «Bencoding», которая является способом безопасного кодирования данных для передачи через сокет. Формат выглядит следующим образом:

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

Кодирование было достаточно простым, но декодирование стало довольно сложным делом. Например, если у меня есть список строк, у меня нет возможности разделить их на отдельные строки. Я пробовал несколько разных решений, включая PyParsing и собственный анализатор токенов. В настоящее время я пытаюсь использовать регулярные выражения, и, похоже, все идет хорошо, но я все еще зациклен на проблеме со строками. Мой текущий регулярное выражение:

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

Однако я не могу использовать первую группу в качестве длины второй группы. Есть ли хороший способ сделать это? Или я все это неправильно подхожу, а ответ сидит прямо передо мной?

Answer 1

Любой парсер, который вы используете для этого, должен быть с состоянием (то есть запоминать вещи), а регулярные выражения в общем случае не с состоянием. Они не тот инструмент для этой работы.

Если это единственные типы данных, о которых вам нужно беспокоиться, я думаю, что я бы просто написал пользовательские парсеры для каждого типа данных, передавая управление соответствующему парсеру после чтения первого символа.

Я бы на самом деле реализовал один сейчас, но уже поздно.

Хорошо, я решил написать реализацию:

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

Вы хотите сделать это в два этапа. Регулярные выражения на самом деле немного излишни для таких простых задач анализа, как эта. Вот как я это сделаю:

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

Это способ синтаксического анализа, возвращающий проанализированное значение и остаток потока.

Для списков, возможно:

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

И тогда вы определите объект read_object, который проверяет первый символ потока и отправляет его соответствующим образом.

Answer 3

Вы можете сделать это, если проанализируете строку дважды. Примените первое регулярное выражение, чтобы получить длину. Объедините длину во втором регулярном выражении, чтобы сформировать правильное выражение.

Не уверен, как это можно сделать в Python, но пример в C # будет:

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

Чтобы сопоставить 1 с длиной без символов, которые могут быть буквенно-цифровыми или _, где длина определяется из предыдущего регулярного выражения, которое извлекает только длину.

Надеюсь, это поможет:)

Answer 4

Псевдокод, без проверки синтаксиса:

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)

Answer 5

Вы используете неправильный инструмент для работы ... Это требует некоторого сохранения состояния, и, вообще говоря, регулярные выражения не сохраняют состояния.

---

Пример реализации bdecoding (и bencoding) в PERL, который я сделал, можно найти здесь .

Объяснение того, как работает эта функция (поскольку я так и не смог ее прокомментировать [упс]):

По сути, вам нужно настроить рекурсивную функцию. Эта функция принимает строковую ссылку (поэтому ее можно изменить) и возвращает «что-то» (природа этого означает, что это может быть массив, хеш-таблица, целое число или строка).

Сама функция просто проверяет первый символ в строке и решает, что делать на основании этого:

• Если это i, то проанализируйте весь текст между i и первым e и попытайтесь проанализировать его как int в соответствии с правилами что разрешено.
• Если это цифра, то читать все цифры до : , а затем читать столько символов из строки.

Списки и словари - вот где все становится интересным ... если в качестве первого символа указан l или d , то вам необходимо удалить l / d, затем передайте текущую строку обратно в функцию, чтобы она могла начать анализ элементов в списке или словаре. Затем просто сохраните возвращенные значения в соответствующих местах в соответствующей структуре, пока не достигнете e, и вернитесь к структуре, с которой вы остались.

Помните, что функция, которую я реализовал, была ДЕСТРУКТИВНОЙ. Переданная строка пуста, когда функция возвращается из-за того, что она была передана по ссылке, или, точнее, она будет лишена всего, что она проанализировала и вернула (поэтому она может использоваться рекурсивно: все, что она не обрабатывает, остается нетронутый). В большинстве случаев при первоначальном вызове это должно обрабатывать все, если вы не делаете что-то странное, так что вышеприведенное верно.