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

Содержание 31
ИНФОРМАЦИОННЫЕ СТРУКТУРЫ И ИХ ПРЕОБРАЗОВАНИЕ
Если такой строки нет, то редукция невозможна.
Последний сканируемый символ помещается в стек, и сканируется
следующий символ предложения.
Предшествование m: n
Грамматика m,n предшествования это такая грамматика, которая
удовлетворяет условиям:
1. Все правые части правил единственны.
2. Для любой пары цепочек xy таких, что |x| = m; |y| = n,
выполняется не более одного из трех рассмотренных ниже отношений.
W = xy |x| = m; |y| = n.
x ∘< y, если первый символ цепочки y является головой основы.
x > ∘ y, если последний символ цепочки x является хвостом основы.
x ≗ y, , если последний символ цепочки x и первый символ цепочки y
принадлежат основе.
3.8. Ограниченный контекст
Недопустимость существования двух правил с одинаковыми правыми
частями, ограничивает использование для синтаксического разбора техники
предшествования.
Рассмотрим следующую грамматику:
R := aUa;
Q := bVb;
U := c;
V := c.
К примеру есть цепочка: аса. Это не контекстно-свободная грамматика
и не грамматика простого предшествования, но по контексту легко
установить, на какой символ (U или на V) следует заменить символ "с".
Данный вывод становится возможным на основе анализа ограниченного