Gramáticas recursivas en FParsec

Question

He decidido consultar FParsec y he intentado escribir un analizador para expresiones λ. Como resultado, el afán dificulta el análisis recursivo. ¿Como puedo resolver esto?

Código:

open FParsec 

type λExpr = 
    | Variable of char 
    | Application of λExpr * λExpr 
    | Lambda of char * λExpr 

let rec FV = function 
    | Variable v -> Set.singleton v 
    | Application (f, x) -> FV f + FV x 
    | Lambda (x, m) -> FV m - Set.singleton x 

let Λ0 = FV >> (=) Set.empty 

let apply f p = 
    parse 
     { let! v = p 
      return f v } 

let λ e = 

    let expr, exprR = createParserForwardedToRef() 

    let var = lower |> apply Variable 

    let app = tuple2 expr expr 
       |> apply Application 

    let lam = pipe2 (pchar 'λ' >>. many lower) 
         (pchar '.' >>. expr) (fun vs e -> 
               List.foldBack (fun c e -> Lambda (c, e)) vs e) 

    exprR := choice [ 
        lam 
        app 
        var 
        (pchar '(' >>. expr .>> pchar ')') 
        ] 

    run expr e 

Gracias!

Answer 1

Como usted ha señalado, el problema es que su programa de análisis para la aplicación llama expr recursivamente y por lo que hay un bucle infinito. El analizador debe escribirse de manera que siempre consuma algo de entrada y luego decida qué hacer.

En caso de cálculo lambda, lo complicado es el reconocimiento de una aplicación y una variable porque si usted tiene de entrada como x... entonces el primer carácter sugiere que podría ser cualquiera de ellos.

Puede combinar las reglas para aplicación y variables así:

let rec varApp = parse { 
    let! first = lower |> apply Variable 
    let! res = 
    choice [ expr |> apply (fun e -> Application(first, e)) 
      parse { return first } ] 
    return res } 

Este primer análisis sintáctico de una variable y luego o bien un análisis sintáctico otra expresión (en cuyo caso se trata de una aplicación) o simplemente devuelve la variable (si no hay expresión después de la variable). El resto de las reglas son similares:

and lam = 
    pipe2 (pchar 'λ' >>. many lower) 
     (pchar '.' >>. expr) (fun vs e -> 
    List.foldBack (fun c e -> Lambda (c, e)) vs e) 
and brac = pchar '(' >>. expr .>> pchar ')' 
and expr = parse.Delay(fun() -> 
    choice 
    [ lam; varApp; brac ]) 

que acaba de evitar la necesidad de una mutación explícitos mediante el uso parse.Delay() (que hace posible la creación de referencias de valor recursivas). En principio, se podría escribir como:

and expr = parse { 
    return! choice [ lam; varApp; brac ] } 

... pero por alguna razón, FParsec no implementa el miembro ReturnFrom que se necesita si desea utilizar return! en las expresiones de cálculo.