Абстрактная машина для языка Exp. Состояния абстрактной машины. Переходы абстрактной машины. | MetodPro.ru

Реклама на сайте

Абстрактная машина для языка Exp. Состояния абстрактной машины. Переходы абстрактной машины.


17.  Абстрактная машина для языка Exp. Состояния абстрактной машины. Переходы абстрактной машины.
Известная уже нам конкретная семантика имела алгоритм перевода в постфиксную запись и процедуру, использующую стек вычислений. Это два рекурсивных процесса. Таким образом абстрактная машина должна иметь два стека: стек вычислений S и стек управления C (control), содержащий последовательность частей вычисляемых выражений. Пара <S,C> определяет состояние машины.  Абстрактная машина должна определять возможные изменения состояния, переходы. Их мы будем записывать в виде: <S, C> -> <S’, C’>. Для вычисления выражения e нужно запустить машину в состоянии <e, [e]> (e обозначает пустой стек) а по окончании работы машина окажется в состоянии <[v], e>, где v – результат вычисления.
Состояния абстрактной машины.
1) Синтаксические категории:  1) st ? States 2) C ? Control  3) S ? Stack  4) cons ? Constants  5) v ? Values
2) Определения: 1) st ::= <S,C>  2) S ::= e | v:S’ 3) C ::= e | e:C’ | cons:C” 4) cons ::= op  5) v ::= n
Оператор «:» конструирует список из головы и хвоста.
Переходы абстрактной машины:
Правило Val: <S, v:C> -> <v:S, C> (Если выражение – число, то оно переходит в стек вычислений)
Правило Anlm: <S, e op e’:C>-> <S, e: e’: op :C> (Если выражение – структура с оператором, то оно разбивается на три части и т. о. задаётся порядок вычислений)
Правило Opm:  <v:v’:S, op:C> -> <Ap(op,v,v’):S, C> (Если выражение – оператор, то он применяется к двум верхним значениям стека вычислений, которые затем заменяются вычисленным значением)



Методические пособия

  • Системы автоматизированного проектирования
  • Социология молодёжи
  • Общая социология
  • Криптография
  • Проектирование трансляторов
  • Компьютерная графика
  • Моделирование систем
  • Информационная безопасность
  • Теория вычислительных процессов
  • Логические основы искусственного интелекта
  • Проектирование распределённых информационных систем