lex (813547), страница 6
Текст из файла (страница 6)
Поэтому целесообразно построить различные альтернативы для групп месяцевравной продолжительности и объединить их с помощью конструкции выбора.В частности, для распознавания дат месяцев январь, март, май, июль, август, октябрь идекабрь, с продолжительностью 31 день, может быть использована следующая альтернатива:(Jan|Mar|May|Jul|Aug|Oct|Dec)[ ](0?[1-9]|[12][0-9]|3[01])Соответствующая альтернатива для месяцев апрель, июнь, сентябрь и ноябрь, где только 30дней, имеет следующий вид:(Apr|Jun|Sep|Nov)[ ]([123]0|[012]?[1-9])Наконец, для февраля, где может быть либо 28, либо 29 дней, требуется составить следующуюотдельную альтернативу:Feb[ ](0?[1-9]|[12][0-9])Для более лаконичной записи этих трех альтернатив можно ввести регулярные определенияDATE31, DATE30 и FEBRUARY, соответственно.
Тогда их объединение с помощьюконструкции выбора образует следующее регулярное выражение, которое обеспечивает поискдат любого месяца года, независимо от продолжительности месяца:{DATE31}|{DATE30}|{FEBRUARY}В некоторых случаях необходимо обеспечить поиск дат, где кроме числа и месяца указан год. Вобщем случае год может представляться любыми натуральными числами. Регулярноевыражение для спецификации натуральных чисел было рассмотрено выше, для иллюстрацииприменения квантификатора итерации. Таким образом, составление регулярного выражениядля корректного распознавания даты в общем случае превращается в сложную проблему,особенно когда необходимо различать високосные и не високосные годы при анализефевральских дат.Еще один пример, где для конструирования регулярного выражения применяется структурныйподход, демонстрирует, каким образом может быть решена задача поиска во входном потокезаписей времени суток.
Допустим, во входном потоке требуется находить записи времени в12-ти часовом формате AM/PM, где часы, минуты и необязательные секунды, разделенысимволом двоеточия, например, 10:15:00, 8:30 или 08:30:00. Очевидно, что регулярноевыражение, которому соответствует указанный формат времени суток, должно состоять из трехчастей, которые специфицируют часы, минуты и необязательные секунды, соответственно.Наиболее просто составить регулярное выражение для распознавания записи минут и секунд.Запись минут или секунд должна состоять из двух десятичных цифр, причем первая цифраограничена диапазоном от 0 до 5, а вторая цифра может быть любой. Таким образом, дляраспознавания записи минут или секунд можно рекомендовать следующий регулярныйфрагмент, который образует конкатенация двух символьных классов:[0-5][0-9]Чтобы специфицировать регулярное выражение для распознавания часов, нужно рассмотретьдва отдельных случая, когда запись часов состоит из двух и из одной значащей цифры.
Приэтом необходимо учесть, что первая цифра записи часа из двух цифр может быть только 1, авторая цифра может представляться 0, 1 или 2. Когда запись часа состоит только из однойцифры, она может быть любой.Объединение этих двух альтернатив в конструкции выбора образует следующий фрагментрегулярного выражения для распознавания записи часов:1[012]|[1-9]Конкатенациярассмотренныхрегулярныхфрагментовдлязаписейчасов,минутинеобязательных секунд позволяет составить следующее регулярное выражение для поискавремени суток в 12-ти часовом формате AM/PM:(1[012]|[1-9]):[0-5][0-9](:[0-5][0-9])?[ ](am|pm)В этом регулярном выражении круглые скобки используются для ограничения областидействия конструкций выбора и группировки необязательных символьных классов, которыеобозначают секунды.Допустим теперь, что во входном потоке требуется находить записи времени в 24-часовомформате, где часы, минуты и необязательные секунды по-прежнему должны быть разделенысимволом двоеточия, например, 23:59:59, 8:30 или 08:30.
Очевидно, что регулярноевыражение, которому соответствует указанный формат времени суток, также должно состоятьиз трех частей, которые специфицируют часы, минуты и необязательные секунды,соответственно. Совершенно понятно, что фрагменты регулярных выражений для записи минути секунд должны быть идентичны в обеих шкалах измерения времени суток. Однакорегулярное выражение для записи часов должно строится на основе иных соображений. Чтобыспецифицировать регулярное выражение для записи часов, естественно разделить сутки на тригруппы часов: утро, от 0 до 9-ти часов, день, от 10-ти до 19-ти часов и вечер, от 20-ти до 23-хчасов. Очевидно, что объединение этих трех альтернатив в регулярном выражении покрываетсуточный диапазон в часах.
Наиболее простое решение, которое отражает предложеннуюдекомпозицию часов и спецификацию минут, реализует следующее регулярное выражение:(0?[0-9]|1[0-9]|2[0-3]):[0-5][0-9](:[0-5][0-9])?Аналогично рассмотренному выше регулярному выражению для поиска времени суток в 12-тичасовом формате AM/PM, в этом регулярном выражении символьные классы после двоеточияспецифицируют запись минут и необязательных секунд, а объединение альтернатив,ограниченное круглыми скобками, обеспечивает распознавание любого часа суток. Композицияпервых двух альтернатив в круглых скобках на основании дистрибутивного закона позволяетполучить следующее логически менее очевидное, но более компактное регулярное выражение,которое эквивалентно регулярному выражению, рассмотренному выше:([01]?[0-9]|2[0-3]):[0-5][0-9](:[0-5][0-9])?Формальную эквивалентность обоих регулярных выражений для времени суток доказываетследующая цепочка тождественных преобразований первых двух альтернатив исходногорегулярного выражения:0?[0-9]|1[0-9] = 0[0-9]|[0-9]|1[0-9] = (0|1)?[0-9] = [01]?[0-9]Полученные регулярные выражения для распознавания даты месяца и времени суток могутбыть дополнены спецификацией года, который в общем случае может задаваться любымнатуральным числом, а затем объединены в следующую комплексную конструкцию:{DATE}[ ]{TIME}[ ]{YEAR}В этом регулярном выражении для сокращения записи используются регулярные определенияDATE, TIME и YEAR, которые обозначают рассмотренные выше регулярные фрагменты,специфицирующие дату, время и год, соответственно.
Оно позволяет обнаружить во входномпотоке, например, следующую запись: Jan 1 00:00:00 1970, которая обозначает базовуюточку отсчета, принятую в OS UNIX для измерения временных интервалов.Обобщаяполученныерезультаты,следуетотметить,чторассмотренныепримерыиллюстрируют применение принципа декомпозиции, который наиболее часто используется длясоставления регулярных выражений в сложных случаях, когда решение неочевидно инеобходим структурный анализ проблемы. Принцип декомпозиции состоит в том, чтобызаменитьрешениесложнойисходнойпроблемырассмотрениемразличныхчастныхальтернатив, которые затем объединяются в результирующее регулярное выражение спомощью конструкции выбора или конкатенации обязательных фрагментов.НЕРЕГУЛЯРНЫЕ МНОЖЕСТВАВ заключение обзора регулярных выражений следует отметить, что их возможности далеко небезграничныдажедлярасширенныхдиалектов,которыеиспользуютсовременныеинструментальные средства обработки символьной информации, в частности генератор LEX.Существуют формальные языки, множества слов которых не могут быть специфицированы спомощью аппарата регулярных выражений.Вчастности,регулярныесбалансированныхиливыражениявложенныхнемогутконструкций,бытьиспользованыкоторыехарактерныдлядляописанияязыковпрограммирования высокого уровня.
Например, множество всех слов из сбалансированныхскобок не может быть задано регулярным выражением.Регулярные выражения также нельзя применить для описания повторяющихся конструкций,где количество повторений подчиняется определенной закономерности. К этому классуотносятся, например, различные множества слов, длины определенных фрагментов которыхобразуют бесконечную возрастающую последовательность целых чисел, где разности соседнихэлементов не ограничены в совокупности. Это означает, что в такой последовательности всегдаможно найти пару соседних чисел, разность которых превосходит величину сколь угоднобольшого целого числа.Такому условию удовлетворяет, например, последовательность квадратов, кубов или другихстепеней чисел натурального ряда. В частности, невозможно составить регулярнуюспецификацию для распознавания бинарных векторов, в которых количество нулей междудвумя не стоящими рядом единицами постоянно удваивается. Таким свойством обладает,например, следующая бесконечная последовательность:1010010000111000000001...Точно также нельзя построить регулярное выражение для распознавания бесконечной бинарнойпоследовательности, где номера позиций единичных элементов являются квадратаминатуральных чисел, а на все остальные позиции заполнены нулями.
Начальный фрагмент такойпоследовательности для, например, пяти единичных элементов образует следующий бинарныйвектор, где символы 1 находятся, соответственно, в позициях с номерами 1, 4, 9, 16 и 25:1001000010000001000000001Перечень примеров бесконечных последовательностей, для описания которых не удаетсяпостроить регулярные выражения, можно легко расширить, включая в него любые бесконечныепоследовательности без повторяющихся фрагментов. Однако, несмотря на указанныеограничения области применения, формальный аппарат регулярных выражений предоставляетудобные инструментальные средства для обработки текстовых данных в подавляющембольшинстве других практически интересных случаев.КОНЕЧНЫЕ АВТОМАТЫ РЕГУЛЯРНЫХ ВЫРАЖЕНИЙСогласно теореме Клини любому регулярному выражению можно поставить в соответствиеконечный автомат, который является формальной моделью алгоритма распознавания лексем,обозначаемых данным регулярным выражением. В наиболее общих терминах конечныйавтомат-распознаватель определяется конечным множеством характерных для него состоянийвходного потока и переходов между ними.
Изменение состояния происходит при получениисимволов входного потока из заданного алфавита в соответствии с функцией переходов,которая определяет возможные последующие состояния по входному символу и текущемусостоянию. Среди возможных состояний выделяется исходное (начальное) и заключительные(допускающие) состояния в которых конечный автомат-распознаватель может находиться,соответственно, при начале и завершении обработки лексем входного потока. Если входнаяпоследовательность символов может порождать последовательность переходов, которая можетпереводить конечный автомат из начального состояния в одно из заключительных, то онасчитается допускающей и принадлежит распознаваемому им регулярному множеству.Конечныйавтомат-распознавательможетбытьреализованвдетерминированноминедетерминированном варианте.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
