Абстрактная машина

Исторически, первый подход к выработке математически строгой операционной семантики программных языков был реализован в терминах абстрактной машины – системы переходов, определяющей интерпретатор языка. Рассмотрим пример, иллюстрирующий данный подход применительно к языку, который назовем простым языком команд (ПЯК). Мы будем использовать абстрактную машину, которая часто называется SMC-машиной. Возникновение данного имени обусловлено тем, что конфигурация машины может быть описана как тройка , где - стек (промежуточных или конечных) результатов, - память, то есть отображение множества целых чисел на некоторое конечное множество адресов, а - управляющий стек выражений, подлежащих разбору. Перейдем к описанию языка ПЯК.