2

私は最近FParsecを使用していますが、汎用パーサーの欠如が私にとって大きな停止点であることがわかりました。この小さなライブラリの私の目標は、単純さと一般的な入力のサポートです。これを改善する追加、または特に悪いものを思いつくことができますか？

LazyListを開く

タイプState<'a、' b>（input：LazyList <'a>、data：' b）=
    メンバーthis.Input=input
    メンバーthis.Data=data

タイプResult<'a、' b、'c> =
| 'c * State <'a、'b>の成功
| 文字列の失敗*State<'a、' b>

タイプParser<'a、' b、'c> = State <'a、'b>-> Result <'a、'b、' c>

（>> =）左右の状態=
    左の状態と一致する
    | 成功（結果、状態）->（正しい結果）状態
    | 失敗（メッセージ、_）->結果<'a、' b、'd>。失敗（メッセージ、状態）

（<|>）左右の状態=
    左の状態と一致する
    | 結果としての成功（_、_）->結果
    | 失敗（_、_）->正しい状態

let（| >>）パーサー変換状態=
    パーサーの状態を
    | 成功（結果、状態）->成功（変換結果、状態）
    | 失敗（メッセージ、_）->失敗（メッセージ、状態）

let（<？>）パーサーerrorMessage状態=
    パーサーの状態を
    | 結果としての成功（_、_）->結果
    | 失敗（_、_）->失敗（errorMessage、state）                     

タイプParseMonad（）=
    メンバーthis.Bind（f、g）= f >> = g
    メンバーthis.Returnxs= Success（x、s）
    メンバーthis.Zero（）s = Failure（ ""、s）                           
    メンバーthis.Delay（f：unit-> Parser <_、_、_>）= f（）

解析する=ParseMonad（）

バックトラック

驚いたことに、あなたが説明したことを実装するのにそれほど多くのコードは必要ありませんでした。それは少しずさんですが、かなりうまくいくようです。

let (>>=) left right state =
    seq {
        for res in left state do
            match res with
            | Success(v, s) ->
                let v  = 
                    right v s 
                    |> List.tryFind (
                        fun res -> 
                            match res with 
                            | Success (_, _) -> true 
                            | _ -> false
                    ) 
                match v with
                | Some v -> yield v
                | None -> ()
    } |> Seq.toList

let (<|>) left right state = 
    left state @ right state

バックトラックパート2

レイジーリストと末尾呼び出しに最適化された再帰を使用するようにコードを切り替えました。

let (>>=) left right state =
    let rec readRight lst =
        match lst with
        | Cons (x, xs) ->
            match x with
            | Success (r, s) as q -> LazyList.ofList [q]                     
            | Failure (m, s) -> readRight xs
        | Nil -> LazyList.empty<Result<'a, 'b, 'd>>
    let rec readLeft lst =
        match lst with
        | Cons (x, xs) ->
            match x with
            | Success (r, s) -> 
                match readRight (right r s) with 
                | Cons (x, xs) ->
                    match x with
                    | Success (r, s) as q -> LazyList.ofList [q]                     
                    | Failure (m, s) -> readRight xs
                | Nil -> readLeft xs   
            | Failure (m, s) -> readLeft xs
        | Nil -> LazyList.empty<Result<'a, 'b, 'd>>
    readLeft (left state)

let (<|>) (left:Parser<'a, 'b, 'c>) (right:Parser<'a, 'b, 'c>) state = 
    LazyList.delayed (fun () -> left state) 
    |> LazyList.append 
    <| LazyList.delayed (fun () -> right state)
4

1 に答える 1

2

パーサーでバックトラックをサポートするかどうかは、設計上の重要な決定の1つだと思います（構文解析理論についてはあまり覚えていませんが、これにより、パーサーが処理できる言語のタイプが指定される可能性があります。 ）。

バックトラック。実装では、パーサーは失敗するか（Failureケース）、または1つの結果のみを生成する（ケース）可能性がありますSuccess。別のオプションは、0個以上の結果を生成することです（たとえば、結果をとして表すseq<'c>）。これがあなたがすでに考えたものであるならば申し訳ありません:-)、しかしとにかく...

違いは、パーサーが常に最初の可能なオプションに従うことです。たとえば、次のようなものを書く場合：

let! s1 = (str "ab" <|> str "a")
let! s2 = str "bcd"

実装を使用すると、これは入力「abcd」で失敗します。<|>演算子の最初のブランチが選択され、最初の2文字が処理され、シーケンス内の次のパーサーが失敗します。シーケンスに基づく実装では、2番目のパスをバックトラックして追跡し<|>、入力を解析できます。

混ぜる。Combine私が思いついたもう1つのアイデアは、パーサー計算ビルダーにメンバーを追加することもできるということです。これは少し微妙ですが（計算式がどのように変換されるかを理解する必要があるため）、便利な場合があります。追加する場合：

member x.Combine(a, b) = a <|> b
member x.ReturnFrom(p) = p

次に、再帰的なパーサーをうまく書くことができます。

let rec many p acc = 
  parser { let! r = p                  // Parse 'p' at least once
           return! many p (r::acc)     // Try parsing 'p' multiple times
           return r::acc |> List.rev } // If fails, return the result
于 2010-11-11T03:43:26.143 に答える