Repository: lark-parser/lark

Issue:
Inconsistent parse results from simple ambiguous grammar
**Describe the bug**

I have a small grammar that is a starting point to parse regular expressions. When run repeatedly on the same input Lark produces two different parse trees.

There is an ambiguity in my toy grammar because a RE `quantifier` (`*`, `+`, `?`) can also be interpreted as a `printable_char` (ASCII values between space and tilde). However my reading previous issues (#81, #83) indicates inconsistent parse results should be treated as a bug (and it was certainly a surprise).


**To Reproduce**

Lark 1.1.9, Python 3.10.12.

```python
#!/usr/bin/env python

from lark import Lark

parser = Lark('''
start: factor+

?factor: atom quantifier?

quantifier: "*" | "+" | "?"

?atom: DOT | printable_char

printable_char: /[ -~]/

DOT: "."
''')

regex = r'a.?'
tree = parser.parse(regex)
print(tree.pretty())
```

**Sample results**

```
start
  printable_char	a
  .
  printable_char	?
```

```
start
  printable_char	a
  factor
    .
    quantifier
```


Discussion:
codecov-commenter: :warning: Please install the !['codecov app svg image'](https://github.com/codecov/engineering-team/assets/152432831/e90313f4-9d3a-4b63-8b54-cfe14e7ec20d) to ensure uploads and comments are reliably processed by Codecov.

## [Codecov](https://app.codecov.io/gh/lark-parser/lark/pull/1435?dropdown=coverage&src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=lark-parser) Report
Attention: Patch coverage is `80.00000%` with `1 line` in your changes missing coverage. Please review.
> Project coverage is 89.77%. Comparing base [(`5016894`)](https://app.codecov.io/gh/lark-parser/lark/commit/501689455b00ff643b7901994dcb6d2a92d4412e?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=lark-parser) to head [(`99ec1fb`)](https://app.codecov.io/gh/lark-parser/lark/commit/99ec1fb01837da0fe46f0d7b820364d8552ef3d2?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=lark-parser).

| [Files](https://app.codecov.io/gh/lark-parser/lark/pull/1435?dropdown=coverage&src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=lark-parser) | Patch % | Lines |
|---|---|---|
| [lark/utils.py](https://app.codecov.io/gh/lark-parser/lark/pull/1435?src=pr&el=tree&filepath=lark%2Futils.py&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=lark-parser#diff-bGFyay91dGlscy5weQ==) | 50.00% | [1 Missing :warning: ](https://app.codecov.io/gh/lark-parser/lark/pull/1435?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=lark-parser) |

:exclamation: Your organization needs to install the [Codecov GitHub app](https://github.com/apps/codecov/installations/select_target) to enable full functionality.

<details><summary>Additional details and impacted files</summary>


```diff
@@            Coverage Diff             @@
##           master    #1435      +/-   ##
==========================================
- Coverage   89.78%   89.77%   -0.02%     
==========================================
  Files          52       52              
  Lines        7811     7813       +2     
==========================================
+ Hits         7013     7014       +1     
- Misses        798      799       +1     
```

| [Flag](https://app.codecov.io/gh/lark-parser/lark/pull/1435/flags?src=pr&el=flags&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=lark-parser) | Coverage Δ | |
|---|---|---|
| [unittests](https://app.codecov.io/gh/lark-parser/lark/pull/1435/flags?src=pr&el=flag&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=lark-parser) | `89.77% <80.00%> (-0.02%)` | :arrow_down: |

Flags with carried forward coverage won't be shown. [Click here](https://docs.codecov.io/docs/carryforward-flags?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=lark-parser#carryforward-flags-in-the-pull-request-comment) to find out more.

</details>

[:umbrella: View full report in Codecov by Sentry](https://app.codecov.io/gh/lark-parser/lark/pull/1435?dropdown=coverage&src=pr&el=continue&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=lark-parser).   
:loudspeaker: Have feedback on the report? [Share it here](https://about.codecov.io/codecov-pr-comment-feedback/?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=lark-parser).


Patch:
diff --git a/lark/parsers/grammar_analysis.py b/lark/parsers/grammar_analysis.py
index b52e50d..28d3cb6 100644
--- a/lark/parsers/grammar_analysis.py
+++ b/lark/parsers/grammar_analysis.py
@@ -3,7 +3,7 @@
 from collections import Counter, defaultdict
 from typing import List, Dict, Iterator, FrozenSet, Set
 
-from ..utils import bfs, fzset, classify
+from ..utils import bfs, fzset, classify, OrderedSet
 from ..exceptions import GrammarError
 from ..grammar import Rule, Terminal, NonTerminal, Symbol
 from ..common import ParserConf
@@ -177,13 +177,13 @@ class GrammarAnalyzer:
 
         self.FIRST, self.FOLLOW, self.NULLABLE = calculate_sets(rules)
 
-    def expand_rule(self, source_rule: NonTerminal, rules_by_origin=None) -> State:
+    def expand_rule(self, source_rule: NonTerminal, rules_by_origin=None) -> OrderedSet[RulePtr]:
         "Returns all init_ptrs accessible by rule (recursive)"
 
         if rules_by_origin is None:
             rules_by_origin = self.rules_by_origin
 
-        init_ptrs = set()
+        init_ptrs = OrderedSet[RulePtr]()
         def _expand_rule(rule: NonTerminal) -> Iterator[NonTerminal]:
             assert not rule.is_term, rule
 
@@ -200,4 +200,4 @@ class GrammarAnalyzer:
         for _ in bfs([source_rule], _expand_rule):
             pass
 
-        return fzset(init_ptrs)
+        return init_ptrs
diff --git a/lark/utils.py b/lark/utils.py
index 04d6eae..3767a66 100644
--- a/lark/utils.py
+++ b/lark/utils.py
@@ -341,3 +341,6 @@ class OrderedSet(AbstractSet[T]):
 
     def __len__(self) -> int:
         return len(self.d)
+
+    def __repr__(self):
+        return f"{type(self).__name__}({', '.join(map(repr,self))})"


Test patch:
diff --git a/tests/test_parser.py b/tests/test_parser.py
index 13124a0..5a0d405 100644
--- a/tests/test_parser.py
+++ b/tests/test_parser.py
@@ -975,6 +975,19 @@ def _make_full_earley_test(LEXER):
             tree = l.parse("")
             self.assertEqual(tree, Tree('start', [Tree('x', [])]))
 
+
+        def test_consistent_derivation_order1(self):
+            # Should return the same result for any hash-seed
+            parser = Lark('''
+                start: a a
+                a: "." | b
+                b: "."
+            ''', lexer=LEXER)
+
+            tree = parser.parse('..')
+            n = Tree('a', [Tree('b', [])])
+            assert tree == Tree('start', [n, n])
+
     _NAME = "TestFullEarley" + LEXER.capitalize()
     _TestFullEarley.__name__ = _NAME
     globals()[_NAME] = _TestFullEarley