Регулярные выражения и языки (стр. 7 )

UNIX-команда lex и ее GNU-версия flex получают на вход список регулярных выражений в стиле UNIX, за каждым из которых в фигурных скобках следует код, ука­зывающий, что должен делать лексический анализатор, если найдет экземпляр этой лексемы. Такая система называется генератором лексического анализатора, посколь­ку на ее вход поступает высокоуровневое описание лексического анализатора и по этому описанию она создает функцию, которая представляет собой работающий лек­сический анализатор.

Такие команды, как lex и flex, оказались очень удобными, поскольку мощность нотации регулярных выражений необходима и достаточна для описания лексем. Эти ко­манды способны использовать процедуру преобразования регулярного выражения в ДКА для того, чтобы генерировать эффективную функцию, разбивающую исходную программу на лексемы. Они превращают задачу построения лексического анализатора в "послеобеденную работу", тогда как до создания этих основанных на регулярных выра­жениях средств построение лексического анализатора вручную могло занимать несколь­ко месяцев. Кроме того, если по какой-либо причине возникает необходимость модифи­цировать лексический анализатор, то намного проще изменить одно или два регулярных выражения, чем забираться внутрь загадочного кода, чтобы исправить дефект.

Пример 3.9. На рис. 3.19 приведен пример фрагмента входных данных команды lex, описывающих некоторые лексемы языка С. В первой строке обрабатывается ключевое слово else, и ее действие заключается в возвращении символьной константы (в данном примере это ELSE) в программу синтаксического анализа для дальнейшей обработки. Вторая строка содержит регулярное выражение, описывающее идентификаторы: буква, за которой следует нуль или несколько букв и/или цифр. Ее действие заключается в сле­дующем. Сначала идентификатор заносится в таблицу символов (если его там еще нет). Затем lex выделяет найденную лексему в буфере, так что в этой части кода известно, какой именно идентификатор был обнаружен. Наконец, лексический анализатор возвра­щает символьную константу ID, с помощью которой в этом примере обозначаются идентификаторы.

Третий вход на рис. 3.19 предназначен для знака >=, который является двухсимволь - ным оператором. В последнем показанном примере обрабатывается односимвольный оператор =. На практике используют выражения, описывающие ключевые слова, знаки и такие символы пунктуации, как запятые или скобки, а также семейства констант, напри­мер, числа или цепочки. Многие из этих выражений чрезвычайно просты — это после­довательности, состоящие из одного или нескольких определенных символов. Однако для некоторых выражений требуется вся мощь нотации регулярных выражений. Другими примерами успешного применения возможностей регулярных выражений в командах типа lex служат целые числа, числа с плавающей точкой, символьные цепочки и ком­ментарии. □

else        {возвращает (ELSE);}

[A-Za-z][A-Za-zO-9]* {код для ввода найденного идентификатора

в таблицу символов;

возвращает (ID); }

>=        {возвращает (GE);}

=        {возвращает (EQ);}

Рис. 3.19. Пример входных данных команды lex

Преобразование набора выражений, подобных представленным на рис. 3.19, в авто­мат происходит почти так же, как это было формально описано в предыдущих разделах. Сначала строится автомат для объединения всех этих выражений. Вообще говоря, этот автомат свидетельствует лишь о том, что распознана какая-то лексема. Однако если учесть конструкцию теоремы 3.7 для объединения выражений, состояние е-НКА точно указывает, к какому типу принадлежит распознанная лексема.

Единственная проблема заключается в том, что лексема может одновременно иметь сразу несколько типов; например, цепочка else соответствует не только регулярному выражению else, но и выражению для идентификаторов. В генераторе лексического ана­лизатора применяется следующее стандартное решение: приоритет отдается выражению, находящемуся в списке первым. Таким образом, если необходимо, чтобы ключевые сло­ва типа else были зарезервированными (т. е. не использовались в качестве идентифика­торов), то они просто перечисляются в списке перед выражением для идентификаторов.

3.3.3. Поиск образцов в тексте

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

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

В качестве примера обсудим одну типичную проблему, возникающую во многих Web - приложениях. Предположим, необходимо просмотреть огромное количество Web-страниц и отметить адреса. Возможно, мы хотим составить список электронных адресов. Или пыта­емся классифицировать фирмы по их месторасположению, чтобы отвечать на запросы типа "найдите мне ресторан в пределах 10-ти минут езды от того места, где я сейчас нахожусь".

В частности, мы сосредоточим внимание на распознавании названий улиц. Что такое название улицы? Необходимо это выяснить, и, если во время тестирования программы будет установлено, что пропущены какие-то варианты, то нужно будет изменять выра­жения таким образом, чтобы включить все, что не было учтено. Начнем с того, что на­звание улицы может заканчиваться словом "Street" (улица) или его сокращением "St." Однако некоторые люди живут на "Avenues" (проспектах) или "Roads" (шоссе), что тоже может быть записано в сокращенном виде. Таким образом, в качестве окончания нашего выражения можно использовать следующие варианты. Street | St\. I Avenue | Ave\. |Road | Rd\.

В этом выражении использованы обозначения в стиле UNIX с вертикальной чертой вместо + для оператора объединения. Обратите также внимание, что перед точками сто­ит обратная косая черта, поскольку в выражениях UNIX точка имеет специальное значе­ние— "любой символ", а в этом случае нам необходимо, чтобы в конце сокращений стоял символ "точка".

Перед таким обозначением, как Street, должно стоять название улицы. Обычно оно состоит из прописной буквы, за которой следует несколько строчных букв. В UNIX этот образец можно описать с помощью выражения [A-Z] [a-z] *. Однако названия некото­рых улиц состоят из нескольких слов, например, "Rhode Island Avenue in Washington DC". Поэтому, обнаружив, что названия такого вида пропущены, необходимо исправить наше описание таким образом, чтобы получилось следующее выражение. ' [A-Z] [a-z]* ( [A-Z] [a-z]*)*'

Это выражение начинается с группы, состоящей из прописной буквы и, возможно, нескольких строчных букв. Далее может следовать несколько групп, состоящих из пробела, еще одной прописной буквы и, возможно, нескольких строчных. В выраже­ниях UNIX пробел является обычным символом, и, чтобы представленное выше вы­ражение не выглядело в командной строке UNIX как два выражения, разделенных пробелом, нужно все выражение заключить в апострофы. Сами апострофы не являют­ся частью выражения.

Теперь в адрес нужно включить номер дома. Большинство номеров домов представ­ляют собой цепочки из цифр. Однако в некоторых номерах после цифр стоит буква, на­пример, "123А Main St." Поэтому выражение для номеров должно включать необяза­тельную прописную букву после цифр: [ 0-9] + [A-Z] ?. Заметьте, что мы здесь исполь­зовали UNIX-оператор + для "одной или нескольких" цифр и оператор? для "ни одной или одной" прописной буквы. Полное выражение для адресов улиц будет иметь следую­щий вид.

' [0-9] + [A-Z]? [A-Z] [a-z] *( [A-Z] [a-z]*)* (Street ISt\. |Avenue IAve\. |Road|Rd\.) '

Используя это выражение, получим вполне приемлемый результат. Однако в какой-то момент мы обнаружим, что пропустили следующие случаи.

Улицы, которые называются иначе, чем "street", "avenue" или "road". Например, мы упустили "Boulevard" (бульвар), "Place" (площадь), "Way" (дорога) и их сокращения. Названия улиц, которые являются числами или частично содержат числа, например, "42nd Street" (42-я улица). Почтовые ящики и маршруты сельской доставки. Названия улиц, которые не оканчиваются словом типа "Street". Например, "Е1 Camino Real in Silicon Valley". С испанского это переводится как "Королевское шос­се в Силиконовой Долине", но если сказать "El Camino Real Road" ("Королевское

шоссе шоссе"), то это будет повторением. Так что приходится иметь дело с адреса­ми типа "2000 El Camino Real". 5. Все другие странные ситуации, которые мы даже не можем вообразить. А вы можете?

Таким образом, с помощью компилятора регулярных выражений процесс постепен­ного приближения к полному распознавателю адресов существенно упрощается по срав­нению с использованием традиционного языка программирования.

3.3.4. Упражнения к разделу 3.3

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

3.4. Алгебраические законы для регулярных выражений

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