Сторнирование регулярного выражения в Python

Question

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

Я знаю, как сделать это на основе теоретической информатики, используя конечный автомат, но я просто хочу знать, написал ли кто-нибудь библиотеку для этого. :)

Я использую Python, поэтому мне нужна библиотека Python.

Повторюсь, я хочу только одну строку, которая будет соответствовать регулярному выражению. Вещи как "." или ". *" приведет к тому, что бесконечное количество строк будет соответствовать регулярному выражению, но мне не нужны все параметры.

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

Answer 1

У кого-то еще был похожий (дубликат?) Вопрос здесь , и я хотел бы предложить небольшую вспомогательную библиотеку для генерации случайных строк с Python , над которым я работал на.

Включает метод xeger(), который позволяет создать строку из регулярного выражения:

>>> import rstr
>>> rstr.xeger(r'[A-Z]\d[A-Z] \d[A-Z]\d')
u'M5R 2W4'

Сейчас он работает с большинством основных регулярных выражений, но я уверен, что его можно улучшить.

Answer 2

Хотя я не вижу особого смысла в этом, вот что:

import re
import string

def traverse(tree):
    retval = ''
    for node in tree:
        if node[0] == 'any':
            retval += 'x'
        elif node[0] == 'at':
            pass
        elif node[0] in ['min_repeat', 'max_repeat']:
            retval += traverse(node[1][2]) * node[1][0]
        elif node[0] == 'in':
            if node[1][0][0] == 'negate':
                letters = list(string.ascii_letters)
                for part in node[1][1:]:
                    if part[0] == 'literal':
                        letters.remove(chr(part[1]))
                    else:
                        for letter in range(part[1][0], part[1][1]+1):
                            letters.remove(chr(letter))
                retval += letters[0]
            else:
                if node[1][0][0] == 'range':
                    retval += chr(node[1][0][1][0])
                else:
                    retval += chr(node[1][0][1])
        elif node[0] == 'not_literal':
            if node[1] == 120:
                retval += 'y'
            else:
                retval += 'x'
        elif node[0] == 'branch':
            retval += traverse(node[1][1][0])
        elif node[0] == 'subpattern':
            retval += traverse(node[1][1])
        elif node[0] == 'literal':
            retval += chr(node[1])
    return retval

print traverse(re.sre_parse.parse(regex).data)

Я взял все от Синтаксиса регулярных выражений до групп - это кажется разумным подмножеством - и я проигнорировал некоторые детали, такие как окончания строк. Обработка ошибок и т. Д. Оставлена ​​читателю в качестве упражнения.

Из 12 специальных символов в регулярном выражении мы можем полностью игнорировать 6 (2 даже с атомом, к которому они применяются), 4,5 приводят к тривиальной замене, а 1,5 заставляют нас думать.

То, что из этого получается, не слишком интересно, я думаю.

Answer 3

Я не знаю ни одного модуля для этого. Если вы не найдете ничего подобного в Кулинарной книге или PyPI, вы можете попробовать развернуть свой собственный, используя (недокументированный) модуль re.sre_parse. Это может помочь вам начать:

In [1]: import re

In [2]: a = re.sre_parse.parse("[abc]+[def]*\d?z")

In [3]: a
Out[3]: [('max_repeat', (1, 65535, [('in', [('literal', 97), ('literal', 98), ('literal', 99)])])), ('max_repeat', (0, 65535, [('in', [('literal', 100), ('literal', 101), ('literal', 102)])])), ('max_repeat', (0, 1, [('in', [('category', 'category_digit')])])), ('literal', 122)]

In [4]: eval(str(a))
Out[4]: 
[('max_repeat',
  (1, 65535, [('in', [('literal', 97), ('literal', 98), ('literal', 99)])])),
 ('max_repeat',
  (0,
   65535,
   [('in', [('literal', 100), ('literal', 101), ('literal', 102)])])),
 ('max_repeat', (0, 1, [('in', [('category', 'category_digit')])])),
 ('literal', 122)]

In [5]: a.dump()
max_repeat 1 65535
  in
    literal 97
    literal 98
    literal 99
max_repeat 0 65535
  in
    literal 100
    literal 101
    literal 102
max_repeat 0 1
  in
    category category_digit
literal 122

Answer 4

Если ваше регулярное выражение не является чрезвычайно простым (то есть без звездочек или плюсов), будет бесконечно много строк, которые ему соответствуют. Если ваше регулярное выражение включает только объединение и чередование, то вы можете расширить каждое чередование на все его возможности, например, (foo|bar)(baz|quux) можно развернуть в список ['foobaz', 'fooquux', 'barbaz', 'barquux'].

Answer 5

Проверьте преобразователь регулярных выражений на UtilityMill . (Исходный код можно просмотреть, основываясь на в этом примере из вики-приложения pyparsing.)

Answer 6

В то время как другие ответы используют re-engine для анализа элементов, которые я собрал, мои собственные, которые анализируют re и возвращают минимальный шаблон, который будет соответствовать. (Обратите внимание, что он не обрабатывает [^ ads], причудливые конструкции группировки, специальные символы начала / конца строки). Я могу поставить модульные тесты, если вам действительно нравится:)

import re
class REParser(object):
"""Parses an RE an gives the least greedy value that would match it"""

 def parse(self, parseInput):
    re.compile(parseInput) #try to parse to see if it is a valid RE
    retval = ""
    stack = list(parseInput)
    lastelement = ""
    while stack:
        element = stack.pop(0) #Read from front
        if element == "\\":
            element = stack.pop(0)
            element = element.replace("d", "0").replace("D", "a").replace("w", "a").replace("W", " ")
        elif element in ["?", "*"]:
            lastelement = ""
            element = ""
        elif element == ".":
            element = "a"
        elif element == "+":
            element = ""
        elif element == "{":
            arg = self._consumeTo(stack, "}")
            arg = arg[:-1] #dump the }     
            arg = arg.split(",")[0] #dump the possible ,
            lastelement = lastelement * int(arg)
            element = ""
        elif element == "[":
            element = self._consumeTo(stack, "]")[0] # just use the first char in set
            if element == "]": #this is the odd case of []<something>]
                self._consumeTo(stack, "]") # throw rest away and use ] as first element
        elif element == "|":
            break # you get to an | an you have all you need to match
        elif element == "(":
            arg = self._consumeTo(stack, ")")
            element = self.parse( arg[:-1] )

        retval += lastelement
        lastelement = element
    retval += lastelement #Complete the string with the last char

    return retval

 def _consumeTo(self, stackToConsume, endElement ):
    retval = ""
    while not retval.endswith(endElement):
        retval += stackToConsume.pop(0)
    return retval

Answer 7

Я не видел Python-модуль для этого, но я видел (частичную) реализацию в Perl: Regexp::Genex. Из описания модуля кажется, что реализация опирается на внутренние детали механизма регулярных выражений Perl, поэтому может оказаться бесполезной даже с теоретической точки зрения (я не исследовал реализацию, просто следуя комментариям в документации ).

Я думаю, что делать то, что вы предлагаете в целом, является сложной проблемой и может потребовать использования недетерминированных методов программирования. Для начала нужно было бы проанализировать регулярное выражение и построить дерево разбора, а затем пройтись по дереву и построить примерную строку (строки) по мере продвижения. Сложными битами, вероятно, будут такие вещи, как обратные ссылки и избегание бесконечных циклов в вашей реализации.

Answer 8

Exrex может создавать строки из регулярных выражений.

Exrex - это инструмент командной строки и модуль Python, который генерирует все или произвольно совпадающие строки с данным регулярным выражением и т. Д.

Пример:

>>> exrex.getone('\d{4}-\d{4}-\d{4}-[0-9]{4}')
'3096-7886-2834-5671'