但是，我发现存在两种不同的编写解析器方法：解析器生成器和解析器。组合器。
有趣的是，我找不到能说明哪种情况更好的资源。相反，我查询的许多资源（和人员）都不知道另一种方法，只是将其方法解释为该方法，而根本没有提及另一种方法：
《龙书》进入词法分析/扫描并提到（f）lex，但根本没有提到解析器组合器。
语言实现模式在很大程度上依赖于Java内置的ANTLR解析器生成器，并且没有提及解析器。完全是组合器。
Parsec上的Parsec入门教程是Haskell中的解析器组合器，根本没有提到解析器生成器。
Boost :: spirit，最著名的C ++ Parser Combinator，根本没有提及Parser Generator。
伟大的解释性博客文章“您可能已经发明了Parser Combinators”根本没有提及Parser Generator。
简单概述：<解析器生成器
解析器生成器接收用DSL编写的文件，该文件是Extended Backus-的一种方言- Naur形式，并将其转换为源代码，然后（在编译时）可以变成此DSL中描述的输入语言的解析器。
这意味着编译过程需要两个单独的步骤来完成有趣的是，解析器生成器本身也是编译器（其中许多确实是自托管的）。
解析器组合器
解析器组合器描述了称为解析器的简单函数，这些函数均将输入作为参数，如果匹配则尝试提取此输入的第一个字符。他们返回一个元组
(result, rest_of_input)，如果解析器无法解析此输入中的任何内容，则其中result可能为空（例如nil或Nothing）。例如，一个digit解析器。其他解析器当然可以将解析器作为第一个参数（最后一个参数仍保留输入字符串）来组合它们：
many1尝试尽可能多地匹配另一个解析器（但至少要匹配一次，否则它本身会失败）。现在，您当然可以组合（组成）
digit和many1来创建一个新的解析器，再说integer。还可以编写一个更高级别的
choice解析器，该解析器使用解析器列表，依次尝试每个解析器。这样，非常复杂可以建立词法分析器/解析器。在支持运算符重载的语言中，即使它仍是直接用目标语言编写的（也可以使用所需的目标语言的所有功能），它看起来也很像EBNF。
简单差异
语言：
解析器生成器是用EBNF-ish DSL和这些语句匹配时应生成的代码组合编写的。 />解析器组合器是直接用目标语言编写的。
词法分析：
解析器生成器在“词法分析器”（词法分析器）之间有非常明显的区别将一个字符串拆分为可能被标记以显示我们正在处理的值的标记）和“解析器”（从词法分析器获取标记的输出列表，并尝试将它们组合起来，从而形成抽象语法树）。 br />解析器组合器不需要/不需要这种区别；通常，简单的解析器执行“词法分析器”的工作，更高级的解析器将这些解析器称为简单的解析器，以决定要创建哪种AST节点。
问题
但是，即使存在这些差异（而且差异列表可能还远远不够完整！），我仍无法就何时使用哪一个做出明智的选择。我看不到这些差异的含义/后果是什么。
哪些问题属性表明使用Parser Generator可以更好地解决问题？
什么问题属性表明存在差异？和使用Parser Combinator更好地解决问题？
#1 楼
过去几天，我做了很多研究，以更好地理解为什么这些独立技术存在的原因以及它们的优缺点。一些已经存在的答案暗示了它们之间有些差异，但它们并没有给出完整的图片，而且似乎有些自以为是，这就是为什么写这个答案的原因。
这个论述很长，但是很重要。和我一起忍受（或者，如果您不耐烦，请滚动至末尾以查看流程图）。
要了解解析器组合器和解析器生成器之间的区别，请先
需要了解存在的各种解析之间的区别。
解析
解析是根据形式分析符号字符串的过程语法。
（在计算科学领域），解析用于使计算机能够理解用某种语言编写的文本，
通常会创建一个表示所编写文本的解析树，存储不同语言的含义。树的每个节点中的书面部分
。然后，可以将此解析树用于各种不同的目的，例如将其翻译成另一种语言（在许多编译器中使用），以某种方式直接解释书面指令（SQL，HTML），允许诸如Linters
之类的工具完成其工作，等等。有时，解析树不是显式生成的，而是直接在树中的每种类型的节点上执行的操作。这样可以提高效率，但是在水下仍然存在一个隐式解析树。
解析是一个计算困难的问题。关于该主题已经进行了五十多年的研究，
但是仍然有很多东西要学习。
粗略地说，有四种让计算机解析输入的通用算法：
LL解析。 （无上下文，自上而下的解析。）
LR解析。 （无上下文，自底向上分析。）
PEG + Packrat解析。
Earley解析。
请注意，这些解析类型是非常笼统的理论描述。有多种方法可以在物理计算机上实现上述算法中的每一个，但要权衡取舍。
理解它们的用法并不重要）。
PEG / Packrat解析和Earley解析的使用少了很多：Earley解析很不错，因为它可以处理整个语法更多（包括那些不一定与上下文无关的语法），但是效率较低（如《龙书》（第4.1.1节）所声称；我不确定这些说法是否仍然正确）。
解析表达式语法+ Packrat解析是一种相对有效的方法，比LL和LR都可以处理更多的语法，但是隐藏了歧义，下面将对此进行快速介绍。
LL（从左到右，最左派生）
这可能是考虑解析的最自然方法。
这个想法是先查看输入字符串中的下一个标记，然后再查看决定应该采取多个可能的递归调用中的哪一个来生成树结构。
此树是“自顶向下”构建的，这意味着我们从树的根开始，并以与
遍历输入字符串相同的方式传播语法规则。也可以看作是为正在读取的“ infix”令牌流构造一个等效的“ postfix”。
执行LL样式解析的解析器可以写成与原始语法非常相似。已指定。
这使得相对容易理解，调试和增强它们。古典解析器组合器只不过是可以组合在一起以构建LL样式解析器的“乐高积木”。
LR解析以相反的方式行进，自下而上：
在每个步骤中，将堆栈中的顶部元素与语法列表进行比较，以查看是否可以将其简化为语法中的更高级别的规则。如果不是，则将输入流中的下一个令牌移位并放置在堆栈的顶部。
如果最后我们在节点上只有一个节点，那么该程序是正确的表示我们语法的起始规则的堆栈。
Lookahead
在这两个系统中的任何一个中，有时都需要从输入中窥视更多标记
，然后才能决定选择哪个。这是
(0)，(1)，(k)或(*)-语法，您会在这两个通用算法的名称之后看到它们，例如LR(1)或LL(k)。 k通常代表“根据您的语法需求而定”，*通常代表“此解析器执行回溯”，虽然功能更强大/易于实现，但具有更大的内存和时间请注意，当LR样式的解析器可能决定“向前看”时，它们在堆栈上已经有很多令牌，因此它们已经有了更多的信息< br进行派遣。这意味着对于同一个语法，它们通常比LL样式的解析器需要更少的“前瞻性”。
LL与LR：歧义性
阅读上述两个说明时，有人可能会问为什么存在LR样式的解析，
因为LL样式的解析似乎更自然。
但是LL样式的解析存在一个问题：左递归。
写这样的语法很自然：
expr ::= expr '+' expr | term
term ::= integer | float
但是，LL式解析器将陷入无限递归循环中
解析此语法时：尝试
expr规则的最左端可能性时，它会再次消耗该规则而又不消耗任何输入。有一些方法可以解决此问题。最简单的方法是重写语法，这样
递归不再发生：
expr ::= term expr_rest
expr_rest ::= '+' expr | ϵ
term ::= integer | float
（这里，ϵ代表“空字符串”）
现在该语法是正确的递归。请注意，立即阅读起来要困难得多。
在实践中，左递归可能会在中间的许多其他步骤之间间接发生。
这使得查找时很难解决。
，但是尝试解决它会使您的语法更难阅读。
正如《龙书》第2.5节所述：
存在冲突：一方面，我们需要一种语法来促进翻译，另一方面，我们需要一种截然不同的语法来促进解析。
解决方案是从语法开始，以便于翻译和翻译。仔细地对其进行转换以利于解析。通过消除左递归
，我们可以获得适用于预测递归下降式翻译器的语法。
LR样式解析器不存在这种左递归问题。递归，因为它们是自下而上构建的树。
但是，将上述语法的思维转换为LR样式的解析器（通常被实现为有限状态自动机）
非常困难（并且容易出错），因为通常要考虑成百上千的状态+状态转换。这就是为什么LR样式的解析器通常由解析器生成器生成的原因，解析器生成器也称为
如何解决歧义
上面我们看到了两种解决左递归歧义的方法：
1）重写语法
2）使用LR分析器。
但是还有其他类型的模棱两可难以解决的问题：
如果两个不同的规则同时适用，该怎么办？
一些常见示例ar e：
算术表达式。
悬空的其他
LL样式解析器和LR样式解析器都存在这些问题。解析问题
算术表达式可以通过引入运算符优先级来解决。
以类似的方式，可以通过选择一个优先级行为并保持不变来解决其他问题，例如“悬空其他”。 （例如，在C / C ++中，悬空的else始终属于最接近的'if'。）另一个解决方案是使用Parser Expression Grammar（PEG）：这类似于上面使用的
BNF语法，但是在模棱两可的情况下，总是“先选择”。当然，这并没有真正“解决”问题，而是掩盖了实际存在的歧义：最终用户可能不知道解析器做出哪种选择，这可能会导致意外结果。
比本文更深入的信息，包括为什么不可能
一般来说知道您的语法是否没有歧义，其含义是
关于上下文的精彩博客文章LL和LR：为什么解析工具很难。
我强烈推荐它；它使我了解了我现在正在谈论的所有内容。
50年的研究
但是生活还在继续。事实证明，实现为有限状态自动机的“正常” LR样式解析器通常需要成千上万个状态+转换，这在程序大小上是一个问题。因此，编写了诸如Simple LR（SLR）和LALR（Look-ahead LR）之类的变体
，它们结合了其他技术来使自动机变小，从而减少了解析器程序的磁盘和内存占用。
此外，解决以上所列歧义的另一种方法是使用通用技术，其中在歧义的情况下，两种可能性都将保留并解析：两种方法都可能无法解析（在另一种可能性是“正确”的情况下，
并在它们都正确的情况下返回两者（并以此方式表明存在歧义）。
有趣的是，在描述了通用LR算法之后，
发现可以使用类似的方法来实现通用LL解析器，
速度很快（$ O（n ^ 3）$模棱两可的语法，$ O（n）$用于完全模棱两可的语法，尽管与简单的（LA）LR解析器相比，簿记功能更多（
，这意味着更高的常数因子）
，但再次允许解析器成为以递归下降（自上而下）的方式编写，这样编写和调试起来自然得多。
解析器组合器，解析器生成器
因此，在这个较长的说明中，我们现在已经成为问题的核心：
解析器组合器和解析器生成器有什么区别，什么时候应该在另一个上使用？
它们确实是不同种类的野兽：
解析器之所以被创建，是因为人们在编写自上而下的解析器，并且意识到
其中许多有很多共同点。
解析器基因之所以创建rators是因为人们希望构建的解析器不具有
LL样式的解析器所存在的问题（即LR样式的解析器），事实证明，手工很难做到这一点。常见的工具包括实现（LA）LR的Yacc / Bison。
有趣的是，如今的情况有些混乱：
可以编写Parser与GLL算法配合使用的组合器，解决了经典LL样式解析器所存在的歧义问题，同时与各种自上而下的解析一样可读/可理解。
解析器生成器也可以为LL-编写样式解析器。 ANTLR正是这样做的，并使用其他启发式方法（自适应LL（*））来解决经典LL样式解析器所具有的歧义。
通常，创建LR解析器生成器和调试在语法上运行的（LA）LR样式解析器生成器的输出
之所以困难，是因为您将原始语法转换为“由内而外”的LR形式。
另一方面，Yacc / Bison之类的工具已经进行了多年的优化，并且在荒谬，这意味着
，现在很多人认为它是解析的方法，并且对新方法持怀疑态度。
您应该使用哪种方法，取决于语法的难易程度，以及解析器需要多快。
取决于语法，这些技术之一（/不同技术的实现）可能更快，内存占用量较小，磁盘占用空间较小，或者比其他方法更具可扩展性或易于调试。您的里程可能会有所不同。
旁注：关于词法分析。
词法分析可用于解析器组合器和解析器生成器。
是要有一个易于实现（因此非常快）的“哑”解析器，该解析器对源代码执行第一遍操作，
删除例如重复的空格，注释等，并可能在其中进行“标记”
主要的优点是第一步使真正的解析器更简单（并且因此可能更快）。 br />主要缺点是您需要单独的翻译步骤，例如行号和列号的错误报告变得更加困难，因为
消除了空格。
最后一个词法分析器只是“另一个”解析器，可以使用以下任何一种实现以上技术。由于其简单性，经常使用除主解析器以外的其他技术，例如存在额外的“词法生成器”。
Tl; Dr：
以下是适用于大多数情况的流程图：
评论
@Sjoerd确实有很多文字，因为事实证明这是一个非常困难的问题。如果您知道我可以使最后一段更清楚的一种方式，我将不胜枚举：“您应该使用哪个，取决于您的语法有多难，以及解析器需要多快。取决于语法，这些技术中的一种（/不同技术的实现）可能比其他技术更快，具有较小的内存占用，较小的磁盘占用，或者更具扩展性或易于调试。您的里程可能会有所不同。”
– Qqwy
16-12-26在14:12
其他答案更短，更清晰，并且在回答方面做得更好。
– Sjoerd
16/12/26在14:40
@Sjoerd我写这个答案的原因是因为其他答案要么简化了问题，要么将部分答案作为完整答案提出，和/或陷入了谬论的陷阱。上面的答案是讨论JörgW Mittag，Thomas Killian和我在理解他们在说什么并在没有假定先验知识的情况下提出该问题后的评论中的体现。
– Qqwy
16/12/26在15:35
当您实际上不使用解析器组合器时，确实无法解决问题。组合符不只是|，这就是重点。 expr的正确重写是更简洁的expr =术语'sepBy'“ +”（此处的单引号代替了反引号以使功能中缀化，因为mini-markdown没有字符转义）。在更一般的情况下，还有chainBy组合器。我意识到很难找到一个不适合PC的简单解析任务作为示例，但这确实是对PC的有力论证。
–史蒂文·阿姆斯特朗（Steven Armstrong）
18/12/30在8:38
@Qqwy以我最近的经验，LL解析器组合器库往往非常慢并且会产生令人讨厌的错误消息，应避免使用。有更强大的解析器组合器库，不仅可以处理词法分析，还可以处理标记化，并且它们一次只在输入流中查看一个标记。实际上，在以下情况下，您可以构建一个相当快的解析器组合器：（1）对输入进行标记，这将导致回溯的频率降低；（2）避免分配（3）间接分配。最后一个，间接调度，取决于您是否使用跟踪JIT。
– John Zabroski
19年11月7日，12：50
#2 楼
对于保证没有语法错误的输入，或者对于语法正确性的总体通过/失败，可以使用解析器组合器，尤其是在函数式编程语言中，解析器组合器更易于使用。这些情况包括编程难题，读取数据文件等。使您想增加解析器生成器复杂性的功能是错误消息。您想要将用户指向行和列的错误消息，并希望人类也可以理解。要正确执行此操作需要大量代码，而更好的解析器生成器（如antlr）可以帮助您解决这一问题。
但是，自动生成只能使您受益匪浅，而大多数商业应用和长期活跃的开源编译器最终手动编写其解析器。我想如果您觉得这样做很舒服，就不会问这个问题，因此建议您使用解析器生成器。
评论
谢谢您的回答！为什么使用解析器生成器比解析器组合器更容易构建可读的错误消息？ （特别是，无论我们讨论的是哪种实现方式），例如，我知道Parsec和Spirit都具有打印包括行+列信息在内的错误消息的功能，因此在Parser Combinators中似乎也可以执行此操作。
– Qqwy
16-12-22在18:59
并不是说您不能使用解析器组合器打印错误消息，而是当您将错误消息放入混合器中时，它们的优势并不明显。使用这两种方法进行相对复杂的语法，您将明白我的意思。
–卡尔·比勒费尔特（Karl Bielefeldt）
16年12月22日在19:50
根据定义，使用Parser Combinator可以得到的所有错误条件是“此时开始，未找到合法输入”。这并不能真正告诉您出了什么问题。从理论上讲，此时调用的各个解析器可以告诉您所期望的内容，但找不到，但是您所能做的就是将所有内容打印出来，从而产生一条错误的错误消息。
– John R. Strohm
16 Dec 25 '12：00
坦白讲，解析器生成器也不以其良好的错误消息而闻名。
–Miles Rout
16 Dec 27 '21：13
默认情况下不是，但是，它们具有用于添加良好错误消息的更方便的挂钩。
–卡尔·比勒费尔特（Karl Bielefeldt）
16年12月27日在22:25
#3 楼
ANTLR解析器生成器的维护者之一Sam Harwell最近写道：我发现[组合器]无法满足我的需求：
ANTLR为我提供了处理歧义之类的工具。在开发过程中，有一些工具可以向我显示模糊的解析结果，因此我可以消除语法中的歧义。在运行时，我可以利用IDE中不完整的输入所产生的歧义来在诸如代码完成之类的功能中产生更准确的结果。
在实践中，我发现解析器组合器不适合满足我的性能目标。其中一部分可以追溯到
将解析结果用于概述，代码完成和智能缩进之类的功能时，对语法进行细微的更改很容易影响这些结果的准确性。 ANTLR提供了可以将这些不匹配转换为编译错误的工具，即使在其他情况下这些类型也会编译。我可以放心地为影响语法的新语言功能创建原型，因为知道构成IDE的所有其他代码将从一开始就为新功能提供完整的体验。我知道的ANTLR 4（基于C＃目标）的分支是我唯一尝试提供此功能的工具。
本质上，解析器组合器是可以玩的很酷的玩具，但他们根本不适合认真工作。
评论
与完全成熟的编程语言+ IDE相比，解析器通常需要简单得多的操作。您多久编写一次这样的代码？一旦？决不？ 90％的时间只需要解析公司的系统应该从客户端导入的奇怪的自定义文件格式。解析器组合器大放异彩：当任务太简单以至于无法证明解析器生成器的巨大开销，但是用手编写一个递归体面的解析器太烦人了。
–晚安书呆子骄傲
20-2-9的10:00
@GoodNightNerdPride“您多久编写一次这样的代码？”实际上，经常发生。 ANTLR到处弹出以解析自定义格式，这些自定义格式“比完全成熟的编程语言更简单”。
–梅森·惠勒
20-2-10在13:28
这正是我的观点！解析器生成器在不应使用的情况下“在各处”使用（一个示例性例外是“完全成熟的编程语言+ IDE”）。我声称解析器组合器在需要某种解析器的情况下有90％的时间是足够的。但是人们使用解析器生成器浪费时间和精力。
–晚安书呆子骄傲
20-2-10在14:27
#4 楼
正如卡尔提到的那样，解析器生成器倾向于具有更好的错误报告。另外：它们趋向于更快，因为生成的代码可以专门用于语法并生成用于超前的跳转表。
它们趋向于具有更好的工具，来识别模棱两可的语法，删除左递归，填充错误分支等。
它们倾向于更好地处理递归定义。
它们往往更健壮，因为生成器沿用了更长的时间并做了更多的工作。
另一方面，组合器具有自己的优势：
它们在代码中，因此，如果您的语法在运行时发生变化，则您可以更轻松地进行更改。
它们往往更易于绑定和实际使用（解析器生成器的输出往往非常通用且难以使用）。
它们在代码中，因此当您的语法未达到您的期望时，调试起来会更容易一些。
它们的学习曲线较浅，因为它们的工作方式与任何其他鳕鱼一样e。解析器生成器往往有自己的怪癖，以学习使工作正常进行。
评论
相对于现实世界中使用的手写LL递归下降解析器，解析器生成器往往具有可怕的错误报告。解析器生成器很少提供添加出色诊断所必需的状态表转换挂钩。这就是为什么几乎每个真正的编译器都不使用解析器组合器或解析器生成器的原因。 LL递归体面的解析器的构建很简单，尽管不是“干净”的PC / PG，但它们更有用。
– dhchdhd
19年1月6日在8:42
评论
还有至少两种您没有提到的实现解析器的方法：解析器解释器（类似于解析器生成器，除了不将解析器语言编译为C或Java，而是直接执行解析器语言），然后简单地编写手动解析器。对于许多现代的可立即投入生产的工业强度语言实现（例如GCC，Clang，javac，Scala），手动编写解析器是实现的首选形式。它为您提供了对内部解析器状态的最大控制，这有助于生成良好的错误消息（近年来，这种错误消息...……已成为语言实施者的高度优先事项）。另外，许多现有的解析器生成器/解释器/组合器并不是真正为应付现代语言实现必须满足的各种需求而设计的。例如。许多现代语言实现将同一段代码用于批处理编译，IDE后台编译，语法突出显示，自动重构，智能代码完成，自动文档生成，自动绘制等。Scala甚至将编译器用于运行时反射及其宏系统。许多现有的解析器...
…框架不够灵活，无法应对。还要注意，有些解析器框架不基于EBNF。例如。用于解析表达式语法的packrat解析器。
我认为这在很大程度上取决于您要编译的语言。它是什么类型的（LR，...）？
……某种程度上是一种自然的选择，而是劣质工具对我们施加的约束。看例如Perl6或Fortress，用于某些语言，它们具有强大的语法功能，无法完全按照lex / YACC派生词来表达。