Lark: priorities in LALR and Earley

[PJCampi]

Hey,

Is it correctly understood that priority can be set on rules only for earley and on terminals only for lalr?

I expected to be able to switch seamlessly between the two algorigthms for my unambiguous and non-recursive grammar but I get a lot of parsing errors when switching from earley to larl. I think that most of them are due to priorities on rules not understood by lalr.

Also btw there may be some inconsistency in the index of priority between the two algorithm.

This grammar parses '1' to b with earley:

%import common.INT

start: a | b

a: INT
b.1: INT

while it resolves to A with lalr:

%import common.INT

start: A | B

A: INT
B.1: INT

One has to increment to B.2 to get the grammar to parse '1' to B.

[erezsh]

Yes, there is a difference in how the two algorithms handle priority. It's not impossible to fix, it's just a lot of work.

Regarding your example, B.1 is the same as B, because 1 is the default priority. So yeah, you need to use B.2 or higher.

This is the same for Earley. The reason Earley resolves this as a, is because when priorities are even (that is, both 1), it determines according to the order of appearance. In this case, a before b.

[PJCampi]

Ok thanks for the info.

Note however that earley resolves to b if both priorities are equal, not a. That's why I believed that the index of a rule without priority was 0.

[night199uk]

That's odd. The logic for the Earley prioritisation is done through the sort_key function on PackedNode. Essentially, each ambiguity in an ambiguous derivation is held under a PackedNode child of the SymbolNode or IntermediateNode. I don't have time to dig in right now, but here are some breadcrumbs for anyone troubleshooting:

The PackedNode children of a SymbolNode are sorted before returning them:

    @property
    def children(self):
        return sorted(self._children, key=attrgetter('sort_key'))

sort_key on PackedNode is this:

    @property
    def sort_key(self):
        """
        Used to sort PackedNode children of SymbolNodes.
        A SymbolNode has multiple PackedNodes if it matched
        ambiguously. Hence, we use the sort order to identify
        the order in which ambiguous children should be considered.
        """
        return self.is_empty, -self.priority, -self.rule.order

The default priority is -inf, and self.rule.order is the ordering of children of the rule (in this case a = 1, b = 2, I think).
Hence, in your case a = 1, b = 2. So the sort key is:
a: False, inf, -1
b: False, inf, -2

So a should sort before b; and be returned.
In a pinch, you could add some debug to these two functions to see if the sort_keys are working correctly and identify any discrepancies. It may be I overlooked something in the logic here.

[night199uk]

Another thing that would be very useful is to hook up the ForestToPyDotVisitor to dump out the resulting Forest. I can't remember how I'd left it hooked up now; but if you dump out the Forest to a graph it should be much easier to see why b is sorting before a.

[night199uk]

After a very quick look, I suspect rule.order is not being set deterministically in load_grammar for some reason. I don't have time to test right now, but my immediate suspicion is that line 523 of load_grammar.py is leaking the variable i in Python 2.7, overlapping with the enumerated i in the same context. This would work in Py3 I think where list comprehension variables are not leaked, IIRC.

        for i, rule_content in enumerate(rules):
...
                empty_indices = [x==_EMPTY for i, x in enumerate(expansion)]

That's probably an issue anyway, but it might not be the only one.

[erezsh]

@night199uk If it overwrote i, that would cause a deterministic error. Anyway, I fixed that line, and the non-determinism persists.

[bilderbuchi]

Is it correctly understood that priority can be set on rules only for earley and on terminals only for lalr?

If this is the case, and a feature rectifying this is not on the horizon, could I ask that the documentation for priorities be clarified/amended (also adding the default priority)?
This kinda surprised me, also because when using lalr, there is no error or warning when using priorites in rules.

[night199uk]

Should be fixed by #428 .

[erezsh]

@night199uk Wouldn't we expect Earley to choose a in the case of no priority? (since it's a | b)

In this case it seems that

            rule = Rule(NonTerminal(name), expansion, -i, alias, exp_options)

Produces the correct result

[PJCampi]

Great news 👍 Thanks guys!
The code merged to master does not resolve my example correctly. However it does if -i instead of i as suggested by Erez.

[night199uk]

Oh. Let me double-check. But I wouldn’t fix this there. I’d fix this in PackedNode.sort_key; but inverting rule.order there instead; as we already do for priority - it’s more intuitive to keep rule.order positive until the last minute for debugging. Let me see if I can PR.

[erezsh]

Yes, of course.

[erezsh]

Should be all fixed in master! Feel free to re-open if an issue persists.