Repository: lark-parser/lark

Issue:
Earley parser produces wrong parse Tree
Over on SO someone asked this question: https://stackoverflow.com/questions/76366280/parsing-formulas-using-lark-ebnf/76381256

As far as I can tell, it shows a bug in the earley parser where it duplicates some Tokens because of enormous amounts of ambiguities. I don't have the expertise with earley to figure out what is happening or the time to create a minimal example right now.

Discussion:

Patch:
diff --git a/lark/parsers/earley.py b/lark/parsers/earley.py
index 2153a0c..8deaa2f 100644
--- a/lark/parsers/earley.py
+++ b/lark/parsers/earley.py
@@ -300,7 +300,10 @@ class Parser:
 
         if self.Tree is not None:
             # Perform our SPPF -> AST conversion
-            transformer = ForestToParseTree(self.Tree, self.callbacks, self.forest_sum_visitor and self.forest_sum_visitor(), self.resolve_ambiguity)
+            # Disable the ForestToParseTree cache when ambiguity='resolve'
+            # to prevent a tree construction bug. See issue #1283
+            use_cache = not self.resolve_ambiguity
+            transformer = ForestToParseTree(self.Tree, self.callbacks, self.forest_sum_visitor and self.forest_sum_visitor(), self.resolve_ambiguity, use_cache)
             solutions = [transformer.transform(s) for s in solutions]
 
             if len(solutions) > 1:
diff --git a/lark/parsers/earley_forest.py b/lark/parsers/earley_forest.py
index cdc613a..c60f3a6 100644
--- a/lark/parsers/earley_forest.py
+++ b/lark/parsers/earley_forest.py
@@ -609,9 +609,10 @@ class ForestToParseTree(ForestTransformer):
                 children.append(data.left)
         if data.right is not PackedData.NO_DATA:
             children.append(data.right)
-        if node.parent.is_intermediate:
-            return self._cache.setdefault(id(node), children)
-        return self._cache.setdefault(id(node), self._call_rule_func(node, children))
+        transformed = children if node.parent.is_intermediate else self._call_rule_func(node, children)
+        if self._use_cache:
+            self._cache[id(node)] = transformed
+        return transformed
 
     def visit_symbol_node_in(self, node):
         super(ForestToParseTree, self).visit_symbol_node_in(node)


Test patch:
diff --git a/tests/test_parser.py b/tests/test_parser.py
index ee5d5a0..13124a0 100644
--- a/tests/test_parser.py
+++ b/tests/test_parser.py
@@ -954,6 +954,26 @@ def _make_full_earley_test(LEXER):
             self.assertEqual(node.start, 0)
             self.assertEqual(node.end, 3)
 
+        def test_resolve_ambiguity_with_shared_node(self):
+            grammar = """
+            start: (a+)*
+            !a.1: "A" |
+            """
+
+            l = Lark(grammar, ambiguity='resolve', lexer=LEXER)
+            tree = l.parse("A")
+            self.assertEqual(tree, Tree('start', [Tree('a', []), Tree('a', []), Tree('a', ['A'])]))
+
+        def test_resolve_ambiguity_with_shared_node2(self):
+            grammar = """
+            start: _s x _s
+            x: "X"?
+            _s: " "?
+            """
+
+            l = Lark(grammar, ambiguity='resolve', lexer=LEXER)
+            tree = l.parse("")
+            self.assertEqual(tree, Tree('start', [Tree('x', [])]))
 
     _NAME = "TestFullEarley" + LEXER.capitalize()
     _TestFullEarley.__name__ = _NAME