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

30 Содержание
ИНФОРМАЦИОННЫЕ СТРУКТУРЫ И ИХ ПРЕОБРАЗОВАНИЕ
2) RS =>∘T тогда и только тогда, когда Z=>+…[R]Ux =>...RSTx .
Чтобы получился этот вывод, нужно: U: = ST.
3) R∘< ST тогда и только тогда, когда Z=>+…RUТx =>+…RSTx… .
Чтобы получился этот вывод, нужно: U: = S .
4) R∘<= ST тогда и только тогда, когда Z=>+…UТx =>…RSTx… .
Чтобы получился этот вывод, нужно: U: = RS .
Если цепочка # S1 S2 … Si Sj … Sn # – сентенциальная форма, то основа
этой сентенциальной формы будет цепочка Si … Sj , если для неё
выполняется условие
Si-1∘< Si Si+1=>∘ Si+2 … S j-1Sj >∘ Sj+1.
=>∘ этот символ означает, что мы ищем хвост основы.
∘<= этот символ означает, что ищем голову основы.
Si … S j –основа.
# ∘<S # -условие, когда заканчивается поиск.
Может быть ситуация:
# S j >∘ Sj+1 #;
# ∘<SiSj #;
# ∘<S #.
Если найден хвост, то можно просмотреть правила и сравнить правые
части.
Алгоритм распознавания
Распознаватель использует единственную таблицу. Таблица содержит
три столбца.
В первом столбце таблицы содержится содержимое стека в форме Tu,
где Т - любой символ или ограничитель, а U-правая часть правила.
Второй столбец содержит соответствующие правые контексты (либо # -
символ конца цепочки ).
В третьем столбце записан номер правила, которое использовано при
редукции.
На каждом шаге работы распознаватель среди строк таблицы ищет ту,
в которой содержимое первого столбца совпадает с верхней частью стека, а
содержимое второго столбца совпадает с последним считанным символом.
Если такая строка найдена, осуществляется редукция в соответствии с
правилом, номер которого указан в третьем столбце.