Repository: neogeny/TatSu

Issue:
Another left recursion problem
Grammar:
```
identifier = /\w+/ ;
expr = mul | identifier ;
mul = expr '*' identifier ;
```

Parsing `a * b` with the start rule `expr` gives the expected result: `['a', '*', 'b']`. But parsing with the start rule `mul` gives the following error:
```
Traceback (most recent call last):
  File "/home/manu/vcs/TatSu/tatsu/contexts.py", line 203, in parse
    result = rule()
  File "/home/manu/vcs/TatSu/tatsu/contexts.py", line 54, in wrapper
    return self._call(ruleinfo)
  File "/home/manu/vcs/TatSu/tatsu/contexts.py", line 513, in _call
    result = self._recursive_call(ruleinfo)
  File "/home/manu/vcs/TatSu/tatsu/contexts.py", line 546, in _recursive_call
    result = self._invoke_rule(ruleinfo, pos, key)
  File "/home/manu/vcs/TatSu/tatsu/contexts.py", line 580, in _invoke_rule
    ruleinfo.impl(self)
  File "parser.py", line 96, in _mul_
    self._token('*')
  File "/home/manu/vcs/TatSu/tatsu/contexts.py", line 617, in _token
    self._error(token, exclass=FailedToken)
  File "/home/manu/vcs/TatSu/tatsu/contexts.py", line 436, in _error
    raise self._make_exception(item, exclass=exclass)
tatsu.exceptions.FailedToken: /proc/self/fd/12(1:1) expecting '*' :

^
mul

During handling of the above exception, another exception occurred:

Traceback (most recent call last):
  File "parser.py", line 122, in <module>
    ast = generic_main(main, UnknownParser, name='Unknown')
  File "/home/manu/vcs/TatSu/tatsu/util.py", line 335, in generic_main
    colorize=args.color
  File "parser.py", line 115, in main
    return parser.parse(text, startrule, filename=filename, **kwargs)
  File "/home/manu/vcs/TatSu/tatsu/contexts.py", line 211, in parse
    raise self._furthest_exception
  File "/home/manu/vcs/TatSu/tatsu/contexts.py", line 679, in _option
    yield
  File "parser.py", line 88, in _expr_
    self._mul_()
  File "/home/manu/vcs/TatSu/tatsu/contexts.py", line 54, in wrapper
    return self._call(ruleinfo)
  File "/home/manu/vcs/TatSu/tatsu/contexts.py", line 513, in _call
    result = self._recursive_call(ruleinfo)
  File "/home/manu/vcs/TatSu/tatsu/contexts.py", line 546, in _recursive_call
    result = self._invoke_rule(ruleinfo, pos, key)
  File "/home/manu/vcs/TatSu/tatsu/contexts.py", line 580, in _invoke_rule
    ruleinfo.impl(self)
  File "parser.py", line 96, in _mul_
    self._token('*')
  File "/home/manu/vcs/TatSu/tatsu/contexts.py", line 617, in _token
    self._error(token, exclass=FailedToken)
  File "/home/manu/vcs/TatSu/tatsu/contexts.py", line 436, in _error
    raise self._make_exception(item, exclass=exclass)
tatsu.exceptions.FailedToken: /proc/self/fd/12(1:1) expecting '*' :

^
mul
expr
mul
```

Discussion:

Patch:
diff --git a/docs/left_recursion.rst b/docs/left_recursion.rst
index 615a5d1..8b16e61 100644
--- a/docs/left_recursion.rst
+++ b/docs/left_recursion.rst
@@ -16,3 +16,30 @@ Left recursion support is enabled by default in |TatSu|. To disable it for a par
 
     @@left_recursion :: False
 
+
+.. warning::
+
+    Not all left-recursive grammars that use the |TatSu| syntax are PEG_. The same happens with right-recursive grammars.  **The order of rules in matters in PEG**.
+
+    For right-recursive grammars the choices that parse the most input must come first. The same is true  for left-recursive grammars.
+
+    Additionally, for grammars with **indirect left recursion, the rules containing choices must be the first invoked during a parse**. The following grammar is correct,but it will not work if the start rule is changed to ```start = mul ;```.
+
+    .. code:: ocaml
+
+            start = expr ;
+
+            expr
+                =
+                mul | identifier
+                ;
+
+            mul
+                =
+                expr '*' identifier
+                ;
+
+            identifier
+                =
+                /\w+/
+                ;
diff --git a/tatsu/contexts.py b/tatsu/contexts.py
index c5dfa78..2a35c4a 100644
--- a/tatsu/contexts.py
+++ b/tatsu/contexts.py
@@ -330,7 +330,6 @@ class ParseContext(object):
             prune_dict(cache, lambda k, _: k[0] < cutpos)
 
         prune(self._memos, self._pos)
-        prune(self._results, self._pos)
 
     def _memoization(self):
         return self.memoize_lookaheads or self._lookahead == 0
@@ -464,7 +463,6 @@ class ParseContext(object):
 
     def _forget(self, key):
         self._memos.pop(key, None)
-        self._results.pop(key, None)
 
     def _memo_for(self, key):
         memo = self._memos.get(key)


Test patch:
diff --git a/test/grammar/left_recursion_test.py b/test/grammar/left_recursion_test.py
index 0dced21..1290c3e 100644
--- a/test/grammar/left_recursion_test.py
+++ b/test/grammar/left_recursion_test.py
@@ -309,3 +309,46 @@ class LeftRecursionTests(unittest.TestCase):
 
         ast = model.parse('foo, bar', trace=trace, colorize=True)
         self.assertEqual(['foo', ',', 'bar'], ast)
+
+    def test_change_start_rule(self, trace=False):
+        grammar = '''
+            start = expr ;
+        
+            expr 
+                = 
+                mul | identifier 
+                ;
+                
+            mul 
+                = 
+                expr '*' identifier 
+                ;
+                
+            identifier 
+                = 
+                /\w+/ 
+                ;
+        '''
+        model = compile(grammar)
+
+        ast = model.parse('a * b', start='expr', trace=trace, colorize=True)
+        self.assertEqual(['a', '*', 'b'], ast)
+
+        try:
+            model.parse('a * b', start='mul', trace=trace, colorize=True)
+            self.fail('failure expected as first recursive rule does not cotain a choice')
+        except FailedParse:
+            pass
+
+    def test_with_gather(self, trace=False):
+        grammar = '''
+            identifier = /\w+/ ;
+            expr = mul | tmp ;
+            mul = expr '*' tmp ;
+            tmp = call | identifier ;
+            call = identifier '(' ','.{expr} ')' ;
+        '''
+        model = compile(grammar)
+
+        ast = model.parse('a(b, c)', start='expr', trace=trace, colorize=True)
+        self.assertEqual(['a', '(', ['b', 'c'], ')'], ast)