使用FParsec解析自描述输入。

Question

我使用FParsec来解析描述自己格式的输入。例如，考虑以下输入：

int,str,int:4,'hello',3

输入的第一部分(冒号之前)描述输入第二部分的格式。在本例中，格式为int、str、int，这意味着实际数据由给定类型的三个逗号分隔的值组成，因此结果应该是4、"hello"、3。

用FParsec解析这样的东西最好的方法是什么？

我已经尽了最大的努力，但我对此并不满意。是否有更好的方法来做到这一点更干净、更少有状态、更少依赖parse？我认为这取决于对UserState的更聪明的管理，但我不知道如何做到这一点。谢谢。

open FParsec

type State = { Formats : string[]; Index : int32 }
    with static member Default = { Formats = [||]; Index = 0 }

type Value =
    | Integer of int
    | String of string

let parseFormat : Parser<_, State> =
    parse {
        let! formats =
            sepBy
                (pstring "int" <|> pstring "str")
                (skipString ",")
                |>> Array.ofList
        do! updateUserState (fun state -> { state with Formats = formats })
    }

let parseValue format =
    match format with
        | "int" -> pint32 |>> Integer
        | "str" ->
            between
                (skipString "'")
                (skipString "'")
                (manySatisfy (fun c -> c <> '\''))
                    |>> String
        | _ -> failwith "Unexpected"

let parseValueByState =
    parse {
        let! state = getUserState
        let format = state.Formats.[state.Index]
        do! setUserState { state with Index = state.Index + 1}
        return! parseValue format
    }

let parseData =
    sepBy
        parseValueByState
        (skipString ",")

let parse =
    parseFormat
        >>. skipString ":"
        >>. parseData

[<EntryPoint>]
let main argv =
    let result = runParserOnString parse State.Default "" "int,str,int:4,'hello',3"
    printfn "%A" result
    0

Answer 1

@bytebuster比我快，但我仍然发布我的解决方案。这种技术类似于“bytebuster”。

谢谢你有个有趣的问题。

在编译器中，我认为首选的技术是将文本解析为AST并在其上运行类型检查器。对于本例，一种可能更简单的技术是解析类型定义返回值的一组解析器。然后将这些解析器应用于字符串的其余部分。

open FParsec

type Value = 
  | Integer of int
  | String  of string

type ValueParser = Parser<Value, unit>

let parseIntValue : Parser<Value, unit> =
  pint32 |>> Integer

let parseStringValue : Parser<Value, unit> =
  between
    (skipChar '\'')
    (skipChar '\'')
    (manySatisfy (fun c -> c <> '\''))
    <?> "string"
    |>> String

let parseValueParser : Parser<ValueParser, unit> =
  choice 
    [
      skipString "int"  >>% parseIntValue
      skipString "str"  >>% parseStringValue
    ]

let parseValueParsers : Parser<ValueParser list, unit> =
    sepBy1
      parseValueParser
      (skipChar ',')

// Runs a list of parsers 'ps' separated by 'sep' parser
let sepByList (ps : Parser<'T, unit> list) (sep : Parser<unit, unit>) : Parser<'T list, unit> =
  let rec loop adjust ps =
    match ps with
    | []    -> preturn []
    | h::t  ->
      adjust h >>= fun v -> loop (fun pp -> sep >>. pp) t >>= fun vs -> preturn (v::vs)
  loop id ps

let parseLine : Parser<Value list, unit> =
  parseValueParsers .>> skipChar ':' >>= (fun vps -> sepByList vps (skipChar ',')) .>> eof

[<EntryPoint>]
let main argv = 
    let s = "int,str,int:4,'hello',3"

    let r = run parseLine s

    printfn "%A" r

    0

解析int,str,int:4,'hello',3会产生Success: [Integer 4; String "hello";Integer 3]。

解析int,str,str:4,'hello',3 (不正确)会产生：

Failure:
Error in Ln: 1 Col: 23
int,str,str:4,'hello',3
                      ^
Expecting: string

Answer 2

原来的代码似乎有几个问题，所以我冒昧地从头重写了它。

首先，可能在其他与FParsec相关的项目中有用的几个库函数：

/// Simple Map
/// usage: let z = Map ["hello" => 1; "bye" => 2]
let (=>) x y = x,y
let makeMap x = new Map<_,_>(x)

/// A handy construct allowing NOT to write lengthy type definitions
/// and also avoid Value Restriction error
type Parser<'t> = Parser<'t, UserState>

/// A list combinator, inspired by FParsec's (>>=) combinator
let (<<+) (p1: Parser<'T list>) (p2: Parser<'T>) =
    p1 >>= fun x -> p2 >>= fun y -> preturn (y::x)

/// Runs all parsers listed in the source list;
/// All but the trailing one are also combined with a separator
let allOfSepBy separator parsers : Parser<'T list> =
    let rec fold state =
        function
        | [] -> pzero
        | hd::[] -> state <<+ hd 
        | hd::tl -> fold (state <<+ (hd .>> separator)) tl
    fold (preturn []) parsers
    |>> List.rev    // reverse the list since we appended to the top

现在，主要代码。基本思想是分三个步骤运行解析：

1. 解析出键(这些键是普通的ASCII字符串)
2. 将这些键映射到实际值解析器
3. 按顺序运行这些解析器

其余的似乎都是在代码中注释的。:)

/// The resulting type
type Output =
    | Integer of int
    | String of string

/// tag to parser mappings
let mappings =
    [
        "int" => (pint32 |>> Integer)
        "str" => (
                    manySatisfy (fun c -> c <> '\'')
                    |> between (skipChar ''') (skipChar ''')
                    |>> String
                 )
    ]
    |> makeMap

let myProcess : Parser<Output list> =
    let pKeys =                     // First, we parse out the keys
        many1Satisfy isAsciiLower   // Parse one key; keys are always ASCII strings
        |> sepBy <| (skipChar ',')  // many keys separated by comma
        .>> (skipChar ':')          // all this with trailing semicolon
    let pValues = fun keys ->
        keys                        // take the keys list
        |> List.map                 // find the required Value parser
                                    // (NO ERROR CHECK for bad keys)
            (fun p -> Map.find p mappings)
        |> allOfSepBy (skipChar ',') // they must run in order, comma-separated
    pKeys >>= pValues

在字符串上运行：int,int,str,int,str:4,42,'hello',3,'foobar'

返回：[Integer 4; Integer 42; String "hello"; Integer 3; String "foobar"]

Answer 3

我改写了@FuleSnabel的sepByList如下，以帮助我更好地理解它。这个看起来对吗？

let sepByList (parsers : Parser<'T, unit> list) (sep : Parser<unit, unit>) : Parser<'T list, unit> = 
    let rec loop adjust parsers =
        parse {
            match parsers with
                | [] -> return []
                | parser :: tail ->
                    let! value = adjust parser
                    let! values = loop (fun parser -> sep >>. parser) tail
                    return value :: values
        }
    loop id parsers