parsing - 在 F# 中使用标记/符号实现用于构建非常简单的树 (AST) 的函数

Question

我看了how to make a tree from a given data with F#和 https://citizen428.net/blog/learning-fsharp-binary-search-tree/
基本上我试图做的是实现一个函数来构建一个非常简单的 AST，使用可区分联合 (DU) 来表示树。
我想使用 token /符号来构建树。我认为这些也可以由 DU 来代表。我正在努力实现插入功能。
假设我们使用以下内容来表示树。基本思想是，对于整数的加法和减法，我只需要二叉树。表达式可以是运算符或常量。这可能是实现树的错误方式，但我不确定。

type Tree =
| Node of Tree * Expression * Tree
| Empty
and Expression =
| Operator //could be a token or another type
| Constant of int

让我们使用以下内容来表示 token 。可能有一种更聪明的方法来做到这一点。这只是一个例子。

type Token =
    | Integer
    | Add
    | Subtract

我应该如何实现插入功能？我已经编写了下面的函数并尝试了不同的插入元素的方法。

let rec insert tree element = 
    match element, tree with
    //use Empty to initalize
    | x, Empty -> Node(Empty, x, Empty)
    | x, Node(Empty,y,Empty) when (*x is something here*) -> Node((*something*))
    | _, _ -> failwith "Missing case"

如果您有任何建议或链接，我将不胜感激。

Answer 1

我认为从树插入的角度考虑问题不是很有帮助，因为您真正想做的是解析一个 token 序列。所以，普通的树插入不是很有用。相反，您需要以更具体的方式构造树(表达式)。
例如，假设我有:

let input = [Integer 1; Add; Integer 2; Subtract; Integer 1;]

假设我想解析这个 token 序列以获得 1 + (2 - 1) 的表示。 (括号的方式错误，但它更容易解释这个想法)。
我的方法是定义一个递归 Expression键入而不是使用通用树:

type Token =
  | Integer of int
  | Add
  | Subtract

type Operator = 
  | AddOp | SubtractOp

type Expression =
  | Binary of Operator * Expression * Expression
  | Constant of int

要解析 token 序列，您可以编写如下内容:

let rec parse input = 
  match input with 
  | Integer i::Add::rest ->
      Binary(AddOp, Constant i, parse rest)
  | Integer i::Subtract::rest ->
      Binary(SubtractOp, Constant i, parse rest)
  | Integer i::[] ->
      Constant i
  | _ -> failwith "Unexpected token"

这将查找以 Integer i; Add; ... 开头的列表或与减法类似，并递归构造一棵树。使用上面的输入，你得到:

> parse input;;
val it : Expression =
  Binary (AddOp, Constant 1, 
    Binary (SubtractOp, Constant 2, Constant 1))