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

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

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


18. Абстрактная машина для языка Fpl. Состояния абстрактной машины. Переходы абстрактной машины.
В отличии от языка Exp4 нужно ввести окружение чтобы использовать переменные. При описании семантики для этого мы использовали функцию из области переменных на область значений. Включим в  абстрактную машину конечные списки, реализующие окружения: env ::= e | (x,v) : env’. Процедуру поиска значения переменной в окружении будем записывать: env, x |- v. Она определяется двумя правилами: 1)[дробь][числитель][/числитель][знаменатель](x,v):env, x |- v[/знаменатель][/дробь]
2)[дробь][числитель]env, x |- v[/числитель][знаменатель](y,v’):env, x|- v [/знаменатель] [/дробь], при x =/= y.
Состояния абстрактной машины для Fpl
Синтаксические категории: 1) st Э States  2) C Э Control  3) S Э Stack  4) env Э Env  5) a Э Assoc  6) cons Э Constants  7) F Э FunVar 8) v Э Values  9) bv Э BValues  10) e Э Exp
Определения: 1) st ::= <S,env,C>  2) S ::= e | v:S’ | bv:S”  3) C ::= e | e:C’ | cons:C” 4) cons ::= op | bop | <x,e> |if (e,e’) | not | equal | pop |F  5) env    ::= e | a:env’  6) a ::= (x,v) | (bx,bv) | (F,(x,e))  7) v ::= n  8) bv    ::= tt | ff
Переходы абстрактной машины
Записываются в виде <S,env,C>  ->  <S’,env’,C’>. Окружение используется только одним правилом для всех типов значений: чисел, булевых и функций: [дробь][числитель]env, x |- v[/числитель][знаменатель] <S,env,x:C>  ->  <v:S,env,C> [/знаменатель][/дробь] (Переменная из окружения переносится в стек). Правила можно разделить на два вида: анализирующие (1) и применяющие (2).
Правило Opm1
<S, env, e op e’:C>  ->  <S, env, e: e’: op :C>
<S, env, be bop be’:C>  ->  <S, env, be: be’: bop :C>
Правило Notm1
<S, env, Not be:C>  ->  <S, env, be:not:C>
Правило Eqm1
<S, env, Equal(e,e’):C>  ->  <S, env, e:e’:equal:C>
Правило Ifm1
<S, env, If be Then e Else e’:C>  ->  <S, env, be:if(e,e’):C>
Правило Funm1
<S, env, F(e):C> ( <S, env, e: F :C>
Правило Locm1
<S, env, let x=e in e’:C>  ->  <S,env, e:<x,e’>:C>
(Нужно вычислить e в текущем окружении, а затем e’ - в модифицированном. Константа  <x,e’> обозначает вычисление e’ в модифицированном окружении (x,v):env когда значение v берётся из стека (а там будет вычисленное значение выражения e))
Правило Locm2
<v:S, env, <x,e>:C>  ->  < S,(x,v):env, e:pop:C>
Правило Pop
<S, (x,e):env, pop:C >  ->  < S, env, C>
Команда pop очищает окружение от введённой ранее связи <x,e>
Подобным образом обрабатываются функции. Для простоты будем использовать функции от одного аргумента: F(x) <=e’.
Определение функции будем хранить в окружении как пару <F,(x,e’)>.
Анализирующее правило (Funm1): <S, env, F(e):C> -> <S, env, e: F :C>
Применяющее правило (Funm2): [дробь][числитель]env,F |- (x,e’)[/числитель] [знаменатель] <v:S,env,F:C>  ->  <S,(x,v):env,e’:pop:C> [/знаменатель][/дробь] (Функция F применяется к вычисленному аргументу v, находящемуся в стеке вычислений. В окружение заносится связь (x,v), которая после вычисления e’ удаляется по команде pop)
Правило для константы equal (Eqm2):
<v:v’:S, env, equal:C> -> <tt:S, env, C> (если v=v’)
<v:v’:S, env, equal:C> -> <ff:S, env, C> (иначе)
Правило для константы if (Ifm2):   
<tt:S, env, if(e,e’):C> -> <S, env, e:C>
<ff:S, env, if(e,e’):C> -> <S, env, e’:C>
Правило для константы not (Notm2):
<tt:S, env, not:C> -> <ff:S, env, C>
<ff:S, env, not:C> -> <tt:S, env, C>
Правило Valm:
<S, env,v:C> -> <v:S, env, C>
<S, env,bv:C> -> <bv:S, env, C>
Правило Opm2:
<v:v’:S, env, op:C>  ->  <Ap(op,v,v’):S, env, C>
<bv:bv’:S, env, bop:C> -> <Ap(bop,bv,bv’):S, env, C>



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

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