Ira*_*ter 17
我认为"解析"这个术语正在被不同的人以不同的方式解释为问题的目的.
在狭隘的技术意义上,解析仅仅是验证源代码是否与语法匹配(或者甚至可能构建树).
有一个相当普遍的民间定理,说你根本无法解析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++编译器平均可以像其他编译器一样快速完成.只有疯狂到足以在模板中编写图灵机的人付出了沉重的代价.(意见:价格实际上是将复杂事物整理到模板上的概念成本,而不是编译器执行成本.)