Автомат с магазинной памятью (АМП)

 

Как известно, распознавателем КС-языков является автомат с магазинной памятью.

 

 

Операции автомата:

 

1. «Вытолкнуть» – выталкивает из стека верхний символ (↑).

2. «Втолкнуть А» - вталкивает в стек магазинный символ А (↓А).

3. «Заменить XYZ». Эквивалентна: ↑↓X↓Y↓Z (↕XYZ).

4. «Состояние t» - переход АМП в другое состояние ([t]).

5. «Сдвиг» («→») - сдвиг головки на один символ вправо относит. входной ленты.

Переход или шаг автомата – это выполнение операций над стеком и входной головкой, а также изменение состояния.

 

Автомат определяется:

 

1. Конечным множеством входных символов, включающим концевой маркер (┤).

2. Конечным множеством магазинных символов, включающим маркер дна (Ñ).

3. Конечным множеством состояний, включающим начальное состояние.

4. Программой устройства управления(УУ), которая каждой комбинации входного символа, магазинного символа и состояния ставит в соответствие выход или переход.

5. Начальным содержимым магазина, содержащим маркер дна и, возможно пустую, цепочку магазинных символов.

Автомат-распознаватель имеет 2 выходных сигнала: «Допустить» и «Отвергнуть».

 

При помощи МП-автоматов можно распознать большую часть конструкций языков программирования. Рассмотрим некоторые из них.