Repository: lark-parser/lark
Pull request #1451 (2024-08-17 05:48:52)

Earley: share nodes created by the scanner with the completer
There should only be one distinct SPPF start node now. 

When a start rule alternative ends in a terminal, the scanner creates the start `SymbolNode`, and when a start rule alternative ends in a nonterminal, the completer creates the start `SymbolNode`. The issue was that if both cases occurred, the scanner would create a start `SymbolNode`, and then the completer would also create one instead of reusing the existing node because the completer did not know the node existed. Hence, we ended up with two different start `SymbolNode`s. The issue is resolved by sharing the `node_cache` from `scan` with `predict_and_complete`.

`test_multiple_start_solutions` and `test_consistent_derivation_order1` were adjusted because the change affected the order in which derivations were produced for some grammars. The order is still consistent across executions though.

`test_cycles2` is back to having only one derivation which I believe is the correct behavior after the change.

Before the change, the SPPF was:

![sppfbefore](https://github.com/user-attachments/assets/f9c13a1d-d651-4219-baad-b408b28d5063)

Notice that the traversal that produces the "triple v" derivation contains two symbol nodes labeled `(v, 1, 2, -inf)`. The existence of two symbol nodes with the same label violates the "Shared" property of SPPFs.

After the change, the SPPF is:

![sppfafter](https://github.com/user-attachments/assets/cfdfc363-9b06-4e82-ac72-e9c9380b129c)

Now, there is only one symbol node labeled `(v, 1, 2, -inf)`. A traversal that produces the 'triple v" derivation still exists, but requires traversing the cycle through `(v, 1, 2, -inf)` which we don't do.


Patch:
diff --git a/lark/parsers/earley.py b/lark/parsers/earley.py
index d173129..d09732e 100644
--- a/lark/parsers/earley.py
+++ b/lark/parsers/earley.py
@@ -75,7 +75,7 @@ class Parser:
         self.term_matcher = term_matcher
 
 
-    def predict_and_complete(self, i, to_scan, columns, transitives):
+    def predict_and_complete(self, i, to_scan, columns, transitives, node_cache):
         """The core Earley Predictor and Completer.
 
         At each stage of the input, we handling any completed items (things
@@ -84,7 +84,6 @@ class Parser:
         non-terminals are recursively processed until we reach a set of,
         which can be added to the scan list for the next scanner cycle."""
         # Held Completions (H in E.Scotts paper).
-        node_cache = {}
         held_completions = {}
 
         column = columns[i]
@@ -203,7 +202,7 @@ class Parser:
             for item in self.Set(to_scan):
                 if match(item.expect, token):
                     new_item = item.advance()
-                    label = (new_item.s, new_item.start, i)
+                    label = (new_item.s, new_item.start, i + 1)
                     # 'terminals' may not contain token.type when using %declare
                     # Additionally, token is not always a Token
                     # For example, it can be a Tree when using TreeMatcher
@@ -227,7 +226,7 @@ class Parser:
                 expect = {i.expect.name for i in to_scan}
                 raise UnexpectedToken(token, expect, considered_rules=set(to_scan), state=frozenset(i.s for i in to_scan))
 
-            return next_to_scan
+            return next_to_scan, node_cache
 
 
         # Define parser functions
@@ -245,16 +244,17 @@ class Parser:
         # step.
         expects = {i.expect for i in to_scan}
         i = 0
+        node_cache = {}
         for token in lexer.lex(expects):
-            self.predict_and_complete(i, to_scan, columns, transitives)
+            self.predict_and_complete(i, to_scan, columns, transitives, node_cache)
 
-            to_scan = scan(i, token, to_scan)
+            to_scan, node_cache = scan(i, token, to_scan)
             i += 1
 
             expects.clear()
             expects |= {i.expect for i in to_scan}
 
-        self.predict_and_complete(i, to_scan, columns, transitives)
+        self.predict_and_complete(i, to_scan, columns, transitives, node_cache)
 
         ## Column is now the final column in the parse.
         assert i == len(columns)-1
@@ -294,9 +294,10 @@ class Parser:
             except ImportError:
                 logger.warning("Cannot find dependency 'pydot', will not generate sppf debug image")
             else:
-                for i, s in enumerate(solutions):
-                    debug_walker.visit(s, f"sppf{i}.png")
+                debug_walker.visit(solutions[0], "sppf.png")
 
+        if len(solutions) > 1:
+            assert False, 'Earley should not generate multiple start symbol items!'
 
         if self.Tree is not None:
             # Perform our SPPF -> AST conversion
@@ -304,14 +305,7 @@ class Parser:
             # 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 and not self.resolve_ambiguity:
-                t: Tree = self.Tree('_ambig', solutions)
-                t.expand_kids_by_data('_ambig')     # solutions may themselves be _ambig nodes
-                return t
-            return solutions[0]
+            return transformer.transform(solutions[0])
 
         # return the root of the SPPF
-        # TODO return a list of solutions, or join them together somehow
         return solutions[0]
diff --git a/lark/parsers/xearley.py b/lark/parsers/xearley.py
index a0f43ac..13d592d 100644
--- a/lark/parsers/xearley.py
+++ b/lark/parsers/xearley.py
@@ -127,7 +127,7 @@ class Parser(BaseParser):
                                            considered_rules=considered_rules
                                            )
 
-            return next_to_scan
+            return next_to_scan, node_cache
 
 
         delayed_matches = defaultdict(list)
@@ -146,10 +146,11 @@ class Parser(BaseParser):
         # processed down to terminals/empty nodes to be added to the scanner for the next
         # step.
         i = 0
+        node_cache = {}
         for token in stream:
-            self.predict_and_complete(i, to_scan, columns, transitives)
+            self.predict_and_complete(i, to_scan, columns, transitives, node_cache)
 
-            to_scan = scan(i, to_scan)
+            to_scan, node_cache = scan(i, to_scan)
 
             if token == '\n':
                 text_line += 1
@@ -158,7 +159,7 @@ class Parser(BaseParser):
                 text_column += 1
             i += 1
 
-        self.predict_and_complete(i, to_scan, columns, transitives)
+        self.predict_and_complete(i, to_scan, columns, transitives, node_cache)
 
         ## Column is now the final column in the parse.
         assert i == len(columns)-1


Test patch:
diff --git a/tests/test_parser.py b/tests/test_parser.py
index 59e9a71..9829071 100644
--- a/tests/test_parser.py
+++ b/tests/test_parser.py
@@ -836,14 +836,14 @@ def _make_full_earley_test(LEXER):
             tree = l.parse('x')
 
             expected = Tree('_ambig', [
+                Tree('start', [Tree('a', ['x'])]),
                 Tree('start', ['x']),
-                Tree('start', [Tree('a', ['x'])])]
-            )
+            ])
             self.assertEqual(tree, expected)
 
             l = Lark(grammar, ambiguity='resolve', lexer=LEXER)
             tree = l.parse('x')
-            assert tree == Tree('start', ['x'])
+            assert tree == Tree('start', [Tree('a', ['x'])])
 
 
         def test_cycle(self):
@@ -872,10 +872,7 @@ def _make_full_earley_test(LEXER):
             tree = l.parse("ab")
             expected = (
                 Tree('start', [
-                    Tree('_ambig', [
-                        Tree('v', [Tree('v', [])]),
-                        Tree('v', [Tree('v', [Tree('v', [])])])
-                    ])
+                    Tree('v', [Tree('v', [])]),
                 ])
             )
             self.assertEqual(tree, expected)
@@ -990,7 +987,7 @@ def _make_full_earley_test(LEXER):
             ''', lexer=LEXER)
 
             tree = parser.parse('..')
-            n = Tree('a', [Tree('b', [])])
+            n = Tree('a', [])
             assert tree == Tree('start', [n, n])
 
     _NAME = "TestFullEarley" + LEXER.capitalize()