Infinite loop (or similar) in parser

[boxed]

The following code will make parsley take 100% CPU and slowly growing in memory for a long long time. This is an incorrect grammar because the rule "output" is referencing "one" directly AND indirectly via the rule "number". It would be better if parsley detected this and threw a helpful error.

from parsley import makeGrammar, termMaker
from itertools import chain

x = makeGrammar("""
one = '1'
two = '2'
number = (one | two)*
output = (number | one)*
""", {})
print x("1122121").output()

[washort]

yep, using a rule that can match the empty string inside a star expression will do that.

more succinctly:

output = ('1'*)*

[boxed]

Shouldn't this be caught? I mean, isn't part of the point of parsley to have nice error messages... an infinite loop isn't very nice.

[washort]

That'd be nice. There's probably even a way to detect some cases of this statically.

[johtso]

This also causes an infinite loop: ('foo'?)*

[washort]

Yes. Repeating any rule that will match an empty string will loop forever.

[SuperDoxin]

so wouldn't it be possible to check a rule to see if it matches the empty string before building it into a star expression? seems like a relatively cheap operation which'd prevent a common error.