Source Code for Module lepl.core.parser

  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  Create and evaluate parsers. 
 32   
 33  Once a consistent set of matchers is constructed (that describes a grammar) 
 34  they must be evaluated against some input.  The code here supports that  
 35  evaluation (via `trampoline()`) and allows the graph of matchers to be  
 36  rewritten beforehand. 
 37  ''' 
 38   
 39   
 40  from collections import deque 
 41  from logging import getLogger 
 42  from traceback import format_exc 
 43  from weakref import ref 
 44  try: 
 45      from itertools import imap 
 46  except ImportError: 
 47      imap = map 
 48   
 49  from lepl.stream.core import s_debug, s_cacheable 
 50  from lepl.core.monitor import prepare_monitors 
 51  from lepl.support.lib import fmt 
 52   
 53   
 54 -def tagged(method): 
 55      ''' 
 56      Decorator for generators to add extra attributes. 
 57      ''' 
 58      def tagged_method(matcher, stream): 
 59          ''' 
 60          Wrap the result. 
 61          ''' 
 62          return GeneratorWrapper(method(matcher, stream), matcher, stream) 
 63      return tagged_method 
 64   
 65   
 66 -def tagged_function(matcher, function): 
 67      ''' 
 68      Decorator for generators to add extra attributes. 
 69      ''' 
 70      def tagged_function(stream): 
 71          ''' 
 72          Wrap the result. 
 73          ''' 
 74          return GeneratorWrapper(function(matcher, stream), matcher, stream) 
 75      return tagged_function 
 76   
 77   
 78 -class GeneratorWrapper(object): 
 79      ''' 
 80      Associate basic info about call that created the generator with the  
 81      generator itself.  This lets us manage resources and provide logging. 
 82      It is also used by `trampoline()` to recognise generators that must  
 83      be evaluated (rather than being treated as normal values). 
 84      ''' 
 85       
 86      __slots__ = ['generator', 'matcher', 'stream',  
 87                   '_GeneratorWrapper__cached_repr', '__weakref__'] 
 88   
 89 -    def __init__(self, generator, matcher, stream): 
 90          self.generator = generator 
 91          self.matcher = matcher 
 92          if s_cacheable(stream): 
 93              self.stream = stream 
 94          else: 
 95              self.stream = '<stream>' 
 96          self.__cached_repr = None 
 97           
 98 -    def __repr__(self): 
 99          ''' 
100          Lazily evaluated for speed - saves 1/3 of time spent in constructor 
101          ''' 
102          if not self.__cached_repr: 
103              try: 
104                  s = s_debug(self.stream) 
105              except AttributeError: 
106                  s = '<stream>' 
107              self.__cached_repr = fmt('{0}({1})', self.matcher, s) 
108          return self.__cached_repr 
109       
110 -    def __str__(self): 
111          return self.__repr__() 
112           
113   
114 -def trampoline(main, m_stack=None, m_value=None): 
115      ''' 
116      The main parser loop.  Evaluates matchers as coroutines. 
117       
118      A dedicated version for when monitor not present increased the speed of 
119      the nat_lang performance test by only around 1% (close to noise).  
120       
121      Replacing stack append/pop with a manually allocated non-decreasing array 
122      and index made no significant difference (at around 1% level) 
123      ''' 
124      from lepl.stream.maxdepth import FullFirstMatchException 
125      stack = deque() 
126      push = stack.append 
127      pop = stack.pop 
128      try: 
129          value = main 
130          exception_being_raised = False 
131          epoch = 0 
132          log = getLogger('lepl.parser.trampoline') 
133          while True: 
134              epoch += 1 
135              try: 
136                  if m_value: m_value.next_iteration(epoch, value, 
137                                                     exception_being_raised, stack) 
138                  # is the value a coroutine that should be added to our stack 
139                  # and evaluated? 
140                  if type(value) is GeneratorWrapper: 
141                      if m_stack: m_stack.push(value) 
142                      # add to the stack 
143                      push(value) 
144                      if m_value: m_value.before_next(value) 
145                      # and evaluate 
146                      value = next(value.generator) 
147                      if m_value: m_value.after_next(value) 
148                  # if we don't have a coroutine then we have a result that 
149                  # must be passed up the stack. 
150                  else: 
151                      # drop top of the stack (which returned the value) 
152                      popped = pop() 
153                      if m_stack: m_stack.pop(popped) 
154                      # if we still have coroutines left, pass the value in 
155                      if stack: 
156                          # handle exceptions that are being raised 
157                          if exception_being_raised: 
158                              exception_being_raised = False 
159                              if m_value: m_value.before_throw(stack[-1], value) 
160                              # raise it inside the coroutine 
161                              value = stack[-1].generator.throw(value) 
162                              if m_value: m_value.after_throw(value) 
163                          # handle ordinary values 
164                          else: 
165                              if m_value: m_value.before_send(stack[-1], value) 
166                              # inject it into the coroutine 
167                              value = stack[-1].generator.send(value) 
168                              if m_value: m_value.after_send(value) 
169                      # otherwise, the stack is completely unwound so return 
170                      # to main caller  
171                      else: 
172                          if exception_being_raised: 
173                              if m_value: m_value.raise_(value) 
174                              raise value 
175                          else: 
176                              if m_value: m_value.yield_(value) 
177                              yield value 
178                          # this allows us to restart with a new evaluation 
179                          # (backtracking) if called again. 
180                          value = main 
181              except StopIteration as exception: 
182                  # this occurs when we need to exit the main loop 
183                  if exception_being_raised: 
184                      raise 
185                  # otherwise, we will propagate this value 
186                  value = exception 
187                  exception_being_raised = True 
188                  if m_value: m_value.exception(value) 
189              except Exception as exception: 
190                  # do some logging etc before re-raising 
191                  if not isinstance(exception, FullFirstMatchException): 
192                      log.debug(fmt('Exception at epoch {0}, {1!s}: {2!s}', 
193                                    epoch, value, exception)) 
194                  if stack: 
195                      log.debug(fmt('Top of stack: {0}', stack[-1])) 
196                      # going to raise original exception 
197                      # pylint: disable-msg=W0702 
198                      try: 
199                          log.debug(format_exc()) 
200                      except: 
201                          log.warn('Exception cannot be formatted!') 
202                      for generator in stack: 
203                          log.debug(fmt('Stack: {0}', generator)) 
204                  raise 
205      finally: 
206          # record the remaining stack 
207          while m_stack and stack: 
208              m_stack.pop(pop()) 
209                       
210                   
211 -def make_raw_parser(matcher, stream_factory, config): 
212      ''' 
213      Make a parser.  Rewrite the matcher and prepare the input for a parser. 
214      This constructs a function that returns a generator that provides a  
215      sequence of matches (ie (results, stream) pairs). 
216      ''' 
217      for rewriter in config.rewriters: 
218          #print(rewriter) 
219          #print(matcher.tree()) 
220          matcher = rewriter(matcher) 
221      (m_stack, m_value) = prepare_monitors(config.monitors) 
222      # pylint bug here? (E0601) 
223      # pylint: disable-msg=W0212, E0601 
224      # (_match is meant to be hidden) 
225      # pylint: disable-msg=W0142 
226      def parser(arg, **kargs): 
227          stream_kargs = dict(config.stream_kargs) 
228          stream_kargs.update(kargs) 
229          return trampoline(matcher._match(stream_factory(arg, **stream_kargs)),  
230                            m_stack=m_stack, m_value=m_value) 
231      parser.matcher = matcher 
232      return parser 
233   
234   
235 -def make_multiple(raw): 
236      ''' 
237      Convert a raw parser to return a generator of results. 
238      ''' 
239      def multiple(arg, **kargs): 
240          ''' 
241          Adapt a raw parser to behave as expected for the matcher interface. 
242          ''' 
243          return imap(lambda x: x[0], raw(arg, **kargs)) 
244      multiple.matcher = raw.matcher 
245      return multiple 
246   
247   
248 -def make_single(raw): 
249      ''' 
250      Convert a raw parser to return a single result or None. 
251      ''' 
252      def single(arg, **kargs): 
253          ''' 
254          Adapt a raw parser to behave as expected for the parser interface. 
255          ''' 
256          try: 
257              return next(raw(arg, **kargs))[0] 
258          except StopIteration: 
259              return None 
260      single.matcher = raw.matcher 
261      return single 
262