FParsec中的递归语法 [英] Recursive grammars in FParsec

问题描述

我决定签出FParsec，并尝试为λ表达式编写一个解析器.事实证明，渴望使递归解析变得困难.我该如何解决?

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?

代码:

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

谢谢！

推荐答案

正如您所指出的那样，问题在于您的 application 解析器会递归调用 expr ，因此是一个无限循环.解析器需要编写成始终消耗一些输入，然后决定要做什么.

As you pointed out, the problem is that your parser for application calls expr recursively and so there is an infinite loop. The parser needs to be written such that it always consumes some input and then decides what to do.

在使用lambda演算的情况下，棘手的事情是识别应用和变量，因为如果输入的内容类似于x...，则第一个字符表明它可能是他们两个.

In case of lambda calculus, the tricky thing is recognizing an application and a variable because if you have input like x... then the first character suggests it could be either of them.

您可以像这样合并 application 和 variable 的规则:

You can merge the rules for application and variable like this:

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

这首先解析一个变量，然后解析另一个表达式(在这种情况下，它是一个应用程序)，或者它仅返回该变量(如果在变量之后没有表达式).其余规则相似:

This first parses a variable and then either parses another expression (in which case it is an application) or it just returns the variable (if there is no expression following the variable). The rest of the rules are similar:

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()避免了显式突变的需要(这使得创建递归值引用成为可能).原则上，它可以写为:

I just avoided the need for explicit mutation by using parse.Delay() (which makes it possible to create recursive value references). In principle, it could be written as:

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

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

...but for some reason, FParsec doesn't implement the ReturnFrom member that is needed if you want to use return! in computation expressions.

这篇关于FParsec中的递归语法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！