F#中如何基于判别联合实现极简AST的令牌插入函数？

现有设计的核心偏差 #

• 原Tree结构混入了二分搜索树的设计残留：针对整数加减法的AST本身不需要冗余的Empty空节点、外层Tree包装层。合法的AST节点本身要么是存储整数值的叶子常量节点，要么是绑定左右子树的运算节点，空节点仅为BST的平衡逻辑设计，完全不匹配AST的结构要求。
• 原Expression定义存在职责混淆：Operator作为无值的判别联合成员，没有和具体的运算类型绑定，导致后续节点构建时无法区分加法、减法的语义差异。
• 原Token设计缺少实际值承载能力：仅标记令牌类型（比如Integer只代表“这是个整数令牌”），没有存储令牌对应的具体整数值，后续树构建阶段无法把解析到的实际值绑定到AST节点上。
• 原insert函数逻辑错配了BST的按序插入逻辑和AST的语法构建逻辑：AST不是无序生长的二叉搜索树，不需要通用“找空位插入元素”的逻辑，必须严格匹配表达式的语法结构、运算优先级来绑定节点关系。

修正后的类型定义 #

// 直接用判别联合定义AST节点结构，去掉冗余的包装层和空节点
type AstNode =
    /// 叶子节点：存储整数值
    | Constant of int
    /// 内部运算节点：绑定左子树、运算符、右子树
    | BinaryOp of left: AstNode * op: Operator * right: AstNode
/// 定义具体的二元运算类型
and Operator =
    | Add
    | Subtract
/// 修正后的令牌结构，携带解析后的实际值
type Token =
    | Integer of int
    | Op of Operator

适配AST构建的核心逻辑 #

• 取消空节点占位：合法AST不存在有效空节点，解析过程中遇到的结构缺失直接判定为语法错误，无需空节点占位。
• 无需复用BST的插入函数：AST的构建是按语法解析流程生成节点关系，不是通用的元素插入过程：
  • 遇到单个整数令牌时，直接生成Constant类型的叶子节点
  • 按语法顺序解析完左子树、匹配到运算符、解析完右子树后，直接生成BinaryOp节点绑定三者关系
  • 若需模拟逐步插入的构建流程，无需匹配BST的排序、平衡规则，仅需按照语法优先级把新节点挂载到对应父节点的子树位置，不需要设计针对Empty节点的插入分支
• 简化的从令牌列表构建AST的可运行基础实现：

let rec buildAst (tokens: Token list) =
    // 解析基础整数因子
    let rec parseFactor (tokens: Token list) =
        match tokens with
        | Integer value :: rest -> Constant value, rest
        | _ -> failwith "语法错误：缺少有效整数值"
    // 解析二元运算表达式
    let rec parseExpr (tokens: Token list) =
        let leftNode, remainingTokens = parseFactor tokens
        match remainingTokens with
        | Op op :: rest ->
            let rightNode, finalRemaining = parseFactor rest
            BinaryOp(leftNode, op, rightNode), finalRemaining
        | _ -> leftNode, remainingTokens
    match parseExpr tokens with
    | ast, [] -> ast
    | _ -> failwith "语法错误：存在未解析的冗余令牌"

内容的提问来源于stack exchange，提问作者justForFun