Алгоритм 7.1. Поиск основы сентенции грамматики

Если грамматика является грамматикой простого предшествования, то для поиска основы каждой ее сентенции надо просматривать элементы сентенции слева направо и найти самую левую пару символов x_j и x_{j +1}, такую что x_j×>x_{j +1}. Окончанием основы сентенции будет x_j. Далее просматривать элементы сентенции справа налево, начиная с символа x_j до тех пор, пока не будет найдена самая правая пара символов x_{i -1} и x_i, такая что x_{i -1} <× x_i. Заголовком основы будет символ x_i. Таким образом, будет найдена основа сентенции, имеющая вид x_i x_{i +1} …x_{j -1} x_j. Схема поиска основы сентенции грамматики представлена на рисунке 7.1.

 

x 1

x 2

…

xi- 1

xi

xi +1

…

xj -1

xj

xj+ 1

…

xn

<× … <× = × … = × ×> … ×>

 

Рисунок 7.1 – Схема поиска основы сентенции грамматики

 

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

Определение 7.3. Построение матрицы предшествования основано на двух вспомогательных множествах, определяемых следующим образом:

 

- L (A) = { X | $ A Þ* Xz }, A Î V_N, X Î V, z Î V ^* - множество крайних левых символов относительно нетерминального символа А;

- R (A) = { X | $ A Þ* zX }, A Î V_N, X Î V, z Î V^* - множество крайних правых символов относительно нетерминального символа А.

 

Определение 7.4. Отношения предшествования можно определить с помощью введенных множеств следующим образом:

 

- B_i =× B_j (" B_i, B_j Î V), если и только если существует правило A ® xB_iB_jy Î P, где A Î V_N, x, y Î V ^*;

 

- B_i <× B_j (" B_i, B_j Î V), если и только если существует правило A ® xB_iDy Î P и B_j Î L (D),где A, D Î V_N, x, y Î V ^*;

 

- B_i ×> B_j (" B_i, B_j Î V), если и только если существует правило A ® xCB_jy и B_i Î R (C) или существует правило A ® xCDy Î P и B_i Î R (C), B_j Î L (D), где A, C, D Î V_N, x, y Î V^*.

 

Матрицу предшествования дополняют символами ^_н и ^_к (начало и конец цепочки). Для них определены следующие отношения предшествования:

 

- ^_н <× X," X Î V, если X Î L (S);

- ^_к ×> X," X Î V, если X Î R (S).

 

Алгоритм 7.2. Построение множеств L (A) и R (A)

Шаг 1. Для каждого нетерминального символа А ищем все правила, содержание А в левой части. Во множество L (A) включаем самый левый символ из правой части правил, а во множество R (A) – самый крайний правый символ из правой части, т.е.

 

" A Î V_N: L ₀(A) = { X | A ® Xy, X Î V, y Î V ^*},

R ₀(A) = { X | A ® yX, X Î V, y Î V ^*}.

 

Шаг 2. Для каждого нетерминального символа А: если множество L (A) содержит нетерминальные символы грамматики А¢, A², …, то множество L (A) надо дополнить символами, входящими в соответствующие множества L (А¢), L (A²) и т.д., … и не входящими в L (A). Аналогичную операцию выполнить для множеств R (A), т.е.

 

" A Î V_N: L_i (A) = L_{i -1}(A)È L_{i -1}(B)," B Î (L_{i -1}(A)Ç V_N),

R _i(A) = R_{i -1}(A)È R_{i -1}(B), " B Î (R_{i -1}(A)Ç V_N).

Шаг 3.Если на предыдущем шаге хотя бы одно множество L (A) или R (A) для некоторого символа грамматики изменилось, то вернуться к шагу 2, иначе построение закончено. Т.е. если существует A Î V_N: R_i (A)¹ R_{i -1}(A) или L_i (A)¹ L_{i -1}(A), то положить i:= i +1 и вернуться к шагу 2, иначе построение закончено и R (A) = R_i (A) и L (A) = L_i (A).

 

Алгоритм 7.3. Функционирование распознавателя для грамматик

Простого предшествования

 

Шаг 1. Поместить в верхушку стека символ ^_н, считывающую головку – в начало входной цепочки символов.

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

- если самый верхний символ стека имеет меньшее или равное предшествование, чем очередной символ входной строки, то производим операцию «сдвиг» (перенос текущего символа из входной цепочки в стек и перемещение считывающей головки на один символ вправо);

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

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

- если в стеке остаются символы ^_н S, а во входном буфере только символ ^_к, то входная строка прочитана полностью, и алгоритм разбора завершен успешно.

 

Пример 7.1. Дана грамматика G ({ a, (,)}, { S, R }, P, S), с правилами P:

1) S ®(R | a; 2) R ® Sa). Построить распознаватель для строки (((aa) a) a)^_к.

 

Этап 1. Построим множества крайних левых и крайних правых символов L (A) и R (A) относительно всех нетерминальных символов грамматики (таблица 7.1).

 

Таблица 7.1 – Построение множеств L (A) и R (A) для грамматики G

 

Шаг	Li (A)	Ri (A)
	L 0(S)={(, a } L 0(R)={ S }	R 0(S)={ R, a } R 0(R)={)}
	L 1(S)={(, a } L 1(R)={ S, (, a }	R 1(S)={ R, a,)} R 1(R)={)}
	L 2(S)={(, a } L 2(R)={ S, (, a }	R 2(S)={ R, a,)} R 2(R)={)}
Результат	L (S)={(, a } L (R)={ S, (, a }	R (S)={ R, a,)} R (R)={)}

 

Этап 2. На основе построенных множеств и правил вывода грамматики составим матрицу предшествования символов (таблица 7.2).

Поясним заполнение матрицы предшествования. В правиле грамматики S ®(R символ (стоит слева от нетерминального символа R. Во множестве L (R) входят символы S, (, a. Ставим знак <× в клетках матрицы, соответствующих этим символам, в строке для символа (.

В правиле грамматики R ® Sa) символ a стоит справа от нетерминального символа S. Во множество R (S) входят символы R, a,). Ставим знак ×> в клетках матрицы, соответствующих этим символам, в столбце для символа a.

В строке символа ^_н ставим знак <× в клетках символов, входящих во множество L (S), т.е. символов (, a. В столбце символа ^_к ставим знак ×> в клетках, входящих во множество R (S), т.е. символов R, a,).

В клетках, соответствующих строке символа S и столбцу символа a, ставим знак =×, т.к. существует правило R ® Sa), в котором эти символы стоят рядом. По тем же соображениям ставим знак =× в клетках строки а и столбца), а также строки (и столбца R.

 

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

 

Символы	S	R	a	(	)	^к
S			=×
R			×>			×>
a			×>		=×	×>
(	<×	=×	<×	<×
)			×>			×>
^н			<×	<×

 

Шаг 3. Функционирование распознавателя для цепочки (((aa)a)a) показано в таблице 7.3.

 

Таблица 7.3 – Алгоритм работы распознавателя цепочки (((aa) a) a)

 

Шаг	Стек	Входной буфер	Действие
	^н	(((aa) a) a)^к	сдвиг
	^н(	((aa) a) a)^к	cдвиг
	^н((	(aa) a) a)^к	cдвиг
	^н(((	aa) a) a)^к	cдвиг
	^н(((a	a) a) a)^к	свертка S ® a
	^н(((S	a) a) a)^к	сдвиг
	^н(((Sa	) a) a)^к	сдвиг
	^н(((Sa)	a) a)^к	свертка R ® Sa)
	^н(((R	a) a)^к	свертка S ®(R
	^н((S	a) a)^к	сдвиг
	^н((Sa	) a)^к	сдвиг
	^н((Sa)	a)^к	свертка R ® Sa)
	^н((R	a)^к	свертка S ®(R
	^н(S	a)^к	сдвиг
	^н(Sa	)^к	сдвиг
	^н(Sa)	^к	свертка R ® Sa)
	^н(R	^к	свертка S ®(R
	^н S	^к	строка принята

 

Шаг 4. Получили следующую цепочку вывода:

 

S Þ(R Þ(Sa)Þ((Ra)Þ((Sa) a)Þ(((Ra) a)Þ(((Sa) a) a)Þ(((aa) a) a).

 

Восходящее дерево вывода цепочки представлено на рисунке 7.2.

 

 

Рисунок 7.2 – Дерево вывода для цепочки (((aa) a) a) в грамматике G