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*.换句话说,没有办法区分一个nullary函数应用程序(假设id Expr*生产应该与函数应用程序匹配)和变量.也许你的意思是id Expr+(禁止使用nullary函数应用程序).

您现有的代码看起来很好,但它不完整:

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

在你的evaluate函数中,你错过了Id构造函数的大小写.这种情况应该在从标识符到值(int)的映射中查找给定标识符的值.为此,您的evaluate函数应该将这样的映射作为附加参数.它还应该从标识符到函数的另一个映射,然后您可以使用它来为函数应用程序循环函数名称.

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

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

最后你没有任何实际解析程序的代码,但我认为这可能是故意的.