c# - 任何生成表驱动的 LL 解析器的解析器生成器？

Question

我正在尝试为我们开发的查询语言构建一个随机查询生成器。这个想法是通过遵循解析表中的规则来生成随机查询。到目前为止，我尝试过的所有 LL 解析器生成器都只生成递归下降解析器。我可以尝试修改生成的解析器，但查看 ANTLR 为小型表达式语言生成的解析器，我们的查询语言的解析器将非常大。

所以，我认为表驱动的解析器会更小，更容易调整。是否有任何开源工具可以生成表驱动的 LL 解析器？

或者，可以“反向”使用 LR 解析表来派生随机查询吗？

Answer 1

是的，LR 解析器表可用于生成随机查询。您只需像解析一样遍历表，并且在状态表为您提供令牌的转换或缩减的任何地方，您随机提议该令牌，一旦查询的大小“足够大”，则优先选择缩减。令牌序列是您的查询。

但是你不需要 LR 表。您可以以类似的方式遍历您的语法定义（一组 BNF 规则）。您需要首先将所有规则标准化为以下形式：

     LHS = RHS1 RHS2 ... RHSn ;

这通过添加新生成的非终结符来表示原始规则中的复杂子短语，从而摆脱了 Kleene 星号和加号以及替代方案。这很简单。

如果你有一个非终结符（最初是目标符号），只需找到与 LHS 匹配的规则，随机选择一个，然后扩展该规则。您必须将您在规则中的位置作为“点”来跟踪（与 LR 解析器生成中的“项目”相同）。给定一个规则和一个点，选择的标记要么是终结符（提出它，别无选择！）或非终结符（使用本段的方法为非终结符递归生成标记序列）。