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

Если требуется указать символы, которые не входят в указанный набор, то используют символ ^ внутри квадратных скобок, например [^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.

a,(,*,),{,}

Рис. 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;