1

我有一个环境，其中包含一组我已经遇到过的令牌；当我查看一个新令牌时，我想将该令牌添加到当前环境中。基本上我想在我执行解析的环境上表达一个集合联合操作。

像Γ' = {Γ, x}

如果我想删除变量“x”（从环境中删除 x）

Γ' = Γ - x 如果 x ∈ Γ 。

写这两种形式的正确方法是什么。谢谢。

4

1 回答 1

2

基本上，您希望将您的环境实现为一些支持插入、删除和搜索的数据结构，并将该数据结构传递给您的解析器。我想在您的解析器中，您会查看当前令牌，对环境进行适当的更新，然后在下一个令牌上递归调用解析器，然后传入更新的环境。

使用哪种特定的数据结构取决于您，二叉搜索树或其变体会很好，或者如果您不关心性能，您可以使用 Haskell 的内置列表类型。

编辑：要正式写下这个过程，你可以借鉴类型规则以及它们是如何编写的，这里是一个参考。例如，我们可以表示一个程序被成功解析Γ ⊢ program:OK（我不确定你是否想在这里处理实际类型）。然后，要将令牌添加到环境中，您可以编写

    Γ,id ⊢ program:OK
-------------------------
  Γ ⊢ add id, program:OK

要删除令牌，您可以编写

        Γ ⊢ program:OK
------------------------------
  Γ,id ⊢ remove id, program:OK
于 2012-07-24T22:55:01.717 回答