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

Как мы узнали, имея шаблон регулярного выражения (например, A B A B A C), мы можем преобразовать его в DFA. В этом примере это будет похоже на цепочку (вы можете протестировать ее здесь).

Этот «похожий на цепочку» DFA может сказать, соответствует ли данная строка шаблону или нет (т. Е. Принять / отклонить ее); Но он не может определить, есть ли какие-либо вхождения в строке, и идентифицировать их все.

Пример. Предположим, это строка для поиска: A B C A B A B A B A C A B C

Хотя есть вхождение, начинающееся с 6-го символа, «цепочечное» DFA не может этого сказать. Все, что он может сделать, это отклонить эту строку.

Вопрос. Можно ли разработать регулярное выражение, поддерживающее такую ​​функциональность?

(Примечание: я понимаю, что этот вопрос немного сбивает с толку; я хотел бы уточнить, что он смущает вас.)


search regex pattern-matching dfa automata
person JackWM    schedule 25.06.2015    source источник
comment
Я предполагаю, что вы говорите о классических регулярных выражениях, которые изучаются в теории формального языка. , а не синтаксис сопоставления регулярных выражений, встречающийся во многих языках программирования (который является довольно далеким потомком классической нотации).   -  person Ilmari Karonen    schedule 25.06.2015
comment
Вполне возможно сделать то, о чем вы просите, поскольку большинство языков программирования имеют функцию замены регулярного выражения, которая требует, чтобы она определяла, где произошло совпадение. Кроме того, операции сопоставления регулярных выражений часто возвращают результат, содержащий совпадающую подстроку.   -  person Barmar    schedule 25.06.2015
comment
Для очень простого примера, так что вариант -o для grep в Linux; вместо того, чтобы показывать всю совпадающую строку, он просто показывает часть строки, совпадающую с регулярным выражением.   -  person Barmar    schedule 25.06.2015
comment
@ Бармар Хороший вопрос. Меня интересует, как эти операции регулярного выражения соответствия переводят определенное пользователем регулярное выражение в функцию поиска. Как я показал, регулярное выражение используется только для проверки того, должна ли строка быть принята или нет (в отличие от поиска).   -  person JackWM    schedule 25.06.2015
comment
Предположительно, когда он проходит через входные данные, когда DFA соответствует чему-то, он устанавливает переменную в текущий индекс. Ему просто нужна одна переменная для позиции начала матча и другая для конца.   -  person Barmar    schedule 25.06.2015
comment
Существует множество библиотек регулярных выражений с открытым исходным кодом, вы можете просто взглянуть на одну из них, чтобы увидеть, как она работает.   -  person Barmar    schedule 25.06.2015
comment
Оригинальная статья Томпсона 1969 года также до сих пор хорошо читается.   -  person tripleee    schedule 26.06.2015

Ответы (1)


arrow_upward
0
arrow_downward

Язык строк, содержащих подстроку ABABAC, соответствует регулярному выражению:

.*ABABAC.*

Где символ . обозначает подвыражение, которое соответствует любому отдельному входному символу (например, (A|B|C), если язык ввода содержит только символы A, B и C). Чтобы узнать, содержит ли строка подстроку ABABAC, вы можете построить NFA или DFA из этого регулярного выражения и проверить, принимает ли он вашу строку.

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

person Ilmari Karonen    schedule 25.06.2015
comment
Рад видеть, что вы поднимаете этот вопрос. Может быть, .*(ABABAC)*.* сможет найти несколько совпадений, верно? - person JackWM; 25.06.2015
comment
Не совсем, нет; он находит соседние повторы ABABAC, ноль или более. Но это не особенно хорошо продуманное регулярное выражение. Конечный .* лишний как в теории, так и на практике. Выражение `(.*ABABAC)* найдет ноль или более повторений в любом месте строки. - person tripleee; 26.06.2015