Re:Parsing in JavaScript: all the tools and libraries you ca...
by matheusmoreira on Monday May 24, 2021 @02:06PM
(#27267692)
Nearley is amazing. The best implementation of the Earley algorithm I know. It's a great algorithm because you can use any context-free grammar as input and it doesn't require code generation. It's the perfect algorithm for a parse(grammar, input) standard library function.
As far as I know, Nearley implements all optimizations published in the literature. Worst case time complexity is cubic for ambiguous grammars, quadratic for unambiguous grammars and linear for grammars suitable for deterministic algorithms. Performance is still going to be worse than constrained parsers that can handle only a subset of context-free grammars such as deterministic LL(1) parsers. Here's what the Parsing Techniques book says:
> If one has the luxury of being in a position to design the grammar oneself, the choice is simple:
> design the grammar to be LL(1) and use a predictive recursive descent parser.
> This can be summarized as: parsing is a problem only if someone else is in charge of the grammar.
As far as I know, Nearley implements all optimizations published in the literature. Worst case time complexity is cubic for ambiguous grammars, quadratic for unambiguous grammars and linear for grammars suitable for deterministic algorithms. Performance is still going to be worse than constrained parsers that can handle only a subset of context-free grammars such as deterministic LL(1) parsers. Here's what the Parsing Techniques book says:
> If one has the luxury of being in a position to design the grammar oneself, the choice is simple:
> design the grammar to be LL(1) and use a predictive recursive descent parser.
> This can be summarized as: parsing is a problem only if someone else is in charge of the grammar.