FParsec'te basit türleri ayrıştırma

Question

FParsec kullanarak standart basit türleri (lambda hesabı için) ayrıştırmaya çalışıyorum, ancak Lex/Yacc stilinden FParsec'te kullanılanlara, özellikle de özyinel tanımlara. Ben ayrıştırmak çalışıyorum türlerinden

örnekleri şunlardır:

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

Ve işte benim girişimim:

    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"` 

Bunu etkileşime yüklediğimde ve son satır bir yığın taşmasına neden olur (bu günlerde arama yapmak ironik olarak oldukça zordur). Yinelemeli referanslar olduğu düşünüldüğünde nedenini hayal edebiliyorum, fakat stype numaralı telefondaki ilk (parantezli) seçimi takiben bir simge belirtisinin önleneceğini düşünürdüm. Bu nedenle, stype'u seçen arr'u seçmem gerektiğini düşünüyorum. Ama bu döngü nasıl önlenir?

Kütüphanenin deyimsel kullanımıyla ilgili yorumların yanı sıra denenen çözümüme yönelik düzeltmelerle ilgileniyorum.

Answer 1

Eğer sequence combinators yardımıyla yerine sol özyineleme ile dizileri ayrıştırmak gerekir. Bu olabilir

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

Bu, ancak, muhtemelen çok fazla birlikte hacklendi çalışır. Derleyici hataları önlemek için type Parser... şeyler FParsec docs. Eğer FParsec ile çalışırken

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 
     }