Почему большинство языков не используют подстановочные регулярные выражения неэффективно?

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

http://swtch.com/~rsc/regexp/regexp1.html

TL; DNR: некоторые регулярные выражения, такие как (a?)^na^n для фиксированного $n $, принимают экспоненциальное время, сопоставляемое, скажем, a^n, потому что оно реализовано путем обратного отслеживания строки при сопоставлении раздела ?. Реализация этих как NFA путем хранения списков штатов делает это намного более эффективным по очевидным причинам.

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

Ответ 1

Хотя можно построить DFA, которые хорошо справляются с этими сложными случаями (например, Tcl RE engine, который был написан Генри Спенсером, является доказательством на примере; связанная статья связала это с его данными о производительности), это также исключительно сложно.

Одна из ключевых моментов заключается в том, что если вы обнаружите, что вам никогда не нужна соответствующая групповая информация, вы можете (для многих RE, особенно без внутренних обратных ссылок) преобразовать RE в тот, который использует только круглые скобки для группировки, позволяющие больше эффективный RE должен быть сгенерирован (поэтому (a?){n}a{n} - я использую современный обычный синтаксис - становится фактически эквивалентным a{n,2n}). Backreferences нарушают эту основную оптимизацию; это не зря, что в коде Henry RE (упоминается выше) есть комментарий к коду, описывающий их как "Feature from the Black Lagoon". Это один из лучших комментариев, которые я когда-либо читал в коде (за исключением ссылок на научные статьи, описывающие кодированный алгоритм).

С другой стороны, двигатели стиля Perl/PCRE с их схемами оценки рекурсивного спуска могут приписать гораздо более здравый набор семантики смешанным жадным REs и многое другое. (В крайнем конце этого, рекурсивные шаблоны - (?R) и др. - полностью невозможны с теоретическими подходами к автоматам. Они требуют соответствия стека, что делает их формально не регулярными выражениями.)

На практическом уровне затраты на строительство NFA и DFA, которые вы затем скомпилируете, могут быть довольно высокими. Вам нужно умное кэширование, чтобы сделать его не слишком дорогостоящим. Кроме того, на практическом уровне реализации PCRE и Perl были применены к ним гораздо больше усилий разработчиков.

Ответ 2

Я понимаю, что основная причина заключается в том, что нам не просто интересно, соответствует ли строка, но в том, как она соответствует, например. с группами захвата. Например, (x*)x должен знать, сколько хs было в группе, поэтому оно может быть возвращено как группа захвата. Точно так же "promises" потребляет как можно больше x символов, что имеет значение, если мы продолжаем сопоставлять больше вещей с оставшейся строкой.

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

Ответ 3

Здесь:

http://haifux.org/lectures/156/PCRE-Perl_Compatible_Regular_Expression_Library.pdf

Они пишут, что pcre использует реализацию на основе NFA. Но эта ссылка также не самая молодая вещь в Интернете...

Вокруг страницы 36 есть сравнение между двигателями. Это также может иметь отношение к исходному вопросу.