在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绑定和变量方面,您需要扩展签名以另外传递将变量映射到其值的环境.这可以像对的列表一样简单(Char, Int).Let将变量及其值添加到传递给in表达式的环境中.所以你最终得到的结果如下:

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

当然,如果使用未受a约束的变量,则必须提供错误处理let.

这有帮助吗？