Рекурсивный парсер f# fparsec

Если вам нужно объединить вещи только на верхнем уровне, то синтаксический анализатор Chainl от FParsec, вероятно, будет хорошим выбором. Что-то вроде этого:

type Formula =
    | MovingAverage of int
    | Price
    | Add of Formula

module Formula =

    let pLiteral = pstring
    let pLeftBracket = pchar '('
    let pInt = pint32
    let pRightBracket = pchar ')'

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

        let pMovingAverage: Parser<Formula, unit> =
            pLiteral "moving_average"
                >>. pLeftBracket
                >>. (pInt |>> MovingAverage)
                .>> pRightBracket

        let pPrice =
            pstring "price"
                >>. pLeftBracket
                >>. pRightBracket
                >>% Price

        let pAdd =
            pLiteral "add"
                >>. pLeftBracket
                >>. (pFormula |>> Add)
                .>> pRightBracket

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

        pFormula |>> List.singleton

    let private parseDot =
        pLiteral "."
            >>% (@)

    let parse =
        chainl parseOne parseDot []

Тестируем это:

runParserOnString Formula.parse () "" "price()"
    |> printfn "%A"   // Success: [Price]

runParserOnString Formula.parse () "" "price().add(price())"
    |> printfn "%A"   // Success: [Price; Add Price]

runParserOnString Formula.parse () "" "price().moving_average(3).moving_average(3)"
    |> printfn "%A"   // Success: [Price; MovingAverage 3; MovingAverage 3]

Обратите внимание, что это не позволит вам анализировать вложенные выражения, такие как price().add(price().add(price()).

Вы правы насчет рекурсии, она действительно вызовет вашу ошибку. На самом деле, проблема именно в (pFormula .>> pLiteral "."), поскольку он будет рекурсивно вызывать ваш парсер в цикле.

Я собираюсь начать с предположения (потому что в вашем вопросе этого не написано), что:

let pLiteral = pstring
let pLeftBracket = pchar '('
let pRightBracket = pchar ')'

Далее, чтобы упростить ваш код, мы определим более простой анализатор для обработки круглых скобок:

let parens p = between pLeftBracket pLeftBracket p

Далее нам нужно разобраться с вашей проблемой с парсером. Как вы указали, вы хотите объединить парсеры в цепочку, поэтому один из способов сделать это — рассматривать pMovingAverage и pAdd как парсеры, которые можно объединять в цепочку, т. е. возвращать Parser<Formula -> Formula, unit>. Мы не делаем это для Price, который (если я правильно понимаю) не цепляется с учетом вашего АСТ. Это дает нам:

let pMovingAverage: Parser<(Formula -> Formula), unit> =
    pstring "moving_average" >>. parens pint32 |>> fun x i -> SingleParamOp(MovingAverage, x, i)

и

let pAdd: Parser<Formula -> Formula, unit> =
    pstring "add" >>. parens pFormula |>> fun r l -> ArithmeticOp(l, Add, r)

Это работает, потому что лямбда-функция каждый раз ожидает дополнительный аргумент (второй), который будет указан позже. Поэтому нам необходимо определить анализатор цепочки, который объединит два предыдущих анализатора. Учитывая вашу проблему, это всегда будет следовать шаблону

"price().[a list of either pMovingAverage or pAdd]"

Поэтому,

let pChained: Parser<Formula, unit> =
    pPrice .>>. many (pchar '.' >>. choice [ pMovingAverage; pAdd ])
    |>> fun (state, fs) -> List.fold (fun acc f -> f acc) state fs

Первая строка представляет собой перевод шаблона, указанного выше, а вторая строка использует этот шаблон для применения синтаксического анализатора к аккумулятору (первое состояние которого просто pPrice).

Мы можем это проверить:

let runParser input =
    match runParserOnString Formula.parse () null input with
    | Success(result, _, _) -> printfn "Parsed: %A" result
    | Failure(msg, _, _) -> printfn "Failure: %s" msg

runParser "price().add(price())" // Parsed: ArithmeticOp (Price, Add, Price)
runParser "price().moving_average(3).moving_average(3)" // Parsed: SingleParamOp (MovingAverage, 3, SingleParamOp (MovingAverage, 3, Price))

Полный код:

open FParsec

type Arithmetic =
    | Add

type IntFunc =
    | MovingAverage

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

module Formula =

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

        let parens (p: Parser<'a, unit>) =
            between (pchar '(') (pchar ')') p

        let pPrice: Parser<Formula,unit> =
            pstring "price" >>. parens spaces >>% Price

        let pMovingAverage: Parser<(Formula -> Formula), unit> =
            pstring "moving_average" >>. parens pint32 |>> fun x i -> SingleParamOp(MovingAverage, x, i)

        let pAdd: Parser<Formula -> Formula, unit> =
            pstring "add" >>. parens pFormula |>> fun r l -> ArithmeticOp(l, Add, r)

        let pChained: Parser<Formula, unit> =
            pPrice .>>. many (pchar '.' >>. choice [ pMovingAverage; pAdd ])
            |>> fun (state, fs) -> List.fold (fun acc f -> f acc) state fs

        pFormulaRef.Value <- pChained
        pFormula .>> eof

    let parse = createParser

let runParser input =
    match runParserOnString Formula.parse () null input with
    | Success(result, _, _) -> printfn "Parsed: %A" result
    | Failure(msg, _, _) -> printfn "Failure: %s" msg

runParser "price().add(price())"
runParser "price().moving_average(3).moving_average(3)"

Есть и другие способы сделать что-то, и тот, который я представил, возможно, не самый лучший или самый простой, но это то, что пришло на ум первым (потому что я раньше делал нечто подобное, но не с помощью парсеров).