c++ - 如何找出 C++ bison 解析器中的意外标记？

Question

我正在使用 bison/flex 在 c++ 中为用户可以在 gui 中的字段中键入的表达式开发解析器。我希望能够在用户输入时向用户提供有关允许的 token (基本上是自动完成)的反馈。 '%error-verbose' 生成的信息就足够了，但它只能作为字符串使用。有没有一种方法可以在处理解析错误时以编程方式访问意外 token 和预期 token 列表？

Answer 1

token 本身在变量 yychar 中。这部分很简单。

找到可能性列表比较棘手。

从概念上讲，您可以重新分析当前输入，但不包括错误的标记；保存解析器状态；然后依次尝试所有其他可能的标记以查看是否产生错误。

您需要重新解析的原因是 LALR 解析器可能会在遇到语法错误之前执行错误的归约。 (不过，它们从不执行错误的移位。)为了发现解析器状态的有效前瞻，必须撤消这些归约，但没有这样做的机制。通常，归约会丢失信息，因此即使在理论上也是不可能的。

如果您启用 LAC (q.v.)，您需要这样做才能获得精确的错误，error-verbose 解析器通过进行探索性解析来避免减少问题(没有减少操作)在每个可能触发不正确减少的 token 上。如果此解析失败，则解析器状态可用于构建选项列表；如果成功，则通过减少操作重做。

不幸的是，bison 没有提供“复制解析器状态”的 API；您可以很容易地对其进行逆向工程，但那将非常脆弱。因此，如果您想在不访问生成的解析器内部的情况下尝试此操作，您实际上必须多次重新解析输入，对每个可能的先行标记一次。

您可以使用规范的 LR 解析器，它具有在任何归约之前检测到错误的特性。完整的 LR 解析表可能非常庞大，但如果您的语法足够简单，这可能不是问题。但是，您仍然没有干净的方法来保存解析器状态，因此除非您对其进行逆向工程，否则您仍然必须为每个成功的先行标记重新解析。 (或者它们的数量足以构建有效的错误消息。Bison 的详细错误设置最多只会输出五种可能性，这是有充分理由的。)

可能最简单的解决方案是解析 bison 错误消息，它具有简单的固定格式。如果您要这样做，我建议您将 token 名称设为简单且易于解析的单词，并在您的 yyerror 处理程序中替换为人类可读的文本。

启用 LAC 肯定会减慢解析速度。一般来说，所有精确的错误检测和报告修改都会减慢解析器的速度，有时甚至会很明显；这包括保留位置信息(尽管这对于调试输出也很有用，因此在实践中无论如何都可能是必要的)。

我一直给出的建议是构建两个解析器，因为它在实践中对我来说效果很好:一个针对无错误代码进行了优化，除了在第一个错误时拒绝输入之外不尝试做任何事情，另一个(可能慢得多)可以处理错误检测和恢复。然后错误的输入被解析两次，一次用快速解析器，然后再用慢速解析器；正确的输入只需要用快速解析器解析一次。这使得项目构建速度很快，并且通常不会减慢初始写入-“编译”-编辑循环的速度，只要快速解析器实际上是快速的。让两个解析器保持同步可能很烦人，但大多数时候错误恢复解析器只需要一些额外的方法，这些方法可以变成空操作，然后在快速解析器中优化掉。使用此策略，您可以使用快速解析器进行“合法先行”生成，而且结果可能足够快。

一如既往，YMMV。祝你好运。