Абстрактный синтаксис языка Fpl. Определение функций. | MetodPro.ru

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

Абстрактный синтаксис языка Fpl. Определение функций.



Абстрактный синтаксис языка Fpl
1) Синтаксические категории
1) p Э  Prog  2) d Э Dec  3) e Э Exp  4) bе Э BExp  5)F Э FunVar  6) op Э Op 
7) bop Э Bop  8) x Э Var  9) bx Э BVar  10) n Э Num 
2) Определения
p ::= <e,D>
D ::= F(x1,…xk) <= e | F(x1,…xk) <= e, D`
op ::= + | - | * | div
bop ::= And | Or
e ::= x | n | e`op e``| let x=e` in e``| if be then e` else e``| F(e1,…ek), где арность F равна k
be ::= bx | T | F | Not be/| Equal (e,e`) | be` bop be``

Ограничение:
В каждой программе <e,D> должны выполняться условия:
 1. Каждое имя функции, встречающееся в e должно иметь определение в D.
 2.  Каждое имя функции может иметь только одно определение в D.

Определение функций
      Введем новую синтаксическую категорию - имена функций. С этими именами будем связывать тела функций и таким образом делать определения.
      Например,
      Square(x) <= x*x.
      Такое определение будем называть декларацией.
      Смысл выражения Square(3) можно сформулировать так: «Вычислить x*x в окружении, где с x связано 3» . Обобщённо в форме правила: Если задана декларация F(x)<=e, то применимо правило:

      p|-e`=> v`            p[x/v`]|-e => v      .
                  p|-F (e`) => v
(Читается: Если в окружении ро выражение е штрих вычисляет (принимает значение) в штрих и в окружении ро с подстановкой х=в штрих  выражение е вычисляет в, то функция (F(x)<=e)  Ф от е штрих в окружении ро вычисляет в)

Рекурсивные функции
Определим функцию, вычисляющую факториал:
Fact(x) <= If Equal(x,0)
            Then 1
            Else x*Fact(x-1).
Вычислим Fact(2).
    p[x/2]|- If Equal(x,0)Then 1 Else x*Fact(x-1)=>
2* Fact(1)=>
p[x/1]|- 2*If Equal(x,0)Then 1 Else x*Fact(x-1)=>
2 * 1 * Fact(0)=>
p[x/0]|- 2*1*If Equal(x,0)Then 1 Else x*Fact(x-1)=>
2 * 1 * 1 => 2



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

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