Collision using LALR

[shewitt-au]

I'm using the LALR parser and I'm getting a problem. This has been discussed in more complex cases, but I must admit I never understood the explanation or how to apply solution to my case, or, for that matter, to decipher the error message. Here's is the problem reduced to the simplest I could make it:

start: one | many
one: LETTER
many: LETTER*

LETTER: /[a-z]/ 

And the error:

lark.exceptions.GrammarError: Collision in Terminal('$END'): 
  * Reduce: <NonTerminal('__anon_star_0') : Terminal('LETTER')>, 
  * Reduce: <NonTerminal('one') : Terminal('LETTER')>

I could get this to work, but without understanding the issue even in a simple case like this I don't have a hope of fixing it in my real parser.

This seems something very simple not to work.

[erezsh]

Imagine you built the parser without an error, and then wrote parse('a'). What parse-tree would you expect as the output? More specifically, which rule do you expect the parser to match?

Well, turns out, both one and many would be "correct" derivations. But, LALR is a strictly deterministic algorithm, and it refuses to make a guess when faced with ambiguity. Instead, it throws an error.

So you have two options:

1) Change the grammar, so that there's only one correct path to take for each input.

2) Use Earley, which will happily accept ambiguous grammars.

I hope that helps.

[shewitt-au]

Thanks for you patience. After I submitted this I read some parser theory and I now understand the issue, I should have done that first. I did get my parser to work with LALR and it exceeded my expectations and then some speed-wise; it blew my current ANTLR4 (Python 3 target) parser out of the water.

[erezsh]

Yep, LALR is the best. It should be more popular, maybe Lark will help that happen.