parsing - 在 Haskell 中评估解析的表达式

Question

这是我关于 SO 的第一个问题 :)

我的 Haskell 知识非常有限，所以我需要一些帮助才能开始。
我有这个 BNF 语法:

num ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
int ::= num | num int
var ::= A | B | C | ... | Z
expr ::= var | int | - expr
        | +(expr , expr) | *(expr , expr)
        | let var be expr in expr

我已经写了一个解析器，在 SO 上的另一篇文章的帮助下。

我的数据类型是:

data Expr =  Var Char | Tall Int | Sum Expr Expr | Mult Expr Expr | Neg Expr | Let Expr  Expr Expr

我需要的是评估解析器输出的表达式(Expr，String)。我真的不知道从哪里开始这项任务。谁能帮我？

我不确定需要哪些更多信息，如有必要，我会发布。

Answer 1

首先，在您的数据类型中，Let 的第一条数据构造函数应该只是变量标识符( Char 在你的情况下)而不是 Expr .

尝试递归函数。您评估您的Expr至Int ，所以基本上你想要签名的功能

evaluate :: Expr -> Int

然后开始匹配 Expr 的构造函数并递归地评估子表达式:

evaluate (Tall n) = n
evaluate (Sum e1 e2) = evaluate e1 + evaluate e2

说到 Let绑定(bind)和变量，您需要扩展签名以另外传递将变量映射到其值的环境。这可以像 (Char, Int) 对列表一样简单。 . Let将变量及其值添加到传递给 in 的环境中。表达。所以你最终会得到类似的东西:

evaluate :: Expr -> Int
evaluate e = evaluate' e EmptyEnv
  where evaluate' :: Expr -> Env -> Int
        evaluate' (Tall n) _ = n
        ...

当然，如果使用的变量未被 let 绑定(bind)，则必须提供错误处理。 .

这已经有帮助了吗？