dzhon_khopkroft_radzhiv_motvani_dzheffri _ulman_vvedenie_v_teoriyu_avtomatov_yazy kov_i_vychisleniy_2008 (852747), страница 28
Текст из файла (страница 28)
Поскольку коды цифр, а также символов верхнего и нижнего регистров упорядочены, то многие важные классы символов можно записывать с помощью нескольких ключевых цепочек. Например, все цифры могут быть представлены в виде [0-9],символы верхнего регистра могут быть выражены как [A-Z], а множество всехбукв и цифр можно записать как [A-Za-z0-9]. Если необходимо включить втакой список символов знак минуса, то его помещают в самом начале или в самом конце списка, чтобы не было путаницы с использованием его для обозначения диапазона символов. Например, набор цифр вместе с точкой и знаками плюси минус, используемый для образования десятичных чисел со знаком, можно записать в виде выражения [-+.0-9].
Квадратные скобки и другие символы,имеющие специальные значения в регулярных выражениях UNIX, задаются в качестве обычных символов с помощью обратной косой черты (\)перед ними.• Для некоторых наиболее часто используемых классов символов введены специальные обозначения. Рассмотрим несколько примеров:а) [:digit:] обозначает множество из десяти цифр, как и [0-9]4;б) [:alpha:] обозначает любой символ (латинского) алфавита, как и [A-Za-z];в) [:alnum:] обозначает все цифры и буквы (буквенные и цифровые символы), как и [A-Za-z0-9].Кроме того, в регулярных выражениях UNIX используется несколько операторов, скоторыми мы раньше не сталкивались. Ни один из этих операторов не расширяет множество выражаемых языков, но иногда облегчает выражение того, что нам нужно.1.Оператор | используется вместо + для обозначения объединения.2.Оператор ? значит “ни одного или один из”. Таким образом, R? в UNIX означает тоже, что и ε + R в системе записи регулярных выражений, принятой в этой книге.Оператор + значит “один или несколько из”.
Следовательно, R+ в UNIX является сокращением для RR* в наших обозначениях.3.4Преимущество обозначения [:digit:] состоит в том, что если вместо кода ASCII используется другой, в котором коды цифр расположены не по порядку, то [:digit:] все так же будетобозначать [0123456789], тогда как [0-9] будет представлять все символы, коды которых находятся в промежутке между кодами для 0 и для 9 включительно.3.3. ÏÐÈÌÅÍÅÍÈÅ ÐÅÃÓËßÐÍÛÕ ÂÛÐÀÆÅÍÈÉСтр. 1271274.Оператор {n} обозначает “n копий”. Таким образом, R{5} в UNIX является сокращенной записью для RRRRR в наших обозначениях.Отметим, что в регулярных выражениях UNIX для группирования подвыражений используются скобки, как и в регулярных выражениях из раздела 3.1.2, и тот же порядок приоритетов операторов (в этом смысле ?, + и {n} трактуются как ∗).
Оператор ∗ используетсяв UNIX (конечно же, не как верхний индекс) в рассмотренном выше значении.3.3.2. Ëåêñè÷åñêèé àíàëèçОдним из наиболее ранних применений регулярных выражений было использованиеих для спецификации компонента компилятора, называемого “лексическим анализатором”. Этот компонент сканирует исходную программу и распознает все лексемы, т.е.подцепочки последовательных символов, логически составляющие единое целое.
Типичными примерами лексем являются ключевые слова и идентификаторы, но существуети множество других примеров.Ïîëíîå îïèñàíèå ðåãóëÿðíûõ âûðàæåíèé â UNIXЧитатель, желающий ознакомиться с полным списком операторов и сокращений,используемых в системе записи регулярных выражений в UNIX, может найти ихна учебных страницах для различных команд. Существуют некоторые различиямежду версиями UNIX, но команда типа man grep выдаст вам обозначения, используемые для команды grep, которая является основной. Кстати, “grep” означает “Global (search for) Regular Expression and Print” (Глобальный поиск регулярного выражения и печать).UNIX-команда lex и ее GNU-версия flex получают на вход список регулярныхвыражений в стиле UNIX, за каждым из которых в фигурных скобках следует код, указывающий, что должен делать лексический анализатор, если найдет экземпляр этойлексемы.
Такая система называется генератором лексического анализатора, поскольку на ее вход поступает высокоуровневое описание лексического анализатора и поэтому описанию она создает функцию, которая представляет собой работающий лексический анализатор.Такие команды, как lex и flex, оказались очень удобными, поскольку мощностьнотации регулярных выражений необходима и достаточна для описания лексем. Эти команды способны использовать процедуру преобразования регулярного выражения вДКА для того, чтобы генерировать эффективную функцию, разбивающую исходнуюпрограмму на лексемы. Они превращают задачу построения лексического анализатора в“послеобеденную работу”, тогда как до создания этих основанных на регулярных выражениях средств построение лексического анализатора вручную могло занимать несколько месяцев.
Кроме того, если по какой-либо причине возникает необходимость модифи128Стр. 128ÃËÀÂÀ 3. ÐÅÃÓËßÐÍÛÅ ÂÛÐÀÆÅÍÈß È ßÇÛÊÈцировать лексический анализатор, то намного проще изменить одно или два регулярныхвыражения, чем забираться внутрь загадочного кода, чтобы исправить дефект.Пример 3.9. На рис. 3.19 приведен пример фрагмента входных данных команды lex,описывающих некоторые лексемы языка С. В первой строке обрабатывается ключевоеслово else, и ее действие заключается в возвращении символьной константы (в данномпримере это ELSE) в программу синтаксического анализа для дальнейшей обработки.Вторая строка содержит регулярное выражение, описывающее идентификаторы: буква,за которой следует нуль или несколько букв и/или цифр.
Ее действие заключается в следующем. Сначала идентификатор заносится в таблицу символов (если его там еще нет).Затем lex выделяет найденную лексему в буфере, так что в этой части кода известно,какой именно идентификатор был обнаружен. Наконец, лексический анализатор возвращает символьную константу ID, с помощью которой в этом примере обозначаютсяидентификаторы.Третий вход на рис. 3.19 предназначен для знака >=, который является двухсимвольным оператором. В последнем показанном примере обрабатывается односимвольныйоператор =. На практике используют выражения, описывающие ключевые слова, знаки итакие символы пунктуации, как запятые или скобки, а также семейства констант, например, числа или цепочки. Многие из этих выражений чрезвычайно просты — это последовательности, состоящие из одного или нескольких определенных символов.
Однакодля некоторых выражений требуется вся мощь нотации регулярных выражений. Другимипримерами успешного применения возможностей регулярных выражений в командахтипа lex служат целые числа, числа с плавающей точкой, символьные цепочки и комментарии. else[A-Za-z][A-Za-z0-9]*>==...{возвращает (ELSE);}{код для ввода найденного идентификаторав таблицу символов;возвращает (ID);}{возвращает (GE);}{возвращает (EQ);}Рис. 3.19. Пример входных данных команды lexПреобразование набора выражений, подобных представленным на рис.
3.19, в автомат происходит почти так же, как это было формально описано в предыдущих разделах.Сначала строится автомат для объединения всех этих выражений. Вообще говоря, этотавтомат свидетельствует лишь о том, что распознана какая-то лексема. Однако еслиучесть конструкцию теоремы 3.7 для объединения выражений, состояние ε-НКА точноуказывает, к какому типу принадлежит распознанная лексема.3.3. ÏÐÈÌÅÍÅÍÈÅ ÐÅÃÓËßÐÍÛÕ ÂÛÐÀÆÅÍÈÉСтр. 129129Единственная проблема заключается в том, что лексема может одновременно иметьсразу несколько типов; например, цепочка else соответствует не только регулярномувыражению else, но и выражению для идентификаторов.
В генераторе лексического анализатора применяется следующее стандартное решение: приоритет отдается выражению,находящемуся в списке первым. Таким образом, если необходимо, чтобы ключевые слова типа else были зарезервированными (т.е. не использовались в качестве идентификаторов), то они просто перечисляются в списке перед выражением для идентификаторов.3.3.3. Ïîèñê îáðàçöîâ â òåêñòåВ разделе 2.4.1 мы отметили, что автоматы могут применяться для эффективного поиска наборов определенных слов в таких больших хранилищах данных, как Web.
Хотяинструментальные средства и технология для этого пока не настолько хорошо развиты,как для лексических анализаторов, регулярные выражения все же очень полезны дляописания процедур поиска желаемых образцов. Как и для лексических анализаторов,возможность перехода от естественного, описательного представления в виде регулярных выражений к эффективной (основанной на автоматах) реализации является важныминтеллектуальным средством решения поставленной задачи.Общая проблема, для решения которой технология регулярных выражений оказаласьвесьма полезной, заключается в описании нечетко определенного класса образцов в тексте.
Нечеткость описания, в сущности, является гарантией того, что с самого начала нетнужды корректно и полно описывать образцы. Не исключено, что мы никогда не сможемполучить точное и полное описание. С помощью регулярных выражений можно, не прилагая больших усилий, описывать такие образцы и быстро изменять эти описания, еслирезультат нас не устраивает.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
