C++解析的复杂性

Question

C++解析的复杂性

c++parsingtheorybig-ocompiler-theory

9

出于好奇，我想知道有关解析C ++的“理论”结果。

假设我的项目大小为n（以LOC为例，但由于我们将处理大O，因此这不是非常重要）

C ++的解析复杂度是否为O（n）？如果不是，那么它的复杂度是什么？
C（或Java或任何语法上更简单的语言）是否以O（n）解析？
C ++ 1x会引入新功能，使得解析更加困难吗？

非常感谢提供参考资料！

- Cpa

关于C++1x：当然可以。只是一些库特性会大量使用模板元编程，这已经众所周知会导致编译时间变长。 - sbi

1

我认为有一些针对C语言的O(N)（或者几乎是O(N)）解析器，但是肯定没有针对C++的。我认为C++解析速度不能用任何大O符号来近似，除非是O(N^frand())，其中'frand'是一个浮点数不可预测的随机值。 - Arafangion

@sbi：不确定它是否“明确”。编译器只需要支持模板/constexpr递归到某个实现定义的值，这意味着无论您调用什么模板，它最多只能添加有限数量的表达式和语句。 O（N + 1000）仍然只是O（N）。 - Damon

@Damon：请再读一遍。我写道___“关于 C++1x:___ 绝对没问题。” 这是来自 2010 年 11 月，所以 C++1x 指的是后来成为 C++11 的那个版本，它引入了 lambda 函数、>> 用于关闭嵌套模板参数列表和其他一些内容，这些都使得 C++ 更难解析。 - sbi

3个回答

2

视你如何理解“parsed”，如果你的解析包含模板实例化，那么通常情况下不行：

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

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 将需要O(k)的时间，很明显，k可以随着程序大小增加而快速增加，直到int类型的极限。

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

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

我希望您能够用递归#include在C ++中生成类似困难的程序，尽管我不确定您是否打算将预处理器包括在解析步骤中。

除此以外，C++与许多其他语言类似，可以进行O(不是很多)的解析。您可能需要符号查找等内容，如David在其答案中所述的那样，在一般情况下无法具有严格的O(1)最坏情况上限，因此O(n)可能有点乐观。即使汇编语言也可能会查找标签的符号。但例如动态语言不一定需要符号查找来解析，因为可以在运行时进行。如果选择一种仅需要解析器建立哪些符号是关键字并进行某种括号匹配的语言，则Shunting Yard算法为O(n)，因此还有希望。

- Steve Jessop

1

很难确定C++是否可以“仅仅解析”，因为与大多数语言不同，它不能在不同时进行语义分析的情况下进行语法分析。

- Kos

那不是真的。看看我的答案。 - Ira Baxter

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Ira Baxter · Accepted Answer

我认为，“解析”这个术语在不同的人群中被用于不同的问题，因此有不同的解释。

从狭义的技术角度来看，解析仅是验证源代码是否符合语法（或者甚至是构建一棵树）。

有一个相当普遍的流言说你无法解析C ++（以这种方式），因为你必须解决某些符号的含义才能解析。这个流言是完全错误的。

它源于使用“弱”（LALR或回溯递归下降）解析器，如果它们在本地模糊的部分文本的若干可能的子解析中做出了错误的选择（这个SO线程讨论了一个例子），则由于偶尔做出这种选择而完全失败。使用这样的解析器的人解决这个困境的方式是在解析过程中收集符号表数据并将额外的检查揉入到解析过程中，以强制解析器在遇到这种选择时做出正确的选择。这样做的代价是将名称和类型解析与解析混淆在一起，使构建这样的解析器变得非常困难。但是，至少对于传统的GCC，他们使用的是LALR，其在解析时是线性时间的，如果包括解析器所做的名称/类型捕获，则我认为代价不会更高（因为我认为他们没有做完所有操作）。

至少有两个使用“纯”GLR解析技术实现的C ++解析器，它简单地承认解析可能是本地模糊的，并在没有注释或重大开销的情况下捕获多个解析结果。当没有本地模糊性时，GLR解析器的速度是线性时间的。在模糊区域，它们的成本更高，但实际上，标准C++程序中的大部分源文本都属于“线性时间”部分。因此，即使捕获了模糊性，有效速率也是线性的。这两个已实现的解析器都在解析后执行名称和类型解析，并利用不一致性来消除不正确的模糊解析结果。这两个实现是Elsa和我们（SD）的C++前端。我不清楚Elsa的当前功能（我认为它已经多年没有更新了），但我们的实现可以处理所有C++11 [编辑于2015年1月：现在完全支持C++14 编辑于2017年10月：现在完全支持C++17]，包括GCC和Microsoft变体。

如果你采取计算机科学中的严格定义，即将一种语言作为任意字符串集合进行外延定义（语法应该是编码内涵意义的简洁方式），并将解析处理视为“检查程序的语法是否正确”，则对于C ++，您需要扩展模板以验证每个模板是否完全展开。在模板中隐藏着一个图灵机，因此理论上检查C ++程序是否有效是不可能的（没有时间限制）。真正的编译器（遵循标准）对模板展开的数量施加固定约束，而真正的内存也是如此，因此在实践中，C ++编译器会完成这个过程。但是在这个意义上，“解析”程序可能需要任意长的时间。我认为这是大多数人关心的答案。

实际上，我猜测大多数模板实际上是相当简单的，因此C ++编译器的平均完成时间与其他编译器一样快。只有那些在模板中编写图灵机的疯子才会付出严重的代价。（个人观点：代价真正的是将复杂事物硬生生地塞入模板的概念成本，而不是编译器执行成本。）