Язык FLAE

Язык

(functions - let - arithmetic expressions)

Определим язык FLAE как:

FLAE ::= <num>
       | <FLAE> + <FLAE>
       | ( <FLAE> )
       | <id>
       | fun <id> -> <FLAE>
       | <FLAE> <FLAE>
       | let <id> = <FLAE> in <FLAE>

Где fun - это описание функции, "<FLAE> <FLAE>" - вызов функции с аргументом, а конструкция 
  let id = expr1 in expr2 
это синтаксический сахар для  
  (fun id -> expr2) (expr1)

Задание

  1. Описать тип, соответствующий синтаксическому дереву языка FLAE
  2. Написать преобразование, переводящее из FLAE в FAE (function - arithmetic expressions), согласно правилу замены let на fun
  3. Написать интерпретатор языка FAE:
    • Интерпретатор принимает дерево, описанное в п.1
    • Вычисляет выражение
    • Если результат число - напечатать
  4. Проверить результат на своих тестах, и на программах, приведенных ниже.
  5. Бонус: написать синтаксический анализатор, переводящий язык FLAE из текстового преставление в дерево из п.1 

Примеры

Пример с let:

let x = 5 in x+3

Он же преобразованный:

(fun x -> x+3)(5)

Пример 2:

((fun x -> x)
 (fun x -> x + 5))
3

Пример 3:

let x = 3 in
 fun y -> x + y

Пример 4:

let x = 3 in
 let f = fun y -> x + y in
  let x = 5 in
   f 4
Comments