有多少种方法可以构建一个解析器？

Question

我正在学习ANTLR v4，它是一个基于所谓Adaptive (*)算法的解析器生成器。它声称比LL(*)算法有很大的改进，但我也听说过一些类似LR的算法。

ANTLR的自适应LL(*)算法(大于LR)的优点/局限性是什么？

Answer 1

有多少当代算法可以构建一个解析器？

首先，可以查看常见解析器生成器的列表。

参见：解析器生成器的比较，并在标题Parsing algorithm下查看。

ALL(*)  
Backtracking Bottom-up  
Backtracking LALR(1)  
Backtracking LALR(k)  
GLR  
LALR(1)  
LR(1)  
IELR(1)  
LALR(K)
LR(K)  
LL  
LL(1)
LL(*)  
LL(1), Backtracking, Shunting yard
LL(k) + syntactic and semantic predicates  
LL, Backtracking  
LR(0)  
SLR  
Recursive descent  
Recursive descent, Backtracking  
PEG parser interpreter, Packrat  
Packrat (modified)  
Packrat  
Packrat + Cut + Left Recursion  
Packrat (modified), mutating interpreter  
2-phase scannerless top-down backtracking + runtime support  
Packrat (modified to support left-recursion and resolve grammar ambiguity)  
Parsing Machine  
Earley  
Recursive descent + Pratt  
Packrat (modified, partial memoization)  
Hybrid recursive descent / operator precedence  
Scannerless GLR  
runtime-extensible GLR  
Scannerless, two phase  
Combinators  
Earley/combinators  
Earley/combinators, infinitary CFGs  
Scannerless GLR  
delta chain  

除了解析器生成器，还有其他算法/方法来解析。特别是，Prolog有DCG，而且大多数没有经过正式培训就从头开始编写第一个解析器的人通常都是从recursive descent开始的。还有图表解析器和左角解析器。

在编写解析器时，我总是问自己的第一个问题是如何为乔姆斯基等级中最高类型的语言制定语法。这里最低的是0型，最高的是-3型.

几乎90%的时间是类型-2语法(上下文无关文法)，而对于简单的任务，则是Type-3语法(正则文法)。我试验过1型语法(上下文敏感文法)，甚至-0型语法(无限制文法).

ANTLR自适应LL(*)算法的优点/局限性是什么？

参见特伦斯·帕尔 ( Adaptive LL(*)：)解析:动态分析的力量的创建者)撰写的论文

实际上，Adaptive LL(*)可以让您更快地从语法转换到工作的解析器，因为您不需要理解那么多的解析理论，因为我要说的是，Adaptive LL(*)足够灵活，可以绕过您在语法中不知情地设置的挖掘。这样做的代价是，您在语法中不知情地放置的一些挖掘可能会导致解析器运行时效率低下。

对于大多数实际编程语言而言，Adaptive LL(*)就足够了。IIRC Adaptive LL(*)不能执行Prolog所能做的类型-0语法(无限制文法)，但正如我所说，大多数人和最常见的编程任务只需要类型2或类型3。

另外，大多数解析器生成器都是针对类型2的，但这并不意味着它们不能执行类型1或类型0。我不能说得更具体，因为我对所有这些问题都没有实际经验。

每当您使用解析工具或库时，都会有一个学习曲线来学习如何使用它，以及它能做什么和不能做什么。

如果你对词法/解析还不熟悉，并且真的想更多地理解它，那么就选修一门课程和/或阅读编译器:原则、技术和工具(第二版)。