c++ - LR(1) 语法的状态、符号和规则的数量的合理上限是多少？

Question

我正在制作一个 LR(1) 解析器，我在很多地方遇到了性能瓶颈。

我想尝试优化解析器的数据结构，但为了做到这一点，我需要大致了解有多少状态、规则和终端符号对于(可能是复杂的)计算机语言是合理的，像 C++。

我的猜测是，复杂语言的典型语法应该是:

• ≤ 100 个终端符号
• 每次生产≤ 50 个符号
• ≤ 2,000 条规则
• ≤ 10,000 个州

但我真的不知道他们有多正确。

请注意，我假设每个规则都是 nonterminal → symbol symbol symbol...,因此，看起来像 foo: (bar | baz)+ 的单个复合“规则”实际上可能包含 5 条规则，而不仅仅是 1 条规则。

它们合理吗？如果不是，我在哪里可以找到这些数字？

Answer 1

我每天开发的 DMS 系统在一台破旧的笔记本电脑上处理生产 IBM Enterprise COBOL 前端语法大约需要 7 秒(刚刚在那台笔记本电脑上测量)。

语法有大约 500 个终端和 2500 个产生式，平均约 2.5 个标记每个生产。我们的产品与您描述的完全一样(没有 EBNF，只是买的不够重要，是的，我们是 DSL 的忠实粉丝。有时人们放入 DSL 的 geegaws 不值得)。解析器生成器产生 3800 个状态。 (这些值也是刚刚测量的)。

DMS 具有完整的 C++11 语法，其中包含许多额外的内容来处理 GCC 和 MS 方言以及 OpenMP。该文法有 457 个终端，约 3000 个产生式，每个产生式平均约 2.3 个记号。解析器生成器产生 5800 个状态。生成时间稍长:11 秒，在 i7 上。您可能会感到惊讶的是，它需要生成词法分析器需要几十秒(实际上是多个词法分析器)； C++11 中的词法怪异比你想象的要多得多。

生成器是我们自己实现的 GLR 生成器。

我们没有做很多事情来优化生成时间。它可能会加速 10 倍或更多；我们没有像大多数关于 LR 解析器生成的论文中所建议的那样进行复杂的循环检测优化。结果是生成表需要更长的时间，但功能上没有任何损失。我们从来没有足够的动力进行这种优化，因为除了担心解析器表生成时间之外，语言前端还有很多其他事情要做。

如果设计合理，我怀疑数据结构是否重要。我们不太担心规则、项目集或状态的大小；我们只使用动态数组，它们会自行处理。我们确实将先行打包到密集的位 vector 中。

作为额外的背景数据，您可能会发现这篇论文很有用:Tiago Alves and Joost Visser, Metrication of SDF Grammars. Technical Report, DI-Research.PURe-05.05.01, Departamento de Informática, Universidade do Minho, May 2005.

解析器生成器不是您在语法方面遇到困难的地方。它正在为特定的实现获取正确的语法规则。