Функции предшествования

Использование матриц с предшествованием.

S ® BC

B ® Axz

C ® xx

A ® xy

Считаем, что она построена.

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

xyxzxx - проставляем все значки

├ <* x =* y∙*> x =* z∙*> x =* x *> ┤

├ <* A ∙ x ∙ y ∙*> x ∙ x ∙ *> ┤

├ <* B <* x =* x *> ┤

├ <* B =* C *> ┤

├ S ┤

Алгоритм распознавания:

1. Между символами строки вставляются отношения предшествования.

5. Строка просматривается слева направо до первого символа ∙*> , после этого просмотр идет в обратном направлении до первого встречаемого символа *<∙ - между этими символами и находится свертка, то есть правая часть правила, которая заменяется левой.

3. Восстанавливаются отношения предшествования.

4. Возвращение к первому пункту. Процесс продолжается до получения начального нетерминального символа. Если этот процесс не завершиться успешно, строка не принадлежит данной грамматике.

У этого метода есть минусы:

1. Далеко не во всех случаях удается построить грамматику с предшествованиями.

2. На практике символов может быть много сотен сотни и в результате получается слабозаполненная матрица большой размерности.

Этот интересный метод придумал Р.Флойд – автор многих остроумных решений в программировании. Вместо матрицы строятся две специальные функции f и g , такие что:

1. Если S_i∙*> S_j Þ f(S_i) > g(S_j).

2. Если S_i <* S_j Þ f(S_i) < g(S_j).

3. Если S_i =* S_j Þ f(S_i) = g(S_j).

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

Построение функций предшествования:

0. Строится матрица предшествования и начальные значения функций принимаются равными единице: f(S_i) = g(S_j) = 1.

1. Матрица просматривается по строкам в поисках отношений ∙*> и, если

f(S_i) > g(S_j), то идем дальше, если же S_i *> S_j, а f(S_i) ≤ g(S_j), то увеличиваем значение f(S_i) - f(S_i) = g(S_j) + 1.

2. Матрица просматривается по столбцам в поисках отношений <*∙ и, если

f(S_i) < g(S_j), то идем дальше, если же S_i <* S_j, а f(S_i) ³ g(S_j), то увеличиваем значение g(S_j) - g(S_j) = f(S_i) + 1.

3. Матрица просматривается в поисках отношений =* и, если f(S_i) = g(S_j), то идем дальше, если S_i =* S_j, а f(S_i) ¹ g(S_j), то выравниваем значения функций путем увеличения меньшего из значений до большего - f(S_i) = g(S_j) = max[f(S_i), g(S_j) ].

4. Возвращение к первому пункту.

Повторять до тех пор, пока рост функций не прекратится (или когда значение одной из функций не превысит 2*n, где n - размерность матрицы - в этом случае алгоритм не сходится).

Пример.

На основе матрицы предшествования в соответствии с описанным алгоритмом построим функции предшествования.

Уточняемые значения функций будем располагать левее строк и выше столбцов с соответствующими символами.

g(S_j)

f(S_i)

	A	B	C	D	E
A		∙>	<∙	∙>	∙
B		∙
C	<∙
D	∙>
E		∙		∙>

В результате получим числовые значения (табличных) функций для всех символов.

Однако, этот метод не свободен от недостатков:

1. Алгоритм не всегда сходится (не всегда приводит.к построению функций).

2. При переходе к функциям происходит «незаконное доопределение» матрицы. То есть как бы появляются отношения предшествования между парами символов, для которых в исходной матрице отношение отсутствовало.