PERL: БИБЛИОТЕКА ПРОГРАММИСТА


PERL: БИБЛИОТЕКА ПРОГРАММИСТА - стр. 174


Но дело не обязательно обстоит именно так. В следующем примере использу­ется awk — язык, от которого Perl позаимствовал немало:

% echo ababacaca  |

awk    match($O,/(a|ba|b)+(a|ac)+/)   {  print substr($0,   RSTART,   RLENGTH)   } ababacaca

Выбор реализации поиска по шаблону в основном зависит от двух факторов: нерегулярности выражений (то есть наличия в них обратных ссылок) и типа возвращаемой величины (логическое «да/нет», все совпадение, подвыраже­ния). Такие инструменты, как awk, egrep и lex, используют регулярные выраже­ния и возвращают либо логическое «да/нет», либо все совпадение. Подобные воз­можности поддерживаются определенными конечными автоматами; поскольку определенные конечные автоматы работают быстрее и проще, реализация в пе­речисленных инструментах основана именно на них. Поиск по шаблону в таких программах и библиотеках, как ed, regex или perl, — совсем другое дело. Обычно приходится поддерживать нерегулярные выражения и знать, какие части строки совпали с различными частями шаблона. Эта задача намного сложнее и отлича­ется экспоненциальным ростом времени выполнения. Естественный алгоритм ее реализации основан на неопределенных конечных автоматах; в этом заключается и проблема, и возможности. Проблема — в том, что неопределенные конечные ав­томаты работают медленно. Возможности — в том, что формулировка шаблона с учетом особенностей конкретной реализации позволяет существенно повысить быстродействие.

Последняя и самая интересная из трех особенностей — возврат. Чтобы шаблон совпал, должно совпасть все регулярное выражение, а не лишь его отдельная часть. Следовательно, если начало шаблона с квантификатором совпадает, а одна из последующих частей шаблона — нет, механизм поиска возвращается к началу и пытается найти для него другое совпадение — отсюда и термин «возврат». Фак­тически это означает, что механизм поиска должен систематически перебирать разные возможности до тех пор, пока не найдет полное совпадение. В некоторых реализациях поиска возврат используется для поиска других совпадающих ком­понентов, которые могли бы увеличить длину найденного совпадения. Механизм поиска Perl этого не делает; найденное частичное совпадение используется немед­ленно, — если позднее другая часть шаблона сделает полное совпадение невозмож­ным, происходит возврат и поиск другого частичного совпадения (см. рецепт 6.16).




- Начало -  - Назад -  - Вперед -