LALRPOP 解析器基础速成 文档/教程-中文翻译 | LALRPOP Crash course on parsers

✏️ 铅笔开头的内容为译者添加
✏️ 翻译自 LALRPOP 教程 | 解析器基础速 | Crash course on parsers, 这篇为基础速成, 如有基础可跳过, 正式内容在下一篇
✏️ 导航: <<[上篇-介绍] - [目录] - [下篇-快速开始]>>
✏️ 完整的中文文档(共9篇19k字): https://yuhanawa.github.io/posts/2023/57877

解析器基础速成 | Crash course on parsers

如果你以前从未使用过解析器生成器(parser generator), 或者对上下文无关文法(context-free grammars)并不熟悉,这节只是非常简要地介绍一下这个基本概念. 语法(grammar)是一种很好的方式, 可以写出哪些类型的输入是合法的.
在我们的例子中, 我们想支持括号内的数字, 像123, (123)等.我们可以用一个简单的语法来表达这一点, 比如:

Term = Num | "(" Term ")"

在这里, 我们说我们试图解析一个Term(术语), 一个Term可以是一个数字(Num)或其他括号内的Term(这里我们没有定义什么是数字, 但在真正的 LALRPOP 例子中, 我们将用正则表达式来定义). 现在想象一个潜在的输入如((123)). 我们可以通过写出一个叫做 “解析树(parse tree)” 的东西来说明如何解析这个数字:

(  (  1  2  3  )  )
|  |  |     |  |  |
|  |  +-Num-+  |  |
|  |     |     |  |
|  |   Term    |  |
|  |     |     |  |
|  +---Term----+  |
|        |        |
+------Term-------+

这里你可以看到, 我们解析((123))的方法是在中间找到一个Num, 把这个Num称为Term, 然后匹配小括号, 在这个基础上形成另外两个Term.

注意, 这个解析树不是一个数据结构, 而是解析的可视化. 我的意思是, 你可以建立一个解析树作为一个数据结构, 但通常你不会这样做: 因为你不需要这么详细.比如, 你可能对从 Num 到 Term 的无操作转换并不感兴趣. 关于解析树的另一个讨厌(weird)之处在于它与你的语法密切相关, 但往往你需要解析一些现有的数据结构 – 所以如果你建立了一个解析树, 那么你就必须将解析树转换为这些数据结构, 这可能是烦人的.

因此, 解析器生成器通常做的是让你选择如何表示解析树中的每个节点, 以及如何进行转换. 你给每个非终结符(nonterminal)一个类型, 它可以是任何Rust中的类型, 你写的代码将在每次解析树中的新节点被构建时执行. 实际上, 在后面的例子中, 我们最终会建立类似于解析树的东西, 但在开始时, 我们根本不会这样做. 相反, 我们将把每个数字和 term 表示为一个 i32 , 并且我们将在节点周围传播这个值.

为了使之更具体, 这里有一个用 LALRPOP 编写的上述语法(Term=Num|"(" Term ")")的版本(在后面详细的教程中会再次讲解). 你可以看到 Term 非终结符被赋予了 i32 类型, 每个定义都有一些代码跟在 => 符号后面.这些是将要执行的代码, 该代码会将匹配的内容(如数字或括号内的)Term转换为 i32:

Term: i32 = {
    Num => /* ... number code ... */,
    "(" Term ")" => /* ... parenthesized code ... */,
};

OK, 基础知识到此为止足够了, 让我们正式的开始吧!