问题与递归在Haskell中编写一个小解析器。检查变量 [英] Issue with recursion writing a tiny parser in Haskell. Check variables

问题描述

我仍然在为学校任务中​​定义的一种小语言开发一个小解析器。生成AST（抽象语法树）的解析器正在工作。我想要的是检查定义的变量，它们必须以let表达式为界。首先是任务中定义的方法（建议，不需要）：

$ $ $ $ $ $ $ $ $ checkVars :: Expr - > char

data Expr = Var Char |高层Int | Sum Expr Expr | Mult Expr Expr | Neg Expr |让Expr Expr Expr
导出（Eq，Show）

一个有效的句子是let X是5 *（2，X）。 X通常是一个Var，5通常是一个int。最后一个可以是dataExpr类型的任何部分。要点： X用在最后一个表达式中的某处。 let的数据类型为：

 设Expr Expr Expr 
  

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

正如你所看到的checkVars的数据类型是Expr，所以这里是我要提供给该函数的一个例子：

<$ p $ （X，Y），Z）中令Z为+（Y，X），让Y为*（2，X） （Var'X'）（高4）（Let'Var'Y'）（Mult（Tall 2）（Var'X'））（Let'b $ b（Var'Z'）（总和（Var'Y'）（Var'X'））（Sum（Sum（Var'X'）（Var'Y'））（Var
'Z'））））
只需24

这是一个全面的例子，最上面的部分是被解析的字符串/程序。第二部分，从第3行开始（Let）是AST，checkVars函数的输入。底部Just 24就是评测。我将回到这里寻求更多帮助。
注意：重点是吐出找到的第一个未绑定变量作为错误，如果一切正常，则为''。很明显，如果你想以另一种方式做到这一点。

解决方案

以下是需要考虑的事情：

Let构造函数的第一个字段是 Expr 。但它是否可以持有除 Var s之外的其他东西？如果没有，你应该通过使该字段的类型，比如 String 来反映这一点，并相应地调整解析器。这将使你的任务变得更容易。

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

  type Env = [（String，Int）] 
 eval :: Expr  - > Env  - > Int 
  

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

以下是特殊情况：

• 在 Var 中，您希望 lookup 环境中的变量名称并返回绑定的值。 （使用标准的Prelude函数 lookup 。）


• 在 Let 您希望在将其传递到子表达式之前在环境列表的前面添加一个额外的（varname，value）。






我省略了一些细节，但这应该足以让您走得更远。如果您遇到困难，请提出另一个问题。 ： - ）





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




I'm still working on a tiny parser for a tiny language defined in a task at school. The parser that generates an AST(Abstract syntax tree) is working. What I want is to check the defined variables, they must be bounded by the let expression. First the method that is defined in the task(suggestion, not needed):

checkVars :: Expr -> Char 

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

A valid sentence would be "let X be 5 in *(2,X)". X would normally be a Var and 5 is normally an int. And the last can be any part of the dataExpr type. Main point: X is used somewhere in the last expression. The datatype for let is:

Let Expr Expr Expr

Link to the other questions I've asked about this task here just FYI; First question Second question

As you see the datatype to the checkVars is Expr, so here is an example of what I would feed to that function:

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

This is an all-inclusive example, the top part is the string/program being parsed. The second part, starting at line 3 (Let) is the AST, input for the checkVars function. And the bottom part "Just 24" is the evaluation. Which I will be back here for more help for. Note: The point is to spit out the first unbound variable found as an error, and ' ' if everything is fine. Obviously if you want to do this another way you can.

解决方案

Here's something to think about:

The first field of your Let constructor is an Expr. But can it actually hold anything else than Vars? If not, you should reflect this by making that field's type, say, String and adapting the parser correspondingly. This will make your task a lot easier.

The standard trick to evaluating an expression with let-bindings (which you are doing) is to write a function

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

Note the extra argument for the environment. The environment keeps track of what variables are bound at any given moment to what values. Its position in the type means that you get to decide its value every time you call eval on child expressions. This is crucial! It also means you can have locally declared variables: binding a variable has no effect on its context, only on subexpressions.

Here are the special cases:

• In a Var, you want to lookup the variable name in the environment and return the value that is bound to it. (Use the standard Prelude function lookup.)
• In a Let, you want to add an extra (varname, value) to the front of the environment list before passing it on to the child expression.

I've left out some details, but this should be enough to get you going a long way. If you get stuck, ask another question. :-)

Oh, and I see you want to return a Maybe value to indicate failure. I suggest you first try without and use error to indicate unbound variables. When you have that version of eval working, adapt it to return Maybe values. The reason for this is that working with Maybe values makes the evaluation quite a bit more complicated.

这篇关于问题与递归在Haskell中编写一个小解析器。检查变量的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！