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

ВВЕДЕНИЕ

регулярный выражение программа

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

В замкнутом полукольце всех языков в алфавите  рассмотрим подалгебру, порожденную множеством, которое состоит из пустого языка, языка , всех языков  (каждый из которых содержит единственную однобуквенную цепочку), и замкнутую относительно итерации. Эта подалгебра, обозначаемая , есть полукольцо с итерацией. Оно играет важнейшую роль в теории формальных языков. Его называют полукольцом регулярных языков.

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

Конечный автомат (КА) - это преобразователь, который позволяет сопоставить входу соответствующий выход, причем выход этот может зависеть не только от текущего входа, но и от того, что происходило раньше, от предыстории работы конечного автомата.

 

ТЕОРЕТИЧЕСКАЯ ЧАСТЬ

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

 

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

Существуют три операции над языками, соответствующими операторам регулярных выражений:

. Объединение двух языков L и M, обозначаемое L M - это множество цепочек, которые содержатся либо в L, либо в M, либо в обоих языках.

. Конкатенация языков L и M - множество цепочек, которые можно образовать путем дописывания к любой цепочке из K любой цепочки из M. Например, если L = {001, 10, 111} и M = {ε, 001}, то L.M, или просто LM - это {001,10,111, 001001, 10001, 111001}. Первые три цепочки в LM - это цепочки из L, соединенные с ε. Поскольку ε является единицей (нейтральным элементом) для операции конкатенации, результирующие цепочки, будут такими же, как и цепочки из L.

. Итерация (“звездочка”, или замыкание Клини) языка L обозначается L* и представляет собой множество всех тех цепочек, которые можно образовать путем конкатенации любого количества цепочек из L. При этом допускаются повторения, т.е. одна и та же цепочка из L может быть выбрана для конкатенации более одного раза. Например, если L = {0,1}, то L* - это все цепочки, состоящие из нулей и единиц. Если L = {0,11}, то в L* входят цепочки из нулей и единиц, содержащие четное количество единиц, например 011, 11110, ε.

 

Лексический анализ

 

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

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

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

 

ПРАКТИЧЕСКАЯ ЧАСТЬ

ЗАКЛЮЧЕНИЕ

регулярный выражение программа

В ходе выполнения данной работы, были рассмотрены основные принципы работы с регулярными выражениями, а также способы их построения.

Регулярные выражения подчиняются многим алгебраическим законам арифметики, хотя есть и различия. Объединение и конкатенация ассоциативны, но только объединение коммутативно. Конкатенация дистрибутивна относительно объединения. Объединение идемпотентно.

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

 

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

 

1. Хопкрофт, Д. Введение в теорию автоматов, языков и вычислений, 2-е изд. / Д. Хопкрофт, Э. Мотвани, Р. Ульман - М.: Издательский дом “Вильямс”, 2002. - 528 с.

. СТО ЮУрГУ 04-2008 Стандарт организации. Курсовое и дипломное проектирование. Общие требования к содержанию и оформлению / составители: Т.И. Парубочая, Н.В. Сырейщикова, В.И. Гузеев, Л.В. Винокурова. - Челябинск: Изд-во ЮУрГУ, 2008. - 56 с.

. Молчанов, А.Ю. Системное программное обеспечение: Учебник для вузов / А.Ю. Молчанов. - СПб.: Питер, 2006. - 396 с.

 

ПРИЛОЖЕНИЯ

 

ПРИЛОЖЕНИЕ А

Листинг программы reg1.cpp

 

ПРИЛОЖЕНИЕ Б

Листинг программы reg2.cpp

ВВЕДЕНИЕ

регулярный выражение программа

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

В замкнутом полукольце всех языков в алфавите  рассмотрим подалгебру, порожденную множеством, которое состоит из пустого языка, языка , всех языков  (каждый из которых содержит единственную однобуквенную цепочку), и замкнутую относительно итерации. Эта подалгебра, обозначаемая , есть полукольцо с итерацией. Оно играет важнейшую роль в теории формальных языков. Его называют полукольцом регулярных языков.

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

Конечный автомат (КА) - это преобразователь, который позволяет сопоставить входу соответствующий выход, причем выход этот может зависеть не только от текущего входа, но и от того, что происходило раньше, от предыстории работы конечного автомата.

 

ТЕОРЕТИЧЕСКАЯ ЧАСТЬ

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

 

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

Существуют три операции над языками, соответствующими операторам регулярных выражений:

. Объединение двух языков L и M, обозначаемое L M - это множество цепочек, которые содержатся либо в L, либо в M, либо в обоих языках.

. Конкатенация языков L и M - множество цепочек, которые можно образовать путем дописывания к любой цепочке из K любой цепочки из M. Например, если L = {001, 10, 111} и M = {ε, 001}, то L.M, или просто LM - это {001,10,111, 001001, 10001, 111001}. Первые три цепочки в LM - это цепочки из L, соединенные с ε. Поскольку ε является единицей (нейтральным элементом) для операции конкатенации, результирующие цепочки, будут такими же, как и цепочки из L.

. Итерация (“звездочка”, или замыкание Клини) языка L обозначается L* и представляет собой множество всех тех цепочек, которые можно образовать путем конкатенации любого количества цепочек из L. При этом допускаются повторения, т.е. одна и та же цепочка из L может быть выбрана для конкатенации более одного раза. Например, если L = {0,1}, то L* - это все цепочки, состоящие из нулей и единиц. Если L = {0,11}, то в L* входят цепочки из нулей и единиц, содержащие четное количество единиц, например 011, 11110, ε.