![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Функции предшествования
В грамматиках алгоритмических языков число терминальных и нетерминальных символов превышает 200-300, поэтому таблица предшествования занимает большой объём памяти. Для уменьшения этого объёма было предложено вместо таблицы предшествования использовать функции предшествования - числовые функции нечислового аргумента, которые определяются следующим образом:
В соответствии с таблицей предшествования граф строится следующим образом: для каждого символа (отношения предшествования в таблице предшествования) определяются две вершины
Рис. 6.6.
После построения графа выполняется следующая последовательность действий: 1) Все вершины, для которых нет потомков, помечаются индексом “1” и удаляются из рассмотрения вместе с входящими в них дугами. 2) Вершины, у которых все потомки помечены, помечаются значениями на единицу больше, чем максимальный индекс его потомков, после этого эти вершины удаляются из рассмотрения вместе с входящими в них дугами.
Рис. 6.7.
Рассмотрим ещё один способ построения функций предшествования - метод инкрементов: 1) Все значения если
![]() ![]()
![]()
![]()
![]()
Функция предшествования не существует, если значения ее получаются больше, чем величина 2n, где n- общее число символов матрицы предшествования.
|