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

谢谢！

- Ramon Snir

---

感谢您在代码中使用希腊字符，我给你点赞 :) - Benjol

好的，我终于下载了 FParsec :-) - Tomas Petricek

Answer 1

正如你所指出的，问题在于你的应用程序解析器递归调用expr，因此会出现无限循环。解析器需要编写成始终消耗一些输入然后决定接下来要做什么。

就lambda演算而言，棘手之处在于识别application和variable，因为如果你有像x...这样的输入，则第一个字符表明它可能是任何一个。

您可以将application和variable的规则合并如下：

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

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

- Tomas Petricek

---

感谢您把这件事情告诉我。在“解析”构建器对象中遗漏了ReturnFrom成员是一个疏忽。在以前的F#版本中，ReturnFrom是隐式定义的。（定义相当简单。）本应在FParsec 0.9中修复这个问题，但是我忘记了。我已经将修复程序提交到BitBucket存储库中。 - Stephan Tolksdorf

个人而言，我不再使用计算表达式语法来构建解析器，因为这里描述的性能问题：http://www.quanttec.com/fparsec/users-guide/where-is-the-monad.html#why-the-monadic-syntax-is-slow - Stephan Tolksdorf

@Stephan Tolksdorf - 起初，缺少ReturnFrom让我感到困扰，但我已经开始避免使用计算表达式语法，因为我注意到解析器以这种方式更快。我刚刚开始习惯您的运算符优先级解析器，这给了我更大的速度提升。 - ChaosPandion

@Tomas Petricek - 对于FParsec而言，与Seq.cache相当的东西将是一个记忆化组合器，就像http://www.quanttec.com/fparsec/users-guide/tips-and-tricks.html#memoizing-parsers中描述的那样。然而，这样的组合器只会在某些特殊情况下帮助性能，其中您有一个频繁回溯的解析器。要摆脱与计算表达式语法相关的开销，您需要更高级的编译器优化，或者您需要使用元编程技术来实现这些优化。 - Stephan Tolksdorf

幸运的是，与计算表达式语法相关的开销通常对于F#中计算表达式最重要的应用——异步表达式来说可以忽略不计。（seq表达式是一个特殊情况，因为F#编译器将它们编译成状态机。） - Stephan Tolksdorf