Изучаем алгоритм работы регулярных выражений в Ruby
Мы все знакомы с регулярными выражениями. Они являются «швейцарским армейским ножом разработчика». Чтобы вы не искали, какой бы текст не разбирали, вы всегда можете сделать это используя регулярные выражения. На самом деле, вероятно, вы начали использовать их гораздо раньше, чем стали использовать Ruby — они уже давно включены в большинство популярных языков программирования: Perl, JavaScript, PHP, Java и прочие. Ruby появился в середине 1990-х годов, тогда как регулярные выражения еще в 1960-х, то есть почти на 30 лет раньше!
Но как на самом деле работают регулярные выражения?
Если вы хотите узнать больше о информационных технологиях, стоящих за движком регулярных выражений, вы обязаны прочитать фантастическую серию статей от Russ Cox:
Я не хочу заново повторять все, что написал Russ. Но я быстро отмечу, что Ruby использует «Non-recursive Backtracking Implementation» (реализация с нерекурсивным обратным ходом), которая обсуждается в его второй статье, что приводит к экспоненциальному падению производительности, точно так же, как и при работе с регулярными выражениями в Perl. Другими словами, Ruby не использует наиболее оптимальный Thompson NFA (алгоритм Томпсона для недетерминированных конечных автоматов), про который Russ рассказывает в своей первой статье.
Мы все знакомы с регулярными выражениями. Они являются «швейцарским армейским ножом разработчика». Чтобы вы не искали, какой бы текст не разбирали, вы всегда можете сделать это используя регулярные выражения. На самом деле, вероятно, вы начали использовать их гораздо раньше, чем стали использовать Ruby — они уже давно включены в большинство популярных языков программирования: Perl, JavaScript, PHP, Java и прочие. Ruby появился в середине 1990-х годов, тогда как регулярные выражения еще в 1960-х, то есть почти на 30 лет раньше!
Но как на самом деле работают регулярные выражения?
Если вы хотите узнать больше о информационных технологиях, стоящих за движком регулярных выражений, вы обязаны прочитать фантастическую серию статей от Russ Cox:
Я не хочу заново повторять все, что написал Russ. Но я быстро отмечу, что Ruby использует «Non-recursive Backtracking Implementation» (реализация с нерекурсивным обратным ходом), которая обсуждается в его второй статье, что приводит к экспоненциальному падению производительности, точно так же, как и при работе с регулярными выражениями в Perl. Другими словами, Ruby не использует наиболее оптимальный Thompson NFA (алгоритм Томпсона для недетерминированных конечных автоматов), про который Russ рассказывает в своей первой статье.
Читать полностью »