SML：用语法中的元素计算节点

Question

我在 SML 中创建了以下简单语法：

datatype identifier = IdentE of char;

datatype term = ID of identifier | MultE of term * term * identifier;

datatype expression = Term of term | AddE of expression * expression * term;

我想计算存在的 IdentE 数据类型的数量。

我对如何做到这一点的猜测如下，这当然行不通，但我不确定如何真正完成这项任务：

fun sum(Empty)= 0 | sum(Term) = sum(ID) + | sum(IdentE) = 1|| sum(AddE(AddE, Term) =  sum(AddE) + sum(Term) |  sum(MultE(MultE, IdentE) =  sum(MultE) + sum(IdentE);

我是 SML 的新手，所以我可能犯了一个新手错误。

Answer 1

您的数据类型似乎模拟了数学表达式的某些子集，并且您已将加法、乘法和变量拆分为两个单独的数据类型 expression 和 term。因为 terms 只引用 terms 而没有返回到 expressions，表达式 a + (b × c)可以编码为：

AddE (Term (ID (IdentE #"a")),
      Term (MultE (ID (IdentE #"b")),
                   ID (IdentE #"c")),
      IdentE #"?")

但是你不能编码表达式 a × (b + c).

我不确定为什么加法有三个参数，大概是二元运算符。

这是您的 sum 函数，具有适当的间距和换行符：

fun sum(Empty) = 0
  | sum(Term) = sum(ID) +
  | sum(IdentE) = 1
 || sum(AddE(AddE, Term) = sum(AddE) + sum(Term)
  | sum(MultE(MultE, IdentE) = sum(MultE) + sum(IdentE)

一些事情变得明显：

您在发布之前没有仔细阅读自己的代码。
您的数据类型中没有 Empty 构造函数。什么是 "empty expression"？
你好像忘记补全第二行+后面的表达式了
你在第四行有一个 | 太多，在第四行和第五行有一个 ) 太少。
您的函数 sum 无法同时处理多种类型的值。如果它在一行中接受与 AddE (...) 匹配的值，则它不能在另一行中也接受与 MultE (...) 匹配的值，因为它们属于不同类型。
您要进行模式匹配的每个值构造函数都没有其参数。每个递归调用都是针对值构造函数的名称而不是传入的值的参数进行的。如果你想要一个接受 expressions 的函数，它可能看起来像：
```
fun sum (AddE (e1, e2, t)) = sum e1 + sum e2 + ...
  | sum (Term t) = ...
```
由于您有多种递归数据类型，最好的办法是使用多个函数来处理每种数据类型的递归。（这不是绝对必要的，但或者你有一些非常复杂的模式。）
```
fun sum (AddE (e1, e2, t)) = sum e1 + sum e2 + sumTerm t
  | sum (Term t) = sumTerm t

and sumTerm (ID id) = 1
  | sumTerm (MultE (t1, t2, id)) = sumTerm t1 + sumTerm t2 + 1
```
同样，我不确定为什么加法有第三项，为什么乘法有第三个标识符，以及为什么有多个数据类型开头。

如果我要对一个简单的算术语法树建模并计算它的变量数量，我会从 one 数据类型开始，二元运算符只有两个个参数每个：

datatype expr = AddE of expr * expr
              | MultE of expr * expr
              | ConstE of int
              | VarE of string

有了这个数据类型定义，

a + (b × c) 变为 AddE (VarE "a", MultE (VarE "b", VarE "c"))，并且
a × (b + c) 变为 MultE (VarE "a", AddE (VarE "b", VarE "c")).

我可以创建一个函数来计算表达式中变量的数量，如下所示：

fun countVars (AddE (e1, e2)) = countVars e1 + countVars e2
  | countVars (MultE (e1, e2)) = countVars e1 + countVars e2
  | countVars (ConstE const) = 0
  | countVars (VarE varname) = 1

我可能对获取这些变量的列表感兴趣：

fun getVars (AddE (e1, e2)) = getVars e1 @ getVars e2
  | getVars (MultE (e1, e2)) = getVars e1 @ getVars e2
  | getVars (ConstE const) = []
  | getVars (VarE varname) = [varname]

SML：用语法中的元素计算节点

SML: Count nodes with Elements in a Grammar

grammar

sml

nodes