FParsec选择以意想不到的方式运行

Question

我计划使用FParsec作为我的一个更大项目的原型.所以我决定通过下面列出的测试程序获得我对该库的第一次体验.但似乎通过使用fparsec"choice"函数组合我的基本解析器(似乎工作)会产生意外行为.

基本上,目标是所有这些简单的计算器解析器代码总是返回数字或子表达式的乘积之和.子表达式依次具有与整个表达式相同的结构.

正如我从"选择"的文档中所理解的那样,在"选择"的解析器列表中指定的从左到右尝试的替代方案.我明白如果列表中的进一步遗留的解析器失败但消耗了输入,则不会尝试后续的解析器.

然而,现在似乎还有比我现在理解的更多,就像我上面所说的那样,代码应该有效.但它不起作用.

如果有人能向我解释a)出了什么问题以及为什么和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"

这里,$ 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开始和结束的paren解析器添加后缀.

您可以编写中间函数来防止它过于冗长:

// ...

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,如果你真的需要它,可以在最小的解析器上调用它.