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,因此存在无限循环.需要编写解析器,使其始终消耗一些输入,然后决定要做什么.

在lambda演算的情况下,棘手的是识别应用程序和变量,因为如果你有像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 ] }

...但由于某种原因,ReturnFrom如果要return!在计算表达式中使用,FParsec不会实现所需的成员.