Hang / infinite loop on some patterns

BenjaminSchaaf / sbnf

A BNF-style language for writing sublime-syntax files

MIT License

58 stars 6 forks source link

Hang / infinite loop on some patterns #15

Closed mitranim closed 1 year ago

mitranim commented 3 years ago

Any of the following malformed definitions cause SBNF to hang forever:

main = (parens|braces)*;
parens = `(` main* `(`;
braces = `{` main* `}`;

main = (parens|braces)*;
parens = `(` main* `)`;
braces = `{` main* `{`;

I tried to narrow it down more, but ran out of ideas for now.

nuchi commented 2 years ago

This is also left recursion. It's because main is already a repetition (main : something*) and then you're writing main*. Replacing main* with main will give an equivalent grammar that doesn't have this problem.

BenjaminSchaaf commented 1 year ago

Closing in favor of #16.