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

[avva]

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

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

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

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

Comments

[avva.livejournal.com]

Используемые на практике регэкспы практически никогда не бывают сильно длинее и сложнее эквивалентных им BNFов.

Твои слова об искалеченном моске программиста на Перле напоминают соответствующий диктум Дайкстры о тех, кто начал программировать когда-то на Бейсике. Учитывая то, что я когда-то начинал на Бейсике, я, видимо, вдвойне покалеченный!

[cmm.livejournal.com]

the damage cancelled out, I guess!

[avva.livejournal.com]

or it just went deeper :)