0

我想在 SML 中实现任意签名。如何为该签名上的术语定义数据类型？我需要它来编写检查术语是否格式正确的函数。

4

1 回答 1

1

在我看来，表示 AST 的主要方式有两种。可以作为一系列（可能是相互递归的）数据类型，也可以作为一个大数据类型。两者都有优点和缺点。

如果我们定义如下 BNF（从 SML 定义中提取并稍微简化）

<exp> ::= <exp> andalso <exp>
        | <exp> orelse <exp>
        | raise <exp>
        | <appexp>

<appexp> ::= <atexp> | <appexp> <atexp>

<atexp> ::= ( <exp>, ..., <exp> )
          | [ <exp>, ..., <exp> ]
          | ( <exp> ; ... ; <exp> )
          | ( <exp> )
          | ()

如前所述，这是简化的，并且大部分 atexp 都被省略了。

1.一系列可能相互递归的数据类型

例如，您可以在这里为表达式、声明、模式等创建一个数据类型。基本上，您将为 BNF 中的每个非终结符创建一个数据类型。

我们很可能会创建以下数据类型

datatype exp = Andalso of exp * exp
             | Orelse of exp * exp
             | Raise of exp
             | App of exp * atexp
             | Atexp of atexp

and atexp = Tuple of exp list
          | List of exp list
          | Seq of exp list
          | Par of exp
          | Unit

请注意，非终端已被消耗为 exp 数据类型，而不是拥有它自己的数据类型。那只会无缘无故地弄乱AST。您必须记住，BNF 通常以这样一种方式编写，即它还定义了先例和关联性（例如，用于算术）。在这种情况下，您通常可以通过将多个非终结符合并为一种数据类型来简化 BNF。

定义多种数据类型的好处是您可以获得一些格式良好的 AST。例如，如果我们也有声明的非终结符，我们知道 AST 将更新在列表中包含声明（因为只有表达式可以在那里）。正因为如此，你们中的大多数人都不需要进行格式良好的检查。

然而，这并不总是一件好事。无论如何，您通常都需要对 AST 进行一些检查，例如类型检查。在许多情况下，BNF 非常大，因此建模 AST 所需的数据类型的数量也非常大。牢记这一点，您必须为每种数据类型创建一个函数，为您不想对 AST 进行的每种修改创建一个函数。在许多情况下，您只想更改 AST 的一小部分，但您（很可能）仍需要为每种数据类型定义一个函数。这些功能中的大多数基本上都是身份，然后只有在少数情况下您才能完成所需的工作。

例如，如果我们不想计算给定 AST 中有多少个单元，我们可以定义以下函数

fun countUnitexp (Andalso (e1, e2)) = countUnitexp e1 + countUnitexp e2
  | countUnitexp (Orelse (e1, e2)) = countUnitexp e1 + countUnitexp e2
  | countUnitexp (Raise e1) = countUnitexp e1
  | countUnitexp (App (e1, atexp)) = countUnitexp e1 + countUnitatexp atexp
  | countUnitexp (Atexp atexp) = countUnitatexp atexp

and countUnitatexp (Tuple exps) = sumUnit exps
  | countUnitatexp (List exps) = sumUnit exps
  | countUnitatexp (Seq exps) = sumUnit exps
  | countUnitatexp (Par exp) = countUnitexp exp
  | countUnitatexp Unit = 1

and sumUnit exps = foldl (fn (exp,b) => b + countUnitexp exp) 0 exps

如您所见，我们正在做很多工作，只是为了这个简单的任务。想象一个更大的语法和更复杂的任务。

2. 一个（大）数据类型（节点）——以及这些节点的树

让我们组合之前的数据类型，但更改它们以使它们（它们自己）不包含它们的子对象。因为在这种方法中，我们构建了一个树结构，该结构具有一个节点和该节点的一些子节点。显然，如果您有一个标识符，那么该标识符需要包含实际的字符串表示形式（例如，变量名）。

因此，让我们从定义树结构的节点开始。

(* The comment is the kind of children and possibly specific number of children
   that the BNF defines to be valid *)
datatype node = Exp_Andalso   (* [exp, exp] *)
              | Exp_Orelse    (* [exp, exp] *)
              | Exp_Raise     (* [exp] *)
              | Exp_App       (* [exp, atexp] *)
(* Superflous:| Exp_Atexp     (* [atexp] *) *)
              | Atexp_Tuple   (* exp list *)
              | Atexp_List    (* exp list *)
              | Atexp_Seq     (* exp list *)
              | Atexp_Par     (* [exp] *)
              | Atexp_Unit    (* [] *)

看看 tupe 中的 Atexp 现在是如何变得多余的，因此我们将其删除。就我个人而言，我认为接下来通过告诉我们可以期待哪些孩子（在树结构中）来发表评论很好。

(* Note this is a non empty tree. That is you have to pack it in an option type
   if you wan't to represent an empty tree *)
datatype 'a tree = T of 'a * 'a tree list

(* Define the ast as trees of our node datatype *)
type ast = node tree

然后我们定义一个通用树并将类型 ast 定义为“节点树”。如果您使用某个库，那么很有可能已经存在这样的树结构。此外，稍后扩展此树结构以包含不仅仅是节点作为数据可能会很方便，但是我们在这里保持简单。

fun foldTree f b (T (n, [])) = f (n, b)
  | foldTree f b (T (n, ts)) = foldl (fn (t, b') => foldTree f b' t) 
                                      (f (n, b)) ts

对于这个例子，我们在树上定义了一个折叠函数，同样如果你使用一个库，那么所有这些用于折叠、映射等的函数很可能已经定义了。

fun countUnit (Atexp_Unit) = 1
  | countUnit _ =  0

如果我们再以之前的例子为例，我们不想计算单元的出现次数，那么我们可以将上述函数折叠在树上。

val someAST = T(Atexp_Tuple, [ T (Atexp_Unit, [])
                             , T (Exp_Raise, [])
                             , T (Atexp_Unit, [])
                             ]
               )

一个简单的 AST 可能看起来像上面那样（请注意，这实际上是无效的，因为我们有一个没有子级的 Exp_Raise）。然后我们可以通过

foldTree (fn (a,b) => (countUnit a) + b) 0 someAST

这种方法的缺点是您必须编写一个检查函数来验证您的 AST 格式是否正确，因为在创建 AST 时没有任何限制。这包括孩子具有正确的“类型”（例如，只有 Exp_* 作为 Exp_Andalso 中的孩子）以及有正确数量的孩子（例如，在 Exp_Andalso 中恰好有两个孩子）。

鉴于您不使用某些定义了树的库（包括用于修改树的辅助函数），这种方法还需要一些构建入门。然而，从长远来看，这是值得的。

于 2011-03-17T15:30:58.720 回答