goldset

One function

AmbiguousExpander in lark-parser/lark

The author described this change as “Fix AmbiguousExpander (Issue #1214)”. It counts as a record because the check below fails on the code as it stood at 7ef5c98d1 and passes on a2f914e01, with nothing else changed between the two runs.

Projectlark-parser/lark
Fix saved2022-11-20
Sharing licenceMIT · LICENSE
Change size+3 −3

What the code was meant to do, written into the code itself as a docstring

Deal with the case where we're expanding children ('_rule') into a parent but the children are ambiguous. i.e. (parent->_ambig->_expand_this_rule). In this case, make the parent itself ambiguous with as many copies as their are ambiguous children, and then copy the ambiguous children into the right parents in the right places, essentially shifting the ambiguity up the tree.

The change

11 class AmbiguousExpander:
22 """Deal with the case where we're expanding children ('_rule') into a parent but the children
33 are ambiguous. i.e. (parent->_ambig->_expand_this_rule). In this case, make the parent itself
4- ambiguous with as many copies as their are ambiguous children, and then copy the ambiguous children
4+ ambiguous with as many copies as there are ambiguous children, and then copy the ambiguous children
55 into the right parents in the right places, essentially shifting the ambiguity up the tree."""
66 def __init__(self, to_expand, tree_class, node_builder):
77 self.node_builder = node_builder
⋯
2727 if not ambiguous:
2828 return self.node_builder(children)
2929
30- expand = [iter(child.children) if i in ambiguous else repeat(child) for i, child in enumerate(children)]
31- return self.tree_class('_ambig', [self.node_builder(list(f[0])) for f in product(zip(*expand))])
30+ expand = [child.children if i in ambiguous else (child,) for i, child in enumerate(children)]
31+ return self.tree_class('_ambig', [self.node_builder(list(f)) for f in product(*expand)])

The check that tells the two apart

fail→pass·tests/test_parser.py::TestFullEarleyDynamic::test_ambiguous_inlined_rule

Check file tests/test_parser.py, taken without changes from the fix and copied onto the older code, so the exact same check runs against both versions.

Origin and history

The fixa2f914e01d215d77481e6ef873eaea6a86fd9f5f
The code before it7ef5c98d10638dbeaf038aef8bf86cc278a9f45a
Broken version dated2022-11-02
Modulelark.parse_tree_builder
Units changedAmbiguousExpander
Fingerprinte09559ce2bc64e76
Checked2026-08-18 by goldset/0.1

Every field above is generated by our program. None of it is written by hand.

Other bugs found in lark-parser/lark