Интерпретация функции - PullRequest
Новая
       7

Интерпретация функции

2 голосов
/ 06 марта 2012

Я должен придумать функцию, которая оценивает абстрактное синтаксическое дерево и возвращает результат его оценки.

у оценки будет тип Exp -> опция int

оценка (Prod (Num 5, Diff (Num 6, Num 1))); val it: int option = Some 25

@ Джон Палмер Как мне это сделать? Могу ли я использовать сопоставление с образцом? если так, как бы я это сделал, чтобы определить операцию, которая должна быть сделана.

Вот что я придумала? Я до сих пор не понимаю код за слово. 

let rec evaluate = function
 | Num n -> Some n
 | Neg e -> match evaluate e with
 |Sum (a,b) -> evaluate(a) + evaluate(b)
 |Diff(a,b) -> evaluate(a) - evaluate(b)
 | Prod (a,b) -> evaluate(a) * evaluate (b) 
 |Quot (a,b) -> evaluate(a) / evaluate(b)

Ответы [ 3 ]

4 голосов
/ 06 марта 2012

Вот несколько советов для начала работы 

let rec evaluate AST =
   match AST with
   |Prod(a,b) -> evaluate(a) * evaluate(b)
   |Num(a) -> a
   ....

РЕДАКТИРОВАТЬ

Поэтому я предполагаю, что ваш тип данных выглядит как 

type AST =
|Num of int
|Neg of AST
|Prod of AST * AST
|Diff of AST * AST
|Quot of AST * AST
|Sum of AST * AST

, поэтомувы устанавливаете свой AST (предположительно, вы анализируете это откуда-то - это совсем другой вопрос) с чем-то вроде 

let ast = Prod(Num 5, Diff(Num 6, Num 1))

, тогда вы можете определить оценку как 

let rec evaluate arg =
    match arg with
    |Num n -> n
    |Neg tree -> - (evaluate tree)
    |Sum (a,b) -> (evaluate a) + (evaluate b)
    |Prod(a,b) -> (evaluate a) * (evaluate b)
    |Quot(a,b) -> (evaluate a) * (evaluate b)
    |Diff(a,b) -> (evaluate a) - (evaluate b)

, затем вызватьи напечатайте результат с помощью 

printfn "%i" (evaluate ast)

Обратите внимание, что evaluate должен иметь тип AST -> int, так как в противном случае вам придется обрабатывать варианты опций - например, что 2 * None или 2 + None

Я не уверен, что вы имеете в виду под

как мне поступить при вызове рекурсивного метода для небольших входных данных.

но, надеюсь, это все объясняет

2 голосов
/ 06 марта 2012

Я опубликовал небольшой интерпретатор, написанный на OCaml для крошечного функционального языка здесь . Обратите особое внимание на функцию eval. Ваша проблема проще, потому что у вас нет переменных, поэтому вам не нужен словарь vars, который у меня был, и вы всегда возвращаете int результаты, поэтому вам не нужен тип объединения value.

Чтобы оценить целочисленное выражение, просто оцените подвыражения и выполните с ними что-то простое. Это наиболее элегантно написано как образец соответствия: 

type Expr =
  | Int of int
  | Neg of Expr
  | Add of Expr * Expr
  | Mul of Expr * Expr

let rec eval = function
  | Int n -> n
  | Neg f -> -eval f
  | Add(f, g) -> eval f + eval g
  | Mul(f, g) -> eval f * eval g

Например: 

Mul(Int 2, Neg(Int 3)) |> eval

Преимущество сопоставления с образцом заключается в том, что вы можете добавлять более сложные действия, основанные на содержании и форме структуры данных. Например: 

| Add(f, Neg g) -> eval f - eval g

Прежде чем вы это знаете, вы занимаетесь компьютерной алгеброй .

2 голосов
/ 06 марта 2012

Начните с изучения грамматик, лексеров и парсеров, чтобы сгенерировать для вас AST. Если у вас есть это, просто пройтись по дереву и оценить его.

Вот ссылка на него для F #:

http://www.quanttec.com/fparsec/

...