A simple lambda calculus parser with FParsec

Viewed 177

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?

1 Answers
Related