0

我仍在为学校任务中​​定义的一种微小语言开发一个微小的解析器。生成 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 在 *(2,X) 中为 5”。X 通常是 Var 而 5 通常是 int。最后一个可以是 dataExpr 类型的任何部分。要点：X 在最后一个表达式中的某处使用。let 的数据类型是：

Let Expr Expr Expr

链接到我在此处询问的有关此任务的其他问题，仅供参考； 第一个问题 第二个问题

如您所见，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”是评价。我会回到这里寻求更多帮助。注意：重点是将找到的第一个未绑定变量作为错误吐出，如果一切正常，则吐出''。显然，如果你想以另一种方式做到这一点，你可以。

4

2 回答 2

5

这里有一些需要考虑的事情：

Let 构造函数的第一个字段是Expr. Var但它实际上可以容纳除s之外的任何东西吗？如果不是，您应该通过设置该字段的类型来反映这一点，String并相应地调整解析器。这将使您的任务更容易。

使用 let-bindings 评估表达式的标准技巧（您正在这样做）是编写一个函数

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

请注意环境的额外参数。环境会跟踪在任何给定时刻将哪些变量绑定到哪些值。它在类型中的位置意味着您每次调用eval子表达式时都可以决定它的值。这很关键！这也意味着您可以拥有本地声明的变量：绑定变量对其上下文没有影响，仅对子表达式有影响。

以下是特殊情况：

  • 在 aVar中，您想要lookup环境中的变量名称并返回绑定到它的值。（使用标准的 Prelude 功能lookup。）
  • 在 aLet中，您想(varname, value)在环境列表的前面添加一个额外的内容，然后再将其传递给子表达式。

我遗漏了一些细节，但这应该足以让你走得很远。如果你卡住了，再问一个问题。:-)

哦，我看到你想返回一个Maybe值来表示失败。我建议您先尝试不使用并使用error来指示未绑定的变量。当您拥有该版本的eval工作时，请将其调整为返回Maybe值。这样做的原因是使用Maybe值会使评估变得相当复杂。

于 2009-10-08T08:40:17.830 回答
0

我实际上会尝试评估AST。首先处理（并因此删除）所有Lets。现在，尝试评估生成的 AST。如果您遇到 aVar那么有一个未绑定的变量。

于 2009-10-07T23:29:21.177 回答