Source Code for Module lepl.matchers.memo

  1   
  2  # The contents of this file are subject to the Mozilla Public License 
  3  # (MPL) Version 1.1 (the "License"); you may not use this file except 
  4  # in compliance with the License. You may obtain a copy of the License 
  5  # at http://www.mozilla.org/MPL/ 
  6  # 
  7  # Software distributed under the License is distributed on an "AS IS" 
  8  # basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See 
  9  # the License for the specific language governing rights and 
 10  # limitations under the License. 
 11  # 
 12  # The Original Code is LEPL (http://www.acooke.org/lepl) 
 13  # The Initial Developer of the Original Code is Andrew Cooke. 
 14  # Portions created by the Initial Developer are Copyright (C) 2009-2010 
 15  # Andrew Cooke (andrew@acooke.org). All Rights Reserved. 
 16  # 
 17  # Alternatively, the contents of this file may be used under the terms 
 18  # of the LGPL license (the GNU Lesser General Public License, 
 19  # http://www.gnu.org/licenses/lgpl.html), in which case the provisions 
 20  # of the LGPL License are applicable instead of those above. 
 21  # 
 22  # If you wish to allow use of your version of this file only under the 
 23  # terms of the LGPL License and not to allow others to use your version 
 24  # of this file under the MPL, indicate your decision by deleting the 
 25  # provisions above and replace them with the notice and other provisions 
 26  # required by the LGPL License.  If you do not delete the provisions 
 27  # above, a recipient may use your version of this file under either the 
 28  # MPL or the LGPL License. 
 29   
 30  ''' 
 31  Memoisation (both as described by Norvig 1991, giving Packrat  
 32  parsers for non-left recursive grammars, and the equivalent described by 
 33  Frost and Hafiz 2006 which allows left-recursive grammars to be used). 
 34    
 35  Note that neither paper describes the extension to backtracking with 
 36  generators implemented here.  
 37  ''' 
 38   
 39  from itertools import count 
 40   
 41  from lepl.matchers.core import OperatorMatcher 
 42  from lepl.matchers.matcher import is_child 
 43  from lepl.matchers.support import NoMemo 
 44  from lepl.core.parser import tagged 
 45  from lepl.stream.core import s_key, s_len 
 46  from lepl.support.state import State 
 47   
 48   
 49  # pylint: disable-msg=R0901, R0904 
 50  # lepl conventions 
 51   
 52   
 53 -class MemoException(Exception): 
 54      ''' 
 55      Exception raised for problems with memoisation. 
 56      ''' 
 57       
 58 -def RMemo(matcher): 
 59      ''' 
 60      Wrap in the _RMemo cache if required. 
 61      ''' 
 62      if is_child(matcher, NoMemo, fail=False): 
 63          return matcher 
 64      else: 
 65          return _RMemo(matcher) 
 66   
 67   
 68 -class _RMemo(OperatorMatcher): 
 69      ''' 
 70      A simple memoizer for grammars that do not have left recursion. 
 71       
 72      Making this class Transformable did not improve performance (it's better 
 73      to place the transformation on critical classes like Or and And).  
 74      ''' 
 75       
 76      # pylint: disable-msg=E1101 
 77      # (using _args to define attributes) 
 78       
 79 -    def __init__(self, matcher): 
 80          super(_RMemo, self).__init__() 
 81          self._arg(matcher=matcher) 
 82          self.__table = {} # s_key(stream) -> [lock, table, generator]  
 83          self.__state = State.singleton() 
 84       
 85      @tagged 
 86 -    def _match(self, stream): 
 87          ''' 
 88          Attempt to match the stream. 
 89          ''' 
 90          key = s_key(stream, self.__state) 
 91          if key not in self.__table: 
 92              self.__table[key] = [False, [], self.matcher._match(stream)] 
 93          descriptor = self.__table[key] 
 94          if descriptor[0]: 
 95              raise MemoException('''Left recursion was detected. 
 96  You can try .config.auto_memoize() or similar, but it is better to re-write  
 97  the parser to remove left-recursive definitions.''') 
 98          for i in count(): 
 99              assert not descriptor[0] 
100              if i == len(descriptor[1]): 
101                  try: 
102                      descriptor[0] = True 
103                      result = yield descriptor[2] 
104                  finally: 
105                      descriptor[0] = False 
106                  descriptor[1].append(result) 
107              yield descriptor[1][i] 
108                       
109 -    def _untagged_match(self, stream): 
110          ''' 
111          Match the stream without trampolining. 
112          ''' 
113          key = s_key(stream, self.__state) 
114          if key not in self.__table: 
115              self.__table[key] = [False, [], self.matcher._match(stream)] 
116          descriptor = self.__table[key] 
117          if descriptor[0]: 
118              raise MemoException('''Left recursion was detected. 
119  You can try .config.auto_memoize() or similar, but it is better to re-write  
120  the parser to remove left-recursive definitions.''') 
121          for i in count(): 
122              assert not descriptor[0] 
123              if i == len(descriptor[1]): 
124                  result = next(descriptor[2].generator) 
125                  descriptor[1].append(result) 
126              yield descriptor[1][i] 
127               
128 -    def __iadd__(self, other): 
129          ''' 
130          Allow memos to wrap Delayed in rewriting. 
131          ''' 
132          self.matcher += other 
133          return self 
134   
135   
136 -def LMemo(matcher, curtail=None): 
137      ''' 
138      Wrap in the _LMemo cache if required. 
139      ''' 
140      if is_child(matcher, NoMemo, fail=False): 
141          return matcher 
142      else: 
143          if curtail is None: 
144              curtail = lambda depth, length: depth > length 
145          return _LMemo(matcher, curtail) 
146   
147   
148 -class _LMemo(OperatorMatcher): 
149       
150 -    def __init__(self, matcher, curtail): 
151          super(_LMemo, self).__init__() 
152          self._arg(matcher=matcher) 
153          self._karg(curtail=curtail) 
154          self.__depth = {} # s_key(stream) -> [depth]  
155          self.__table = {} # (s_key(stream), depth) -> [table, generator]  
156          self.__state = State.singleton() 
157       
158      @tagged 
159 -    def _match(self, stream): 
160          ''' 
161          Attempt to match the stream. 
162          ''' 
163          key = s_key(stream, self.__state) 
164          if key not in self.__depth: 
165              self.__depth[key] = 0 
166          depth = self.__depth[key] 
167          if self.curtail(depth, s_len(stream)): 
168              return 
169          if (key, depth) not in self.__table: 
170              self.__table[(key, depth)] = [[], self.matcher._match(stream)] 
171          descriptor = self.__table[(key, depth)] 
172          for i in count(): 
173              assert depth == self.__depth[key] 
174              if i == len(descriptor[0]): 
175                  try: 
176                      self.__depth[key] += 1 
177                      result = yield descriptor[1] 
178                  finally: 
179                      self.__depth[key] -= 1 
180                  descriptor[0].append(result) 
181              yield descriptor[0][i] 
182                       
183 -    def _untagged_match(self, stream): 
184          ''' 
185          Match the stream without trampolining. 
186          ''' 
187          key = s_key(stream, self.__state) 
188          if key not in self.__depth: 
189              self.__depth[key] = 0 
190          depth = self.__depth[key] 
191          if self.curtail(depth, s_len(stream)): 
192              return 
193          if (key, depth) not in self.__table: 
194              self.__table[(key, depth)] = [[], self.matcher._match(stream)] 
195          descriptor = self.__table[(key, depth)] 
196          for i in count(): 
197              assert depth == self.__depth[key] 
198              if i == len(descriptor[0]): 
199                  result = next(descriptor[1].generator) 
200                  descriptor[0].append(result) 
201              yield descriptor[0][i] 
202   
203 -    def __iadd__(self, other): 
204          ''' 
205          Allow memos to wrap Delayed in rewriting. 
206          ''' 
207          self.matcher += other 
208          return self 
209