dzhon_khopkroft_radzhiv_motvani_dzheffri _ulman_vvedenie_v_teoriyu_avtomatov_yazy kov_i_vychisleniy_2008 (852747), страница 29
Текст из файла (страница 29)
Кроме того, “компилятор” для регулярных выражений пригоден и для преобразования записываемых выражений в выполнимый код.В качестве примера обсудим одну типичную проблему, возникающую во многих Webприложениях. Предположим, необходимо просмотреть огромное количество Web-страници отметить адреса. Возможно, мы хотим составить список электронных адресов. Или пытаемся классифицировать фирмы по их месторасположению, чтобы отвечать на запросы типа“найдите мне ресторан в пределах 10-ти минут езды от того места, где я сейчас нахожусь”.В частности, мы сосредоточим внимание на распознавании названий улиц.
Что такоеназвание улицы? Необходимо это выяснить, и, если во время тестирования программыбудет установлено, что пропущены какие-то варианты, то нужно будет изменять выражения таким образом, чтобы включить все, что не было учтено. Начнем с того, что название улицы может заканчиваться словом “Street” (улица) или его сокращением “St.”Однако некоторые люди живут на “Avenues” (проспектах) или “Roads” (шоссе), что тожеможет быть записано в сокращенном виде. Таким образом, в качестве окончания нашеговыражения можно использовать следующие варианты.Street | St\.
| Avenue | Ave\. |Road | Rd\.130Стр. 130ÃËÀÂÀ 3. ÐÅÃÓËßÐÍÛÅ ÂÛÐÀÆÅÍÈß È ßÇÛÊÈВ этом выражении использованы обозначения в стиле UNIX с вертикальной чертойвместо + для оператора объединения. Обратите также внимание, что перед точками стоит обратная косая черта, поскольку в выражениях UNIX точка имеет специальное значение — “любой символ”, а в этом случае нам необходимо, чтобы в конце сокращенийстоял символ “точка”.Перед таким обозначением, как Street, должно стоять название улицы.
Обычно оносостоит из прописной буквы, за которой следует несколько строчных букв. В UNIX этотобразец можно описать с помощью выражения [A-Z][a-z]*. Однако названия некоторых улиц состоят из нескольких слов, например, “Rhode Island Avenue in WashingtonDC”. Поэтому, обнаружив, что названия такого вида пропущены, необходимо исправитьнаше описание таким образом, чтобы получилось следующее выражение.'[A-Z][a-z]*( [A-Z][a-z]*)*'Это выражение начинается с группы, состоящей из прописной буквы и, возможно,нескольких строчных букв. Далее может следовать несколько групп, состоящих изпробела, еще одной прописной буквы и, возможно, нескольких строчных. В выражениях UNIX пробел является обычным символом, и, чтобы представленное выше выражение не выглядело в командной строке UNIX как два выражения, разделенныхпробелом, нужно все выражение заключить в апострофы.
Сами апострофы не являются частью выражения.Теперь в адрес нужно включить номер дома. Большинство номеров домов представляют собой цепочки из цифр. Однако в некоторых номерах после цифр стоит буква, например, “123A Main St.” Поэтому выражение для номеров должно включать необязательную прописную букву после цифр: [0-9]+[A-Z]?.
Заметьте, что мы здесь использовали UNIX-оператор + для “одной или нескольких” цифр и оператор ? для “ни однойили одной” прописной буквы. Полное выражение для адресов улиц будет иметь следующий вид.'[0-9]+[A-Z]? [A-Z][a-z]*( [A-Z][a-z]*)*(Street|St\.|Avenue|Ave\.|Road|Rd\.)'Используя это выражение, получим вполне приемлемый результат. Однако в какой-томомент мы обнаружим, что пропустили следующие случаи.1.Улицы, которые называются иначе, чем “street”, “avenue” или “road”.
Например, мыупустили “Boulevard” (бульвар), “Place” (площадь), “Way” (дорога) и их сокращения.2.Названия улиц, которые являются числами или частично содержат числа, например,“42nd Street” (42-я улица).3.Почтовые ящики и маршруты сельской доставки.4.Названия улиц, которые не оканчиваются словом типа “Street”. Например, “ElCamino Real in Silicon Valley”. С испанского это переводится как “Королевское шоссе в Силиконовой Долине”, но если сказать “El Camino Real Road” (“Королевское3.3.
ÏÐÈÌÅÍÅÍÈÅ ÐÅÃÓËßÐÍÛÕ ÂÛÐÀÆÅÍÈÉСтр. 131131шоссе шоссе”), то это будет повторением. Так что приходится иметь дело с адресами типа “2000 El Camino Real”.5.Все другие странные ситуации, которые мы даже не можем вообразить. А вы можете?Таким образом, с помощью компилятора регулярных выражений процесс постепенного приближения к полному распознавателю адресов существенно упрощается по сравнению с использованием традиционного языка программирования.3.3.4. Óïðàæíåíèÿ ê ðàçäåëó 3.33.3.1.(!) Напишите регулярное выражение для описания телефонных номеров всехвидов, которые только можно себе представить. Учтите международные номера,а также тот факт, что в разных странах используется разное количество цифр вкодах областей и в локальных номерах телефонов.3.3.2.(!!) Напишите регулярное выражение для представления заработной платы в томвиде, в котором она указывается в объявлениях о работе.
Учтите, что можетбыть указан размер зарплаты в час, в неделю, месяц или год. Она может включать или не включать знак доллара или какой-либо другой единицы, например“К”. Рядом может находиться слово или слова, обозначающие, что речь идет озарплате. Предложение: просмотрите рекламные объявления в газетах или списки вакансий в режиме on-line, чтобы получить представление о том, какие образцы могут вам пригодиться.3.3.3.(!) В конце раздела 3.3.3 мы привели несколько примеров изменений, которыемогут быть внесены в регулярное выражение, описывающее адреса. Модифицируйте построенное там выражение таким образом, чтобы включить все упомянутые варианты.3.4.
Àëãåáðàè÷åñêèå çàêîíû äëÿ ðåãóëÿðíûõ âûðàæåíèéВ примере 3.5 мы столкнулись с необходимостью упрощения регулярных выраженийдля того, чтобы их размер не превышал разумные пределы. Мы объяснили, почему одновыражение можно было заменить другим. Во всех рассмотренных ситуациях основнойвывод заключался в том, что эти выражения оказывались эквивалентными, т.е. задавалиодин и тот же язык. В этом разделе будет предложен ряд алгебраических законов, позволяющих рассматривать вопрос эквивалентности двух регулярных выражений на болеевысоком уровне.
Вместо исследования определенных регулярных выражений, мы рассмотрим пары регулярных выражений с переменными в качестве аргументов. Два выражения с переменными являются эквивалентными, если при подстановке любых языковвместо переменных оба выражения представляют один и тот же язык.132Стр. 132ÃËÀÂÀ 3. ÐÅÃÓËßÐÍÛÅ ÂÛÐÀÆÅÍÈß È ßÇÛÊÈРассмотрим подобный пример в алгебре обычной арифметики. Одно дело сказать,что 1 + 2 = 2 + 1. Данный частный случай закона коммутативности операции сложениялегко проверить: выполнив операцию сложения в обеих частях этого равенства, получим3 = 3. Однако коммутативный закон сложения утверждает большее, а именно, что x + y= y + x, где x и y — переменные, которые можно заменять любыми двумя числами. Следовательно, он гласит, что, какие бы числа мы ни складывали, получим один и тот же результат независимо от порядка суммирования.Регулярные выражения, подобно обычным арифметическим, подчиняются ряду законов.
Многие из них подобны законам арифметики, если рассматривать объединение каксложение, а конкатенацию — как умножение. Однако в некоторых случаях эта аналогиянарушается. Кроме того, существует ряд законов для регулярных выражений, которым варифметике аналогов нет, особенно если речь идет об операторе итерации.
Следующиеразделы содержат перечень главных законов для регулярных выражений. В завершениеобсуждается вопрос, как вообще можно проверить, является ли некоторый формулируемый для регулярных выражений закон на самом деле законом, т.е. выполняется ли он длялюбых языков, подставляемых вместо его переменных.3.4.1. Àññîöèàòèâíîñòü è êîììóòàòèâíîñòüКоммутативность — это свойство операции, заключающееся в том, что при перестановке ее операндов результат не меняется.
Арифметический пример мы уже приводили выше: x + y = y + x. Ассоциативность — это свойство операции, позволяющее перегруппировывать операнды, если оператор применяется дважды. Например, ассоциативный закон умножения имеет вид: (x × y) × z = x × (y × z). Для регулярных выраженийвыполняются три закона такого типа.• L + M = M + L, т.е. коммутативный закон для объединения утверждает, что дваязыка можно объединять в любом порядке.• (L + M) + N = L + (M + N). Этот закон — ассоциативный закон объединения —говорит, что для объединения трех языков можно сначала объединить как двапервых, так и два последних из них. Обратите внимание на то, что вместе с коммутативным законом объединения этот закон позволяет объединять любое количество языков в произвольном порядке, разбивая их на любые группы, и результат будет одним и тем же.
Очевидно, что некоторая цепочка принадлежит объединению L1 U L2 U … U Lk тогда и только тогда, когда она принадлежит одномуили нескольким языкам Li.• (LM)N = L(MN). Этот ассоциативный закон конкатенации гласит, что для конкатенации трех языков можно сначала соединить как два первых, так и два последних из них.3.4. ÀËÃÅÁÐÀÈ×ÅÑÊÈÅ ÇÀÊÎÍÛ ÄËß ÐÅÃÓËßÐÍÛÕ ÂÛÐÀÆÅÍÈÉСтр. 133133В предложенном списке нет “закона” LM = ML, гласящего, что операция конкатенации является коммутативной, поскольку это утверждение неверно.Пример 3.10. Рассмотрим регулярные выражения 01 и 10. Эти выражения задают языки{01} и {10}, соответственно. Поскольку эти языки различаются, то общий закон LM = MLдля них не выполняется.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
