FParsec选择行为以意外的方式

Question

我打算使用FParsec我的一个较大的工程样机。所以我决定通过下面列出的测试程序的方式让我与此库的第一个经验。但似乎我的基本解析器（这似乎工作）使用fparsec“选择”功能的组合产生意外的行为。

基本上，我们的目标是，所有这些简单的计算器解析器代码也总是返回的数字或子表达式的乘积之和。反过来子词语具有相同的结构整体表达。

当我从“选择”的文件理解的，替代品试图从左至右为给“选择”解析器的列表中指定。我的理解是，如果在列表中进一步左解析器失败，但消耗的输入，随后的解析器将不会尝试。

然而，似乎有更多的东西比我现在能理解，就好像它是为我如上所述，代码应工作。但是，这是行不通的。

这将不胜感激，如果有人可以给我）解释了什么错误，为什么和b）如何解决它。

在我的主要项目中，我打算从一些输入计算解析器，所以我需要了解究竟是如何解析器免费惊喜的可靠方法相结合。

(*
    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"

在这里，$做测试总和“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: '*'

我还没有连foggiest想法，为什么会想到“*”在这里。

Answer 1

基本的错误，这是一个与解析器组合启动时完成的，很多时候，是他们并不直接等同于EBNF。最根本的区别是，当你给秒差距一个选择，它会尝试他们令，而一旦选择之一，甚至单个字符匹配，那么它停留在这个分支。如果你把你的选择在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，如果你真的需要它，叫它上最小的解析器可能。