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

Я читал эту статью сегодня по двум различным алгоритмам регулярных выражений.

Согласно статье старых инструментов Unix, таких как ed, sed, grep, egrep, awk и lex, все используют то, что называется Thompson NFA алгоритм в их регулярных выражениях...

Однако новые инструменты, такие как Java, Perl, PHP и Python, используют другой алгоритм для своих регулярных выражений, которые намного медленнее.

В этой статье не упоминается вообще Javascript regex algorthim (и да, я знаю, что там есть различные JS-движки), но я был что кто-нибудь знает, какой из этих алгоритмов они используют, и, возможно, эти алгоритмы должны быть заменены для Thompson NFA.

Ответ 1

Описание языка ECMA Javascript не налагает требования для конкретной реализации регулярных выражений, так что часть вопроса не является корректной. Вы действительно интересуетесь конкретной реализацией в определенном браузере.

Причина, по которой Perl/Python и т.д. использует более медленный алгоритм, заключается в том, что определенный язык регулярного выражения не является обычным выражением. Реальное регулярное выражение может быть выражено как машина конечного состояния, но язык регулярного выражения не имеет контекста. Именно поэтому мода просто называть его "регулярным выражением" вместо того, чтобы говорить о регулярных выражениях.

Update

Да, на самом деле регулярное выражение javascript не является ~~бесплатным контентом~~. Рассмотрим синтаксис с помощью `{n, m} ', то есть совпадений от n до m принятых регулярных выражений. Пусть d разность d = | n-m |. Синтаксис означает, что существует допустимая строка ux ^d w, но строка ux ^{k > d} w, которой нет. Из леммы о перекачке для регулярных языков следует, что это не регулярный язык.

(исправлено значение "Дуоту" ).

Ответ 2

Perl использует memoized рекурсивный поиск обратного отслеживания и, с некоторыми улучшениями в 5.10, больше не взрывается на perl -e '("a" x 100000) =~ /^(ab?)*$/;'. В последних тестах, которые я выполнил в OS X, Perl 5.10 превзошел awk, даже в тех случаях, когда алгоритм awk должен был быть лучше.

Ответ 3

Хотя стандарт ECMA не указывает алгоритм, который должна использовать реализация ECMAScript, тот факт, что стандарт требует, чтобы регулярные выражения ECMAScript поддерживали обратные ссылки (\ 1,\и т.д.), исключают DFA и "Thompson NFA" реализации.