Some grammars can throw the CYK parser into an infinite loop

[erezsh]

Not likely to happen naturally, but possible.

For example:

parser = lark.Lark("start: a\na: b\n b:c\n c:a\n | /a/")
parser.parse('a')

Throws all parsers into an infinite loop (the cyk parser already enters an infinite loop on the first line)

Possible solution: Detect infinite loops in grammar, and throw an exception.

[SarthakDandriyal]

Hey I would like to work on this issue.

[erezsh]

Great, be my guest.

Earley doesn't enter a loop anymore in recent versions.

The only thing left to fix is the cyk parser.

[SarthakDandriyal]

I would like to work on that can you guide me more about the cyk parser .

[erezsh]

What kind of guidance do you need?

The code of the cyk parser is here: https://github.com/lark-parser/lark/blob/master/lark/parsers/cyk.py

You should figure out which line is causing the infinite loop, and take it from there.

[SarthakDandriyal]

Thank you I will work on it.

[SarthakDandriyal]

hey @erezsh can you give me some test cases for the cyk parser.

[erezsh]

What do you mean?

Did you see this page? https://lark-parser.readthedocs.io/en/latest/how_to_develop/