Add support for LR parsingleft_recursion_support

* first draft of LR parsing
* removed debug output
* cache is owned and cleared by ParserElement
* bounded recursion must be enabled explicitly
* packrat rejects recursion
* basic LR unit test
* tests for associativity and nesting
* added math example
* fixed test typo
* unittest for empty and non-peg clauses
* LR-Forward can match Empty
* fixed test typos
* added base case to unittest
* memo cache only provides copies
* flattened Forward parse method
* added high-level description of algorithm
* expanded docstring
* added tests for repetition rules
* renamed bounded to left recursion
* naive test for existing suite
* explicitly testing tests for LR compatibility
* LR memo no longer mixes action/no-action results
* simplified replacement logic
* adjusted example with ambiguous failure case
* LR memo content is always returned as copy
* draft for peeking recursion
* memo update consistent for all actions
* fixed a bug for non-string token identifiers
* action wins against no-action
* cleanup
* properly setting names in tests
* memoization can be turned off
* testing memo switches
* typos
* flattened recursion memo
* left recursion memo size may be limited
* adjusted docs for recursion cache

1 files changed, 46 insertions, 0 deletions

diff --git a/pyparsing/util.py b/pyparsing/util.py
index 3cb69d2..875799d 100644
--- a/pyparsing/util.py
+++ b/pyparsing/util.py
@@ -119,6 +119,52 @@ class _FifoCache:
         self.clear = types.MethodType(clear, self)
 
 
+class LRUMemo:
+    """
+    A memoizing mapping that retains `capacity` deleted items
+
+    The memo tracks retained items by their access order; once `capacity` items
+    are retained, the least recently used item is discarded.
+    """
+    def __init__(self, capacity):
+        self._capacity = capacity
+        self._active = {}
+        self._memory = collections.OrderedDict()
+
+    def __getitem__(self, key):
+        try:
+            return self._active[key]
+        except KeyError:
+            self._memory.move_to_end(key)
+            return self._memory[key]
+
+    def __setitem__(self, key, value):
+        self._memory.pop(key, None)
+        self._active[key] = value
+
+    def __delitem__(self, key):
+        try:
+            value = self._active.pop(key)
+        except KeyError:
+            pass
+        else:
+            while len(self._memory) >= self._capacity:
+                self._memory.popitem(last=False)
+            self._memory[key] = value
+
+    def clear(self):
+        self._active.clear()
+        self._memory.clear()
+
+
+class UnboundedMemo(dict):
+    """
+    A memoizing mapping that retains all deleted items
+    """
+    def __delitem__(self, key):
+        pass
+
+
 def _escapeRegexRangeChars(s):
     # escape these chars: ^-[]
     for c in r"\^-[]":