Реферат (стр. 1 )

СОДЕРЖАНИЕ

ВВЕДЕНИЕ        3

ГЛАВА 1. ТЕОРЕТИЧЕСКИЕ ОСНОВЫ ГРАММАТИКИ ПО РЕГУЛЯРНЫМ ВЫРАЖЕНИЯМ        5

1.1. Сущность регулярных операций и выражений        5

1.2. Свойства регулярных языков        8

1.3. Взаимосвязь регулярных множеств, регулярных грамматик и конечных автоматов        11

ГЛАВА 2. ПРАКТИКА СОЗДАНИЯ ГРАММАТИКИ ПО РЕГУЛЯРНЫМ ВЫРАЖЕНИЯМ И ПОСТРОЕНИЕ ДЕРЕВА ВЫВОДА        15

2.1. Состав и синтаксис регулярных выражений        15

2.2. Пример построения конечного автомата на основе заданной грамматики        17

2.3. Разработка программы грамматики по регулярным выражениям и построение дерева вывода        20

ЗАКЛЮЧЕНИЕ        28

СПИСОК ЛИТЕРАТУРЫ        30

ВВЕДЕНИЕ

Регулярные выражения - это формальный язык поиска и осуществления манипуляций с подстроками в тексте, основанный на использовании метасимволов (символов-джокеров, англ. wildcard characters). По сути это строка-образец (англ. pattern, по-русски её часто называют «шаблоном», «маской»), состоящая из символов и метасимволов и задающая правило поиска.

Регулярные выражения произвели прорыв в электронной обработке текстов в конце XX века. Набор утилит (включая редактор sed и фильтр grep), поставляемых в дистрибутивах UNIX, одним из первых способствовал популяризации регулярных выражений для обработки текстов. Многие современные языки программирования имеют встроенную поддержку регулярных выражений. Среди них ActionScript, Perl, Java, PHP, JavaScript, языки платформы. NET Framework, Python, Tcl, Ruby, Lua, Gambas, C++(стандарт 2011 года) и др.

Регулярные выражения используются некоторыми текстовыми редакторами и утилитами для поиска и подстановки текста. Например, при помощи регулярных выражений можно задать шаблоны, позволяющие:

-найти все последовательности символов «кот» в любом контексте, как то: «кот», «котлета», «терракотовый»;

-найти отдельно стоящее слово «кот» и заменить его на «кошка»;

-найти слово «кот», которому предшествует слово «персидский» или «чеширский»;

-убрать из текста все предложения, в которых упоминается слово кот или кошка.

Регулярные выражения позволяют задавать и гораздо более сложные шаблоны поиска или замены.

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

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

Объектом курсовой работы являются регулярные выражения в языке Pascal.

Задачами курсовой работы является:

- рассмотрение теоретических основ создания регулярных выражений;

- анализ синтаксиса регулярных выражений;

- практика создания грамматики по регулярным выражениям и построения дерева вывода.

Структура курсовой работы. Курсовая работа состоит из введения, двух глав, заключения и списка литературы.

ГЛАВА 1. ТЕОРЕТИЧЕСКИЕ ОСНОВЫ ГРАММАТИКИ ПО РЕГУЛЯРНЫМ ВЫРАЖЕНИЯМ

1.1. Сущность регулярных операций и выражений

Рассмотрим специальный класс операций над языками - регулярные операции. Множество языков, получаемое из элементарных языков в результате применения конечного числа регулярных операций, - регулярные множества.

Способ их описания - регулярные выражения и недетерминированные конечные автоматы, допускающие цепочки из этих множеств.

Определение регулярного множества

Определим над множествами цепочек символов из алфавита V операции конкатенации и итерации следующим образом:

РQ - конкатенация P?V* и Q?V*: PQ, = {pq | ?p?P, ?q?Q.};

Р* - итерация P?V*: Р* = {р* | ?p?P}.

Тогда для алфавита V регулярные множества определяются рекурсивно:

1. ? - регулярное множество.

2. {?} - регулярное множество.

3. {а} - регулярное множество ?a?V.

4. Если Р и Q, - произвольные регулярные множества, то множества P?Q, PQ и Р* также являются регулярными множествами.

5. Ничто другое не является регулярным множеством.

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

Три основных способа, с помощью которых можно задавать регулярные языки – это:

-регулярные (праволинейные и леволинейные) грамматики,

-конечные автоматы (КА) и

-регулярные множества (равно как и обозначающие их регулярные выражения).

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

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

Утверждение 1. Язык является регулярным множеством тогда и только тогда, когда он задан леволинейной (праволинейной) грамматикой.

Утверждение 2. Язык может быть задан леволинейной (праволинейной) грамматикой тогда и только тогда, когда он является регулярным множеством.

Утверждение 3. Язык является регулярным множеством тогда и только тогда, когда он задан с помощью конечного автомата.

Утверждение 4. Язык распознается с помощью конечного автомата тогда и только тогда, когда он является регулярным множеством.

Все три способа определения регулярных языков эквивалентны. Существуют алгоритмы, которые позволяют для регулярного языка, заданного одним из указанных способов, построить другой способ, определяющий тот же самый язык. Это не всегда справедливо для других способов, которыми можно определить регулярные языки.

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

Регулярные множества можно обозначать с помощью регулярных выражений. Эти обозначения вводятся следующим образом:

1. 0 - регулярное выражение, обозначающее ?.

2. ? - регулярное выражение, обозначающее {?}.

3. а - регулярное выражение, обозначающее {a} ?a?V.

4. Если р и q - регулярные выражения, обозначающие регулярные множества Р и Q, то p+q, pq, р* - регулярные выражения, обозначающие регулярные множества P?Q, PQ и Р* соответственно.

Два регулярных выражения ? и ? равны, ? = ?, если они обозначают одно и то же множество.

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

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

Если ?, ? и ? - регулярные выражения, то свойства регулярных выражений можно записать в виде следующих формул:

1. ?+??* = ?+?*? = ?*

2. ?+? = ?+?.

3. ?+(?+?) = (?+?)+?

4. ?(?+?) = ??+??

5. (?+?)? = ??+??

6. ?(??) = (??)?

7. ?+? = ?

8. ?+?* = ?*

9. ?+?* = ?*+? = a*

10. 0* = ?

11. 0? = ?0 = 0

12. 0+? = ?+0 = ?

13. ?? = ?? = ?

14. (?*)* = ?*

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

Следует также обратить внимание на то, что среди прочих свойств отсутствует равенство ?? = ??, то есть операция конкатенации не обладает свойством коммутативности. Это и не удивительно, поскольку для этой операции важен порядок следования символов.

1.2. Свойства регулярных языков

Множество называется замкнутым относительно некоторой операции, если в результате выполнения этой операции над любыми элементами, принадлежащими данному множеству, получается новый элемент, принадлежащий тому же множеству.

Например, множество целых чисел замкнуто относительно операций сложения, умножения и вычитания, но оно не замкнуто относительно операции деления - при делении двух целых чисел не всегда получается целое число.

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

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

-пересечения;

-объединения;

-дополнения;

-итерации;

-конкатенации;

-гомоморфизма (изменения имен символов и подстановки цепочек вместо символов).

Поскольку регулярные множества замкнуты относительно операций пересечения, объединения и дополнения, то они представляют булеву алгебру множеств. Существуют и другие операции, относительно которых замкнуты регулярные множества. Вообще говоря, таких операций достаточно много.

Регулярные языки представляют собой очень удобный тип языков. Для них разрешимы многие проблемы, неразрешимые для других типов языков.

Например, доказано, что разрешимыми являются следующие проблемы.

Проблема эквивалентности. Даны два регулярных языка L1(V) и L2(V). Необходимо проверить, являются ли эти два языка эквивалентными.

Проблема принадлежности цепочки языку. Дан регулярный язык L(V) и цепочка символов ??V*. Необходимо проверить, принадлежит ли цепочка данному языку.

Проблема пустоты языка. Дан регулярный язык L(V). Необходимо проверить, является ли этот язык пустым, то есть найти хотя бы одну цепочку ???, такую что ??L(V).

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

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