Размещено на http://www.allbest.ru/

Министерство образования и науки Российской Федерации

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования

«Владимирский государственный университет имени Александра Григорьевича и Николая Григорьевича Столетовых» (ВлГУ)

Кафедра «Физика и прикладная математика»

Курсовая работа

по дисциплине «Теория формальных языков и трансляций»

Тема: «Нисходящий грамматический разбор»

Выполнил:

Кузин Ю.С.

Проверил:

Голубев А.С.

Владимир 2015

СОДЕРЖАНИЕ

ВВЕДЕНИЕ

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

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

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

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

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

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

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

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

ЗАКЛЮЧЕНИЕ

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



ВВЕДЕНИЕ

Регулярные грамматики - это формальный язык поиска и осуществления манипуляций с подстроками в тексте, основанный на использовании метасимволов (символов-джокеров, англ. 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 - конкатенация

PV* и QV*: PQ, = {pq | pP, qQ.};

Р* - итерация

PV*: Р* = {р* | pP}.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4. Если р и q - регулярные выражения, обозначающие регулярные множества Р и Q, то p+q, pq, р* - регулярные выражения, обозначающие регулярные множества PQ, 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).

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

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

Существует простой метод проверки, является или нет заданный язык регулярным. Этот метод основан на проверке так называемой леммы о разрастании языка. Доказано, что если для некоторого заданного языка выполняется лемма о разрастании регулярного языка, то этот язык является регулярным; если же лемма не выполняется, то и язык регулярным не является.

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

Формально эту лемму можно записать так: если дан язык L, то константа р > 0, такая, что если L и || р, то цепочку можно записать в виде = , где 0 < || < р, и тогда ' = i, 'L i 0.

Используя лемму о разрастании регулярных языков, докажем, что язык L = {аnЬn | n > 0} не является регулярным.

Предположим, что этот язык регулярный, тогда для него должна выполняться лемма о разрастании. Возьмем некоторую цепочку этого языка = аnЬn и запишем ее в виде = . Если a+ или b+ то тогда для i = 0 цепочка 0 = не принадлежит языку L, что противоречит условиям леммы; если же a+b+, тогда для i = 2 цепочка 2 = не принадлежит языку L. Таким образом, язык L не может быть регулярным языком.

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

Регулярные выражения и регулярные грамматики связаны между собой следующим образом:

-для любого регулярного языка, заданного регулярным выражением, можно построить регулярную грамматику, определяющую тот же язык;

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

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

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

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

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

Связь регулярных грамматик и конечных автоматов

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

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

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

Все языки программирования определяют нотацию записи «слева направо». В той же нотации работают и компиляторы. Поэтому далее рассмотрены алгоритмы для леволинейных грамматик.

Построение конечного автомата на основе леволинейной грамматики

Пусть имеется леволинейная грамматика G(VT,VN,P,S), необходимо построить эквивалентный ей конечный автомат M(Q,V,,qo,F).

Прежде всего для построения автомата исходную грамматику G необходимо привести к автоматному виду. Известно, что такое преобразование можно выполнить для любой регулярной грамматики. Алгоритм преобразования к автоматному виду был рассмотрен выше, поэтому здесь на данном вопросе останавливаться нет смысла. Можно считать, что исходная грамматика G уже является леволинейной автоматной грамматикой.

Тогда построение конечного автомата M(Q,V,,qo,F) на основе грамматики G(VT, VN, P, S) выполняется по следующему алгоритму.

Шаг 1. Строим множество состояний автомата Q, Состояния автомата строятся таким образом, чтобы каждому нетерминальному символу из множества VN грамматики G соответствовало одно состояние из множества Q автомата М. Кроме того, во множество состояний автомата добавляется еще одно дополнительное состояние, которое будем обозначать Н. Сохраняя обозначения нетерминальных символов грамматики G, для множества состояний автомата М можно записать:

Q=VN{H}.

Шаг 2. Входным алфавитом автомата М является множество терминальных символов грамматики G: V = VT.

Шаг 3. Просматриваем все множество правил исходной грамматики.

Если встречается правило вида AtP, где AVN, tVT, то в функцию переходов (H,t) автомата М добавляем состояние A: A(H,t).

Если встречается правило вида ABtP, где A,BVN, tVT, то в функцию переходов (B,t) автомата М добавляем состояние A: A(B,t).

Шаг 4. Начальным состоянием автомата М является состояние Н: qo = Н.

Шаг 5. Множество конечных состояний автомата М состоит из одного состояния. Этим состоянием является состояние, соответствующее целевому символу грамматики G: F = {S}.

На этом построение автомата заканчивается.

Построение леволинейной грамматики на основе конечного автомата

Имеется конечный автомат M(Q, V, , qo, F), необходимо построить эквивалентную ему леволинейную грамматику G(VT, VN, P, S).

Построение выполняется по следующему алгоритму.

Шаг 1. Множество терминальных символов грамматики G строится из алфавита входных символов автомата М: VT = V.

Шаг 2. Множество нетерминальных символов грамматики G строится на основании множества состояний автомата М таким образом, чтобы каждому состоянию автомата, за исключением начального состояния, соответствовал один нетерминальный символ грамматики: VN = Q\{qo}.

Шаг 3. Просматриваем функцию переходов автомата М для всех возможных состояний из множества Q для всех возможных входных символов из множества V.

Если имеем (A,t) = , то ничего не выполняем.

Если имеем (A,t) = {B1,B2,...,Bn}, n >0, где AQ, ni0: BiQ, tV, тогда для всех состояний Вi выполняем следующее:

добавляем правило Bit во множество Р правил грамматики G, если А = qo;

добавляем правило BiAt во множество Р правил грамматики G, если A qo.

Шаг 4. Если множество конечных состояний F автомата М содержит только одно состояние F = {F0}, то целевым символом S грамматики G становится символ множества VN, соответствующий этому состоянию: S = Fo; иначе, если множество конечных состояний F автомата М содержит более одного состояния F = {F1, F2,...,Fn}, n>1, тогда во множество нетерминальных символов VN грамматики G добавляется новый нетерминальный символ S: VN = VN{S}, а во множество правил Р грамматики G добавляются правила: SF1 | F2 | ... | Fn.

На этом построение грамматики заканчивается.



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

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

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

(пустое множество) ?.

(пустая строка) е обозначает строку, не содержащую ни одного символа. Эквивалентно «».

(символьный литерал) «a», где a - символ алфавита У.

и следующие операции:

(сцепление, конкатенация) RS обозначает множество {бв | б ? R & в ? S}. Например, {"boy", "girl"}{"friend", "cott"} = {"boyfriend", "girlfriend", "boycott", "girlcott"}.

(дизъюнкция, чередование) R|S обозначает объединение R и S. Например, {"ab", "c"}|{"ab", "d", "ef"} = {"ab", "c", "d", "ef"}.

(замыкание Клини, звезда Клини) R* обозначает минимальное надмножество множества R, которое содержит е и замкнуто относительно конкатенации. Это есть множество всех строк, полученных конкатенацией нуля или более строк из R. Например, {"Go", "Russia"}* = {е, "Go", "Russia", "GoGo", "GoRussia", "RussiaGo", "RussiaRussia", "GoGoGo", "GoGoRussia", "GoRussiaGo", …}.

Синтаксис

Большинство символов в регулярном выражении представляют сами себя за исключением специальных символов [ ] \ / ^ $ . | ? * + ( ) { }, которые могут быть предварены символом \ (обратная косая черта) («экранированы», «защищены») для представления их самих в качестве символов текста. Можно экранировать целую последовательность символов, заключив её между \Q и \E.

Пример	Соответствие
a\.?	a. или a
a\\\\b	a\\b
a\[F\]	a[F]
\Q+-*/\E	+-*/

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

Метасимвол . (точка) означает один любой символ, но в некоторых реализациях исключая символ новой строки.

Набор символов в квадратных скобках [ ] именуется символьным классом и позволяет указать интерпретатору регулярных выражений, что на данном месте в строке может стоять один из перечисленных символов. В частности, [абв]задаёт возможность появления в тексте одного из трёх указанных символов, а [1234567890] задаёт соответствие одной из цифр. Возможно указание диапазонов символов: например, [А-Яа-я] соответствует всем буквам русского алфавита, за исключением букв «Ё» и «ё».

Если требуется указать символы, которые не входят в указанный набор, то используют символ ^ внутри квадратных скобок, например [^0-9] означает любой символ, кроме цифр.

Некоторые символьные классы можно заменить специальными метасимволами:

Символ	Эквивалент	Соответствие
\d	[0-9]	Цифровой символ.
\D	[^0-9]	Нецифровой символ.
\s	[ \f\n\r\t\v]	Пробельный символ.
\S	[^ \f\n\r\t\v]	Непробельный символ.
\w	[[:word:]]	Буквенный или цифровой символ или знак подчеркивания.
\W	[^[:word:]]	Любой символ, кроме буквенного или цифрового символа или знака подчеркивания.

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

Представление	Позиция	Пример	Соответствие
^	Начало строки	^a	aaa aaa
$	Конец строки	a$	aaa aaa
\b	Граница слова	a\b	aaa aaa
		\ba	aaa aaa
\B	Не граница слова	\Ba\B	aaa aaa
\G	Предыдущий успешный поиск	\Ga	aaa aaa (поиск остановился на 4-й позиции - там, где не нашлось a)

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

Рассмотрим грамматику G({"a", "(", "*", ")", "{", "}"}, {S.C.K}, Р, S) (символы а, (, *, ), {, } из множества терминальных символов грамматики взяты в кавычки, чтобы выделить их среди фигурных скобок, обозначающих само множество):

Р:S С*) | К}

С (* | Са | С{ | С} | С( | С* | С)

К . { | Ка | К( | К* | К) | К{

Это леволинейная регулярная грамматика. Она описывает множество комментариев языка Паскаль. Как было показано выше, ее можно преобразовать к автоматному виду.

После преобразования получим леволинейную автоматную грамматику следующего вида: G'({"a", "(", "*",.")", "{", "}"}, {S, D, C, E, K}, P', S):

Р':S E) | К}

D C*

С D* I Са | C{ | C} | C( | C* | C)

E (

К { | Ка | K( | K* | K) | K{

Построим конечный автомат M(Q,V,,qo,F), эквивалентный указанной грамматике.

Шаг 1. Построим множество состояний автомата: Q = VN{H}= {S, E, C, D, K, H}.

Шаг 2. В качестве алфавита входных символов автомата берем множество терминальных символов грамматики. Получаем: V = {"а", "(", "*", ")", "{", "}"}.

Шаг 3. Рассматриваем множество правил грамматики.

Для правил S Е) | К} имеем (Е,")") = {S}; (K,"}") = {S}.

Для правила Е С* имеем (С,"*") = {Е}.

Для правил С D* | Са | С{ | С} | С( | С* | С) имеем (D,"*") = {С}; (С,"а") = {С}; (С,"{") = {С}; (С, "}") = {С}; (С,"(") = {С}; (С, “*”) = {Е.С}; (С, ")") = {С}.

Для правила D ( имеем (Н, "(") = {D}.

Для правил К { | Ка | К( | К* | К) | К{ имеем (Н, "{") = {К}; (К, "а") = {К}; (К, “(") = {К}; (К,"*") = {К}; (К, ")") = {К}; (К, "{") = {К}.

Шаг 4. Начальным состоянием автомата является состояние qo = Н.

Шаг 5. Множеством конечных состояний автомата является множество F = {S}.

Выполнение алгоритма закончено.

В итоге получаем автомат M({S.E,C,D,K,H}, {"а", "(", "*", ")",."{", "}"}. , Н, {S}) с функцией переходов:

(Н, "{") = {K}(H, "(") = {D} (К, "а") = {К} (К, "(") = {К}

(К, "*") = {К} (К, ")") = {К} (К, "{“) = {К} (К, ")") = {S}

(D, "*") = {С} (С, "а") = {С} (С, "{") = {С} (C, "}") = {С}

(С, "(") = {С} (С, "*") = {Е, С}(С, ")") = (С) (Е, “)”) = {S}

Граф переходов этого автомата изображен на рис. 1.

Рис. 1. Недетерминированный КА для языка комментариев в Borland Pascal

Это недетерминированный конечный автомат, поскольку существует состояние, в котором множество, получаемое с помощью функции переходов по одному и тому же символу, имеет более одного следующего состояния. Это состояние С и функция (С,"*") = {Е,С}.

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

В результате всех преобразований получаем детерминированный конечный автомат М'({S.E,С,D, К,Н}, {"а", "(", "*", ")", "{", "}"} .', H, {S}) с функцией переходов:



'(Н, "{") = {К} '(Н, “(") = {D} '(К, "а") = {К} '(К, "(") = {К} '(К, "*") = {К} '(К, ")") = {К}

'(К, "{") = {К} '(К, "}") = {S) '(D, "*") = {С} '(С, "а") = {С} '(С, “{“) = {С} '(С, "}") = {С}

'(С, "(") = {С} '(С, ")") = {С} '(С, "*") = {Е} '(Е, “а") = {С} '(E, “{“) = {С} '(Е, "}") = {С}

'(Е, "(") = {С} '(Е, "*") = {Е} '(Е, ")") = {S}

Граф переходов этого автомата изображен на рис. 2.

Рис. 2. Детерминированный КА для языка комментариев в Borland Pascal

На основании этого автомата можно легко построить распознаватель. В данном случае мы можем получить распознаватель для двух типов комментариев языка Программирования Borland Pascal, если учесть, что а может означать любой алфавитно-цифровой символ, кроме символов (, *, ), {, }.

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

Составим пример грамматики по регулярным выражениям и попробуем построить дерево вывода. Терминальные символы выделены жирным шрифтом. Вместо символа a должны подставляться лексемы.

Дана грамматика вида:

S®T<T | T>T | T<=T | T>=T

E®a*a | a/a | a

T®T+E | T-E | E

Допустимые лексемы входного языка: идентификаторы, целые десятичные числа со знаком.

Описание грамматики входного языка в форме Бэкуса-Наура

Грамматика для распознавания идентификаторов:

Грамматика для распознавания целых десятичных чисел со знаком:

Грамматика для лексического анализатора получается объединением этих 2-х грамматик.

Множества крайних правых и крайних левых символов с указанием шагов построения

Символ	Шаг 1	Последний шаг
(U)	L(U)	R(U)	L(U)	R(U)
S	T	T	TEa	TEa
T	TE	E	TEa	Ea
E	a	a	a	a

Множества крайних правых и крайних левых терминальных символов

Символ	Шаг 1	Шаг 2
(U)	Lt(U)	Rt(U)	Lt(U)	Rt(U)
S	< > <= >=	< > <= >=	< > <= >= +-a	< > <= >=+-a
T	+-	+-	+-a	+-a
E	a	a	a	a

Матрица предшествования для грамматики



Символ	<	>	+	-	*	/	<=	>=	a	к
<			=	=					=
>			=	=					=
+			>	>					<	>
-			>	>					<	>
*									=
/									=
<=			=	=					=
>=			=	=					=
a					=	=				>
н			<	<					<

Пример выполнения разбора предложения

Входная цепочка: a+a<a

{ к a+a<a; н; } п { к+a<a; н a; } c {к+a<a; нE; 10} п {к a<a;

нE+; 10} п {к<a; н E+a;10} с {к<a; н E+Е;10,10} с {к<a; н

E;10,10,5} п {к a; н E<;10,10,5} п {к; н E<a;10,10,5} c {к; н

E<E;10,10,5,10} с {к; н E; 10,10,5,10,1}

Дерево вывода:

Текст программы program Project1;

{$APPTYPE CONSOLE}

uses

SysUtils;

label

X,Y,Z,W,TX,AX;

var

a,i,j,k,count,c,n,g,b,bb,aa,ii:integer;

fin:file of char;

m:real;

fout:text;

ch,del,umn,minus,plus:char;

slovo:array[1..30] of string;

tip:array[1..20] of integer;

tip_:array[1..20] of string;

tmp,tmp_:string;

dl_tmp:integer;

s:string;

t:array[1..20] of string;

tt:array[1..20] of string;

e:array[1..20] of string;

a_:array[1..20] of string;

term:array[1..30] of char;

term_:array[1..30] of char;

nn:array[1..20] of integer;

begin

{ TODO -oUser -cConsole Main : Insert code here }

a:=0;writeln('‡ ¤ ­ЁҐ:');writeln;

writeln('Vipolnit leksicheskii analiz vxodnogo teksta,postroyit tablitsy

leksem');

writeln('I vipolnit sintaksicheskii razbor teksta po zadannoi grammatike s

postroeniem dereva ');

writeln('а §Ў®а .');

writeln('');

writeln('Zadannaya grammatika);writeln('');

writeln('S->T<T|T>T|T<=T|T>=T');

writeln('T->T+E|T-E|E');

writeln;

writeln('Vypolnili studenty VM-31 Petrov,Sorokin');

writeln('');

writeln('!!!!!!!!!!!!!!!!!!!!!WARNING!!!!!!!!!!!!!!!!!!!!!!!!!!!!!');

writeln('Vhodnoi fail dolzhen nahoditsya na diske C:\spo3_in.txt');

writeln('!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!');

writeln;readln;

assign(fin,'C:\spo3_in.txt');reset(fin);

for i:=1 to 30 do

slovo[i]:='';

j:=0;

i:=1;

c:=1;

a:=1;

ii:=1;

count:=0;

s:='';n:=0;

while not eof(fin) do

begin read(fin,ch);

s:=s+ch;n:=n+1;

Y: if(((ch>='a')and(ch<='z'))or((ch>='A')and(ch<='Z')))

then begin if(a=0)then i:=i+1;slovo[i]:=slovo[i]+ch;a:=1;tip[i]:=1;end

else if(ch='+')

then begin i:=i+1;slovo[i]:=slovo[i]+ch;a:=0;tip[i]:=3;end

else if(ch='-')

then begin i:=i+1;slovo[i]:=slovo[i]+ch;a:=0;tip[i]:=4;end

else if(ch='*')

then begin i:=i+1;slovo[i]:=slovo[i]+ch;a:=0;tip[i]:=5;end

else if(ch='/')

then begin i:=i+1;slovo[i]:=slovo[i]+ch;a:=0;tip[i]:=6;end

else if((ch='<')or(ch='>'))

then begin i:=i+1;slovo[i]:=slovo[i]+ch;a:=0;tip[i]:=7;end

else if(ch='=')

then begin slovo[i]:=slovo[i]+ch;a:=0;end

else if(ch='(')

then begin

i:=i+1;tip[i]:=2;

read(fin,ch);s:=s+ch;n:=n+1;a:=0;

slovo[i]:=slovo[i]+ch;

X:read(fin,ch);s:=s+ch;n:=n+1;

if((ch>='0')and(ch<='9'))

then begin slovo[i]:=slovo[i]+ch;goto X;end

else goto Y;

end

else if(ch=')')

then begin end

else begin j:=1;goto Z;end;

end;

close(fin);

for j:=1 to i do

begin

if(tip[j]=1)then tip_[j]:='identificator';

if(tip[j]=2)then tip_[j]:='celoe 10_noe chislo so znakom';

if(tip[j]=3)then tip_[j]:='znak slozheniya';

if(tip[j]=4)then tip_[j]:='znak vichitaniya';

if(tip[j]=5)then tip_[j]:='znak ymnozheniya';

if(tip[j]=6)then tip_[j]:='znak deleniya';

if(tip[j]=7)then tip_[j]:='znak neravenstva';

end;

c:=0;

assign(fout,'C:\spo3_out.txt');rewrite(fout);

writeln(fout,'');writeln(fout,'Tablica lecsem');

writeln(fout,'N Lecsema Tip lecsemi');

for j:=1 to i do

writeln(fout,j,' ',slovo[j],' ',tip_[j]);

writeln(fout,'');writeln(fout,'Derevo vivoda:');

tmp:='';

for j:=1 to 20 do

begin a_[j]:='';t[j]:='';tt[j]:='';e[j]:='';end;

aa:=1;

for j:=1 to n do

begin

if((s[j]='<')or(s[j]='>'))

then begin

for i:=1 to j-1 do

t:=t+s[i];

term:=s[j];

for i:=j+1 to n do

tt:=tt+s[i];

c:=1;

end

else if(s[j]='=')

then begin term:='=';delete(t,1,1);end;

end;

if(c=0)then begin j:=2;goto Z;end;

tmp:='T'+term+term+'T -> ';

write(fout,'S -> ',tmp);

b:=1;a:=1;bb:=0;aa:=3;

TX:

nn[b]:=length(t[b]);

if(nn[b]>0)then

begin

for i:=nn[b] downto 1 do

begin

if((t[b][i]='+')or(t[b][i]='-'))

then begin

if(t[b][i-1]<>'(')then

begin

for g:=i+1 to nn[b] do

e[a]:=e[a]+t[b][g];

term[aa]:=t[b][i];

for g:=1 to i-1 do

t[b+1]:=t[b+1]+t[b][g];

bb:=1;break;

end;end;

end;

if(bb=0)then begin e[a]:=t[b];delete(tmp,1,1);tmp:='E'+tmp;bb:=0;end

else begin delete(tmp,1,1);tmp:='T'+term[aa]+'E'+tmp;bb:=0;end;

a:=a+1;

end;

nn[b]:=length(tt[b]);

if(nn[b]>0)then

begin

for i:=nn[b] downto 1 do

begin

if((tt[b][i]='+')or(tt[b][i]='-'))

then begin

if(tt[b][i-1]<>'(')then

begin

for g:=i+1 to nn[b] do

e[a]:=e[a]+tt[b][g];

aa:=aa+1;

term[aa]:=tt[b][i];

for g:=1 to i-1 do

tt[b+1]:=tt[b+1]+tt[b][g];

bb:=1;break;

end;end;

end;

dl_tmp:=length(tmp);

for g:=dl_tmp downto 1 do

if(tmp[g]='T')then

begin k:=g;break;end;

delete(tmp,k,1);

if(bb=0)then begin insert('E',tmp,k);e[a]:=tt[b];write(fout,tmp);bb:=0;end

else begin

tmp_:='T'+term[aa]+'E';insert(tmp_,tmp,k);write(fout,tmp);bb:=0;end;

a:=a+1;

end;

begin

for g:=1 to length(e[ii]) do

begin

if((e[ii][g]='*')or(e[ii][g]='/'))

then begin

for i:=1 to g-1 do

a_:=a_+e[ii][i];

term_:=e[ii][g];

for i:=g+1 to length(e[ii]) do

a_:=a_+e[ii][i];

bb:=1;break;

end;

end;

for g:=1 to length(tmp) do

if(tmp[g]='E') then

begin delete(tmp,g,1);break;end;

if(bb=0)then begin

insert('a',tmp,g);bb:=0;

end

else begin

tmp_:='a'+term_+'a';

insert(tmp_,tmp,g);bb:=0;

end;

ii:=ii+1;

for g:=1 to length(e[ii]) do

begin

if((e[ii][g]='*')or(e[ii][g]='/'))

then begin

for i:=1 to g-1 do

a_:=a_+e[ii][i];

term_:=e[ii][g];

for i:=g+1 to length(e[ii]) do

a_:=a_+e[ii][i];

bb:=1;break;

end;

end;

for g:=1 to length(tmp) do

if(tmp[g]='E') then

begin delete(tmp,g,1);break;end;

if(bb=0)then begin

insert('a',tmp,g);bb:=0;

end

else begin

tmp_:='a'+term_+'a';

insert(tmp_,tmp,g);bb:=0;

end;

c:=0;ii:=ii+1;

end;

if((length(t[b])>0)or(length(tt[b])>0))

then

begin b:=b+1;goto TX;end;

for g:=length(tmp) downto 1 do

begin

if(tmp[g]='>')then begin delete(tmp,g-1,10);break;end;

end;

write(fout,tmp,'-> ',s);

close(fout);

Z:if(j=1)

then writeln('Leksicheskaya oshibka!');

if(j=2)

then readln;

end.

end.



ЗАКЛЮЧЕНИЕ

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

-регулярные базисные выражения задаются символами и определяют соответствующие регулярные базисные множества, например, выражение f задает одноэлементное множество {f} при условии, что f - символ алфавита T;

-если p и q - регулярные выражения, то операции объединения, конкатенации и итерации - p+q, pq, p*, q* - являются регулярными выражениями, определяющими соответствующие регулярные множества.

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

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

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

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



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

1. Мельников С. В. Perl для профессиональных программистов. Регулярные выражения. - М.: «Бином», 2007.

2. Смит, Билл. Методы и алгоритмы вычислений на строках (regexp) = Computing Patterns in Strings. - М.: «Вильямс», 2006.

3. Форта, Бен. Освой самостоятельно регулярные выражения. 10 минут на урок = Sams Teach Yourself Regular Expressions in 10 Minutes. - М.: «Вильямс», 2005.

4. Фридл, Дж. Регулярные выражения. - СПб.: «Питер», 2001.

5. Ян Гойвертс, Стивен Левитан Регулярные выражения. Сборник рецептов. - СПб.: «Символ-Плюс», 2010.

Размещено на Allbest.ru

...