Хопкрофт, Джон, Э., Мотвани, Раджив, Ульман, Джеффри, Д. - Введение в теорию автоматов, языков и вычислений (1082271), страница 28
Текст из файла (страница 28)
(*!!) Построй~с алгоритм, который по данному ДКА А вычисляет количество цепочек длины и, допускаемых ДКА А (и не связано с количеством состояний автомата А). Ваш алгоритм должен быль полиномиальным как относительно и, так и о~носительно количества состояний А. Указивие. Используйте технику, предложенную в доказательстве теоремы 3,4. 3.3. Применение регулярных выражений Основным средством приложений для поиска образцов (образов, шаблонов) в тексте являются регулярные выражения, задающие "схему" образца, который нужно распознать.
Регулярные выражения компилируются в детерминированные или недетермини- рованные автоматы, которые затем молелируются для получения программы распознавания образов в тексте. В этом разделе мы рассмотрим два важных класса приложений, основанных на регулярных выражениях: лексические анализаторы и поиск в тексте.
3.3.1. Регулярные выражения в ЬМХ Прежде чем рассмотреть данные приложения, ознакомимся с системой обозначений, используемой в 1)МХ для расширенных регулярных выражений. Эти обозначения предоставляют много дополнительных возможностей. На самом деле, расширения 1)М1Х включают некоторые особенности, в частности, возможность именовать и ссылаться на предыдущие цепочки, соответствующие шаблону, что, фактически, позволяет распознавать нерегулярные языки. Здесь эти особенности не рассматриваются, но вволятся со- крашения, позволяющие записывать сложные регулярные выражения в сжатом виде. Первое усовершенствование в системе обозначений регулярных выражений связано с тем, что большинство приложений работает с символами в коде АЗС11. В наших примерах обычно использовался алфавит (О, 1).
Наличие только двух символов позволяет использовать сокращенные выражения вроде 0 + 1 для обозначения "любого символа". Однако если алфавит состоит, скажем, из 128 символов, то аналогичное выражение включало бы список всех этих символов и с~ало бы весьма неудобным для написания. Таким образом, регулярные выражения в ПМ1Х позволяют задавать классы символов для представления множеств символов в наиболес кратком виде. Существуют следующие прави- ла для классов символов. ° Символ .
(точка) обозначает "любой символ'*. ° Последовательность ~а~аж ..аг) обозначает регулярное выражение а~ ь из ч ... + аг ГЛАВА 3. РЕГУЛЯРНЫЕ ВЫРАЖЕНИЯ И ЯЗЫКИ 126 Такое обозначение позволяет записывать примерно вдвое меньше символов, поскольку нет необходимости писать знак "ч-". Например, четыре символа, используемые в операторах сравнения языка С, можно выразить в виде [<>=! ]. ° В квадратных скобках записывается диапазон вида х — у для обозначения всех символов от х до у из последовательности символов в коде АЯС11.
Поскольку коды цифр, а также символов верхнего и нижнего регистров упорядочены, то мно- гие важные классы символов можно записывать с помощью нескольких ключевых цепочек. Например, все цифры могут быть представлены в виде [0-9], символы верхнего регистра могут быть выражены как [А-З], а множество всех букв и пнфр можно записать как [А-За-зО-9]. Если необходимо включить в такой список символов знак минуса, то его помещают в самом начале нли в самом конце списка, чтобы не было путаницы с использованием его для обозначения диапазона символов, Например, набор цифр вместе с точкой и знаками плюс и минус, используемый для образования десятичных чисел со знаком, можно записать в виде выражения [-я. 0-9]. Квадратные скобки и другие символы, имеющие специальные значения в регулярных выражениях [31[]Х, задаются в качестве обычных символов с помощью обратной косой черты [з)перед ними.
° Для некоторых наиболее часто используемых классов символов введены специальные обозначения. Рассмотрим несколько примеров: а) [: с]101г: ] обозначает множество из десяти цифр, как и [0-9] ', б) [: а1р]за: ] обозначает любой символ [латинского) алфавита, каки [А-За-а]; в) [:а1пит: ] обозначает все цифры и буквы [буквенные и цифровые символы), каки [А-ка-я0-9].
Кроме того, в регулярных выражениях ]ЛчПХ используется несколько операторов, с которыми мы раньше не сталкивались. Ни один из этих операторов не расширяет множество выражаемых языков, но иногда облегчает выражение того, что нам нужно. 1. Оператор ~ используется вместо ч- для обозначения объединения, 2. Оператор 7 значит "ни одного или один из". Таким образом, й? в [)з [1Х означает то же, что и а ж )г в системе записи регулярных выражений, принятой в этой кшзге. 3. Оператор + значит "один или несколько из". Следовательно, тг-ь в [)[ч[1Х является сокрашением для зИ в наших обозначениях.
' Преимушество обозначения [: Ждз с: 1 состоит в том, что если вместо кода АЗСП использчется другой, в котором коды пифр расположены не по порядку, то [:еыдзе:) все так же будет обозначать (0123456789А тогда как [0-9) будет представлять все символы, коды которых находятся в промежутке межлу колами лля 0 и для 9 включительно. З.З. ПРИМЕНЕНИЕ РЕГУЛЯРНЫХ ВЫРАЖЕНИЙ 127 4. Оператор (н) обозначает "л копий*'. Таким образом, г((5) в ~3)Ч1Х является сокращенной записью для ЕЛИ()г в наших обозначениях.
Отметим, что в регулярных выражениях (ЛЧ1Х для группирования подвыражений используются скобки, как и в регулярных выражениях из раздела 3.1.2„и тот же порядок приоритетов операторов (в этом смысле?, .ь и (н) трактуются как я). Оператор я используется в 1))ч1Х (конечно же, не как верхний индекс) в рассмотренном выше значении. 3,3.2. Лексический анализ Одним из наиболее ранних применений регулярных выражений было использование их для спецификации компонента компилятора, называемого "лексическим анализатором". Этот компонент сканирует исходную программу и распознает все лексемы, т.е. подцепочки последовательных символов, логически составляющие единое целое. Типичными примерами лексем являются ключевые слова и идентификаторы, но существует и множество других примеров.
Полное описание регулярных выражений в Т)МТХ Читатель, желающий ознакомиться с полным списком операторов и сокращений, используемых в системе записи регулярных выражений в 1)1ч1Х, может найти их на учебных страницах для различных команд. Существуют некоторые различия между версиями ОХ1Х, но команда типа азап дгер выдаст вам обозначения, используемые для команды дгер, которая является основной. Кстати, "втер" означает "01оЬа1 (яеагсЬ гог) неко!аг Ехргезгйоп апб Рппг" (Глобальный поиск регулярного выражения и печать).
1)(ч!Х-команда 1ех н ее ОЬ)1)-версия 21ех получают на вход список регулярных выражений в стиле ()Х1Х, за каждым из которых в фигурных скобках следует код, указывающий, что должен делать лексический анализатор, если найдет экземпляр этой лексемы. Такая система называется генератором лекснческого анализатора, посколь- ку на ее вход поступает высокоуровневое описание лексического анализатора и по этому описанию она создает функцию, которая представляет собой работающий лексический анализатор. Такнс команды, как 1ех и й1ех, оказались очень удобными, поскольку мощность нотации регулярных выражений необходима и достаточна для описания лексем.
Эти команды способны использовать процедуру преобразования регулярного выражения в ДКА для того„чтобы генерировать эффективную функцию, разбивающую исходную программу на лексемы. Они превращают задачу построения лексического анализатора в "послеобеденную работу", тогда как до создания этих основанных на регулярных выра- жениях средств построение лексического анализатора вручную могло занимать несколько месяцев. Кроме того, если по какой-либо причине возникает необхолимость модифи- ГЛАВА 3. РЕГУЛЯРНЫЕ ВЫРАЖЕНИЯ И ЯЗЫКИ 128 (возвращает (ЕЛЕЕ);) (код для ввода найденного идентификатора в таблицу символов; возвращает (1)Э); (возвращает (ЯЕ)г) (возвращает (Е(1);) е1зе [А-Еа-г)[А-2а-хО-9]* Рис, 3.19.
Пример вкоднык данны» команды 1ех Преобразование набора выражений, подобных представленным на рис. 3.19, в автомат происходит почти так же, как это было формально описано в предыдуших разделах. Сначала строится автомат для объединения всех этих выражений. Вообще говоря, этот автомат свидетельствует лишь о том, что распознана какая-гпо лексема. Однако если учесть консзрукцию теоремы 3.7 для объединения выражений, состояние е-НКА точно указывает, к какому типу принадлежит распознанная лексема. 3.3. ПРИМЕНЕНИЕ РЕГУЛЯРНЫХ ВЫРАЖЕНИИ 129 цировать лексический анализатор, то намного проще изменить одно или два регулярных выражения, чем забираться внутрь загадочного кода, чтобы исправить дефект. Пример 3.9. На рис. 3.!9 приведен пример фрагмента входных данных команды 1ех, описывающих некоторые лексемы языка С.
В первой строке обрабатывается ключевое слово е1ве, и ее действие заключается в возвращении символьной константы [в данном примере это ЕЕЕЕ) в программу синтаксического анализа для дальнейшей обработки, Вторая строка содержит регулярное выражение, описывающее идентификаторы: буква, за которой следует нуль или несколько букв и/или цифр. Ее действие заключается в следующем.
Сначала идентификатор заносится в таблицу символов [если его там еще нет). Затем 1ех выделяет найденную лексему в буфере, так что в этой части кода известно, какой именно идентификатор был обнаружен. Наконец, лексический анализатор возвращает символьную константу 1(), с помощью которой в этом примере обозначаются идентификаторы. Третий вход на рис.
3.19 предназначен для знака >а, который является двухсимвольным оператором. В последнем показанном примере обрабатывается односимвольный оператор =. На практике используют выражения, описывающие ключевые слова, знаки и такие символы пунктуации, как запятые или скобки, а также семейства констант, например, числа или цепочки. Многие из этих выражений чрезвычайно просты — это последовательности, состоящие из одного нли нескольких определенных символов. Однако для некоторых выражений требуется вся мощь нотации регулярных выражений. Другими примерами успешного применения возможностей регулярных выражений в командах типа 1ех служат целые числа, числа с плавающей точкой, символьные цепочки и комментарии. П Единственная проблема заключается в том, что лексема может одновременно иметь сразу несколько типов; например, цепочка е1ве соответствует не только регулярному выражению еие, но и выражению для идентификаторов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
