search

kach / nearley

📜🔜🌲 Simple, fast, powerful parser toolkit for JavaScript.
https://nearley.js.org
MIT License
3.57k stars 232 forks source link

Infinite loop #240

Open joshyrobot opened 7 years ago

joshyrobot commented 7 years ago

Possibly related to #167, the following grammar brings nearley to an infinite loop with any input. This code is very simplified, but in larger grammars this can go unnoticed and cause a lot of headaches.

main -> err:*
err -> null

After being simplified, it is pretty obvious that it would go into an infinite loop, because this can match infinitely many times. I'm not sure if a fix is even possible, but might as well report it.

System info: Node version: v7.10.0 npm version: 4.6.1 yarn version: 0.24.6 nearley version: 2.9.2

kach commented 7 years ago

Thanks — this is, indeed, a manifestation of #167. Looking back, perhaps a bit of static analysis is what we need here, to tell the user when they have a "bogus" grammar (as Loup does in http://loup-vaillant.fr/tutorials/earley-parsing/parser). @tjvr, what do you think?

tjvr commented 7 years ago

If we can do this using static analysis at compile-time, that'd be great :-)

Let's resolve #167 as a duplicate of this...