FParsec中的递归语法

Question

我已经决定检查FParsec并尝试为λ表达式编写解析器。事实证明，渴望使得递归解析变得困难。我该如何解决这个问题？

代码：

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 

谢谢！

Answer 1

正如你所指出的，问题是，你的应用程序调用 EXPR 解析器递归等有一个无限循环。解析器需要被写入，以便它总是消耗一些输入，然后决定要做什么。

在演算的情况下，棘手的事情是因为如果你有喜欢的输入然后x...的第一个字符表明它可以是他们的认识的应用和变量。

可以合并的规则应用和可变这样的：

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

该第一解析变量，然后或者解析的另一种表达（在这种情况下，它是一个应用程序），或者它只是返回变量（如果变量后面没有表达式）。规则其余的都是相似的：

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 ]) 

我只是用parse.Delay()（这使得它可以创建递归值参考）避免了明确的突变的需要。在原则上，它可以写成：

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

...但由于某些原因，如果你想在计算表达式中使用return! FParsec没有实现所需要的ReturnFrom成员。