Хопкрофт, Джон, Э., Мотвани, Раджив, Ульман, Джеффри, Д. - Введение в теорию автоматов, языков и вычислений (1082271), страница 29

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 29)

В генераторе лексического ана- лизатора применяется следующее стандартное решение: приоритет отдается выражению, находящемуся в списке первым. Таким образом, если необходимо, чтобы ключевые слова типа е1ве были зарезерелроеаяными (т.е. не использовались в качестве идентификаторов), то они просто перечисляются в списке перед выражением для идентификаторов. 3.3.3. Поиск образцов в тексте В разделе 2.4.1 мы отметили, что автоматы могут применяться для эффективного поиска наборов определенных слов в таких больших хранилищах данных, как УЬеЬ.

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

Нечеткость описания, в сущности, является гарантией того, что с самого начала нет нужды корректно и полно описывать образцы. Не исключено, что мы никогда не сможем получить точное и полное описание. С помощью регулярных выражений можно, не прилагая больших усилий, описывать такие образцы и быстро изменять эти описания, если результат нас не устраивает. Кроме того, "компилятор" для регулярных выражений пригоден и для преобразования записываемых выражений в выполнимый код. В качестве примера обсудим одну типичную проблему, возникающую во многих >УеЬ- приложениях.

Предположим, необходимо просмотреть огромное количество >УеЬ-страниц и отметить адреса. Возможно, мы хотим составить список электронных адресов. Или пытаемся классифицировать фирмы по их месторасположению, чтобы отвечать на запросы типа "найдите мне ресторан в пределах 1О-ти минут езды от того места, где я сейчас нахожусь". В частности, мы сосредоточим внимание на распознавании названий >лиц, Что такое название улицы? Необходимо это выяснить, и, если во время тестирования программы будет установлено, что пропущены какие-то варианты, то нужно будет изменять выражения ~аким образом, чтобы включить все, что не было учтено. Начнем с того, что название улицы может заканчиваться словом "Зггее!*' (улица) или его сокрашением "Зь" Однако некоторые люди живут на "Атепоез" (проспектах) или "Еоабз" (шоссе), что тоже может быть записано в сокращенном виде.

Таким образом, в качестве окончания нашего выражения можно использовать следующие варианты. Бсгеес ~ БГ>. ~ Ачепие ~ Аке>. ~ йоас1 ~ йс1>. ГЛАВА 3. РЕГУЛЯРНЫЕ ВЫРАЖЕНИЯ И ЯЗЫКИ 130 В этом выражении использованы обозначения в стиле ()МХ с вертикальной чертой вместо + для оператора объединения. Обратите также внимание, что перед точками стоит обратная косая черта, поскольку в выражениях [)Х1Х точка имеет специальное значение — "любой символ", а в этом случае нам необходимо, чтобы в конце сокращений стоял символ "точка". Перед таким обозначением, как Ясгеес, должно стоять название улицы.

Обычно оно состоит из прописной буквы, за которой следует несколько строчных букв. В [)Н1Х этот образец можно описать с помощью выражения [А-Е ] [а-а ] . Однако названия некоторых улиц состоят из нескольких слов, например, "К(зобе 1э!апд Ачепие (и %азп!пйгоп ))С". Поэтому, обнаружив, что названия такого вида пропущены, необходимо исправить наше описание таким образом, чтобы получилось следующее выражение, ' [А-3) [а-а] ( [А-2) [а-э]*) Это выражение начинается с группы, состоящей из прописной буквы и, возможно, нескольких строчных букв. Далее может следовать несколько групп, состоящих из пробела, еще одной прописной буквы и, возможно, нескольких строчных.

В выражениях ()]41Х пробел является обычным символом, и, чтобы представленное выше выражение не выглядело в командной строке 1)Н1Х как два выражения, разделенных пробелом, нужно все выражение заключить в апострофы. Сами апострофы не являются частью выражения. Теперь в адрес нужно включить номер дома. Большинство номеров домов представляют собой цепочки из цифр.

Однако в некоторых номерах после цифр стоит буква, например, "!2ЗА Ма!и Яь" Поэтому выражение для номеров должно включать необязательную прописную букву после цифр: [0-9) + [А-3]?. Заметьте, что мы здесь использовали ()]ч1Х-оператор + для "одной или нескольких" цифр и оператор ? лля "ни одной или одной" прописной буквы. Полное выражение для адресов улиц будет иметь следующий вид. ' [0-9] Э [А-3]? [А-3) [а-х) * ( [А-2) [а-я] *) * (Ясгеес(ЯС1.(Ачепце)Аче~.(Коас](Кс(~.)' Используя это выражение, получим вполне приемлемый результат Однако в какой-то момент мы обнаружим, что пропустили следующие случаи.

!. Улицы, которые называются иначе, чем "аггее!", "ачепое" или "гоасГ'. Например, мы упустили "Вои!ечагд" (бульвар), "Р!асс" (площадь), "%ау" (дорога) и их сокращения. 2. Названия улиц, которые являются числами или частично содержат числа, например, "42пб Яггее!" (42-я улица). 3. Почтовые ящики и маршруты сельской доставки. 4. Названия улиц, которые не оканчиваются словом типа "Япеег". Например, "Е! Санино Ееа! (и Я(!)соп Ча!!еу". С испанского это переводится как "Королевское шоссе в Силиконовой Долине", но если сказать "Е! Сапппо Кеа! Еоаг)" (" Королевское 3.3. ПРИМЕНЕНИЕ РЕГУЛЯРНЫХ ВЫРАЖЕНИЙ 131 шоссе шоссе"), то это будет повторением.

Так что приходится иметь дело с адреса- ми типа "2000 Е! Сапппо ЕеаГ'. 5. Все другие странные ситуации, которые мы даже не можем вообразить. А вы можете? Таким образом, с помощью компилятора регулярных выражений процесс постепенного приближения к полному распознавателю адресов существенно упрощается по срав- нению с использованием традиционного языка программирования. 3.3.4. Упражнения к разделу 3.3 П) Напишите регулярное выражение для описания телефонных номеров всех видов, которые только можно себе представить. Учтите международные номера, а также тот факт, что в разных странах используется разное количество цифр в кодах областей и в локальных номерах телефонов.

3.3.1. (!!) Напишите регулярное выражение для представления заработной платы в том виде, в котором она указывается в объявлениях о работе. Учтите, что может быть указан размер зарплаты в час, в неделю, месяц или год. Она может включать или не включать знак доллара или какой-либо другой единицы, например "К". Рядом может находиться слово или слова, обозначающие, что речь идет о зарплате. Предложение: просмотрите рекламные объявления в газетах или списки вакансий в режиме оп-йпе, чтобы получить представление о том, какие об- 3.3.2. разцы могут вам пригодиться.

(!) В конце раздела 3.3.3 мы привели несколько примеров изменений, которые могут быть внесены в регулярное выражение, описывающее адреса. Модифици- руйте построенное там выражение таким образом, чтобы включить все упомя- нутые варианты. ЗЗ.З. 3.4. Алгебраические законы для регулярных выражений ГЛАВА 3. РЕГУЛЯРНЫЕ ВЫРАЖЕНИЯ И ЯЗЫКИ 132 В примере 3.5 мы столкнулись с необходимостью упрощения регулярных выражений для того, чтобы их размер не превышал разумные пределы.

Мы объяснили, почему одно выражение можно бьшо заменить другим. Во всех рассмотренных ситуациях основной вывод заключался в том, что эти выражения оказывались эквивалентными, т.е. задавали один и тот же язык. В этом разделе будет предложен ряд алгебраических законов, позволяющих рассматривать вопрос эквивалентности двух регулярных выражений на более высоком уровне.

Вместо исследования определенных регулярных выражений, мы рассмотрим пары регулярных выражений с переменными в качестве аргументов. Два выражения с переменными являются эквивалентны ив, если при подстановке любых языков вместо переменных оба выражения представляют один и тот же язык. Рассмотрим подобный пример в ачгебре обычной арифметики. Одно дело сказать, что 1+ 2 = 2+ 1. Данный частный случай закона коммутативности операции сложения легко проверить: выполнив операцию сложения в обеих частях этого равенства, получим 3 = 3.

Однако комиутативный закон сложения утверждает большее, а именно, что х+у = у+ х, где х ну — переменные„которые можно заменять любыми двумя числами. Следовательно, он гласит, что, какие бы числа мы ни складывали, получим один и тот же ре- зультат независимо от порядка суммирования. Регулярные выражения, подобно обычным арифметическим, подчиняются ряду законов. Многие из них подобны законам арифметики, если рассматривать объединение как сложение, а конкатенацию — как умножение. Однако в некоторых случаях эта аналогия нарушается. Кроме того, существует ряд законов для регулярных выражений, которым в арифметике аналогов нет, особенно если речь идет об операторе итерации.

Следующие разделы содержат перечень главных законов для регулярных выражений. В завершение обсуждается вопрос, как вообще можно проверить, является лн некоторый формулируемый для регулярных выражений закон на самом деле законом, т.е, выполняется ли он для любых языков, подставляемых вместо его переменных. 3.4.1. Ассоциативность и коммутативность Колсиутативность — это свойство операции, заключающееся в том, что при перестановке ее операндов результат не меняется. Арифметический пример мы уже приводили выше: х+ у = у+ х.

Характеристики

Список файлов книги