GCC和Clang解析器真的是手写的吗？

Question

GCC和Clang解析器真的是手写的吗？

JCL*_*CLL 84 c compiler-construction parsing compilation

似乎GCC和LLVM-Clang使用手写递归下降解析器,而不是机器生成,基于Bison-Flex,自下而上解析.

请问有人请确认是这种情况吗？如果是这样,为什么主流编译器框架使用手写解析器？

更新:这里有关此主题的有趣博客

Answer 1

Ira*_*ter 98

有一个民间定理说C很难解析,而C++基本上是不可能的.

事实并非如此.

真实的是,使用LALR(1)解析器很难解析C和C++,而不会破解解析机制并纠缠符号表数据.GCC实际上用来解析它们,使用YACC和这样的额外hackery,是的它很难看. 现在GCC使用手写解析器,但仍然使用符号表hackery.Clang人从未尝试使用自动解析器生成器; AFAIK的Clang解析器一直是手工编码的递归下降.

真实的是,C和C++使用更强大的自动生成的解析器(例如GLR解析器)进行解析相对容易,并且您不需要任何黑客攻击.所述埃尔莎 C++解析器是这样的一个例子.我们的C++前端是另一个(就像我们所有的"编译器"前端一样,GLR是非常精彩的解析技术).

我们的C++前端没有GCC那么快,而且肯定比Elsa慢; 我们很少精力调整它,因为我们还有其他更紧迫的问题(尽管如此,它已被用于数百万行C++代码).Elsa可能比GCC慢,因为它更通用.鉴于目前的处理器速度,这些差异在实践中可能并不重要.

但是今天广泛分布的"真正的编译器"源于10或20年前或更长时间的编译器.效率低下然后更重要,没有人听说过GLR解析器,所以人们做了他们知道怎么做的事情.Clang肯定是最近的,但民间定理长期保持其"说服力".

你不必再以那种方式去做了.您可以非常合理地使用GLR和其他此类解析器作为前端,并提高编译器的可维护性.

什么是真实的,是让符合您的睦邻友好编译器的行为语法是很难的.虽然几乎所有C++编译器都实现了(大多数)原始标准,但它们也往往有很多暗角扩展,例如MS编译器中的DLL规范等.如果你有一个强大的解析引擎,你可以花时间试图获得与现实相匹配的最终语法,而不是试图弯曲语法以匹配解析器生成器的限制.

编辑2012年11月:自写这个答案以来,我们改进了C++前端以处理完整的C++ 11,包括ANSI,GNU和MS变体方言.虽然有很多额外的东西,但我们不必改变我们的解析引擎; 我们刚刚修改了语法规则.我们确实需要改变语义分析; C++ 11在语义上非常复杂,这项工作淹没了使解析器运行的努力.

编辑2015年2月:...现在处理完整的C++ 14.(请参阅c ++代码中的人类可读AST,以获取一小段代码的GLR解析,以及C++臭名昭着的"最令人烦恼的解析").

编辑2017年4月:现在处理(草稿)C++ 17.

@Martin:我们的解析器解析它*两种方式,生成一个包含特殊"歧义节点"的树,其子节点是替代解析; 孩子们最大限度地分享他们的孩子,所以我们最终得到的是DAG而不是树.*解析完成后,我们在DAG上运行一个属性语法评估器(AGE)(如果你不知道的话,"走树和做东西"的花哨名称)计算所有声明的标识符的类型.... (13认同)
......暧昧的孩子不能两者都是一致的; 发现一个不能明智打字的暧昧孩子的AGE只是删除它.剩下的是好孩子; 因此,我们已经确定了哪个解析"foo*bar;" 是正确的.这招适用于各种中,我们建立的C++ 11的真正方言真正发现语法歧义的疯狂,以及**完全分开语义分析解析为名称.这种干净的分离意味着很少的工程工作(没有纠结调试).有关更多讨论,请参见http://stackoverflow.com/a/1004737/120163. (11认同)
PostScript:正如获得语法以匹配供应商真正做的更难,获得名称和类型解析以匹配不同供应商对C++ 11手册的解释更加困难,因为您拥有的唯一证据是稍微编译的程序不同的是,如果你能找到它们.我们在2013年8月对C++ 11本身大致过去了,但我对C++委员会感到绝望,这个委员会似乎很想以C的形式产生更大的(并且来自经验,更令人困惑的)标准. ++ 1Y. (6认同)
我真的很想知道:你如何处理那个`foo*bar;`歧义？ (5认同)
@TimCas：您似乎将“实现中的错误”与“无法解析”混淆了。我们同意这个标准很复杂，甚至可能在许多黑暗的角落被破坏。您最近检查过 Java 标准/编译器吗？（你看过 PHP 吗？？？）你能展示任何没有错误的特定编译器（甚至非 C++）吗？*你想说啥？* (2认同)
@TimCas：告诉 C++ 委员会。并且，对于所有其他语言标准委员会和编译器实现者。它们都不是完美的。没有人能做对。所以呢？ (2认同)
@TimCas:实际上,我和你在一起,因为设计语言语法(和语义)的愚蠢之处在于如此复杂以至于很难做到这一点(是的,C++语言在这里很糟糕).我希望语言设计委员会能够设计语法,使解析技术更加简单,并明确定义语言语义并使用一些语义分析工具进行检查.唉,世界似乎并不那样.所以,我认为你尽可能地建立你必须建造的东西,并且尽管有尴尬,仍然可以继续生活. (2认同)

Answer 2

Mat*_*ery 73

是:

GCC仙界使用YACC(野牛)解析一次,但它是在3.x系列某一位置被手写的递归下降解析器代替:看http://gcc.gnu.org/wiki/New_C_Parser为指向相关修补程序提交的链接.
Clang还使用手写的递归下降解析器:请参阅http://clang.llvm.org/features.html末尾附近的"C,Objective C,C++和Objective C++的单一统一解析器"部分.

不:即使是C,这三者中最简单的,也有一个含糊不清的语法.例如,`foo*bar;`可以解析为乘法表达式(结果未使用),或者变量`bar`的声明,其类型为pointer-to-`foo`.哪一个是正确的取决于当时`foo`的`typedef`是否在范围内,这不是任何可以用任何量的前瞻确定的东西.但这只意味着递归下降解析器需要添加一些丑陋的额外机制来处理它. (43认同)
我可以从经验证据中确认,C++ 11,C和Objective C具有GLR解析器可以处理的上下文无关语法. (8认同)
这是否意味着ObjC,C和C++有LL(k)语法？ (3认同)
关于上下文敏感性，[this answer](http://stackoverflow.com/a/14589567/1959808) 两者都没有声明：解析这些语言可能是图灵完备的。 (2认同)

Answer 3

小智 30

Clang的解析器是一个手写的递归下降解析器,以及其他几个开源和商业C和C++前端.

Clang使用递归下降解析器有以下几个原因:

性能:手写解析器允许我们编写快速解析器,根据需要优化热路径,并且我们始终控制该性能.拥有快速解析器允许Clang用于其他通常不使用"真实"解析器的开发工具,例如IDE中的语法突出显示和代码完成.
诊断和错误恢复:因为您可以使用手写的递归下降解析器完全控制,所以可以轻松添加检测常见问题并提供出色诊断和错误恢复的特殊情况(例如,请参阅http://clang.llvm .org/features.html #expressivediags)使用自动生成的解析器,您只能使用生成器的功能.
简单性:递归下降解析器易于编写,理解和调试.您不需要成为解析专家或学习扩展/改进解析器的新工具(这对于开源项目尤为重要),但您仍然可以获得很好的结果.

总的来说,对于C++编译器来说,它并不重要:C++的解析部分非常重要,但它仍然是更容易的部分之一,因此保持简单是值得的.语义分析 - 特别是名称查找,初始化,重载解析和模板实例化 - 比解析更复杂.如果你想要证明,请查看代码的分布并提交Clang的"Sema"组件(用于语义分析)与其"Parse"组件(用于解析).

是的,语义分析很难.我们有大约4000行语法规则,包括我们的C++ 11语法,以及大约180,000行属性语法代码,用于上面的"语义分析"Doub列表,另有100,000行支持代码.解析真的不是问题,虽然如果你从错误的脚开始就很难. (4认同)
我不太确定手写的解析器*一定*更适合错误报告/恢复。看起来人们确实在这种解析器上投入了更多的精力，而不是在实践中增强自动解析器生成器生成的解析器。关于这个主题似乎有相当好的研究；这篇特别的论文确实引起了我的注意：MG Burke，1983，LR 和 LL 句法错误诊断和恢复的实用方法，博士论文，纽约大学计算机科学系，请参阅 https://archive.org/details/实用方法f00burk (2认同)
...继续这个思路：如果您愿意修改/扩展/自定义您的手工构建的解析器来检查特殊情况以获得更好的诊断，那么您应该愿意在机械生成的解析器的更好诊断上进行同等的投资。对于可以为手动解析器编码的任何特殊解析器，您也可以为机械解析器编写检查（对于 (G)LR 解析器，您几乎可以将其作为对归约的语义检查来执行此操作）。在某种程度上，这似乎令人倒胃口，人们只是懒惰，但这并不是对机械生成的解析器的控诉（恕我直言）。 (2认同)

Answer 4

Raf*_*ler 8

gcc的解析器是手写的..对于铿锵,我怀疑是一样的.这可能有以下几个原因:

性能:您针对特定任务手动优化的内容几乎总是比一般解决方案更好.抽象通常会影响性能
时间安排:至少在GCC的情况下,GCC早于许多免费的开发人员工具(1987年出版).当时没有yacc等的免费版本,我认为这将成为FSF人员的首选.

这可能不是"不是在这里发明"综合症的情况,而是更多的是"没有任何针对我们需要的东西进行优化,所以我们写了自己的".

1987年没有yacc的免费版本？我认为yacc在70年代首次在Unix下交付时有免费版本.和IIRC(其他海报似乎相同),GCC*使用*来拥有一个基于YACC的解析器.我听到改变它的借口是获得更好的错误报告. (14认同)
我想添加它通常更容易从手写解析器生成良好的错误消息. (7认同)

Answer 5

reu*_*uns 6

那里有奇怪的答案!

C/C++语法不是上下文无关的.由于Foo*bar,它们对上下文敏感; 歧义.我们必须构建一个typedef列表来知道Foo是否是一个类型.

艾拉巴克斯特:我没有看到你的GLR的重点.为什么要构建一个包含歧义的解析树.解析意味着解决歧义,构建语法树.你可以在第二遍中解决这些歧义,所以这并不是那么难看.对我来说它更难看......

Yacc是LR(1)解析器生成器(或LALR(1)),但它可以很容易地修改为上下文敏感.并没有什么难看的.创建Yacc/Bison是为了帮助解析C语言,所以可能它不是生成C语法分析器最丑陋的工具......

在GCC 3.x之前,C语言分析器由yacc/bison生成,在解析期间构建了typedefs表.使用"in parse"typedefs表构建,C语法变为本地上下文无关,并且还"本地LR(1)".

现在,在Gcc 4.x中,它是一个递归下降解析器.它与Gcc 3.x中的解析器完全相同,它仍然是LR(1),并且具有相同的语法规则.不同之处在于yacc解析器已被手动重写,shift/reduce现在隐藏在调用堆栈中,并且没有"state454:if(nextsym =='(')goto state398",如gcc 3.x yacc中解析器,因此它更容易修补,处理错误和打印更好的消息,并在解析过程中执行一些下一个编译步骤.代价为gcc noob的"易于阅读"代码.

他们为什么从yacc转为递归下降？因为非常有必要避免使用yacc来解析C++,并且因为GCC梦想成为多语言编译器,即在不同语言之间共享最大代码,它可以编译.这就是为什么C++和C语法分析器以相同的方式编写的原因.

C++比C更难解析,因为它不是"本地"LR(1)作为C,它甚至不是LR(k).看看func<4 > 2>哪个是用4> 2实例化的模板函数,即func<4 > 2> 必须读为func<1>.这绝对不是LR(1).现在考虑,func<4 > 2 > 1 > 3 > 3 > 8 > 9 > 8 > 7 > 8>.这是递归下降可以轻松解决歧义的地方,代价是更多的函数调用(parse_template_parameter是模糊的解析器函数.如果parse_template_parameter(17tokens)失败,请再次尝试parse_template_parameter(15tokens),parse_template_parameter(13tokens)......直到有用).

我不知道为什么不可能添加到yacc/bison递归子语法中,也许这将是gcc/GNU解析器开发的下一步？

"对我来说,它更难看".我可以告诉你的是,使用GLR和延迟模糊度分辨率的生产质量解析器的设计对于一个非常小的团队来说是实用的.我所看到的所有其他解决方案都涉及多年来在公共场合咬牙切齿以及使其与LR一起工作所需的黑客,递归下降,你说出来.你可以假设许多其他很酷的新解析技术,但据我所知,这只是咬牙切齿的重点.想法很便宜; 执行是亲爱的. (9认同)

归档时间：	14 年，6 月前
查看次数：	28184 次
最近记录：	7 年，2 月前