Язык 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