使用递归下降解析 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]

parse 函数生成一个 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 后过滤/删除标记的函数。或者有没有更简单/更好的方法来解决这个问题？

任何意见，将不胜感激。或者你有一个有用的链接？

Answer 1

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

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

• 不仅能够返回 an Expression，还能够返回任何类型的值 - 即泛型。通过这种方式，您可以解析本身Expression还不是的中间值，然后将它们组合成一个Expression.
• 不是一个单一的函数，而是一个完整的函数家族——每个函数都解析自己的一点点，而不是试图在一个镜头中囊括所有的荣耀。
• 能够返回失败 - 即无法解析函数正在解析的任何内容的情况。这将允许您连续尝试多个解析器以查看它们中是否有任何匹配。
• 不仅返回结果/失败，而且至关重要的是，返回输入流的其余部分- 即解析函数停止解析后出现的标记列表。通过这种方式，您可以连续解析多个内容，一个接一个 - 例如，“打开括号”，然后是“一些表达式”，然后是“关闭括号”。
• 提供一种将多个解析器组合在一起的方法，如上所述 - 连续或作为一个接一个尝试的替代方法。我们稍后会回到这个问题。

让我们试着写下这个函数的类型，这样我们就可以看到它，可以回过头来参考：

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

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

• 通用的
• 获取令牌的输入列表
• 返回要么解析结果'a加上标记的其余部分，或者一个错误

考虑到该签名，让我们尝试实现最简单的解析函数——解析“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函数将它应该解析的标记作为参数，并返回 aParserFn<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。那么该怎么办？嗯，这是需要特殊函数来解析文字的合理情况。通常，在设计解析器时，您或多或少会为语法中的每个规则找到一个单独的函数。有时它们可​​以被参数化，比如parseParOpenand 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

注意 howfirstParser只是一个解析器，而是nextParser一个函数，它接受第一个解析器的结果并返回另一个解析器，然后我们将其应用于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返回一个解析函数，我们将其存储在combinedParser变量中，然后使用 out 参数调用它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和返回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

在这里，我们首先 try parseParens，只有失败了，我们才回去 try 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是 a TERM，然后是Add，然后是EXPRESSION
• PARENS是ParOpen，然后是EXPRESSION，然后是ParClose

注 1：这些定义是相互递归的。它们必须是，因为您需要括号内的子表达式，并将括号作为表达式的一部分。
注 2：我必须发明一个新概念 - TERM。这是避免使语法无限递归所必需的：因为EXPRESSIONcan be an ADDITION，我们不能让ADDITION自己以 an 开头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 形式，请查看。
• 如果您添加更多运算符，例如减法或乘法，由于运算符优先级的微妙处理，这将变得更加复杂。如果/当您遇到此问题时，请记住：秘诀在于发明更多中间概念，就像我在TERM上面所做的那样。