Package lepl :: Package matchers :: Module memo
[hide private]
[frames] | no frames]

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