I'm trying to parse standard simple types (in the sense of lambda calculus) using FParsec, but I've having difficulty going from a Lex/Yacc style to that used in FParsec, specifically with respect to recursive definitions.
Examples of the types I am trying to parse are:
- o
- o -> o
- (o -> o -> o) -> o
And here is my attempt:
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"`
When I load this into the interactive the last line causes a stack overflow (ironically quite hard to search for these days). I can imagine why, given that there are recursive references, but I would have thought the one token lookahead would have prevented following the first (bracketed) choice in stype
. I assume therefore that it must be choosing arr
, which chooses stype
, and so on. But how to prevent this loop?
I'm interested in comments on idiomatic use of the library as well as corrections to my attempted solution.