parsing - FParsec 选择以意想不到的方式表现

Question

我计划将 FParsec 用于我的一个更大项目的原型(prototype)。所以我决定通过下面列出的测试程序来获得我对这个库的第一次体验。但似乎通过使用 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 ，如果你真的需要它，可以在最小的解析器上调用它。