OCaml解释器

Question

有人能帮我构建一个针对以下语法的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

这个好吗？

- Spreadzz

Answer 1

在您的语法中，单个id可以由产生式Expr :: = id或Expr :: = id Expr * 匹配。换句话说，无法区分零元函数应用（假设id Expr *产生式应匹配函数应用）和变量。也许你的意思是id Expr + 而不是id Expr *（禁止零元函数应用）。

您现有的代码看起来很好，但不完整：

您的expr 类型缺少一个构造函数，用于表示文法的id Expr *产生式，即您缺少一个表示函数应用的构造函数。您应该添加一个并在evaluate 函数中添加一个案例。

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

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

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

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

- sepp2k

---

请问您能否给我展示一个表示定义过程的代码示例？我不需要解析的代码，也没有编写Id构造函数，因为我不知道如何编写，如果您能够展示给我就太好了。 - Spreadzz

@Spreadzz 类型应该只是类似于 type def = Def of string * string list * expr，或者如果你想区分变量和函数定义的话，可以使用 type def = VarDef of string * expression | FunDef of string * string list * expression。 - sepp2k

你能给我展示一下我的解释器中Add和Multiply的类型定义吗，这样我就可以完全理解了吗？ - Spreadzz

@Spreadzz，“Add”和“Multiply”的“类型定义”是什么意思？我在早期评论中定义的名为“def”的类型与“exp”类型的“Add”和“Multiply”构造函数无关。 - sepp2k

然后我真的在理解上搞砸了，我以为类型定义是相关的。我讨厌OCaml pfu :) 这是一个学校项目。那么你定义的类型定义是为我的解释器而定义的 Def ::= id id* = Expr？对不起，这个问题很愚蠢，但我是OCaml和ML语言的新手。 - Spreadzz

@Spreadzz 类型 def 应该表示定义。函数定义由函数名称、函数参数名称列表和函数体（作为 expr）组成。函数的主体当然可以包含加法或乘法，但这并不重要，因为在处理 def 时，您只需要将主体与函数名称和参数列表一起存储，然后在调用函数时检索该信息即可。主体是什么类型的表达式并不重要。 - sepp2k