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

32 Содержание
ИНФОРМАЦИОННЫЕ СТРУКТУРЫ И ИХ ПРЕОБРАЗОВАНИЕ
числа элементов. В данном случае используется 1:1 ограниченный
контекстный преобразователь.
Определение 1:1 ограниченного контекстного распознавателя
Пусть в грамматике G(Z) имеется вывод Z => +xTuRy.
Также пусть имеется правило: U := u.
Тогда, если в процессе разбора сентенциальной формы в стеке
окажется …xTu, а входной символ будет R, то цепочку u следует привести к
нетерминалу U. При такой конструкции: …TuR… необходимо уметь
определить, является ли цепочка u простой фразой для нетерминала U.
Пример :
Цепочка: Z => …VR…;
Правило: V := Tu;
То имеем вывод: Z => +…TuR.
Но так как правила U := u у нас нет, мы не можем произвести замену
цепочки u на нетерминал U. Если бы такое правило было, то можно было
построить 1:1 ограниченный контекстный преобразователь.
Алгоритм 1:1 ограниченного контекстного преобразователя
Распознаватель пользуется единственной таблицей, которая содержит 3
столбца. В первом находится возможное содержимое стека в форме Tu.
Т - любой символ или ограничитель.
U - правая часть правила.
Во втором столбце находятся соответствующие правые контексты. В
третьем столбце указывается номер правила, которое используется в этом
случае.
На каждом шаге работы распознаватель среди строк таблицы ищет ту,
в которой содержимое первого столбца совпадает с верхней частью стека. А
содержимое второго столбца совпадает с последним считанным символом.
Если такая строка найдена, осуществляется редукция. Основа в стеке
заменяется в соответствии с правилом, номер которого указан в третьем