c++ - 我应该如何构建一个简单的 LR 解析器？

Question

我正在尝试为一种将用于生成其他文件的模板(配置)文件构建一个简单的 LR 解析器。我已经阅读和阅读了有关 LR 解析器的信息，但我似乎无法理解它!我知道有一个解析栈，一个状态栈和一个解析表。 token 被读入解析堆栈，当规则匹配时， token 被移动或减少，具体取决于解析表。这递归地继续下去，直到所有的标记都被减少，然后解析完成。

问题是我真的不知道如何生成解析表。我已经阅读了很多描述，但是语言是技术性的，我就是看不懂。谁能告诉我该怎么做？

此外，我将如何存储语法规则之类的东西？

http://codepad.org/oRjnKacH是我尝试解析其语言语法的文件示例。

我以前从未这样做过，所以我只是在寻求一些建议，谢谢。

Answer 1

在您对解析器理论的研究中，您似乎忽略了一个更实际的事实:几乎没有人像您正在讨论的那样考虑手写一个表驱动的、自下而上的解析器。对于大多数实际用途，手写解析器使用自上而下(通常是递归下降)结构。

使用表驱动解析器的主要原因是它允许您编写(相当)少量的代码来操作表等，这几乎是完全通用的(即它适用于任何解析器)。然后，您将有关特定语法的所有内容编码为计算机易于操作的形式(即一些表格)。

显然，如果您真的愿意，完全可能手动完成，但几乎没有真正的意义。完全手动生成表格本身会非常痛苦。

例如，您通常从构造一个 NFA 开始，它是一个大表 -- 通常，每个解析器状态一行，每个可能的输入一列。在每个单元格中，当您从该状态开始时，您对要进入的下一个状态进行编码，然后接收该输入。大多数这些转换基本上是空的(即他们只是说当您处于该状态时不允许输入)。注意:由于有效转换非常稀疏，大多数解析器生成器都支持某种压缩这些表的方法，但这不会改 rebase 本思想。

然后您逐步完成所有这些并遵循一些相当简单的规则将 NFA 状态集收集在一起成为 DFA 中的状态。规则非常简单，很容易将它们编程到计算机中，但您必须对 NFA 表中的每个单元格重复这些规则，并进行本质上完美的簿记以生成有效的 DFA正确。

计算机可以而且将会做得很好——对它来说，对 NFA 状态表中的两万个单元格中的每一个单元格应用几个简单的规则是小菜一碟。很难想象让一个人做同样的事情——我敢肯定，根据 union 国的指导方针，这将是非法的酷刑。