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

这有什么好处吗？

Answer 1

在您的语法中，单个 id 可以与产生式 Expr ::= id 匹配。或 Expr ::= id Expr* .换句话说，无法区分无效函数应用程序(假设 id Expr* 产生式应该匹配函数应用程序)和变量。也许你的意思是 id Expr+相反(禁止无效函数应用程序)。

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

您的 expr type 缺少 id Expr* 的构造函数语法的产生，即您缺少表示函数应用程序的构造函数。您应该添加一个，然后为它添加一个案例到 evaluate功能一样。

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

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

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

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