使用递归下降解析 F# 中的嵌套括号

Question

我正尝试在 F# 中制作递归下降解析器。我查看了 http://www.fssnip.net/bM，但这种类型的解析器使用字符串而不是列表。

我正在努力解析括号，尤其是嵌套的括号。有很多解析器失败的边缘情况。

我使用以下数据类型来表示标记。

type Token =
    | ParOpen
    | ParClose
    | Identifier of string
    | IntLiteral of int
    | Add

let example = [ParOpen;IntLiteral 3;Token.Add;IntLiteral 5;ParClose]

下面的数据类型用于表示AST中的节点。有点像生产规则。

type Expression =
  | Add of Expression * Expression
  | Par of Expression
  | Constant of int
  | Leaf //not used currently

下面的函数可以用来解析例如“3 + 5”。但在解析括号时，它对大多数情况不起作用。例如“(3 + 5) + 1”将失败。

let rec parse listOfTokens = 
    match listOfTokens with
    | IntLiteral i::Token.Add::list -> Add(Constant i, parse list)
    | IntLiteral i::[] -> Constant i
    | ParOpen::list -> Par(parse list)
    | IntLiteral i::ParClose::[] -> Constant i
    | _ -> failwith "Unexpected token"

let example = [ParOpen;IntLiteral 3;Token.Add;IntLiteral 5;ParClose;Token.Add;IntLiteral 1]

解析函数生成一个 AST，可以使用以下函数对其进行评估。但它并不总是计算正确。

let rec evaluateExpression exp =
    match exp with
    | Add(x, y) -> evaluateExpression(x) + evaluateExpression(y)
    | Par(expression) -> evaluateExpression(expression)
    | Constant i -> i 
    | _ -> failwith "Unexpected expression"

一个大问题是与列表的模式匹配允许我一次只能查看几个标记。例如：

match tokens with
| ParOpen::exp::ParClose -> Par(parse exp) //exp is just one token right now, this does not work

我可以实现一个函数，该函数会在检测到 ParClose 后 filter/remove 标记。或者有什么 easier/better 方法可以解决这个问题？

如有任何建议，我们将不胜感激。或者你有一个有用的 link?

Answer 1

你试图在这个微弱的函数中加入太多内容。您试图将所有事情作为一个简单的递归函数同时完成，但问题本质上更复杂，这就是您以“太多边缘情况”的形式发现的问题。作为一般规则，如果您有太多边缘情况，则意味着您需要重新定义边缘。

这里的关键见解是解析函数不应该有一个简单的签名 Token list -> Expression。相反，解析函数应该：

能够 return 不仅仅是 Expression，而是任何类型的值 - 即通用。这样你就可以解析中间值，它们本身还不是 Expression，然后将它们组合成 Expression.
不是一个单一的函数，而是一个完整的函数家族 - 每个函数都在解析自己的一点点，而不是试图一次包含所有的荣耀。
能够 return 失败 - 即函数正在解析的任何内容都无法解析的情况。这将允许您连续尝试多个解析器以查看它们是否匹配。
Return 不仅是 result/failure，而且至关重要的是，return 输入流的其余部分 - 即列表解析函数停止解析后出现的标记。这样你就可以连续解析几件事，一个接一个——例如，“open paren”，然后是“some expression”，然后是“close paren”。
提供一种将多个解析器组合在一起的方法，如上文所述 - 可以连续进行，也可以作为替代方案逐个尝试。我们稍后会回到这个话题。

我们试着把这个函数的类型写下来，这样我们就可以眼前一亮，回过头来可以参考：

type ParseError = string  // Error is going to be just a string for now
type ParseFn<'a> = Token list -> Result< ('a * Token list), ParseError >

所以在这里你可以看到 ParserFn 是：

通用
获取令牌的输入列表
Returns 或者解析结果'a加上token的余数，或者一个错误

考虑到该签名，让我们尝试实现最简单的解析函数——解析“open paren”标记：

let parseParOpen tokens = 
    match tokens with
    | ParOpen::rest -> Ok (ParOpen, rest)
    | first::_ -> Error $"expected ParOpen, got {first}"
    | [] -> Error $"expected ParOpen, got EOF"

我们来测试一下：

> parseParOpen [ParOpen; Add]
Ok (ParOpen, [Add])

> parseParOpen [Add]
Error "expected ParOpen, got Add"

> parseParOpen []
Error "expected ParOpen, got EOF"

不错！现在让我们为 ParClose:

实现一个解析器

let parseParClose tokens = 
    match tokens with
    | ParClose::rest -> Ok (ParClose, rest)
    | first::_ -> Error $"expected ParClose, got {first}"
    | [] -> Error $"expected ParClose, got EOF"

嗯，这看起来非常重复，不是吗？我们可以提取公共部分吗？我们当然可以！

let parseToken t tokens = 
    match tokens with
    | first::rest when first = t -> Ok (t, rest)
    | first::_ -> Error $"expected {t}, got {first}"
    | [] -> Error $"expected {t}, got EOF"

parseToken 函数将它应该解析的标记作为参数，结果 return 是一个 ParserFn<Token>。让我们试试看：

> parseToken ParOpen [ParOpen; Add; ParClose]
Ok (ParOpen, [Add; ParClose])

> parseToken ParClose [ParOpen; Add; ParClose]
Error "expected ParClose, got ParOpen"

> parseToken ParClose [ParClose; Add]
Ok (ParClose, [Add])

更好看！

解析文字怎么样？这有点棘手：我们不能只调用 parseToken (IntLiteral 3)，因为那只会解析文字 3，但会在文字 5 上出错。那么该怎么办？好吧，这是一个合法的情况，需要一个特殊的函数来解析文字。通常，在设计解析器时，您或多或少会为语法中的每个规则找到一个单独的函数。有时它们可以被参数化，比如 parseParOpen 和 parseParClose，但通常它们不能。

所以让我们解析一个文字：

let parseIntLiteral tokens =
    match tokens with
    | (IntLiteral i)::rest -> Ok (i, rest)
    | first::_ -> Error $"expected an int literal, got {first}"
    | [] -> Error $"expected an int literal, got EOF"

（请注意，即使这样也可以在一定程度上与 parseToken 结合使用，以避免重复这两个错误行；但我不会深入讨论，因为这个答案已经太长了）

我们来测试一下：

> parseIntLiteral [IntLiteral 5; Add; ParClose]
Ok (5, [Add; ParClose])

> parseIntLiteral [ParOpen; Add; ParClose]
Error "expected an int literal, got ParOpen"

现在，我们将如何连续解析几件事 - 例如，“3 + 5”？好吧，这应该非常简单：首先解析一个 int，然后解析一个加号，然后再解析一个 int。让我们试试看：

let parseAddition tokens = 
    match parseIntLiteral tokens with
    | Error e -> Error e
    | Ok (x, tokens1) ->
        match parseToken Add tokens1 with
        | Error e -> Error e
        | Ok (_, tokens2) ->
            match parseIntLiteral tokens2 with
            | Error e -> Error e
            | Ok (y, rest) -> Ok (Expression.Add (Constant x, Constant y), rest)

哇，这就是所谓的“厄运金字塔”！这个只有三个级别，但想象一下如果我们得到更复杂的东西！

那怎么办？我们可以提取一些共同的部分吗？哦，是的，我们可以！请注意它在所有三个级别上的模式是如何相同的：首先我们对传入的令牌应用一些解析器，然后如果它是一个错误，我们立即退出，否则我们应用下一个解析器，冲洗并重复。我们当然可以将该模式捕获为一个函数：

let applyNextParser firstParser nextParser tokens =
    match firstParser tokens with
    | Error e -> Error e
    | Ok (r, rest) -> nextParser r rest

请注意 firstParser 只是一个解析器，而 nextParser 是一个函数，它获取第一个解析器的结果和 return 另一个解析器，然后我们将其应用于 rest 代币。

let parseAddition tokens =
    let combinedParser =
        applyNextParser parseIntLiteral (fun x ->
            applyNextParser (parseToken Add) (fun _ ->
                applyNextParser parseIntLiteral (fun y ->
                    fun restTokens -> Ok (Expression.Add (Constant x, Constant y), restTokens)
                )
            )
        )
      
    combinedParser tokens

需要注意的一点是applyNextParser return是一个解析函数，我们将其存储在combinedParser变量中，然后使用我们的参数tokens调用它.当然我们可以去掉中间变量：

let parseAddition =
    applyNextParser parseIntLiteral (fun x ->
        applyNextParser (parseToken Add) (fun _ ->
            applyNextParser parseIntLiteral (fun y ->
                fun restTokens -> Ok (Expression.Add (Constant x, Constant y), restTokens)
            )
        )
    )

另一件需要注意的事情是最中间的表达式——它是一个接受 restTokens 和 returns Ok 而没有消耗任何 restTokens 的函数。这样的函数也可以看作是一种解析器。它是一个不消耗任何输入的解析器，但已经为您准备好了解析结果。这将在我们继续进行时非常有用，所以让我们也提取此模式：

let constParser c tokens = Ok (c, tokens)

然后：

let parseAddition =
    applyNextParser parseIntLiteral (fun x ->
        applyNextParser (parseToken Add) (fun _ ->
            applyNextParser parseIntLiteral (fun y ->
                constParser (Expression.Add (Constant x, Constant y))
            )
        )
    )

好吧，这比原来的毁灭金字塔好看多了，但仍然很像金字塔。我们能做得更好吗？哦，是的，我们可以，只要我们将 applyNextParser 变成一个运算符：

let (>>=) firstParser nextParser tokens =
    match firstParser tokens with
    | Error e -> Error e
    | Ok (r, rest) -> nextParser r rest

然后：

let parseAddition =
    parseIntLiteral >>= (fun x ->
        parseToken Add >>= (fun _ ->
            parseIntLiteral >>= (fun y ->
                constParser (Expression.Add (Constant x, Constant y))
            )
        )
    )

那是什么？你说好不了多少？可是等等！现在它是一个运算符，F# 语法允许我们删除括号：

let parseAddition =
    parseIntLiteral >>= fun x ->
        parseToken Add >>= fun _ ->
            parseIntLiteral >>= fun y ->
                constParser (Expression.Add (Constant x, Constant y))

什么，还是金字塔形？但是再等等！ F# 语法还允许我们摆脱缩进：

let parseAddition =
    parseIntLiteral >>= fun x ->
    parseToken Add >>= fun _ ->
    parseIntLiteral >>= fun y ->
    constParser (Expression.Add (Constant x, Constant y))

看哪！现在看起来我们几乎是在将每个解析器的结果“分配”给一个变量。第一个parseIntLiteral被“赋值”给x，第二个parseIntLiteral被“赋值”给y，最后的结果就是x和y得到一个新的解析结果。我们终于有了一个理智的方法来将多个解析器组合成一个序列！

我们来测试一下：

> parseAddition [IntLiteral 3; Add; IntLiteral 5]
Ok (Add (Constant 3, Constant 5), [])

> parseAddition [IntLiteral 3; ParOpen; IntLiteral 5]
Error "expected Add, got ParOpen"

> parseAddition [Add; IntLiteral 5]
Error "expected an int literal, got Add"

呸！现在，我们终于可以解析令人垂涎的圆括号表达式了：

let parseParens =
    parseToken ParOpen >>= fun _ ->
    parseAddition >>= fun exp ->
    parseToken ParClose >>= fun _ ->
    constParser exp

> parseParens [ParOpen; IntLiteral 3; Add; IntLiteral 5; ParClose]
Ok (Add (Constant 3, Constant 5), [])

> parseParens [ParOpen; IntLiteral 3; Add; IntLiteral 5]
Error "expected ParClose, got EOF"

好的，行得通，但是等等！这是否意味着我们只能解析括号？没有括号的表达式呢？好吧，在这里我们终于谈到了按顺序尝试多个解析器并查看哪个有效的问题。如您所见，您的表达式语法实际上有一个隐藏的结构：它可以带括号也可以不带括号，并且带括号的应该优先。也就是说，我们首先尝试解析带括号的表达式，只有当它不起作用时，我们才应该回退到“常规”表达式。

所以，就像以前一样，让我们尝试这样做：

let parseExpression tokens =
    match parseParens tokens with
    | Ok (exp, rest) -> Ok (exp, rest)
    | Error _ ->
        match parseAddition tokens with
        | Ok (exp, rest) -> Ok (exp, rest)
        | Error e -> Error e

这里，我们先尝试parseParens，只有失败了，我们才返回尝试parseAddition。这行得通，但我们又一次得到了厄运金字塔。当然它现在又小又可爱，但想象一下再添加一些替代品。除了这一次，金字塔从 Error 个案例中生长出来，而上次是 Ok 个案例。但没关系：就像上次一样，我们可以将金字塔方面提取到一个方便的运算符中：

let (<|>) p1 p2 tokens =
    match p1 tokens with
    | Ok (result, rest) -> Ok (result, rest)
    | Error _ ->
        match p2 tokens with
        | Ok (result, rest) -> Ok (result, rest)
        | Error e -> Error e

let parseExpression =
    parseParens <|> parseAddition

轰！现在我们可以清楚地看到“表达式”是“parens”或“addition”。可读，嗯？

（请注意，我们对 <|> 的定义吞没了第一个错误，只保留了第二个错误；这个答案已经太长了，所以我将保留组合错误作为练习）

好的，我们来测试一下：

> parseExpression [ParOpen; IntLiteral 3; Add; IntLiteral 5; ParClose]
Ok (Add (Constant 3, Constant 5), [])

> parseExpression [IntLiteral 3; Add; IntLiteral 5]
Ok (Add (Constant 3, Constant 5), [])

不错！让我们再测试一下：

> parseExpression [IntLiteral 3]
Error "expected Add, got EOF"

哦。天啊。这里发生了什么？

好吧，程序的行为与我们告诉它的完全一样，实际上：表达式要么是带括号的加法，要么是裸加法。不允许使用单个 int 文字。这就是我们所写的，所以这就是程序所做的。事实上，我们需要做更多的工作来定义我们的表达式实际上是什么：

EXPRESSION 是 ADDITION 或 TERM
TERM 是 IntLiteral 或 PARENS
ADDITION 是一个 TERM，然后是 Add，然后是 EXPRESSION
PARENS是ParOpen，接着是EXPRESSION，接着是ParClose

注1：这些定义是相互递归的。它们必须是，因为您希望子表达式位于括号内，并且括号作为表达式的一部分。
注释 2：我不得不发明一个新概念 - TERM。这是避免使语法无限递归所必需的：因为 EXPRESSION 可以是 ADDITION，我们不能让 ADDITION 本身以 EXPRESSION 开头。这是只有通过经验（或正规教育）才能获得的微妙之处。
注释3：我漏掉了Identifier：你根本没有在谈论它，所以我把它留作练习。

现在我们有了这些规则，让我们尝试重写我们的解析器。它们当然必须相互递归，我们可以非常严格地遵循上面的英文定义，或多或少地将它们逐字翻译成 F#：

let rec parseExpression =
    parseAddition <|> parseTerm

and parseTerm =
    parseParens
    <|> (parseIntLiteral >>= fun i -> constParser (Constant i))

and parseAddition =
    parseTerm >>= fun x ->
    parseToken Add >>= fun _ ->
    parseExpression >>= fun y ->
    constParser (Expression.Add (x, y))

and parseParens =
    parseToken ParOpen >>= fun _ ->
    parseExpression >>= fun exp ->
    parseToken ParClose >>= fun _ ->
    constParser exp

我们来测试一下：

> parseExpression [ParOpen; IntLiteral 3; Add; IntLiteral 5; ParClose]
Ok (Add (Constant 3, Constant 5), [])

> parseExpression [ParOpen; IntLiteral 3; Add; IntLiteral 5; ParClose; Add; IntLiteral 8]
Ok (Add (Add (Constant 3, Constant 5), Constant 8), [])

> parseExpression [IntLiteral 3; Add; IntLiteral 5; Add; IntLiteral 8]
Ok (Add (Constant 3, Add (Constant 5, Constant 8)), [])

> parseExpression [IntLiteral 3]
Ok (Constant 3, [])

> parseExpression [ParOpen; IntLiteral 3; ParClose]
Ok (Constant 3, [])

> parseExpression [ParOpen; IntLiteral 3; Add; IntLiteral 5; ParClose; Add; ParOpen; IntLiteral 8; Add; ParOpen; IntLiteral 1; Add; IntLiteral 10; ParClose; ParClose];;
Ok
  (Add
     (Add (Constant 3, Constant 5),
      Add (Constant 8, Add (Constant 1, Constant 10))), [])

最后，一些一般性说明：

上面解释了逻辑它是如何工作和组合在一起的，但实际的现代解析器库有点复杂，因为它们是性能优化的并且支持流输入.
F# 的此类实际解析器库之一是 FParsec。它实现了以上所有以及更多。我强烈建议您检查一下。
如前所述，您必须小心递归。确保你理解你的语法是什么以及它应该如何工作的最好方法是在开始编写代码之前正式地把它写下来——有点像我上面用 EXPRESSION、TERM、ADDITION 和 PARENS。有完善的正式系统来记录语法。一个事实上的标准是 Backus-Naur form，检查一下。
如果您添加更多运算符，例如减法或乘法，由于对运算符优先级的微妙处理，这将变得更加复杂。 If/when 你明白了，记住：秘诀在于创造更多的中间概念，就像我在上面 TERM 所做的那样。

使用递归下降解析 F# 中的嵌套括号

Parsing nested parentheses in F# using recursive descent

parsing

f#

abstract-syntax-tree

recursive-descent