2

我最近一直在使用 FParsec，我发现缺乏通用解析器对我来说是一个主要的停止点。我对这个小库的目标是简单性以及对通用输入的支持。你能想到任何可以改善这一点或有什么特别糟糕的补充吗？

打开懒惰列表

type State<'a, 'b> (input:LazyList<'a>, data:'b) =
    成员 this.Input = 输入
    成员 this.Data = 数据

输入结果<'a, 'b, 'c> =
| 'c * State<'a, 'b> 成功
| 字符串失败 * State<'a, 'b>

type Parser<'a,'b, 'c> = State<'a, 'b> -> 结果<'a, 'b, 'c>

让 (>>=) 左右状态 =
    将左状态与
    | Success (result, state) -> (right result) state
    | 失败（消息，_）-> Result<'a，'b，'d>.Failure（消息，状态）

让 (<|>) 左右状态 =
    将左状态与
    | 成功 (_, _) 作为结果 -> 结果
    | 失败 (_, _) -> 正确状态

让 (|>>) 解析器转换状态 =
    匹配解析器状态
    | Success（结果，状态）-> Success（转换结果，状态）
    | 失败（消息，_）-> 失败（消息，状态）

让 (<?>) 解析器错误消息状态 =
    匹配解析器状态
    | 成功 (_, _) 作为结果 -> 结果
    | 失败 (_, _) -> 失败 (errorMessage, state)                     

类型 ParseMonad() =
    成员 this.Bind (f, g) = f >>= g
    成员 this.Return xs = 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

我认为您需要做出的一个重要设计决定是您是否要在解析器中支持回溯（我不太记得解析理论，但这可能指定了您的解析器可以处理的语言类型）。

回溯。在您的实现中，解析器可能会失败（Failure案例）或仅产生一个结果（Success案例）。另一种选择是生成零个或多个结果（例如，将结果表示为seq<'c>）。对不起，如果这是您已经考虑过的事情:-)，但无论如何......

不同之处在于您的解析器始终遵循第一个可能的选项。例如，如果您编写如下内容：

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

使用您的实现，输入“abcd”将失败。它将选择<|>运算符的第一个分支，然后处理前两个字符，序列中的下一个解析器将失败。基于序列的实现将能够回溯并遵循第二条路径<|>并解析输入。

结合。我想到的另一个想法是，您还可以将Combine成员添加到解析器计算构建器中。这有点微妙（因为您需要了解计算表达式是如何翻译的），但它有时会很有用。如果添加：

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 回答