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

ГЛАВА 3

Регулярные выражения и языки

В этой главе вводится система записи "регулярных выражений". Такие выражения пред­ставляют собой еще один способ определения языков, рассмотренный вкратце в разде­ле 1.1.2. Регулярные выражения можно рассматривать также как "язык программирова­ния" для описания некоторых важных приложений, например, программ текстового поиска или компонентов компилятора. Регулярные выражения тесно связаны с НКА и могут служить удобной альтернативой для описания программных компонентов.

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

3.1. Регулярные выражения

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

Команды поиска, например, команда grep операционной системы UNIX или анало­гичные команды для поиска цепочек, которые можно встретить в Web-броузерах или системах форматирования текста. В таких системах регулярные выражения ис­пользуются для описания шаблонов, которые пользователь ищет в файле. Различные поисковые системы преобразуют регулярное выражение либо в ДКА, либо в НКА и применяют этот автомат к файлу, в котором производится поиск. Генераторы лексических анализаторов, такие как Lex или Flex. Напомним, что лек­сический анализатор — это компонент компилятора, разбивающий исходную про­грамму на логические единицы {лексемы), которые состоят из одного или несколь­ких символов и имеют определенный смысл. Примерами лексем являются ключевые слова (например while), идентификаторы (любая буква, за которой следует нуль или несколько букв и/или цифр) и такие знаки, как + или < = . Генератор лексических анализаторов получает формальные описания лексем, являющиеся по существу ре­гулярными выражениями, и создает ДКА, который распознает, какая из лексем по­является на его входе.

3.1.1. Операторы регулярных выражений

Регулярные выражения обозначают (задают, или представляют) языки. В качестве простого примера рассмотрим регулярное выражение 01*+10*. Оно определяет язык всех цепочек, состоящих либо из одного нуля, за которым следует любое количество единиц, либо из одной единицы, за которой следует произвольное количество нулей. В данный момент мы не рассчитываем, что читатель знает, как интерпретируются регулярные вы­ражения, поэтому наше утверждение о языке, задаваемом этим выражением, пока долж­но быть принято на веру. Чтобы понять, почему наша интерпретация заданного регуляр­ного выражения правильна, необходимо определить все использованные в этом выраже­нии символы, поэтому вначале познакомимся со следующими тремя операциями над языками, соответствующими операторам регулярных выражений1.

Объединение двух языков L и М, обозначаемое L\J М, — это множество цепочек, ко­торые содержатся либо в L, либо в М, либо в обоих языках. Например, если L = {001, 10, 111} и М= {Ј, 001}, то LUМ= {Ј, 10, 001, 111}. Конкатенация языков L и М— это множество цепочек, которые можно образовать путем дописывания к любой цепочке из L любой цепочки из М. Выше в разделе 1.5.2 было дано определение конкатенации двух цепочек: результатом ее является запись одной цепочки вслед за другой. Конкатенация языков обозначается либо точкой, ли­бо вообще никак не обозначается, хотя оператор конкатенации часто называют "точкой". Например, если L= {001, 10, 111} и М - {Ј,001}, то L. M, или просто LM, — это {001, 10, 111, 001001, 10001, 111001}. Первые три цепочки в LM— это цепочки из L, соединенные с Ј. Поскольку Ј является единицей (нейтральным эле­ментом) для операции конкатенации, результирующие цепочки будут такими же, как и цепочки из L. Последние же три цепочки в LM образованы путем соединения каж­дой цепочки из L со второй цепочкой из М, т. е. с 001. Например, 10 из L, соединен­ная с 001 из М, дает 10001 для LM.

3. Итерация ("звездочка", или замыкание Клини2) языка I обозначается L* и представ­ляет собой множество всех тех цепочек, которые можно образовать путем конкате­нации любого количества цепочек из L. При этом допускаются повторения, т. е. одна и та же цепочка из L может быть выбрана для конкатенации более одного раза. На­пример, если L = {0, 1}, то L* — это все цепочки, состоящие из нулей и единиц. Если L = {0, 11}, то в L' входят цепочки из нулей и единиц, содержащие четное количест­во единиц, например, цепочки 011, 11110 или Ј, и не входят цепочки 01011 или 101. Более формально язык L* можно представить как бесконечное объединение Ueo L\ где L0 = {Ј},/,'=/, и L1 для i > 1 равен LL...L (конкатенация i копий L).

Пример 3.1. Поскольку идея итерации языка может показаться довольно сложной, рассмотрим несколько примеров. Для начала возьмем L= {0, 11}. L° = {Ј} независимо от языка L\ нулевая степень означает выбор нулевого количества цепочек из языка L. Ll = L, что означает выбор одной цепочки из L. Таким образом, первые два члена в разложении L* дают {е, 0, 11}.

Далее рассмотрим /Л Выберем две цепочки из L и, поскольку их можно выбирать с повторениями, получим четыре варианта, которые дают L2 = {00, 011, 110, 1111}. Анало­гично, Z,3 представляет собой множество цепочек, образованных троекратным выбором из двух цепочек языка L. Следовательно, ll имеет вид

{000, 0011,0110, 1100,01111, 11011, 11110, 111111}

Для вычисления L необходимо вычислить L' для каждого i и объединить все эти язы­ки. Язык Z,1 содержит 21 элементов. Хотя каждое множество V конечно, объединение бес­конечного числа множеств L1 образует, как правило, бесконечный язык, что справедливо, в частности, и для нашего примера.

Пусть теперь L — множество всех цепочек, состоящих из нулей. Заметим, что такой язык бесконечен, в отличие от предыдущего примера, где был рассмотрен конечный язык. Однако нетрудно увидеть, что представляет собой L*. Как всегда, L0 = {Ј}, l) = L. L2 — это множество цепочек, которые можно образовать, если взять одну цепочку из нулей и соединить ее с другой цепочкой из нулей. В результате получим цепочку, так­же состоящую из нулей. Фактически, любую цепочку из нулей можно записать как конкатенацию двух цепочек из нулей (не забывайте, что Ј — тоже "цепочка из нулей"; она всегда может быть одной из двух соединяемых цепочек). Следовательно, L2 = L. Аналогично, I? = L и так далее. Таким образом, бесконечное объединение L* = Z,0 U Ll U L2 U •■■ совпадает с L в том особом случае, когда язык L является множеством всех нулевых цепочек.

В качестве последнего примера рассмотрим 0 = {е}. Заметим, что 0°= {Ј}, тогда как 01 для любого / > 1 будет пустым множеством, поскольку мы не можем выбрать ни одной цепочки из пустого множества. Фактически, 0 является одним из всего двух язы­ков, итерация которых не является бесконечным множеством. □

3.1.2. Построение регулярных выражений

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

Использование оператора "звездочка"

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

Предположим, что L — это язык, содержащий цепочки длины 1, и для каждого сим­вола а из Е существует цепочка а в [.. Тогда, хотя L и Ј "выглядят" одинаково, они принадлежат к различным типам: L представляет собой множество цепочек, а 2 — множество символов. С другой стороны, L* обозначает тот же язык, что и Ј*.

Алгебра регулярных выражений строится по такой же схеме: используются констан­ты и переменные для обозначения языков и операторы для обозначения трех операций из раздела 3.1.1 — объединение, точка и звездочка. Регулярные выражения можно опреде­лить рекурсивно. В этом определении не только характеризуются правильные регуляр­ные выражения, но и для каждого регулярного выражения Е описывается представлен­ный им язык, который обозначается через L(E).

Базис. Базис состоит из трех частей.

Константы Ј и 0 являются регулярными выражениями, определяющими языки {Ј} и 0, соответственно, т. е. L(e) = {Ј} и Ц0) = 0. Если а — произвольный символ, то а — регулярное выражение, определяющее язык {а}, т. е. 1(a) = {а}. Заметим, что для записи выражения, соответствующего символу, используется жирный шрифт. Это соответствие, т. е. что а относится к а, должно быть очевидным.

3. Переменная, обозначенная прописной курсивной буквой, например, L, представляет произвольный язык.

Индукция. Индуктивный шаг состоит из четырех частей, по одной для трех операто­ров и для введения скобок.

Если Е и F— регулярные выражения, то E+F— регулярное выражение, опреде­ляющее объединение языков L(E) и L(F), т. е. L(E + F) = L(E) U L(F)- Если E и F — регулярные выражения, то EF — регулярное выражение, определяю­щее конкатенацию языков L(E) и L(F). Таким образом, L(EF) = L(E)L(F). Заметим, что для обозначения оператора конкатенации— как операции над языками, так и оператора в регулярном выражении — можно использовать точку. Например, регу­лярное выражение 0.1 означает то же, что и 01, и представляет язык {01}. Однако мы избегаем использовать точку в качестве оператора конкатенации в регулярных выражениях4. Если Е— регулярное выражение, то Е*— регулярное выражение, определяющее итерацию языка Ь(Е). Таким образом, ЦБ') = (ЦБ))'. Если Е — регулярное выражение, то (Е) — регулярное выражение, определяющее тот же язык L(E), что и выражение Е. Формально, L{{E)) = L(E).

Выражения и соответствующие языки