Описание КС-языка с помощью порождающей КС-грамматики не является описанием алгоритма порождения предложений этого языка. Правила подста­новки грамматики — это не последовательность предписаний, а совокупность разрешений, причем порядок применения правил в грамматике произволен, тогда как в алгоритме должен быть задан жесткий порядок применения от­дельных инструкций.

Получение алгоритмического описания процесса распознавания языка яв­ляется одной из первоочередных задач при разработке блока синтаксического анализа транслятора.

Одним из способов описания алгоритма распознавания языка является за­дание его в виде некоторого распознающего устройства. Для КС-языков таки­ми устройствами являются магазинные автоматы (или, иначе, автоматы с магазинной памятью, МП-автоматы).

Дадим формальное определение и содержательное описание функциониро­вания МП-автомата.