基于FParsec的F#链式公式表达式解析故障排查求助

AST定义 #

type Arithmetic =
    | Add

type IntFunc =
    | MovingAverage

type Formula =
    | SingleParamOp of IntFunc * int * Formula
    | ArithmeticOp of Formula * Arithmetic * Formula
    | Price

背景 #

原有FParsec解析器可正确解析前缀式表达式，如moving_average(3, price())、moving_average(3, moving_average(3, price()))。现在希望改为链式调用风格（如price().moving_average(3).moving_average(3)），修改后的解析器代码如下：

module Formula =
    let private createParser =
        let pFormula, pFormulaRef = createParserForwardedToRef<Formula, unit> ()

        let pMovingAverage: Parser<Formula, unit> =
            pipe2
                (pFormula .>> pLiteral ".")
                (pLiteral "moving_average" >>. pLeftBracket >>. pInt .>> pRightBracket)
                (fun i x -> SingleParamOp(MovingAverage, x, i))

        let pPrice = pstring "price" >>. pLeftBracket >>. pRightBracket |>> (fun _ -> Price)

        let pAdd =
            pipe2
                (pFormula .>> pLiteral ".")
                (pLiteral "add" >>. pLeftBracket >>. pFormula .>> pRightBracket)
                (fun l r -> ArithmeticOp(l, Add, r))

        pFormulaRef.Value <- choice [ pMovingAverage; pPrice; pAdd ]

        pFormula .>> eof

    let parse = createParser

问题 #

解析price.add(price())时返回退出码134，推测是解析器从左到右处理时，因定义的解析器以Formula而非标识符开头导致无限递归。请问：

• 是否必须自行处理递归，还是有方法可继续借助现有解析器实现？
• 左右递归是否是核心难点？

解答 #

核心问题：左递归导致的无限循环 #

你当前的解析器确实陷入了左递归死循环：pFormula的第一个备选分支是pMovingAverage，而pMovingAverage又以pFormula开头，解析器会不断尝试调用pFormula，永远无法前进到终结符（比如price()），最终触发栈溢出（退出码134通常对应栈溢出导致的进程终止）。

解决思路：拆分表达式层级 #

不需要完全自行实现递归逻辑，依然可以借助FParsec的工具解决，核心是把解析器拆分为基础表达式和链式调用扩展两个层级，这是处理左递归的标准方式：

1. 基础表达式（Primary）：对应AST中的终结节点，也就是无递归的price()：

   let pPrimary = pstring "price" >>. pLeftBracket >>. pRightBracket |>> (fun _ -> Price)
   

2. 链式调用操作：定义单个链式调用的解析规则，每个操作返回一个函数，接收基础表达式并生成新的Formula节点。然后用chainl1组合基础表达式和多个链式操作，自动处理递归扩展。

修改后的完整解析器：

module Formula =
    let private createParser =
        let pFormula, pFormulaRef = createParserForwardedToRef<Formula, unit> ()

        // 基础表达式：仅处理无递归的price()
        let pPrimary = pstring "price" >>. pLeftBracket >>. pRightBracket |>> (fun _ -> Price)

        // 解析.moving_average(n)，返回一个函数：基础表达式 -> SingleParamOp节点
        let pMovingAverageOp =
            pLiteral "." >>. pLiteral "moving_average" >>. pLeftBracket >>. pInt .>> pRightBracket
            |>> (fun param -> fun baseExpr -> SingleParamOp(MovingAverage, param, baseExpr))

        // 解析.add(expr)，返回一个函数：基础表达式 -> ArithmeticOp节点
        let pAddOp =
            pLiteral "." >>. pLiteral "add" >>. pLeftBracket >>. pFormula .>> pRightBracket
            |>> (fun rhs -> fun lhs -> ArithmeticOp(lhs, Add, rhs))

        // 所有可能的链式操作
        let pChainOp = choice [ pMovingAverageOp; pAddOp ]

        // pFormula = 基础表达式 后面跟随0个或多个链式操作，由chainl1自动组合
        pFormulaRef.Value <- chainl1 pPrimary pChainOp

        pFormula .>> eof

    let parse = createParser

关键说明 #

• 拆分层级：通过pPrimary避免左递归的起点，pChainOp处理单个链式调用，chainl1会自动把基础表达式和后续操作从左到右组合（比如price().moving_average(3)会被转换为SingleParamOp(MovingAverage, 3, Price)）。
• 无需手动处理递归：FParsec的chainl1已经封装了递归扩展的逻辑，你只需要定义好基础节点和单个操作即可。

关于左右递归的核心难点 #

是的，左递归是核心问题。递归下降解析器（FParsec默认的解析方式）天生无法直接处理左递归，因为左递归会导致解析器无限调用自身，永远无法匹配到终结符。链式调用的结构本质是左递归的（Expr = Expr . Op(...) | Primary），所以必须通过拆分层级、使用组合子转换为可解析的逻辑，才能避免栈溢出。

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