Выбор FParsec ведет себя неожиданным образом

Question

Я планирую использовать FParsec для прототипа моего более крупного проекта. Поэтому я решил получить свой первый опыт работы с этой библиотекой с помощью тестовой программы, перечисленной ниже. Но кажется, что комбинация моих основных синтаксических анализаторов (которые, кажется, работают) с использованием функции fparsec 'choice' приводит к неожиданному поведению.

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

Как я понял из документации по "выбору", альтернативы предпринимаются слева направо, как указано в списке парсеров, заданных для "выбора". Я понял, что если синтаксический анализатор, оставленный далее в списке, потерпит неудачу, но использует входные данные, последующие анализаторы не будут предприниматься.

Тем не менее, кажется, что сейчас есть нечто большее, чем я могу понять, как если бы это было, как я уже говорил выше, код должен работать. Но это не работает.

Было бы очень признательно, если бы кто-то мог объяснить мне: а) что идет не так и почему и б) как это исправить.

В моем основном проекте я планирую вычислить парсеры на основе некоторого ввода, и поэтому мне нужно точно понять, как надежно комбинировать парсеры без сюрпризов.

(*
    SimpleAOSCalculator

    Should implement the following grammar:

    SimpleAOSCalculator := SUM
    SUM := SUMMAND [ '+' SUMMAND ]*
    SUMMAND := PRODUCT | SUBEXPR
    PRODUCT := FACTOR [ '*' FACTOR ]*
    FACTOR := NUMBER | SUBEXPR
    SUBEXPR := '(' SUM ')'
    NUMBER := pfloat
*)

// NOTE: If you try this in fsi, you have to change the 2 lines below to point to the spot you have your fparsec dlls stored at.
#r @"C:\hgprojects\fparsec\Build\VS11\bin\Debug\FParsecCS.dll"
#r @"C:\hgprojects\fparsec\Build\VS11\bin\Debug\FParsec.dll"

open FParsec

let testParser p input =
    match run p input with
    | Success(result, _, _) -> printfn "Success: %A" result
    | Failure(errorMsg, _, _) -> printfn "Failure %s" errorMsg
    input

type Node = 
    | Sum of SumNode
    | Product of ProductNode
    | Number of NumberNode
    | SubExpression of SubExpressionNode
and SumNode = 
    {
        Summands : Node list
    }
and ProductNode = 
    {
        Factors : Node list
    }
and NumberNode =
    {
        Value : float
    }
and SubExpressionNode =
    {
        N : Node
    }

let CreateSubExpression (n : Node) : Node =
    let s : SubExpressionNode = { N = n }
    SubExpression  s

let (PrimitiveAOSCalculator : Parser<Node,unit>), (PrimitiveAOSCalculatorImpl : Parser<Node,unit> ref) = createParserForwardedToRef()

let SubExpression : Parser<Node,unit> =
    between (pchar '(') (pchar ')') PrimitiveAOSCalculator |>> CreateSubExpression

let Number : Parser<Node,unit> =
   pfloat |>> (fun v -> Number { Value = v })

let Product : Parser<Node,unit> = 
    let Factor : Parser<Node,unit> = choice [Number; SubExpression]
    let Mult = spaces >>. pchar '*' .>> spaces
    sepBy1 Factor Mult |>> (fun l -> Product { Factors = l})

let Summand : Parser<Node,unit> =
    choice [ attempt Product; attempt SubExpression ]

let Sum = 
    let Add = (spaces >>. pchar '+' .>> spaces)
    sepBy1 Summand Add |>> (fun l -> Sum { Summands = l })

do PrimitiveAOSCalculatorImpl :=
    Sum

let rec Eval (n : Node) : float =
    match n with
    | Number(v) -> v.Value
    | Product(p) -> List.map (fun n -> Eval n) p.Factors |> List.fold (fun a b -> a * b) 1.0
    | Sum(s) -> List.map (fun t -> Eval t) s.Summands |> List.fold (fun a b -> a + b) 0.0
    | SubExpression(x) -> Eval x.N


let Calculate (term : string) : float =
    let parseResult = run PrimitiveAOSCalculator term
    match parseResult with
    | Success(ast,_,_) -> Eval ast
    | Failure(errorMessage,_,_) -> failwith ("Parsing of the expression failed: " + errorMessage)

let Show (s : string) : string =
    printfn "%s" s
    s

let test p i =
    testParser p i |> Show |> Calculate |> printfn "result = %f"

do test Product "5.1 * 2" 
do test Product "5.1"
do test Product "5.1"
do test Sum "(4 * 3) + (5 * 2)"
do test Sum "4 * 3 + 5 * 2"

do test PrimitiveAOSCalculator "42"
do test PrimitiveAOSCalculator "42 * 42"
do test PrimitiveAOSCalculator "42 + 42"
do test PrimitiveAOSCalculator "42 * 42 + 47.11"
do test PrimitiveAOSCalculator "5.1 * (32 + 88 * 3) + 1.4"

Здесь $do test Sum "4 * 3 + 5 * 2" завершается неудачно со следующим выводом:

Failure Error in Ln: 1 Col: 1
4 * 3 + 5 * 2
^
Expecting: '('

The parser backtracked after:
  Error in Ln: 1 Col: 7
  4 * 3 + 5 * 2
        ^
  Expecting: '*'

4 * 3 + 5 * 2
System.Exception: Parsing of the expression failed: Error in Ln: 1 Col: 1
4 * 3 + 5 * 2
^
Expecting: '('

The parser backtracked after:
  Error in Ln: 1 Col: 7
  4 * 3 + 5 * 2
        ^
  Expecting: '*'

И я даже не имею ни малейшего представления, почему здесь следует ожидать "*".

Answer 1

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

Точнее, в вашем коде ошибка в ваших разделителях. Комбинаторы, такие как sepBy1 построены из вариантов. Когда он соответствует элементу, он пытается сопоставить разделитель. В этом случае разделитель spaces >>. pchar '*' .>> spaces, поскольку spaces совпадения успешно, он не будет возвращен, даже если pchar '*' затем терпит неудачу; он просто будет считать этот парсер в целом неудачным. Это очень распространенная проблема, касающаяся пробелов с помощью комбинаторов синтаксического анализа. Обычный способ исправить это - всегда анализировать пробелы как суффикс другого парсера, а не как префикс. В вашем случае вам необходимо:

• замещать pfloat в Number с pfloat .>> spaces,

• Удалить префикс spaces >>. в ваших разделителях.

• Вы, вероятно, также хотите добавить суффикс .>> spaces как открывающим, так и закрывающим парсерным парсерам.

Вы можете написать промежуточные функции, которые не позволят этому получить слишком многословный:

// ...

let sp parser = parser .>> spaces

let spchar c = sp (pchar c)

let SubExpression : Parser<Node,unit> =
    between (spchar '(') (spchar ')') PrimitiveAOSCalculator |>> CreateSubExpression

let Number : Parser<Node,unit> =
    sp pfloat |>> (fun v -> Number { Value = v })

let Product : Parser<Node,unit> = 
    let Factor : Parser<Node,unit> = choice [Number; SubExpression]
    let Mult = spchar '*'
    sepBy1 Factor Mult |>> (fun l -> Product { Factors = l})

let Summand : Parser<Node,unit> =
    choice [ Product; SubExpression ]

let Sum = 
    let Add = spchar '+'
    sepBy1 Summand Add |>> (fun l -> Sum { Summands = l })

// ...

Я также удалил звонки attempt в Summand, Они являются причиной, по которой ваши ошибки обнаруживаются в таких странных местах: когда парсер разделителя не работает, ошибка распространяется вверх, пока не достигнет вызова attempt Product; этот attempt превратил ошибку в простое "нет совпадений и нет входных данных", поэтому выбор попытался SubExpression вместо того, чтобы вообще потерпеть неудачу. Это в конечном итоге сказал вам, что ожидал '(' хотя первоначальная ошибка была на самом деле где-то еще. Как правило, вам следует избегать attemptи если вам это действительно нужно, вызывайте его наименьшим из возможных анализаторов.