parsing - FParsec の選択が予期しない動作をする

Question

私は、私のより大きなプロジェクトのプロトタイプに FParsec を使用する予定です。そこで、以下に示すテストプログラムを使用して、このライブラリを初めて体験することにしました。しかし、fparsec 'choice' 関数を使用して私の基本的なパーサー (動作しているように見える) を組み合わせると、予期しない動作が発生するようです。

基本的に、目標は、この単純な電卓パーサーコードがすべて、数値またはサブ式の積の合計を常に返すことです。サブ式は、式全体と同じ構造を持つ必要があります。

「choice」のドキュメントから理解したように、「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: '*'

そして、なぜここに「*」が必要なのか、私には最も漠然とした考えさえありません。

score 8 · Accepted Answer

パーサーコンビネータを使い始めるときによく犯す基本的な間違いは、コンビネータがEBNF と直接同等ではないということです。基本的な違いは、parsec に選択肢を与えると、それらを順番に試行し、選択肢の 1 つが 1 文字でも一致するとすぐに、このブランチにとどまることです。選択したものをで指定した場合にのみバックトラックします。attemptこれはできるだけ少なくする必要があります (パフォーマンス上の理由とエラー報告の理由から - 最後の段落を参照してください)。

より具体的には、コードでは、間違いは区切り文字にあります。などのコンビネータsepBy1は、選択肢から構築されます。要素と一致すると、セパレータとの一致を試みます。この場合、セパレータはspaces >>. pchar '*' .>> spaces. 一致に成功し、文字を消費するため、失敗しspacesてもバックトラックしません。pchar '*'このパーサー全体が失敗したと見なすだけです。これは、パーサーコンビネータの空白に関する非常に一般的な問題です。これを修正する通常の方法は、空白を常に接頭辞としてではなく、別のパーサーの接尾辞として解析することです。あなたの場合、次のことが必要です。

をpfloatに置き換えます。Numberpfloat .>> 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 })

// ...

attemptinへの呼び出しも削除しましたSummand。これらが、エラーがそのような奇妙な場所に表示された理由です。セパレーターパーサーが失敗すると、エラーがattempt Product;への呼び出しに到達するまで伝播しました。これattemptにより、エラーが単純な「一致せず、入力が消費されません」に変わったため、選択はSubExpression完全に失敗するのではなく試行されました。'('これは最終的に、元のエラーが実際には別の場所にあったとしても、予期していたことを示しています。原則として、は避けるべきattemptであり、本当に必要な場合は、可能な限り最小のパーサーで呼び出してください。

parsing - FParsec の選択が予期しない動作をする

1 に答える 1

Related

Reference