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

В грамматиках алгоритмических языков число терминальных и нетерминальных символов превышает 200-300, поэтому таблица предшествования занимает большой объём памяти. Для уменьшения этого объёма было предложено вместо таблицы предшествования использовать функции предшествования - числовые функции нечислового аргумента, которые определяются следующим образом:

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

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

		, аналогично,

Рис. 6.6.

После построения графа выполняется следующая последовательность действий:

1) Все вершины, для которых нет потомков, помечаются индексом “1” и удаляются из рассмотрения вместе с входящими в них дугами.

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

, то функция предшествования не существует.

Рис. 6.7.

Рассмотрим ещё один способ построения функций предшествования - метод инкрементов:

1) Все значения и приравниваем к единице.

если , то = +1
если , то = +1
если

1 3 5 5 1 5

1 2 4 6 6 1

Функция предшествования не существует, если значения ее получаются больше, чем величина 2n, где n- общее число символов матрицы предшествования.