Особенности представления алгебраических операций над регулярными языками. Операторы, основные принципы работы с регулярными выражениями, способы их построения. Разработка программ для поиска в тексте необходимой информации, их тестирование и отладка.
Аннотация к работе
Регулярные выражения (РВ) - это очень удобная форма записи так называемых регулярных или автоматных языков. Поэтому РВ используются в качестве входного языка во многих системах, обрабатывающих цепочки. В замкнутом полукольце всех языков в алфавите рассмотрим подалгебру, порожденную множеством, которое состоит из пустого языка, языка , всех языков (каждый из которых содержит единственную однобуквенную цепочку), и замкнутую относительно итерации.Как говорилось выше: регулярные выражений обозначают (задают, или представляют) языки. Оно определяет язык всех цепочек, состоящих либо из одного нуля, за которым следует любое количество единиц, либо из одной единицы, за которой следует произвольное количество нулей. Объединение двух языков L и M, обозначаемое L M - это множество цепочек, которые содержатся либо в L, либо в M, либо в обоих языках. Конкатенация языков L и M - множество цепочек, которые можно образовать путем дописывания к любой цепочке из K любой цепочки из M. Итерация (“звездочка”, или замыкание Клини) языка L обозначается L и представляет собой множество всех тех цепочек, которые можно образовать путем конкатенации любого количества цепочек из L.Основным средством для поиска образцов (шаблонов) в тексте являются регулярные выражения, задающие “схему” образца, который нужно распознать. Регулярные выражения компилируются в детерминированные или недетерминированные автоматы, которые затем моделируются дл получения программы распознавания образов в тексте. Данный формат, можно использовать как шаблон или образец, и с помощью регулярных выражений, извлечь сведения о пользователях не составит труда. Как говорилось при постановке задачи, программа будет извлекать из текста данные по некоторому шаблону. Для примера, создадим программу, которая будет проверять текст, и в случае если найдет конструкцию .regtest, будет извлекать слово, написанное перед точкой.В ходе выполнения данной работы, были рассмотрены основные принципы работы с регулярными выражениями, а также способы их построения. Регулярные выражения подчиняются многим алгебраическим законам арифметики, хотя есть и различия.Листинг программы reg1.cppЛистинг программы reg2.
Вывод
В ходе выполнения данной работы, были рассмотрены основные принципы работы с регулярными выражениями, а также способы их построения.
Регулярные выражения подчиняются многим алгебраическим законам арифметики, хотя есть и различия. Объединение и конкатенация ассоциативны, но только объединение коммутативно Конкатенация дистрибутивна относительно объединения. Объединение идемпотентно.
Также были разработаны две программы на основе регулярных выражений, для поиска в тексте необходимой информации. Данные приложения были протестированные и проверены на правильность функционирования.
Список литературы
1. Хопкрофт, Д. Введение в теорию автоматов, языков и вычислений, 2-е изд. / Д. Хопкрофт, Э. Мотвани, Р. Ульман - М.: Издательский дом “Вильямс”, 2002. - 528 с.
2. СТО ЮУРГУ 04-2008 Стандарт организации. Курсовое и дипломное проектирование. Общие требования к содержанию и оформлению / составители: Т.И. Парубочая, Н.В. Сырейщикова, В.И. Гузеев, Л.В. Винокурова. - Челябинск: Изд-во ЮУРГУ, 2008. - 56 с.
3. Молчанов, А.Ю. Системное программное обеспечение: Учебник для вузов / А.Ю. Молчанов. - СПБ.: Питер, 2006. - 396 с.