5

我计划将 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: '*'

而且我什至没有最模糊的想法，为什么它会在这里期待'*'。

4

1 回答 1

8

从解析器组合器开始时经常会犯的一个基本错误是它们不直接等同于 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我还删除了对in的调用Summand。它们是您的错误出现在如此奇怪的地方的原因：当分隔符解析器失败时，错误会向上传播，直到它到达对attempt Product;的调用。这attempt将错误变成了一个简单的“不匹配且不消耗任何输入”，因此选择尝试SubExpression而不是完全失败。这最终告诉您，'('即使最初的错误实际上在其他地方，它也是预期的。作为一项规则，您应该避免attempt使用 ，如果您真的需要它，请尽可能在最小的解析器上调用它。

于 2014-05-26T10:30:40.507 回答