Приглашаем посетить
6.12. Локальный контекст в регулярных выражениях
Проблема
Требуется преобразовать регистр в другом локальном контексте или заставить метасимвол \w совпадать с символами национальных алфавитов - например, Jose или dejd vu.
Предположим, у вас имеется полгигабайта текста на немецком языке, для которого необходимо составить предметный указатель. Вы хотите извлекать слова (с помощью \w+) и преобразовывать их в нижний регистр (с помощью 1с или \L). Однако обычные версии \w и 1с не находят слова немецкого языка и не изменяют регистр символов с диакритическими знаками.
Решение
Регулярные выражения и функции обработки текста Perl имеют доступ к локальному контексту POSIX. Если включить в программу директиву use locale, Perl
позаботится о символах национальных алфавитов - конечно, при наличии разумной спецификации LC_CTYPE и системной поддержки.
use locale;
Комментарий
По умолчанию \w+ и функции преобразования регистра работают с буквами верхнего и нижнего регистров, цифррами и подчеркиваниями. Преобразуются лишь простейшие английские слова, и даже в очень распространенных заимствованных словах происходят сбои. Директива use locale помогает справиться с затруднениями.
Пример 6.10 показывает, чем отличаются выходные данные для английского (en) и немецкого (de) локальных контекстов.
Пример 6.10. localeg
#!/usr/bin/perl -w
# localeg - выбор локального контекста
use locale;
use POSIX 'locale_h';
$name = "andreas k\xF6nig";
@locale{qw(German English)} = qw(de_DE.ISO_8859-1 us-ascii);
setlocale(LC_CTYPE, $locale{English})
or die "Invalid locale $locale{English}";
@english_names = ();
while ($name =~ /\b(\w+)\b/g) {
push(@english_names, ucrirst($1));
} setlocale(LC_CTYPE, $locale{German})
or die "Invalid locale $locale{German}";
@german_names = ():
while ($name =~ /\b(\w+)\b/g) {
push(@german_names, ucfirst($1));
}
print "English names: @english_names\n":
print "German names: @german_names\n";
English names: Andreas К Nig German names: Andreas Konig
Решение основано на поддержке локальных контекстов в POSIX. Ваша система может обладать, а может и не обладать такой поддержкой. Но даже если система заявляет о поддержке локальных контекстов POSIX, в стандарте не определены имена локальных контекстов. Разумеется, переносимость такого решения не гарантирована.
Смотри также: Описание метасимволов \b, \w и \s в perlre(1), описание локальных контекстов Perl в perllocale( 1) и странице руководства local(3) вашей системы; рецепт 6.2.
Проблема
Требуется выполнить неформальный поиск по шаблону.
Задача часто возникает в ситуации, когда пользовательский ввод может быть неточным или содержащим ошибки.
Решение
Воспользуйтесь модулем String::Approx от СРАМ:
use Strin::Approx qw(amatch);
if (amatch("ШАБЛОН", @list)) {
# Совпадение
}
@matches = amatch("ШАБЛОН", (slist);
Комментарий
Модуль String::Approx вычисляет, насколько шаблон отличается от каждой строки списка. Если количество односимвольных вставок, удалений или замен для получения строки из шаблона не превышает определенного числа (по умолчанию 10 процентов длины шаблона), строка "совпадает" с шаблоном. В скалярном контексте amatch возвращает количество успешных совпадений. В списковом контексте возвращаются совпавшие строки.
use String::Approx qw(amatch);
open(DICT, "/usr/dict/words" or die "Can't open diet: $!";
while() {
print if amatch("balast");
}
ballast
ballustrade
blast
blastula
sandblast
Функции amatch также можно передать параметры, управляющие учетом регистра и количеством допустимых вставок, удалений и подстановок. Параметры передаются в виде ссылки на список. Они полностью описаны в документации по String::Approx.
Следует заметить, что поисковые функции модуля работают в 10-40 раз медленнее встроенных функций Perl. Используйте String::Approx лишь в том случае, если регулярные выражения Perl не справляются с неформальным поиском.
Смотри также: Документация по модулю String::Approx от CPAN; рецепт 1.16.
Проблема
Требуется возобновить поиск с того места, где было найдено последнее совпадение.
Такая возможность пригодится при многократном извлечении фрагментов данных из строки,
Решение
Воспользуйтесь комбинацией модификатора /g, метасимвола \G и функции роз.
Комментарий
При наличии модификатора /д механизм поиска запоминает текущую позицию в строке. При следующем поиске с /д совпадения ищутся, начиная с сохраненной позиции. Это позволяет создать цикл while для извлечения необходимой информации из строки:
while (/(\d+)/g) {
print "Found $1\n":
}
Присутствие \G в шаблоне привязывает поиск к концу предыдущего совпадения. Например, если число хранится в строке с начальными пробелами, замена каждого пробела нулем может выполняться так:
$n = " 49 here";
$n =` s/\g /0/g;
print $n;
00049 here
\G часто применяется в циклах while. Например, в следующем примере анализируется список чисел, разделенных запятыми:
while (/\G,?(\d+)/g) <
print "Found number $1\n";
}
Если поиск закончился неудачей (например, если в последнем примере кончились числа), сохраненная позиция по умолчанию перемещается в начало строки. Если это нежелательно (например, требуется продолжить поиски с текущей позиции, но с другим шаблоном), воспользуйтесь модификатором /с в сочетании с /д;
$_ = "the year 1752 lost 10 days on the 3rd of september";
while (/(\d+)/gc) {
print "Found number $1\n";
}
if (/\G(\S+)/g) {
print "Found $1 after the last number.\n";
}
Found numeral 1752
Found numeral 10
Found numeral 3
Found rd after the last number.
Как видите, при последовательном применении шаблонов можно изменять позицию начала поиска с помощью модификатора /д. Позиция последнего совпадения связывается со скалярной величиной, в которой происходит поиск, а не с шаблоном. Позиция не копируется вместе со строкой и не сохраняется оператором local.
Позиция последнего совпадения читается и задается функцией роз. Аргументом функции является строка, для которой читается или задается позиция последнего совпадения. Если аргумент не указан, роз работает с переменной $_:
print "The position in \$a is ", pos($a):
pos($a) = 30;
print "The position in \$_ is ", pos;
pos = 30;
Смотри также: Описание модификатора /g в perlre(1).
Проблема
Имеется шаблон с максимальным квантификатором -*,+,? или {}. Требуется перейти от максимального поиска к минимальному.
Классический пример - наивная подстановка для удаления тегов из HTML-документа. Хотя s#. *##gsi выглядит соблазнительно, в действительности будет удален весь текст от первого открывающего до последнего закрывающего тега ТТ. От строки "Even vi can edit troff effectively." остается лишь "Even effectively" - смысл полностью изменился!
Решение
Замените максимальный квантификатор соответствующим минимальным. Другими словами, *, +, ? или {} соответственно заменяются *?,+?,?? и {}?.
Комментарий
В Perl существуют два набора квантификаторов: максимальные (*, +, ? и {}) и минимальные1 (*?, +?, ?? и {}?). Например, для строки "Perl is a Swiss Army Chainsaw!" шаблон/(г. *s)/совпадет с "rl is a Swiss Army Chains", а шаблон /(r.*?s)/-c "rl is".
Также часто называемые "жадными" (greedy) и "скупыми" (stingy) квантификаторами. -Примеч. перев.
Предположим, шаблон содержит максимальный квантификатор. При поиске подстроки, которая может встречаться переменное число раз (например, 0 и более раз для * или 1 и более раз для +), механизм поиска всегда предпочитает "и более". Следовательно, шаблон /foo. *bar/ совпадает от первого "too" до последнего "bar", а не до следующего "bar", как можно ожидать. Чтобы при поиске предпочтение отдавалось минимальным, а не максимальным совпадениям, поставьте после квантификатора вопросительный знак. Таким образом, *?, как и *, соответствует 0 и более повторений, но при этом выбирается совпадение минимальной, а не максимальной длины.
# Максимальный поиск
s/<.*>//gs; # Неудачная попытка удаления тегов
# Минимальный поиск
s/<.*?>//gs; # Неудачная попытка удаления тегов
Показанное решение не обеспечивает правильного удаления тегов из HTML-документа, поскольку отдельное регулярное выражение не заменит полноценного анализатора. Правильное решение этой проблемы продемонстрировано в рецепте 20.6.
Впрочем, с минимальными совпадениями дело обстоит не так просто. Не стоит ошибочно полагать, что BEGIN. *?END в шаблоне всегда соответствует самому короткому текстовому фрагменту между соседними экземплярами BEGIN и END. Возьмем шаблон /BEGIN(. *?)END/. После поиска в строке "BEGIN and BEGIN and END" переменная $1 будет содержать "and BEGIN and". Вероятно, вы рассчитывали на другой результат.
Представьте, что мы хотим извлечь из HTML-документа весь текст, оформ ленный полужирным и курсивным шрифтом одновременно:
bxi this /i> and are important
Может показаться, что шаблон для поиска текста, находящегося между тегами HTML (то есть не включающий теги), должен выглядеть так:
m{ bXL (.*?) /ix/b> }sx;
Как ни странно, шаблон этого не делает. Многие ошибочно полагают, что он сначала находит последовательность "", затем нечто отличное от " , а затем - "", оставляя промежуточный текст в $1. Хотя по отношению к входным данным он часто работает именно так, в действительности делается совершенно иное. Шаблон просто находит левую строку минимальной длин in, которая соответствует всему шаблону. В данном примере это вся строка. EC.II! вы хотели ограничиться текстом между "" и "", не включающим другие теги полужирного или курсивного начертания, результат окажется ш o-верным.
Если искомая строка состоит всего из одного символа, инвертированный клан (например, /Х["Х]*)Х/) заметно превосходит минимальный поиск по эффектпи ности. Однако обобщенный шаблон, который находит "сначала BEGIN, затем не-BEGIN, затем END" для произвольных BEGIN и END и сохраняет промежуточны i' текст в $1, выглядит следующим образом:
/BEGIN(C?:(?!BEGIN).)*)END/ Наш пример с тегами HTML выглядит примерно так:
m{ | /i>). )* ) }sx;
или так:
т{ <Ь><1>( (?: (?!). )* ) }sx;
Как замечает Джеффри Фридл, это скороспелое решение не очень эффективно. В ситуациях, где скорость действительно важна, он предлагает воспользоваться более сложным шаблоном:
m{b i ["<]* # Заведомо допустимо
(?:
# Символ '<' возможен, если он не входит в недопустимую конструкцию
(?! ) # Недопустимо
< # Все нормально, найти
< ["<]* # и продолжить
)* }sx
Смотри также:
Описание минимальных квантификаторов в разделе "Regular Expressions" perlre(\).
Проблема
Требуется найти в документе повторяющиеся слова.
Решение
Воспользуйтесь обратными ссылками в регулярных выражениях.
Комментарий
Механизм поиска запоминает часть строки, которая совпала с частью шаблона, заключенной в круглые скобки. Позднее в шаблоне обозначение \1 ссылается на первый совпавший фрагмент, \2 - на второй и т. д. Не используйте обозначение $1 - оно интерпретируется как переменная и интерполируется до начала поиска. Шаблон /([A-Z])\1/ совпадает с символом верхнего регистра, за которым следует не просто другой символ верхнего регистра, а именно тот, что был сохранен в первой паре скобок.
Следующий фрагмент читает входной файл по абзацам. При этом используется принятое в Perl определение абзаца как фрагмента, заканчивающегося двумя и более смежными переводами строк. Внутри каждого абзаца находятся все но-
вторяющиеся слова. Программа не учитывает регистр и допускает межстрочные совпадения.
Модификатор /х разрешает внутренние пропуски и комментарии, упрощающие чтение регулярных выражений. Модификатор /i позволяет найти оба экземпляра "is" в предложении "Is is this ok?". Модификатор/д в цикле while продолжает поиск повторяющихся слов до конца текста. Внутри шаблона метасимволы \Ь (граница слова) и \s (пропуск) обеспечивают выборку целых слов.
$/ = o o;
while (<>) { while ( m{
\b
(\S+) \b (\s+\1 \b ) + }xig
}
{
print "dup word '$1' at paragraph $.\n";
}
}
Приведенный фрагмент найдет удвоенное test в следующем примере:
This is a test test of the duplicate word funder.
Проверка \8+ между двумя границами слов обычно нежелательна, поскольку граница слова определяется как переход между \w (алфавитно-цифровым символом или подчеркиванием) и либо концом строки, либо He-\w. Между двумя \Ь обычный смысл \8+ (один и более символов, не являющихся пропусками) распространяется до последовательности символов, не являющихся пропусками, первый и последний символ которой должны быть алфавитно-цифровыми символами или подчеркиваниями.
Рассмотрим другой интересный пример использования обратных ссылок. Представьте себе два слова, причем конец первого совпадает с началом второго - например, "nobody" и "bodysnatcher". Требуется найти подобные "перекрытия" и сформировать строку вида "nobodysnatcher". Это вариация на тему нашей основной проблемы - повторяющихся слов.
Чтобы решить эту задачу, программисту на С, привыкшему к традиционной последовательной обработке байтов, придется написать длинную и запутанную программу. Но благодаря обратным ссылкам задача сводится к одному простому поиску:
$а = 'nobody';
$b = 'bodysnatcher';
if ("$a $b" =~ /"(\w+)(\w+) \2(\w+)$/) {
print "$2 overlaps in $1-$2-$3\n";
}
body overlaps in no-body-snatcher
Казалось бы, из-за наличия максимального квантификатора переменная $1 должна захватывать все содержимое "nobody". В действительности так и происходит - на некоторое время. Но после этого не остается ни одного символа, который можно было бы занести в $2. Механизм поиска дает задний ход, и $1 неохотно уступает один символ переменной $2. Пробел успешно совпадает, но далее в шаблоне следует переменная \2, которая в настоящий момент содержит просто "у". Следующий символ в строке - не "у", а "Ь". Механизм поиска делает следующий шаг назад; через некоторое время $1 уступит $2 достаточно символов, чтобы шаблон нашел фрагмент, пробел и затем тот же самый фрагмент.
Этот прием не работает, если само перекрытие содержит повторяющиеся фраг менты - как, например, для строк " rococo" и "cocoon". Приведенный выше алгоритм решит, что перекрываются символы "со", а не "coco". Однако мы хотим получить не "rocococoon", a "rococoon". Задача решается включением минимального квантификатора в $1:
/"(\w+?)(\w+) \2(\w+)$/
Трудно представить, насколько мощными возможностями обладают обратные ссылки. Пример 6.11 демонстрирует принципиально новый подход к проблеме разложения числа на простые множители
(см. главу 2 "Числа).
Пример 6.11. prime-pattern
#!/usr/bin/perl
# prime_pattern - разложение аргумента на простые множители по шаблону
for ($N = ('о' х shift): $n =~ /"(oo+^)\1+$/; $n =~ s/$1/o/g)
{ print length($1), " ";
} print length ($N), "\n";
Несмотря на свою непрактичность, этот подход отлично демонстрирует возможности обратных ссылок и потому весьма поучителен.
Приведем другой пример. Гениальная идея, предложенная Дугом Макилро-ем (Doug.McIlroy) - во всяком случае, так утверждает Эндрю Хыом (Andrew Hume), - позволяет решать диофантовы уравнения первого порядка с помощью регулярных выражений. Рассмотрим уравнение 12х + 15у + 16z = 281. Сможете ли вы найти возможные значения х, у и z? А вот perl может!
# Решение 12х + 15у + 16z = 281 для максимального х
if (($X, $Y, $Z) =
(('о' х 281) -- /"(0*)\1{11}(о")\2{14}(о*)\3{15}$/)) {
($х, $у, $z) = (length($x), length($y), length($z));
print "One solution is: x=$x; y=$y; z=$z.\n";
} else {
print "No solution.\n":
} One solution is: x=17; y=3; z=2.
Поскольку для первого о* ищется максимальное совпадение, х растет до максимума. Замена одного или нескольких квантификаторов * на *?, + или +? дает другие решения:
((oо' х 281) =~ /-(о+)\1{11}(о+)\2{14}(о+)\3{15}$/))
One solution is: x=17; y=3; z=2.
((oо- х 281) =~ /-(о.7)\1{11}(о*)\2{14}(о.)\3{15}$/))
One solution is: x=0; y=17; z=11.
(('о' х 281) =~ /"(о+^)\1{11}(о.)\2{14}(о*)\3{15}$/))
One solution is: x=1; y=3; z=14,
Подобные демонстрации математических возможностей выглядят потрясающе, но из них следует вынести один важный урок: механизм поиска по шаблону (особенно с применением обратных ссылок) всей душой желает предоставить вам ответ и будет трудиться с феноменальным усердием. Однако обратные ссылки в регулярных выражениях могут привести к экспоненциальному росту времени выполнения. Для любых нетривиальных данных программа будет работать так медленно, что даже дрейф континентов по сравнению с ней покажется быстрым.
Смотри также: Описание обратных ссылок в разделе "Regular Expressions" perlre (1).
