9

出于好奇，我想知道解析 C++ 的一些“理论”结果是什么。

让 n 是我的项目的大小（例如，在 LOC 中，但由于我们将处理 big-O，所以它不是很重要）

  • C++ 是否在 O(n) 中解析？如果不是，那么复杂性是多少？
  • C（或 Java 或其语法意义上的任何更简单的语言）是否在 O(n) 中解析？
  • C++1x 会引入更难解析的新特性吗？

参考将不胜感激！

4

3 回答 3

17

我认为出于问题的目的，不同的人以不同的方式解释了“解析”一词。

在狭义的技术意义上，解析只是验证源代码是否与语法匹配（甚至可能构建一棵树）。

有一个相当普遍的民间定理说您根本无法解析 C++（在这个意义上），因为您必须解析某些符号的含义才能解析。这个民间定理是完全错误的。

它源于使用“弱”（LALR 或回溯递归下降）解析器，如果他们对文本的局部模糊部分的几个可能的子解析做出错误选择（这个SO 线程讨论了一个示例)，由于有时做出这样的选择而完全失败。使用这种解析器解决困境的方法是在解析发生时收集符号表数据，并将额外的检查混搭到解析过程中，以强制解析器在遇到此类选择时做出正确的选择。这样做的代价是名称和类型解析与解析显着纠缠不清，这使得构建这样的解析器非常困难。但是，至少对于传统的 GCC，他们使用 LALR，它是解析的线性时间，如果你包含解析器所做的名称/类型捕获，我认为不会更昂贵（解析后还有更多工作要做，因为我没有'不认为他们做这一切）。

至少有两种 C++ 解析器的实现是使用“纯” GLR 解析技术完成的，它只是承认解析可能是局部模糊的，并在没有注释或显着开销的情况下捕获多个解析。GLR 解析器是没有局部歧义的线性时间。它们在歧义区域更昂贵，但实际上，标准 C++ 程序中的大多数源文本都属于“线性时间”部分。所以有效率是线性的，甚至可以捕捉到歧义。两个实现的解析器都在解析后进行名称和类型解析，并使用不一致来消除不正确的歧义解析。（这两个实现是Elsa和我们的（SD 的）C++ 前端. 我不能说 Elsa 目前的能力（我认为它已经多年没有更新了），但我们的 C++11 的全部内容 [2015 年 1 月编辑：现在是完整的 C++14 2017 年 10 月编辑：现在是完整的 C ++17] 包括 GCC 和 Microsoft 变体）。

如果您采用硬计算机科学定义，即语言被扩展定义为任意字符串集（语法应该是简洁地对其进行编码的方式）并将解析视为“检查程序的语法是否正确”，那么对于C++ 你已经扩展了模板以验证每个模板实际上都完全扩展了。模板中隐藏着一个图灵机，因此理论上检查 C++ 程序是否有效是不可能的（没有时间限制）。真正的编译器（遵守标准）对模板展开的数量设置了固定的约束，实际内存也是如此，因此在实践中 C++ 编译器完成了。但是从这个意义上说，他们可以花费任意长的时间来“解析”一个程序。我认为这是大多数人关心的答案。

实际上，我猜大多数模板实际上都非常简单，因此 C++ 编译器的平均完成速度与其他编译器一样快。只有疯狂到在模板中编写图灵机的人才会付出沉重的代价。（意见：价格实际上是将复杂的东西硬塞到模板上的概念成本，而不是编译器执行成本。）

于 2010-11-13T16:38:54.393 回答
1

很难判断 C++ 是否可以“仅解析”，因为与大多数语言相反，如果不同时执行语义分析，就无法对其进行语法分析。

于 2010-11-13T11:50:28.313 回答
1

取决于“已解析”的含义，但如果您的解析应该包括模板实例化，那么通常不会：

[如果您想避免阅读示例的快捷方式 - 模板提供了足够丰富的计算模型，因此实例化它们通常是一个暂停式问题]

template<int N>
struct Triangle {
    static const int value = Triangle<N-1>::value + N;
};

template<>
struct Triangle<0> {
    static const int value = 0;
};

int main() {
    return Triangle<127>::value;
}

显然，在这种情况下，编译器理论上可以发现三角形数有一个简单的生成器函数，并使用它计算返回值。但除此之外，实例化Triangle<k>将花费 O(k) 时间，并且显然k可以随着该程序的大小而很快上升，直至int类型的限制。

[快捷方式结束]

现在，为了知道Triangle<127>::value是对象还是类型，编译器实际上必须实例化Triangle<127>（同样，在这种情况下，也许它可以采取捷径，因为value在每个模板特化中都被定义为对象，但不是一般情况下）。符号表示对象还是类型与 C++ 的语法相关，所以我可能会争辩说“解析”C++确实需要模板实例化。不过，其他定义可能会有所不同。

实际实现任意限制模板实例化的深度，使大 O 分析无关紧要，但我忽略了这一点，因为无论如何实际实现都有自然资源限制，也使大 O 分析无关紧要......

我希望您可以在 C 中使用 recursive 生成​​同样困难的程序#include，尽管我不确定您是否打算将预处理器作为解析步骤的一部分。

除此之外，与许多其他语言一样，C 可以进行 O（不是很多）解析。您可能需要符号查找等，正如大卫在他的回答中所说，一般情况下不能有严格的 O(1) 最坏情况界限，所以 O(n) 可能有点乐观。即使是汇编程序也可能会查找标签的符号。但是例如动态语言甚至不一定需要符号查找来进行解析，因为这可能在运行时完成。如果你选择一种语言，解析器需要做的就是确定哪些符号是关键字，并进行某种括号匹配，那么 Shunting Yard 算法是 O(n)，所以有希望。

于 2010-11-13T14:21:29.077 回答