A simple lambda calculus parser with FParsec

Question

I'm new to F# and have a pretty annoying problem. I want to parse the following grammar:

Application := Expression Expression
Expression  := "(" "lambda" Name "." Application ")"
             | Name
Name        := [a-z]+

That would match things like (lambda x. (lambda y. x y)) z and (lambda x. x) y.

My problem is that two rules depend on each other:

let popen = pchar '('
let pclose = pchar ')'
let pname = many1 letter |>> Seq.toArray |>> System.String |>> NameNode
let plambda = pstring "lambda"
let pdot = pchar '.'
let phead = plambda >>. pname .>> pdot
let pexpression = 
        popen >>. pname .>>. papplication .>> pclose |>> ExpressionNode
    <|> pname
let papplication = pexpression .>>. pexpression

pexpression depends on papplication and vicebersa. How can I get rid of that dependency?

Answer 1

Recursive parsers can be implemented via createParserForwardedToRef. This function returns a pair of parser "handle", so to speak, and a mutable cell that holds the parser implementation. The "handle", once called upon to actually parse something, will forward the call to the implementation.

After acquiring this pair, you can implement the other part of the recursion using the "handle", and then create the forwarded parser's implementation and assign it to the mutable cell.

let pexpression, pexpressionImpl = createParserForwardedToRef()
let papplication = pexpression .>>. pexpression
pexpressionImpl := 
       popen >>. pname .>>. papplication .>> pclose |>> ExpressionNode
   <|> pname