7

有人可以给我一些帮助，使用以下语法为该语言构建一个 ocaml 解释器：

Prog ::= Def* Expr
Def ::= id id* = Expr
Expr ::= int | id | Expr '+' Expr | Expr '*' Expr | id Expr* | if Expr then Expr else Expr

到目前为止，我这样做了：

type expr = I of int
| Id of string
| Add of expr * expr
| Multiply of expr * expr
| If of  expr * expr * expr

let rec evaluate = function
| I n -> n 
| Add(e1,e2) -> evaluate e1 + evaluate e2
| Multiply(e1,e2) -> evaluate e1 * evaluate e2
| If(a,b,c) -> if evaluate a<>0 then evaluate b else evaluate c

这有什么好处吗？

4

1 回答 1

6

在您的语法中，单个 id 可以与产生式Expr ::= id或Expr ::= id Expr*. 换句话说，没有办法区分空函数应用程序（假设id Expr*产生式应该与函数应用程序匹配）和变量。也许您的意思是id Expr+（禁止空函数应用程序）。

您现有的代码看起来不错，但它不完整：

您的expr类型缺少用于id Expr*生成语法的构造函数，即缺少表示函数应用程序的构造函数。您应该添加一个，然后为它添加一个案例到evaluate函数中。

在您的evaluate函数中，您缺少Id构造函数的案例。这种情况应该在从标识符到值（整数）的映射中查找给定标识符的值。为此，您的evaluate函数应该将这样的映射作为附加参数。它还应该采用另一个从标识符到函数的映射，然后您可以在函数应用程序的情况下使用它来循环函数名称。

说到这些映射，您目前没有任何代码来表示或处理定义。你应该想出一个类型来表示定义和另一个来表示函数。后一种类型应该包含函数参数的名称和作为expr.

然后，您应该编写一个函数，该函数接受定义列表并创建变量和函数的映射。对于每个变量定义，它应该评估右侧的表达式并将结果值添加到变量映射中。对于每个函数定义，您应该将函数类型的值添加到函数映射中。evaluate处理完定义后，您应该通过使用该表达式和您创建的两个映射作为参数调用您的函数来评估最终表达式。

最后，您没有任何用于实际解析程序的代码，但我认为这可能是故意的。

于 2012-10-12T15:43:10.107 回答