Используйте 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 

Run на строку: int,int,str,int,str:4,42,'hello',3,'foobar'
Возвращается: [Integer 4; Integer 42; String "hello"; Integer 3; String "foobar"]

Answer 3

Я переписал @ sepByList FuleSnabel как следует, чтобы помочь мне лучше понять его. Правильно ли это выглядит?

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