FParsecの単純型の解析

Question

FParsecを使用して標準的な単純型（ラムダ計算の意味で）を解析しようとしていますが、FParsecで使用されているLex/Yacc形式から、再帰的な定義に。私が解析しようとしているタイプの

例は次の通りである：

〇〇

• - > O
• （O - > O - > O） - > O

そして、ここに私の試みがあります：

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

これをインタラクティブにロードすると最後の行はスタックオーバーフローを引き起こします（皮肉なことに、これらの日を検索するのは非常に困難です）。なぜ再帰的な参照があるのか​​想像することができますが、先読みの1トークンがstypeの最初の（括弧で囲まれた）選択に続くのを防ぐことができたと思います。したがって、arrを選択する必要があります。これはstypeなどを選択します。しかし、このループを防ぐ方法は？

私は、ライブラリの慣用的な使用についてのコメントだけでなく、試行した解決策への修正にも興味があります。

Answer 1

あなたはFParsecで作業するときは、代わりに左再帰のsequence combinatorsの助けを借りて、シーケンスを解析する必要があります。これは、あなたが欲しい欲しいことができ

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

これは実行されますが、あまりに多く一緒にハッキングされている可能性があります。 type Parser...は、コンパイルエラーを避けるためにFParsecのドキュメントにあります。

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 
     }