Anatoly Vorobey (avva) wrote,
Anatoly Vorobey
avva

Category:

свежий взгляд на regexp-ы (программистское)

Я весьма рекомендую эту статью: Regular Expression Matching Can Be Simple And Fast всем, кто интересуется программированием и компьютерными науками. У автора статьи есть, как говорят по-английски, agenda, определенная пропагандистская цель: он хочет убедить нас, что наиболее распостраненный способ распознавания регулярных выражений - путем детерминистского поиска с возвратом (backtracking) - неправильное решение, и лучше использовать более редкий метод прогона недетерминистского автомата.

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

Что же касается утверждения автора, он меня не убедил, но заинтриговал. Конечно, тот факт, что с некоторыми "патологическими" regexp-ами обычные методы справляются только за экспоненциальное время хорошо известен. На практике программистам приходится их избегать: переписывать по-другому, менять логику итд. Но неясно, стоит ли преимущество того, что у нас гарантированно не будет "патологических" случаев определенной потери скорости в "обычных" случаях. Интуитивно мне кажется, что такая потеря, в среднем, неизбежна. Автор старательно обходит этот вопрос стороной, предлагая измерения только одного патологического случая. Кроме того, без некоторых дополнительных возможностей, кроме собственно сравнения строки по regexp-у, современные языки не могут обойтись - например, автоматической поимки вложенных паттернов в переменные ($1, $2 итд. в Перле). Автор упоминает, что есть возможность достичь этого и в методе недетерминистского прогона, что мне кажется интересным (потому что неочевидно, как к этому подойти); постараюсь пойти по его ссылкам и разобраться в подробностях.

Мнения и комментарии, как обычно, приветствуются.

Subscribe
  • Post a new comment

    Error

    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 57 comments