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

Question

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

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

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

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

Answer 1

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

Answer 2

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

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

Обновление

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

(тьфу. Thinko исправлено.)

Answer 3

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