parsing - 使用递归下降解析 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 后过滤/删除令牌的函数。或者有没有更简单/更好的方法来解决这个问题？

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

标签： parsingf#abstract-syntax-treerecursive-descent

Answer 1

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

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

• 不仅能够返回Expression，而且能够返回任何类型的值 - 即是通用的。通过这种方式，您可以解析本身Expression还不是中间值，然后将它们组合成一个Expression.
• 不是一个单一的函数，而是一个完整的函数家族——每个函数都解析自己的一点点，而不是试图在一个镜头中包含所有的荣耀。
• 能够返回失败 - 即无法解析任何正在解析的函数的情况。这将允许您连续尝试多个解析器以查看它们是否匹配。
• 不仅返回结果/失败，而且至关重要的是，返回输入流的其余部分- 即在解析函数停止解析之后出现的标记列表。这样你可以连续解析几个东西，一个接一个 - 例如，“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：

• 通用的
• 获取令牌的输入列表
• 返回解析结果加上剩余的标记，或错误'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。那么该怎么办？好吧，这是一个需要特殊函数来解析文字的合理案例。通常，在设计解析器时，您或多或少会为语法中的每条规则找到一个单独的函数。有时可以对它们进行参数化，例如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它是一个函数，它接受第一个解析器的结果并返回另一个解析器，然后我们将其应用于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变量中，然后使用我们的参数调用它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

在这里，我们首先尝试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是 a TERM, 后跟Add, 后跟 anEXPRESSION
• PARENS是ParOpen, 紧接着EXPRESSION, 紧接着ParClose

注 1：这些定义是相互递归的。它们必须是，因为您希望括号内的子表达式和括号作为表达式的一部分。
注 2：我必须发明一个新概念 - TERM. 这是避免使语法无限递归所必需的：因为EXPRESSION可以是 a ADDITION，所以我们不能让ADDITION自己以 a 开头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上面所做的那样。