title: Recursive grammars in FParsec
body: <p>I've decided to check out FParsec, and tried to write a parser for λ expressions. As it turns out, eagerness makes recursive parsing difficult. How can I solve this?</p>
  
  <p>Code:</p>
  
  <pre><code>open FParsec
  
  type λExpr =
      | Variable of char
      | Application of λExpr * λExpr
      | Lambda of char * λExpr
  
  let rec FV = function
      | Variable v -&gt; Set.singleton v
      | Application (f, x) -&gt; FV f + FV x
      | Lambda (x, m) -&gt; FV m - Set.singleton x
  
  let Λ0 = FV &gt;&gt; (=) Set.empty
  
  let apply f p =
      parse
          { let! v = p
            return f v }
  
  let λ e =
  
      let expr, exprR = createParserForwardedToRef()
  
      let var = lower |&gt; apply Variable
  
      let app = tuple2 expr expr
                   |&gt; apply Application
  
      let lam = pipe2 (pchar 'λ' &gt;&gt;. many lower)
                          (pchar '.' &gt;&gt;. expr) (fun vs e -&gt;
                                                  List.foldBack (fun c e -&gt; Lambda (c, e)) vs e)
  
      exprR := choice [
                      lam
                      app
                      var
                      (pchar '(' &gt;&gt;. expr .&gt;&gt; pchar ')')
                      ]
  
      run expr e
  </code></pre>
  
  <p>Thanks!</p>