在 F# 中使用 tokens/symbols 实现用于构建非常简单的树 (AST) 的函数

Question

我看了how to make a tree from a given data with F# and https://citizen428.net/blog/learning-fsharp-binary-search-tree/

基本上我试图做的是实现一个函数来构建一个非常简单的 AST，使用可区分的联合 (DU) 来表示树。

我想用tokens/symbols来建树。我觉得这些也可以用DU来代表。我正在努力实现插入功能。

假设我们使用以下来表示树。基本思想是，对于整数的加法和减法，我只需要二叉树。表达式可以是运算符或常量。这可能是实现树的错误方式，但我不确定。

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

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

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"

如果您有什么建议或者 link，我将不胜感激。

Answer 1

我认为从树插入的角度来思考问题不是很有帮助，因为你真正想做的是解析一个标记序列。所以，普通的树插入不是很有用。相反，您需要以更具体的方式构建树（表达式）。

例如，假设我有：

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

假设我想解析这个标记序列以获得 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

要解析一系列标记，您可以这样写：

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))

在 F# 中使用 tokens/symbols 实现用于构建非常简单的树 (AST) 的函数

Implementing a function for building a very simple tree (AST) using tokens/symbols in F#

f#

parsing

abstract-syntax-tree