在Haskell中编写一个小解析器的递归问题.检查变量

Question

我还在为一个学校任务中​​定义的小语言编写一个小解析器.生成AST(抽象语法树)的解析器正在运行.我想要的是检查已定义的变量,它们必须以let表达式为界.首先是任务中定义的方法(建议,不需要):

checkVars :: Expr -> Char 

data Expr =  Var Char | Tall Int | Sum Expr Expr | Mult Expr Expr | Neg Expr | Let Expr Expr Expr
    deriving(Eq, Show) 

一个有效的句子是"让X为5 in*(2,X)".X通常是Var,5通常是int.最后一个可以是dataExpr类型的任何部分.要点:X在最后一个表达式的某处使用.let的数据类型是:

Let Expr Expr Expr

在这里仅仅与FYI联系我提出的有关此任务的其他问题; 第一个问题 第二个问题

正如您看到checkVars的数据类型是Expr,所以这里是我将要提供给该函数的示例:

parseProg "let X be 4 in let Y be *(2 , X) in let Z be +(Y , X) in
+(+(X , Y) , Z)"
Let (Var 'X') (Tall 4) (Let (Var 'Y') (Mult (Tall 2) (Var 'X')) (Let
(Var 'Z') (Sum (Var 'Y') (Var 'X')) (Sum (Sum (Var 'X') (Var 'Y')) (Var
'Z'))))
Just 24

这是一个包罗万象的例子,顶部是要解析的字符串/程序.第二部分,从第3行(Let)开始是AST,checkVars函数的输入.底部"Just 24"就是评价.我将回到这里寻求更多帮助.注意:重点是吐出第一个被发现为错误的未绑定变量,并且''如果一切正常.显然,如果你想以另一种方式做到这一点,你可以.

Answer 1

这是需要考虑的事情:

Let构造函数的第一个字段是Expr.但除了Vars 之外,它还能拥有其他东西吗？如果没有,你应该通过制作该字段的类型来反映这一点,比如说,String并相应地调整解析器.这将使您的任务变得更加容易.

使用let-bindings(你正在做)评估表达式的标准技巧是编写一个函数

type Env = [(String, Int)]
eval :: Expr -> Env -> Int

请注意环境的额外参数.环境会跟踪在任何给定时刻绑定到哪些变量的值.它在类型中的位置意味着每次调用eval子表达式时都可以决定它的值.这至关重要!它还意味着您可以拥有本地声明的变量:绑定变量对其上下文没有影响,仅在子表达式上有效.

以下是特殊情况:

• 在a中Var,您希望lookup在环境中使用变量名称并返回绑定到它的值.(使用标准Prelude功能lookup.)
• 在a中Let,您希望在将其(varname, value)传递给子表达式之前在环境列表的前面添加一个额外的内容.

我遗漏了一些细节,但这应该足以让你走很长的路.如果你遇到困难,请问另一个问题.:-)

哦,我看到你想要返回一个Maybe值来表示失败.我建议你首先尝试不用,并error用来表示未绑定的变量.如果您具有该版本的eval工作,请将其调整为返回Maybe值.这样做的原因是使用Maybe值会使评估变得更加复杂.