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

Содержание 39
ИНФОРМАЦИОННЫЕ СТРУКТУРЫ И ИХ ПРЕОБРАЗОВАНИЕ
STK=#а001#.
д) Так как i=2 и в стеке не содержится #Z#, то делаем вывод, что
цепочка построена неверно.
Определение m: n - ограниченного контекста
Так же, как и в простом предшествовании, расширим ограниченный
контекст до m:n символов.
Пусть имеем правило U:=u ,где для каждой пары цепочек:
|V| = m;
|W| = n.
И некоторый вывод: Z => +..VuW...
Цепочка u является основой сентенциальной формы, и данная цепочка
u может быть заменена на нетерминал U. Такое правило m:n - ограниченно
контекстное, в то время как R[W](то есть R содержит W)содержит R входных
символов. В этом случае можно заменить u на U.
Однако, если в стеке оказывается комбинация, для которой выбор
правил неоднозначен, следует увеличить контекст. С какой стороны это
сделать, рассматривается для каждого случая отдельно.
4. АВТОМАТЫ С МАГАЗИННОЙ ПАМЯТЬЮ, [ МП-АВТОМАТ ]
Конечные автоматы успешно решали задачи распознавания цепочек,
построенных на основе автоматической грамматики. Но эта грамматика не в
состоянии охватить всё множество конструкций языков программирования.
Более приемлемой является КС-грамматика. Для распознавания цепочек
генерируемых КС-грамматикой вводят понятие МП-автомат. Как и в случае с
КА, обработка осуществляется за несколько шагов. В отличие от КА, МП
может обработать входной символ в течение нескольких шагов. Каждый шаг
процесса определяется несколькими правилами, то есть состоянием автомата,
верхним символом магазина и текущим символом входной цепочки.
а 1 а2 …
Устройство управления