Parsowanie prostych typów w FParsec

Question

Próbuję parsować standardowe typy proste (w znaczeniu rachunku lambda) przy użyciu FParsec, ale mam trudności z przechodzeniem od stylu Lex/Yacc do tego używanego w FParsec, szczególnie z szacunkiem do definicji rekursywnych.

Przykłady typów Staram się analizować to:

• o
• O -> O
• (O -> O -> O) -> O

A oto moja próba:

    type SType = 
     | Atom 
     | Arrow of SType * SType 

    let ws = spaces 
    let stype, styperef = createParserForwardedToRef() 

    let atom = pchar 'o' .>> ws |>> (fun _ -> Atom) 

    let arrow = pipe2 (stype .>> (pstring "->" .>> ws)) 
         stype 
         (fun t1 t2 -> Arrow (t1,t2)) 

    let arr = parse { 
       let! t1 = stype 
       do! ws 
       let! _ = pstring "->" 
       let! t2 = stype 
       do! ws 
       return Arrow (t1,t2) 
       } 

    styperef := choice [ pchar '(' >>. stype .>> pchar ')'; 
         arr; 
         atom ] 

    let _ = run stype "o -> o"` 

Kiedy ładuję to do interakcji ve ostatnia linia powoduje przepełnienie stosu (ironicznie dość trudne do wyszukania w tych dniach). Mogę sobie wyobrazić, dlaczego, biorąc pod uwagę, że istnieją referencje rekursywne, ale przypuszczam, że przewinięcie z jednym znacznikiem uniemożliwiłoby dokonanie pierwszego (w nawiasie) wyboru w stype. Zakładam więc, że musi to być wybór arr, który wybiera stype i tak dalej. Ale jak zapobiec tej pętli?

Interesują mnie komentarze na temat idiomatycznego wykorzystania biblioteki, a także poprawki do mojego rozwiązania.

Answer 1

Podczas pracy z FParsec trzeba analizować sekwencje z pomocą sequence combinators zamiast lewej rekursji. W twoim przypadku można na przykład użyć sepBy1 COMBINATOR:

open FParsec 

type SType = 
    | Atom 
    | Arrow of SType * SType 

let ws = spaces : Parser<unit, unit> 
let str_ws s = pstring s >>. ws 

let stype, stypeRef = createParserForwardedToRef() 

let atom = str_ws "o" >>% Atom 

let elem = atom <|> between (str_ws "(") (str_ws ")") stype 

do stypeRef:= sepBy1 elem (str_ws "->") 
       |>> List.reduceBack (fun t1 t2 -> Arrow(t1, t2)) 

let _ = run stype "o -> o" 

Answer 2

To działa, ale prawdopodobnie jest zhakowane razem zbyt wiele. Kompilacja type Parser... pochodzi z dokumentów FParsec, aby uniknąć błędów kompilatora.

type SType = 
    | Atom 
    | Arrow of SType * SType 

type UserState = unit 
type Parser<'t> = Parser<'t, UserState> 


let ws = spaces 

let atom : Parser<_> = pchar 'o' .>> ws |>> (fun _ -> Atom) 

let rec term = 
    parse { 
     // Force something to come before another term. Either 
     // an atom, or a term in parens. 
     let! first = choice [atom; 
          (pstring "(" .>> ws) >>. term .>> 
           (pstring ")" .>> ws)] 

     // Check if this is an arrow. If not, just return first. 
     let! res = choice [((pstring "->") .>> ws) >>. term |>> (fun x -> 
           Arrow (first, x)); 
          preturn first] 
     return res 
     }