Какой из этих случаев связан с возвратом?

Question

Я пытаюсь изучить регулярные выражения из нескольких источников, но столкнулся с путаницей в отношении обратного отслеживания, потому что каждый определяет возврат, что означает состояние, когда механизм регулярных выражений не соответствует шаблону, поэтому он возвращается в положение где первый атом соответствовал , например, чтобы соответствовать cat в He captured a catfish for his cat, двигатель будет работать следующим образом:

• Он будет искать c, пока не найдет соответствиеc в captured
• , то же самое для a
• , но не удается сопоставить t с p
• , когда двигатель возвращается в положение послеc в captured, поскольку он знал, что до этого момента совпадение не произойдет.

Таким образом, во всех случаях без квантификаторов двигатель будет сбрасывать весь шаблон, чтобы попытаться снова сопоставить его.из другой позиции.

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

Как указано здесь :

Фундаментальная особенность сопоставления регулярных выражений включает в себя понятие, называемое обратным отслеживанием.который используется (когда это необходимо) всеми квантификаторами регулярных выражений, а именно *, * ?, +, + ?, {n, m} и {n, m}?.

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

Это означает, что шаблон, подобный ([A-Z][A-Z0-9]*)\b[^>]*>.*<\/\1> для соответствия Testing <B><I>bold italic</I></B> text., будет работать следующим образом:

• Сначала он будет соответствовать <B>
• Затем шаблон должен соответствовать .* который будет соответствовать до конца строки.
• , затем он будет пытаться соответствовать <, но он уже достиг конца, поэтому он будет возвращать один символ за другим, пока не совпадет.

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

Но в другой ситуации, если я добавлю ? после .*, регулярное выражение пропускает этот атом .*?, пытаясь сопоставить оставшиеся символы, но если нет совпадения, оно возвращается к ., чтобы соответствовать, пока не будет <, а затем начинайте сопоставлять атомы после него.

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

Answer 1

Давайте проверим возврат определений.

"Суть механизма NFA заключается в следующем: он рассматривает каждый подвыражение или компонент по очереди и всякий раз, когда ему необходимо решить,два одинаково жизнеспособных варианта, он выбирает один и запоминает другой, чтобы вернуться к более позднему, если нужно будет . Если попытка выбора была успешной, а остальная часть регулярного выражения также успешна, вы заканчиваете сопоставлением.что-либо в остальной части регулярного выражения в конечном итоге вызывает сбой, механизм регулярных выражений знает, что он может вернуться туда, где он выбрал опцию, и может продолжить сопоставление, попробовав другую. Таким образом, он в конечном итоге пробует все возможные перестановки регулярного выражения (или, по крайней мере,столько, сколько нужно, пока совпадение не будет найдено). " Освоение регулярных выражений Мощные методы для Perl и других инструментов, Джеффри Э. Ф. Фридл, с.102

Еще одно:

"Когда регулярное выражениевключает необязательные квантификаторы или альтернативные конструкции, оценка входной строки больше не является линейной. Сопоставление шаблонов с механизмом NFA определяется элементами языка в регулярном выражении, а не символами, которые должны быть сопоставлены во входной строке. ПоэтомуМеханизм регулярных выражений пытается полностью сопоставить необязательные или альтернативные подвыражения. Когда он переходит к следующему элементу языка в подвыражении и совпадение не удается, механизм регулярных выражений может отказаться от части своего успешного совпадения и вернуться к ранее сохраненномув интересах сопоставления регулярного выражения в целом с входной строкой . Этот процесс возврата в предыдущее сохраненное состояние для поиска совпадения называется обратным отслеживанием. "( Возврат в регулярных выражениях, документы Microsoft )

Еще один:

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

Похоже, что центральная часть backtracking является процессом "возврата" в более раннее состояние для повторной оценки (повторного соответствия) строка, чтобы сделать совпадение всего выражения. не ограничивается тем, как это должно быть сделано для вызова процесса как такового.

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