看起来GCC和LLVM-Clang正在使用手写递归下降解析器，而不是基于Bison-Flex的机器生成自下而上分析。
请问这里是否有人能够确认这一点？如果是这样的话，为什么主流编译器框架使用手写解析器呢？
GCC和Clang解析器真的是手写的吗？
102
- JCLL
6
29几乎所有主流编译器都使用手写的解析器。这有什么问题？ - SK-logic
2如果需要性能，您必须（半）手动完成它。 - Gene Bushuyev
16不仅如此，还包括更好的错误信息、恢复能力等方面。 - SK-logic
MS VisualStudio怎么样？虽然不是开源的，但微软的工程师能否验证他们也在使用手写递归下降解析器呢？ - OrenIshShalom
3来自GCC维基的@GeneBushuyev：“尽管时间显示了1.5％的加速，但主要的好处是促进未来的增强...”这个加速似乎相当微小... - OrenIshShalom
1为什么这让人惊讶？即使是我的递归命令行解析器也是手写的... - MarcusJ
6个回答
120
有一个民间定理说C很难解析，而C++几乎是不可能的。
这是不正确的。
正确的是，如果不通过修改解析机制和纠缠符号表数据，使用LALR（1）解析器解析C和C++确实相当困难。事实上，GCC曾经使用YACC和其他hackery来解析它们，是的，那很丑陋。现在GCC使用手写解析器，但仍然使用符号表hackery。Clang的开发人员从未尝试过使用自动化解析器生成器；据我所知，Clang解析器一直是手写递归下降的。
真正的是，使用更强大的自动生成解析器（例如GLR解析器），C和C++相对容易解析，而且不需要任何hack。Elsa 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在语义上非常复杂，这项工作超过了让解析器运行的努力。
这是不正确的。
正确的是，如果不通过修改解析机制和纠缠符号表数据，使用LALR（1）解析器解析C和C++确实相当困难。事实上，GCC曾经使用YACC和其他hackery来解析它们，是的，那很丑陋。现在GCC使用手写解析器，但仍然使用符号表hackery。Clang的开发人员从未尝试过使用自动化解析器生成器；据我所知，Clang解析器一直是手写递归下降的。
真正的是，使用更强大的自动生成解析器（例如GLR解析器），C和C++相对容易解析，而且不需要任何hack。Elsa 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，请参见get human readable AST from c++ code，以及C++的臭名昭著的“最令人烦恼的解析”）。
编辑于2017年4月：现在支持（草案）C++17。
- Ira Baxter
21
7后记：就像让语法与供应商实际操作相匹配一样困难，让名称和类型解析与不同供应商对C++11手册的解释相匹配更加困难，因为您唯一拥有的证据是编译略有不同的程序，如果您能找到它们的话。对于C++11本身而言，我们在2013年8月基本上已经过了这个阶段，但我对C++委员会感到有些绝望，他们似乎痴迷于以C++1y的形式制定一个更大（并且从经验上来看更加令人困惑）的标准。 - Ira Baxter
5我真的很想知道：你如何处理那个
foo * bar; 的歧义？ - Martin16@Martin：我们的解析器可以进行“双向解析”，生成一棵包含特殊“歧义节点”的树，其子节点是替代解析结果；子节点最大程度共享其子节点，因此我们得到了一个有向无环图（DAG），而非树形结构。在解析完成后，我们对DAG运行属性文法求值器（AGE）（如果你不知道它的花哨名称，则可以理解为“遍历树并执行操作”），计算所有已声明标识符的类型。... - Ira Baxter
13这些模糊的子节点不能同时保持类型一致；如果在发现一个无法明确确定类型的模糊子节点时，AGE就会将其删除。剩下的都是类型正确的子节点；因此，我们已经确定了“foobar;”的正确解析方式。这个技巧适用于我们为C++11的真实方言构建的所有种类的疯狂歧义，并且完全*将名称的语义分析与语法分析分开。这种干净的分离意味着需要做的工程工作大大减少（没有纠缠需要调试）。更多讨论请参见https://dev59.com/6nVC5IYBdhLWcg3wnCSA#1004737。 - Ira Baxter
4@TimCas：实际上，我同意你对语言语法（和语义）设计的愚蠢之处进行批评，因为它们过于复杂，很难做到正确（是的，C++语言在这方面遭受了很大的困扰）。我希望语言设计委员会可以设计出更简单的语法，以便更简单的解析技术能够使用，并明确定义语言语义并使用一些语义分析工具进行检查。不幸的是，世界似乎并不是这样。因此，我认为你必须尽可能构建你需要构建的东西，然后继续生活，尽管有些笨拙。 - Ira Baxter
显示剩余16条评论
84
是的：
GCC曾经使用过yacc（bison）解析器，但在3.x系列的某个时候被手写的递归下降解析器替换了：请参见http://gcc.gnu.org/wiki/New_C_Parser以获取相关补丁提交的链接。
Clang也使用手写的递归下降解析器：请参见http://clang.llvm.org/features.html末尾的“一个统一的解析器用于C、Objective C、C++和Objective C++”部分。
- Matthew Slattery
4
3那是否意味着 ObjC、C 和 C++ 具有 LL(k) 文法？ - Lindemann
51即使是最简单的 C 语言，它的语法也具有歧义。例如，“foo * bar;”既可以解析为乘法表达式（结果未使用），也可以解析为声明一个类型为指向“foo”类型的指针变量“bar”。哪个是正确的取决于在该时刻是否在范围内有“foo”的typedef，这是无法通过任何先行查看来确定的。但这只意味着递归下降解析器需要添加一些丑陋的额外机制来处理这个问题。 - Matthew Slattery
9根据实证证据，我可以确认C++11、C和Objective C都有上下文无关语法，并且GLR解析器可以处理它们。 - Ira Baxter
36
Clang的解析器是手写的递归下降解析器，和其他几个开源和商业的C和C ++前端一样。
Clang使用递归下降解析器的原因有几个：
- 性能：手写解析器允许我们编写快速的解析器，根据需要优化热点路径，并且我们始终控制该性能。拥有快速的解析器使得Clang可以在其他开发工具中使用，在那里通常不使用“真正”的解析器，例如IDE中的语法高亮显示和代码完成。
- 诊断和错误恢复：由于手写递归下降解析器完全可控，因此很容易添加检测常见问题并提供出色诊断和错误恢复的特殊情况（例如，请参见http://clang.llvm.org/features.html#expressivediags）。对于自动生成的解析器，您受限于生成器的功能。
- 简单性：递归下降解析器易于编写、理解和调试。您不需要成为解析专家或学习新工具来扩展/改进解析器（这对于开源项目尤为重要），但仍然可以获得出色的结果。
总体而言，对于C ++编译器而言，这并不太重要：C ++的解析部分是非常复杂的，但它仍然是比较容易的部分，因此保持简单性很重要。语义分析-特别是名称查找、初始化、重载决议和模板实例化-比解析复杂几个数量级。如果您想证明，请去查看Clang的“Sema”组件（用于语义分析）和其“Parse”组件（用于解析）的代码和提交的分布情况。
- Doug
5
4是的，语义分析要难得多。我们有大约4000行语法规则组成C++11语法，还有约180,000行属性文法代码用于上面Doub所提到的“语义分析”，还有另外100,000行支持代码。解析并不是问题，尽管如果你从错误的角度入手，它也很困难。 - Ira Baxter
2我并不确定手写解析器在错误报告/恢复方面一定比自动生成的解析器更好。实际上，人们似乎更注重这种解析器而不是增强自动生成的解析器。关于这个话题似乎有相当好的研究；这篇论文特别引起了我的注意：M.G. Burke, 1983年，《LR和LL语法错误诊断和恢复的实用方法》，计算机科学系，纽约大学博士论文，请参见https://archive.org/details/practicalmethodf00burk - Ira Baxter
2延续这个思路：如果你愿意修改/扩展/定制你手工构建的解析器以检查特殊情况以获得更好的诊断结果，那么你应该愿意在机械生成的解析器的更好诊断方面做出同等的投资。对于任何你可以为手动解析器编码的特殊解析，你也可以为机械解析器编写检查代码（对于(G)LR解析器，你几乎可以将其作为规约的语义检查）。在某种程度上，如果这似乎不令人感到兴奋，那么只是因为有些人懒惰，但这并不是对机械生成的解析器的指控。 - Ira Baxter
@IraBaxter 如果您能与我们分享一些关于“用C手写编写一个良好的解析器”的资源，我会非常高兴。 - user15307601
如果您想要构建玩具项目，那是可以的。对于真实语言来说这种方法是可行的，但是解析器生成器才是处理复杂语法的正确方式。我在回答另一个类似问题时已经提到过这一点。如果您想编写递归下降解析器，我的另一篇Stack Overflow答案告诉您如何操作。请参见：https://dev59.com/v3E95IYBdhLWcg3wlu6z#2336769。价格：您需要处理解析器生成器为您处理的复杂情况。 - Ira Baxter
10
这里的答案很奇怪！
C/C++语法不是上下文无关的。它们是上下文敏感的，由于Foo * bar;的二义性。我们必须建立一个typedef列表来确定Foo是否为类型。
Ira Baxter：我不明白你的GLR的意义所在。为什么要构建包含歧义的解析树。解析意味着解决歧义，建立语法树。您可以在第二次通过中解决这些歧义，因此这并不比较丑陋。对我来说，它更加丑陋……
Yacc是一个LR（1）解析生成器（或LALR（1）），但可以轻松地修改为上下文敏感。而且这并不难看。 Yacc / Bison已被创建以帮助解析C语言，因此可能不是最丑陋的用于生成C解析器的工具...
直到GCC 3.x，C解析器是由yacc / bison生成的，在解析期间构建typedefs表。通过“解析”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新手来说代码不那么“易读”。
为什么他们从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解析器开发的下一步？- reuns
4
10对我而言，这更加丑陋。我可以告诉你的是，使用GLR和延迟歧义解析工程化生产级别的解析器，只需要一个真正小的团队即可实现。我见过的所有其他解决方案都涉及多年在公共场合进行咬牙切齿的努力，以使其与LR、递归下降等技术配合使用，需要各种反复试错和修改。你可以构思许多其他很酷的新解析技术，但据我所知，这在目前阶段只会导致更多的挣扎。构思容易，执行难。 - Ira Baxter
@IraBaxter：糟糕！http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.925.5298&rep=rep1&type=pdf - Fizz
@Fizz：有一篇关于解析Fortress的论文很有意思，Fortress是一种复杂的科学编程语言。他们提到了几个值得注意的问题：a）经典的解析器生成器（LL(k)，LALR(1)）无法处理复杂的语法；b）他们尝试了GLR，在规模方面遇到了麻烦，但开发人员缺乏经验，因此没有完成[这不是GLR的错]；c）他们使用回溯（事务性）Packrat解析器，并付出了很多努力，包括改进错误消息的工作。关于他们解析“{|x||x←mySet,3|x}”的例子，我认为GLR可以很好地完成，而且它不需要空格。 - Ira Baxter
func<4 > 2> 不是 func<1>。这段代码无法编译。第一个 > 关闭了模板。 - Phil19709
GCC的解析器是手写的。我猜clang也是一样。这可能有几个原因：
- 性能：你为特定任务优化过的手写代码通常比通用解决方案执行得更好。抽象通常会影响性能。
- 时间：至少在GCC的情况下，GCC早于许多免费开发工具（1987年发布）。当时没有yacc等免费版本，我想这对FSF的人们来说可能是一个优先考虑的问题。
这可能不是“非此即彼”综合征的情况，而更多地是“没有针对我们所需进行优化的东西，所以我们编写了自己的代码”。
- Rafe Kettler
3
161987年没有免费的yacc版本吗？我认为当yacc在70年代首次在Unix下发布时，就已经有了免费版本。如果我没记错（其他帖子似乎也是这样），GCC曾经有一个基于YACC的解析器。我听说更改的借口是为了获得更好的错误报告。 - Ira Baxter
7我想补充一点，用手写解析器生成良好的错误信息通常更容易。 - Dietrich Epp
1你对时间的观点不准确。GCC曾经使用基于YACC的解析器，但后来被手写的递归下降解析器所取代。 - Tommy Andersen
0
看起来GCC和LLVM-Clang使用手写的递归下降解析器，而不是基于Bison-Flex的机器生成的自底向上解析。
特别是Bison，我认为它无法处理语法而不会有一些歧义，并在稍后进行第二次处理。
我知道Haskell的Happy允许使用单调（即状态相关）解析器来解决C语法的特定问题，但我不知道有哪些C解析器生成器允许用户提供状态单子。
理论上，手写解析器的错误恢复将是一个优点，但我对GCC / Clang的经验是错误消息并不特别好。
至于性能-一些声明似乎没有依据。使用解析器生成器生成大型状态机应该会产生O（n）的结果，我怀疑解析不是很多工具中的瓶颈。
- Vanessa McHale
1
3这个问题已经有一个非常高质量的答案，你想要添加什么？ - tod
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接