LR vs LL
Parser users tend to separate themselves into bottom-up and top-down tribes. Top-down users value the readability of recursive descent (
RD) implementations of LL parsing along with the ease of semantic action incorporation. Bottom-up users value the extended parsing power of LR parsers, in particular the admissibility of left recursive grammars, although LR parsers cannot cope with hidden left recursion and even LR(0) parse tables can be exponential in the size of the grammar, while an LL parser is linear in the size of the grammar. Both tribes suffer from the need to coerce their grammars into forms which are deterministic, or at least near-deterministic for their chosen parsing technology.
But
On the other hand there are algorithms, which do not fit in one bucket:
- An LLLR parser uses an LL parser as its backbone and parses as much of its input string using LL parsing as possible. To resolve LL conflicts it triggers small embedded LR parsers.
- Earley parser may be converted from top-down memoized recursive form into bottom-up dynamic programming form.
A chart parser is a type of parser suited to parsing ambiguous grammars. Chart parsers avoid exponential blowup in parsing time arising from the nondeterminism of a grammar by reducing duplication of work through the use of memoization. Top-down chart parsers (such as packrat parsers) use memoized recursion, whereas bottom-up chart parsers more specifically use Dynamic programming. The Earley parser is a top-down chart parser, and is mainly used for parsing natural language in computational linguistics. It can parse any context-free grammar, including left-recursive grammars. The
Earleyparser executes in cubic time in the general case, quadratic time for unambiguous grammars, and linear time for all LR(k) grammars… TheEarleyparser may be converted from top-down memoized recursive form into bottom-up dynamic programming form. Parsing with pictures is a chart parsing algorithm that provides an alternative approach to parsing context-free languages. The authors claim that this method is simpler and easier to understand than standard parsers using derivations or pushdown automata. This parsing method unifiesEarley,SLL, LL, SLR: Simple LR, and LR parsers, and demonstrates thatEarleyparsing is the most fundamental Chomskyan context-free parsing algorithm, from which all others derive.