Стр. 22 - Информационные структуры и их преобразование

20 Содержание
ИНФОРМАЦИОННЫЕ СТРУКТУРЫ И ИХ ПРЕОБРАЗОВАНИЕ
U V S+ R , W PR+ S.
… V W …
… R S …
Вычисление отношений предшествования
1) R≐ S, U: = …RS…
2) R⋖ S, U: = …RW, W=>+S…
⋖ = (≐) × (PR+)
3) R⋗ S, U: = …VW…, V=>+…R, W=>+S…
⋗ = (S+)T × (≐) × (1+PR+)
Грамматика G(Z) называется грамматикой простого
предшествования или грамматикой 1.1 предшествования, если между двумя
любыми символами из словаря определено не более чем одно отношение и
ни у каких двух правил нет одинаковых правых частей. Запись 1.1 означает,
что для принятия решения о том, действительно ли рассматриваемая часть
сентенциальной формы является основой, используют по одному символу
слева и справа от неё. Если S1 – начальный символ основы и вместе с тем
первый символ рассматриваемого предложения(сентенциальной формы), то
символа S0 не существует. Для фиксации этого факта заключают
предложение между некоторыми символами, не являющимися символами
грамматики: Sj ⋗ # или # ⋖ Sj .
Отношение предшествования представляется двумерным массивом,
элементы которого имеют следующие значения:
Правила находятся в таблице. Организация таблицы должна позволять
по заданной правой части указать соответствующую левую. Символы
входной цепочки просматриваются слева направо и заносятся в стек до тех







•<
>•
=
=
. S если ,3
; S если ,2
;S S если ,1
; несравнимыS и S если ,0
i
i
j i
j i
,
j
j
j i
S
S P 