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屋！