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

Question

我正在学习ANTLR v4,它是一个基于所谓的自适应LL(*)算法的解析器生成器.它声称是对LL(*)算法的重大改进.但我也听说过像LR这样的算法.

因此,出于好奇而得到一个大局:

• 有多少现代算法可以构建解析器？
• 什么是ANTLR自适应LL(*)算法的优势/局限？

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.此外图表解析器和左角解析器.

在编写解析器时,我总是问自己的第一个问题是如何在Chomsky层次结构中为最高类型的语言编写语法.这里最低的是Type-0,最高的是Type-3.

几乎90%的时候它是Type-2语法(无上下文语法),然后对于easer任务,它是Type-3语法(常规语法).我已经尝试了Type-1语法(上下文相关语法)甚至Type-0语法(不受限制的语法).

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

看到写在纸上泰伦斯帕尔的创造者Adaptive LL(*): 自适应LL(*)解析:动态分析的力量

实际上Adaptive LL(*),你可以更快地从一个语法到一个工作的解析器,因为你不必理解那么多的解析理论,因为Adaptive LL(*)我可以说,它足够灵活,可以在你不知不觉中放入语法中.这样做的代价是,您在语法中不知不觉中放置的某些地雷会导致解析器运行时效率低下.

对于大多数实用的编程语言来说Adaptive LL(*)已经足够 IIRC Adaptive LL(*)不能做Prolog DCG可以做的Type-0语法(不受限制的语法),但正如我所说,大多数人和最常见的编程任务只需要类型2或类型3.

大多数解析器生成器也适用于类型2,但这并不意味着它们不能执行类型1或可能类型0.我不能更具体,因为我没有所有这些的实际经验.

无论何时使用解析工具或库,都有学习如何使用它以及它能做什么和不能做什么的学习曲线.

如果您是lexing/parsing的新手,并且真的想更多地了解它,那么请参加课程和/或阅读编译器:原理,技术和工具(第2版)