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

Ответ 1

Я думаю:— в теории; чтобы определить, соответствует ли regexp A подмножество того, что соответствует регулярному выражению B, алгоритм мог:

• Вычислить минимальный детерминированный конечный автомат B, а также "объединение" A|B.
• Проверьте, идентичны ли два DFA. Это верно тогда и только тогда, когда A соответствует подмножеству того, что соответствует B.

Однако, скорее всего, это был бы крупный проект на практике. Существуют такие пояснения, как Построение DFA с минимальным состоянием из регулярного выражения, но они имеют тенденцию рассматривать математически чистые регулярные выражения, Вам также придется обрабатывать расширения, которые Python добавляет для удобства. Более того, если какой-либо из расширений приводит к тому, что язык является нерегулярным (я не уверен, что это так), вы, возможно, не сможете обработать эти.

Но что вы пытаетесь сделать? Возможно, есть более простой подход...?

Ответ 2

Помимо ответа antinome:

Многие из конструкций, которые не являются частью основного определения регулярных выражений, по-прежнему являются регулярными и могут быть преобразованы после синтаксического анализа регулярного выражения (с помощью реального парсера, поскольку язык регулярного выражения не является регулярным): (x?) to (x|), (x+) до (xx*), классы символов, такие как [a-d], к их соответствующему объединению (a|b|c|d) и т.д. Таким образом, можно использовать эти конструкции и по-прежнему проверять, совпадает ли одно регулярное выражение с подмножеством другого регулярного выражения с использованием сравнения DFA антиномом.

Некоторые конструкции, такие как обратные ссылки, не являются регулярными и не могут быть представлены NFA или DFA.

Даже кажущаяся простая проблема проверки того, соответствует ли регулярное выражение с обратными ссылками определенной строкой, NP-complete (http://perl.plover.com/NPC/NPC-3COL.html).

Ответ 3

Проверка сообщения "antinome" с использованием двух регулярных выражений: 55 * и 5 *:

REGEX_A: 55 * [Это соответствует "5", "55", "555" и т.д. и не соответствует "4", "54" и т.д.]

REGEX_B: 5 * [Это соответствует "", "5" "55", "555" и т.д. и не соответствует "4", "54" и т.д.]

[Здесь мы предположили, что 55 * неявно .55. * и 5 * не .5. * - Вот почему 5 * не соответствует 4]

REGEX_A может иметь NFA, как показано ниже:

  {A}--5-->{B}--epsilon-->{C}--5-->{D}--epsilon-->{E}
           {B} -----------------epsilon --------> {E} 
                          {C} <--- epsilon ------ {E}

REGEX_B может иметь NFA, как показано ниже:

  {A}--epsilon-->{B}--5-->{C}--epsilon-->{D}
  {A} --------------epsilon -----------> {D} 
                 {B} <--- epsilon ------ {D}

Теперь мы можем получить NFA * DFA (REGEX_A | REGEX_B), как показано ниже:

  NFA:
  {state A}  ---epsilon --> {state B} ---5--> {state C} ---5--> {state D}
                                              {state C} ---epsilon --> {state D} 
                                              {state C} <---epsilon -- {state D}
  {state A}  ---epsilon --> {state E} ---5--> {state F}
                            {state E} ---epsilon --> {state F} 
                            {state E} <---epsilon -- {state F}

  NFA -> DFA:

       |   5          |  epsilon*
   ----+--------------+--------
    A  |  B,C,E,F,G   |   A,C,E,F
    B  |  C,D,E,F     |   B,C,E,F
    c  |  C,D,E,F     |   C
    D  |  C,D,E,F,G   |   C,D,E,F
    E  |  C,D,E,F,G   |   C,E,F
    F  |  C,E,F,G     |   F
    G  |  C,D,E,G     |   C,E,F,G

                    5(epsilon*)
    -------------+---------------------
              A  |  B,C,E,F,G 
      B,C,E,F,G  |  C,D,E,F,G 
      C,D,E,F,G  |  C,D,E,F,G 

    Finally the DFA for (REGEX_A|REGEX_B) is:
         {A}--5--->{B,C,E,F,G}--5--->{C,D,E,F,G}
                                     {C,D,E,F,G}---5--> {C,D,E,F,G}

         Note: {A} is start state and {C,D,E,F,G} is accepting state. 

Аналогично DFA для REGEX_A (55 *):

       |   5    |  epsilon*
   ----+--------+--------
    A  | B,C,E  |   A
    B  | C,D,E  |   B,C,E
    C  | C,D,E  |   C
    D  | C,D,E  |   C,D,E
    E  | C,D,E  |   C,E


            5(epsilon*)
   -------+---------------------
       A  |  B,C,E  
   B,C,E  |  C,D,E
   C,D,E  |  C,D,E

    {A} ---- 5 -----> {B,C,E}--5--->{C,D,E}
                                    {C,D,E}--5--->{C,D,E}
Note: {A} is start state and {C,D,E} is accepting state

Аналогично DFA для REGEX_B (5 *):

       |   5    |  epsilon*
   ----+--------+--------
    A  | B,C,D  |   A,B,D
    B  | B,C,D  |   B
    C  | B,C,D  |   B,C,D
    D  | B,C,D  |   B,D


            5(epsilon*)
   -------+---------------------
       A  |  B,C,D  
   B,C,D  |  B,C,D

    {A} ---- 5 -----> {B,C,D}
                      {B,C,D} --- 5 ---> {B,C,D}
Note: {A} is start state and {B,C,D} is accepting state

Выводы:

DFA of REGX_A|REGX_B identical to DFA of REGX_A 
      -- implies REGEX_A is subset of REGEX_B
DFA of REGX_A|REGX_B is NOT identical to DFA of REGX_B 
      -- cannot infer about either gerexes.

Ответ 4

Это возможно с строковым представлением регулярного выражения, поскольку любая строка может быть сопоставлена ​​с регулярными выражениями, но не с скомпилированной версией, возвращаемой re.compile. Однако я не понимаю, какое использование это будет. Кроме того, он принимает другой синтаксис.

Изменить: вы, похоже, ищете возможность определить, является ли язык, определенный RE, подмножество других RE. Да, я думаю, что это возможно, но нет, модуль Python re не делает этого.

Ответ 5

Вы должны сделать что-то в этом направлении:

re.match("\[[b-x]-[b-x]\]", "[a-z]")

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

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

Ответ 6

Требуется какое-то уточнение, я думаю:

.

rA = re.compile('(?<! )[a-z52]+')

'(?<! )[a-z52]+' - шаблон

rA - это экземпляр класса RegexObject, тип которого < * type '_sre.SRE_Pattern' > *.

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

Обратите внимание, что rB = re.compile(rA) также возможно, он создает один и тот же объект (id (rA) == id (rB) равен True)

ch = 'lshdgbfcs luyt52uir bqisuytfqr454'
x = rA.match(ch) 
# or
y = rA.search(ch)

x и y являются экземплярами класса MatchObject, тип которого * < type '_sre.SRE_Match' > *

.

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

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

Ответ 7

pip3 install https://github.com/leafstorm/lexington/archive/master.zip
python3
>>> from lexington.regex import Regex as R
>>> from lexington.regex import Null
>>> from functools import reduce
>>> from string import ascii_lowercase, digits
>>> a_z = reduce(lambda a, b: a | R(b), ascii_lowercase, Null)
>>> b_x = reduce(lambda a, b: a | R(b), ascii_lowercase[1:-2], Null)
>>> a_z | b_x == a_z
True
>>> m_n = R("m") | R("n")
>>> zero_nine = reduce(lambda a, b: a | R(b), digits, Null)
>>> m_n | zero_nine == m_n
False

Также успешно протестирован с Python 2. См. также как это сделать с другой библиотекой.

В качестве альтернативы pip3 install https://github.com/ferno/greenery/archive/master.zip и:

from greenery.lego import parse as p
a_z = p("[a-z]")
b_x = p("[b-x]")
assert a_z | b_x == a_z
m_n = p("m|n")
zero_nine = p("[0-9]")
assert not m_n | zero_nine == m_n