Отрицание регулярного выражения

Question

Отрицание регулярного выражения

Я не уверен, как это называется: отрицание, дополнение или инверсия. Концепция заключается в следующем. Например, имея алфавит "AB"

R = 'a'
!R = the regexp that matche everyhting exept what R matches

В этом простом примере это должно быть

!R = 'b*|[ab][ab]+'

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

3

regex computation-theory

Источник

user1029825 10 сен '12 в 10:22

2 ответа

Другие вопросы по тегам regex computation-theory

user1092672 11 июн '13 в 23:48 2013-06-11 23:48 · Answer 1 · 2013-06-11 23:48

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

Чтобы дополнить регулярное выражение:

Конвертировать в эквивалент NFA. Это хорошо известный и определенный процесс.
Преобразование NFA в DFA через конструкцию powerset
Дополните DFA, заставив принимать состояния не принимать и наоборот.
Преобразуйте DFA в регулярное выражение.

Теперь у вас есть дополнение оригинального регулярного выражения!

user861178 19 сен '12 в 05:59 2012-09-19 05:59 · Answer 2 · 2012-09-19 05:59

Если все, что вы делаете, - это поиск, то в некоторых программах / языках для регулярных выражений есть способ отрицать встроенное совпадение. Например, с помощью grep вы можете использовать опцию -v, чтобы получить строки, которые не совпадают, и варианты SQL, которые я видел, позволяют вам использовать квалификатор not, чтобы отрицать совпадение.

Другой вариант, который поддерживают некоторые / большинство / все диалекты регулярных выражений, - это использовать "негативный взгляд". Возможно, вам придется поискать свой конкретный синтаксис, но это интересный инструмент, о котором стоит прочитать. Вообще то как то так: если R='<regex>', затем Negative_of_R='(?!<regex>)', К сожалению, это может варьироваться в зависимости от особенностей вашего языка (например, vim использует \(<regex>\)\@!).

Предостережение: если вы не будете осторожны, регулярное выражение с отрицанием будет соответствовать больше, чем вы ожидаете. Если у вас есть текст This doesn't match 'mystring'. и искать (?!mystring)тогда он будет соответствовать всему, кроме "m" в mystring.