3 ms·

Anyone have experience with Nearley? I recently did some reading on JS parsers and ended up feeling like it was easier to use than most of the others where you

by dahart 5y ago

Anyone have experience with Nearley? I recently did some reading on JS parsers and ended up feeling like it was easier to use than most of the others where you have to pay attention to and know some tricks for handling recursive grammar rules. What I don't have a sense for yet is what the downsides of Nearley might be down the road once my grammar gets bigger and/or goes into production, if the performance issues might pop up suddenly and be hard to fix.

inbx0 5y ago
I've done a little toy language implementation with Nearley and really enjoyed it. If you have some JS experience under your belt, Nearley should be pretty easy to pick up and I felt it was easy to build on top of the basic building blocks. It's almost too easy to drop into custom JS with Nearley's inline JS syntax, so you can do all sorts of stuff with JS regexes or what not if you can't find a built-in feature that would do what you want. Unfortunately my project was not big enough that I'd be able to say anything about performace in scale, though. Being JS based has the advantage that you can (depending on your application needs) sometimes move some of that workload to the client :)
matheusmoreira 5y ago
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.

by dahart 5y ago

inbx0 5y ago

I've done a little toy language implementation with Nearley and really enjoyed it. If you have some JS experience under your belt, Nearley should be pretty easy to pick up and I felt it was easy to build on top of the basic building blocks. It's almost too easy to drop into custom JS with Nearley's inline JS syntax, so you can do all sorts of stuff with JS regexes or what not if you can't find a built-in feature that would do what you want. Unfortunately my project was not big enough that I'd be able to say anything about performace in scale, though. Being JS based has the advantage that you can (depending on your application needs) sometimes move some of that workload to the client :)

matheusmoreira 5y ago

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.