使用FParsec解析自描述输入

Question

我正在使用FParsec来解析描述其自己格式的输入.例如,考虑这个输入:

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

输入的第一部分(冒号前)描述了输入的第二部分的格式.在这种情况下,格式是int,str,int,这意味着实际的数据由三个以逗号分隔的给定类型的值,所以结果应该是4,"hello",3.

使用FParsec解析类似这样的东西的最佳方法是什么？

我已经在下面尽了最大的努力,但我对此并不满意.有没有更好的方法来做到更清洁,更少有状态,更少依赖parsemonad？我认为这取决于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

原始代码似乎有几个问题,所以我冒昧地从头开始重写它.

首先,几个库函数可能在其他与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 2

@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