Parser produces different trees on separate runs

[eyadams]

I have defined a grammar. The goal is to have something where a user can specify a logical condition to be met, like foo or bar. I am testing a more complicated example, foo in [FIELD] or bar in [FIELD]. The problem I have is that about half the time the tree produced by the parser is what I expect, and about half the time it is something different.

I have created a test script, lark_test.txt that has my full grammar and just prints the results of pretty(). On three separate runs, it produced three different trees, which you can see in the file output.txt.

I'm kind of at a loss here. Any help would be appreciated.

[MegaIng]

Your grammar is ambiguous. All parse trees you are seeing are valid interpretations of the grammar. You need to make sure that there is exactly one possible parse Tree, and that that is the one you want. I would recommend using parser='lalr' which makes Lark generate errors for potential ambiguities. See the calc.py example in this repo for an example of how to structure your grammar in a non-ambiguous fashion.

@erezsh It might be interesting to have an ambiguity="error" mode for the earley parser which triggers in situations where no priorities are given and it would resolve to an arbitrary choice and make that the default mode instead of resolve: Rarely do beginners actually want ambiguies/non-determinsitc results and often this just leads to this kind of question and confusion. If one explicitly provides ambiguity="resolve", it's back to the current behavior.

[erezsh]

@MegaIng That's an interesting idea. However, I don't think there is a simple way to detect an ambiguity, without an input that produces that ambiguity. And to produce an error only on input, would be a worse default behavior.

Of course, even in LALR grammars there are some ambiguities, it's just that we are consistent in how we resolve them. I think it might prove quite tedious to write a grammar where all ambiguities have to be accounted for explicitly.

I do think the bigger problem here is if Earley isn't consistent, because ideally it should be.

@eyadams Try setting PYTHONHASHSEED to a fixed number when running the parser. Does that make the results consistent?

[MegaIng]

@erezsh I mean exactly that an error is generated for earley when an ambiguous input is being parsed and resolve would make an arbitrary decision, not based on priories. I think that should be possible, and preferably to having different executions of the same script produce different results if you don't expect that. The error message can then provide a reference that this can be avoided by setting the resolver strategy to resolve.

Even if earley were fully consistent, I don't think that would be nice behavior, because small changes in the grammar like renaming a rule can lead to unexpected cascade effects that change the parse tree if you aren't aware that there is an ambiguity.

Either way, we should probably create a central doc page to commonly asked questions about how to resolve ambiguity/inconsistent parsing in earley.

[erezsh]

@MegaIng I don't know how I feel about error being the default behavior. I would be worried about scripts that work for expected input, to suddenly throw an error when there is unexpected input, even though that error isn't necessary. But I'm willing to consider it.

I think the practical implementation will be harder than it seems, since it might be hard to distinguish between trivial ambiguity and substantial ambiguity. And throwing an error for every trivial ambiguity might end up a being a bit much. But perhaps I'm wrong!

we should probably create a central doc page

I'm all for it! I would even be happy to use part of Lark's budget towards that end.

[eyadams]

I'll go back and try to remove the ambiguity. But it's weird that the same input and same script can produce different output on different runs. If nothing else changes, shouldn't the tree always be the same?

[MegaIng]

What changes it the HASHSEED of the python environment. This means the dictionaries and sets have a different order, which leads to different behavior in the ambiguity resolving steps.

[davidmcnabnz]

I'm watching this with interest. Gotta admit it's a bit scary that parser handling on the same input in different runs can produce different outcomes.

If this was happening to me, I'd be hunting down and manually sorting out ambiguity conflicts. I am extremely reluctant to let a parser handle any production traffic if it has even just one shift/reduce or reduce/reduce conflict.