funcparserlib/parser.py

   1 # -*- coding: utf-8 -*-
   2
   3 # Copyright (c) 2008/2013 Andrey Vlasovskikh
   4 # Small Python 3 modifications by Jacob Alexander 2014
   5 #
   6 # Permission is hereby granted, free of charge, to any person obtaining
   7 # a copy of this software and associated documentation files (the
   8 # "Software"), to deal in the Software without restriction, including
   9 # without limitation the rights to use, copy, modify, merge, publish,
  10 # distribute, sublicense, and/or sell copies of the Software, and to
  11 # permit persons to whom the Software is furnished to do so, subject to
  12 # the following conditions:
  13 #
  14 # The above copyright notice and this permission notice shall be included
  15 # in all copies or substantial portions of the Software.
  16 #
  17 # THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  18 # EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  19 # MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
  20 # IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
  21 # CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
  22 # TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
  23 # SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  24
  25 """A recurisve descent parser library based on functional combinators.
  26
  27 Basic combinators are taken from Harrison's book ["Introduction to Functional
  28 Programming"][1] and translated from ML into Python. See also [a Russian
  29 translation of the book][2].
  30
  31   [1]: http://www.cl.cam.ac.uk/teaching/Lectures/funprog-jrh-1996/
  32   [2]: http://code.google.com/p/funprog-ru/
  33
  34 A parser `p` is represented by a function of type:
  35
  36     p :: Sequence(a), State -> (b, State)
  37
  38 that takes as its input a sequence of tokens of arbitrary type `a` and a
  39 current parsing state and return a pair of a parsed token of arbitrary type
  40 `b` and the new parsing state.
  41
  42 The parsing state includes the current position in the sequence being parsed and
  43 the position of the rightmost token that has been consumed while parsing.
  44
  45 Parser functions are wrapped into an object of the class `Parser`. This class
  46 implements custom operators `+` for sequential composition of parsers, `|` for
  47 choice composition, `>>` for transforming the result of parsing. The method
  48 `Parser.parse` provides an easier way for invoking a parser hiding details
  49 related to a parser state:
  50
  51     Parser.parse :: Parser(a, b), Sequence(a) -> b
  52
  53 Altough this module is able to deal with a sequences of any kind of objects, the
  54 recommended way of using it is applying a parser to a `Sequence(Token)`.
  55 `Token` objects are produced by a regexp-based tokenizer defined in
  56 `funcparserlib.lexer`. By using it this way you get more readable parsing error
  57 messages (as `Token` objects contain their position in the source file) and good
  58 separation of lexical and syntactic levels of the grammar. See examples for more
  59 info.
  60
  61 Debug messages are emitted via a `logging.Logger` object named
  62 `"funcparserlib"`.
  63 """
  64
  65 __all__ = [
  66     'some', 'a', 'many', 'pure', 'finished', 'maybe', 'skip', 'oneplus',
  67     'forward_decl', 'NoParseError',
  68 ]
  69
  70 import logging
  71
  72 log = logging.getLogger('funcparserlib')
  73
  74 debug = False
  75
  76
  77 class Parser(object):
  78     """A wrapper around a parser function that defines some operators for parser
  79     composition.
  80     """
  81
  82     def __init__(self, p):
  83         """Wraps a parser function p into an object."""
  84         self.define(p)
  85
  86     def named(self, name):
  87         """Specifies the name of the parser for more readable parsing log."""
  88         self.name = name
  89         return self
  90
  91     def define(self, p):
  92         """Defines a parser wrapped into this object."""
  93         f = getattr(p, 'run', p)
  94         if debug:
  95             setattr(self, '_run', f)
  96         else:
  97             setattr(self, 'run', f)
  98         self.named(getattr(p, 'name', p.__doc__))
  99
 100     def run(self, tokens, s):
 101         """Sequence(a), State -> (b, State)
 102
 103         Runs a parser wrapped into this object.
 104         """
 105         if debug:
 106             log.debug(u'trying %s' % self.name)
 107         return self._run(tokens, s)
 108
 109     def _run(self, tokens, s):
 110         raise NotImplementedError(u'you must define() a parser')
 111
 112     def parse(self, tokens):
 113         """Sequence(a) -> b
 114
 115         Applies the parser to a sequence of tokens producing a parsing result.
 116
 117         It provides a way to invoke a parser hiding details related to the
 118         parser state. Also it makes error messages more readable by specifying
 119         the position of the rightmost token that has been reached.
 120         """
 121         try:
 122             (tree, _) = self.run(tokens, State())
 123             return tree
 124         except NoParseError as e:
 125             max = e.state.max
 126             if len(tokens) > max:
 127                 tok = tokens[max]
 128             else:
 129                 tok = u'<EOF>'
 130             raise NoParseError(u'%s: %s' % (e.msg, tok), e.state)
 131
 132     def __add__(self, other):
 133         """Parser(a, b), Parser(a, c) -> Parser(a, _Tuple(b, c))
 134
 135         A sequential composition of parsers.
 136
 137         NOTE: The real type of the parsed value isn't always such as specified.
 138         Here we use dynamic typing for ignoring the tokens that are of no
 139         interest to the user. Also we merge parsing results into a single _Tuple
 140         unless the user explicitely prevents it. See also skip and >>
 141         combinators.
 142         """
 143
 144         def magic(v1, v2):
 145             vs = [v for v in [v1, v2] if not isinstance(v, _Ignored)]
 146             if len(vs) == 1:
 147                 return vs[0]
 148             elif len(vs) == 2:
 149                 if isinstance(vs[0], _Tuple):
 150                     return _Tuple(v1 + (v2,))
 151                 else:
 152                     return _Tuple(vs)
 153             else:
 154                 return _Ignored(())
 155
 156         @Parser
 157         def _add(tokens, s):
 158             (v1, s2) = self.run(tokens, s)
 159             (v2, s3) = other.run(tokens, s2)
 160             return magic(v1, v2), s3
 161
 162         # or in terms of bind and pure:
 163         # _add = self.bind(lambda x: other.bind(lambda y: pure(magic(x, y))))
 164         _add.name = u'(%s , %s)' % (self.name, other.name)
 165         return _add
 166
 167     def __or__(self, other):
 168         """Parser(a, b), Parser(a, c) -> Parser(a, b or c)
 169
 170         A choice composition of two parsers.
 171
 172         NOTE: Here we are not providing the exact type of the result. In a
 173         statically typed langage something like Either b c could be used. See
 174         also + combinator.
 175         """
 176
 177         @Parser
 178         def _or(tokens, s):
 179             try:
 180                 return self.run(tokens, s)
 181             except NoParseError as e:
 182                 return other.run(tokens, State(s.pos, e.state.max))
 183
 184         _or.name = u'(%s | %s)' % (self.name, other.name)
 185         return _or
 186
 187     def __rshift__(self, f):
 188         """Parser(a, b), (b -> c) -> Parser(a, c)
 189
 190         Given a function from b to c, transforms a parser of b into a parser of
 191         c. It is useful for transorming a parser value into another value for
 192         making it a part of a parse tree or an AST.
 193
 194         This combinator may be thought of as a functor from b -> c to Parser(a,
 195         b) -> Parser(a, c).
 196         """
 197
 198         @Parser
 199         def _shift(tokens, s):
 200             (v, s2) = self.run(tokens, s)
 201             return f(v), s2
 202
 203         # or in terms of bind and pure:
 204         # _shift = self.bind(lambda x: pure(f(x)))
 205         _shift.name = u'(%s)' % (self.name,)
 206         return _shift
 207
 208     def bind(self, f):
 209         """Parser(a, b), (b -> Parser(a, c)) -> Parser(a, c)
 210
 211         NOTE: A monadic bind function. It is used internally to implement other
 212         combinators. Functions bind and pure make the Parser a Monad.
 213         """
 214
 215         @Parser
 216         def _bind(tokens, s):
 217             (v, s2) = self.run(tokens, s)
 218             return f(v).run(tokens, s2)
 219
 220         _bind.name = u'(%s >>=)' % (self.name,)
 221         return _bind
 222
 223
 224 class State(object):
 225     """A parsing state that is maintained basically for error reporting.
 226
 227     It consists of the current position pos in the sequence being parsed and
 228     the position max of the rightmost token that has been consumed while
 229     parsing.
 230     """
 231
 232     def __init__(self, pos=0, max=0):
 233         self.pos = pos
 234         self.max = max
 235
 236     def __str__(self):
 237         return unicode((self.pos, self.max))
 238
 239     def __repr__(self):
 240         return u'State(%r, %r)' % (self.pos, self.max)
 241
 242
 243 class NoParseError(Exception):
 244     def __init__(self, msg=u'', state=None):
 245         self.msg = msg
 246         self.state = state
 247
 248     def __str__(self):
 249         return self.msg
 250
 251
 252 class _Tuple(tuple):
 253     pass
 254
 255
 256 class _Ignored(object):
 257     def __init__(self, value):
 258         self.value = value
 259
 260     def __repr__(self):
 261         return u'_Ignored(%s)' % repr(self.value)
 262
 263
 264 @Parser
 265 def finished(tokens, s):
 266     """Parser(a, None)
 267
 268     Throws an exception if any tokens are left in the input unparsed.
 269     """
 270     if s.pos >= len(tokens):
 271         return None, s
 272     else:
 273         raise NoParseError(u'should have reached <EOF>', s)
 274
 275
 276 finished.name = u'finished'
 277
 278
 279 def many(p):
 280     """Parser(a, b) -> Parser(a, [b])
 281
 282     Returns a parser that infinitely applies the parser p to the input sequence
 283     of tokens while it successfully parsers them. The resulting parser returns a
 284     list of parsed values.
 285     """
 286
 287     @Parser
 288     def _many(tokens, s):
 289         """Iterative implementation preventing the stack overflow."""
 290         res = []
 291         try:
 292             while True:
 293                 (v, s) = p.run(tokens, s)
 294                 res.append(v)
 295         except NoParseError as e:
 296             return res, State(s.pos, e.state.max)
 297
 298     _many.name = u'{ %s }' % p.name
 299     return _many
 300
 301
 302 def some(pred):
 303     """(a -> bool) -> Parser(a, a)
 304
 305     Returns a parser that parses a token if it satisfies a predicate pred.
 306     """
 307
 308     @Parser
 309     def _some(tokens, s):
 310         if s.pos >= len(tokens):
 311             raise NoParseError(u'no tokens left in the stream', s)
 312         else:
 313             t = tokens[s.pos]
 314             if pred(t):
 315                 pos = s.pos + 1
 316                 s2 = State(pos, max(pos, s.max))
 317                 if debug:
 318                     log.debug(u'*matched* "%s", new state = %s' % (t, s2))
 319                 return t, s2
 320             else:
 321                 if debug:
 322                     log.debug(u'failed "%s", state = %s' % (t, s))
 323                 raise NoParseError(u'got unexpected token', s)
 324
 325     _some.name = u'(some)'
 326     return _some
 327
 328
 329 def a(value):
 330     """Eq(a) -> Parser(a, a)
 331
 332     Returns a parser that parses a token that is equal to the value value.
 333     """
 334     name = getattr(value, 'name', value)
 335     return some(lambda t: t == value).named(u'(a "%s")' % (name,))
 336
 337
 338 def pure(x):
 339     @Parser
 340     def _pure(_, s):
 341         return x, s
 342
 343     _pure.name = u'(pure %r)' % (x,)
 344     return _pure
 345
 346
 347 def maybe(p):
 348     """Parser(a, b) -> Parser(a, b or None)
 349
 350     Returns a parser that retuns None if parsing fails.
 351
 352     NOTE: In a statically typed language, the type Maybe b could be more
 353     approprieate.
 354     """
 355     return (p | pure(None)).named(u'[ %s ]' % (p.name,))
 356
 357
 358 def skip(p):
 359     """Parser(a, b) -> Parser(a, _Ignored(b))
 360
 361     Returns a parser which results are ignored by the combinator +. It is useful
 362     for throwing away elements of concrete syntax (e. g. ",", ";").
 363     """
 364     return p >> _Ignored
 365
 366
 367 def oneplus(p):
 368     """Parser(a, b) -> Parser(a, [b])
 369
 370     Returns a parser that applies the parser p one or more times.
 371     """
 372     q = p + many(p) >> (lambda x: [x[0]] + x[1])
 373     return q.named(u'(%s , { %s })' % (p.name, p.name))
 374
 375
 376 def with_forward_decls(suspension):
 377     """(None -> Parser(a, b)) -> Parser(a, b)
 378
 379     Returns a parser that computes itself lazily as a result of the suspension
 380     provided. It is needed when some parsers contain forward references to
 381     parsers defined later and such references are cyclic. See examples for more
 382     details.
 383     """
 384
 385     @Parser
 386     def f(tokens, s):
 387         return suspension().run(tokens, s)
 388
 389     return f
 390
 391
 392 def forward_decl():
 393     """None -> Parser(?, ?)
 394
 395     Returns an undefined parser that can be used as a forward declaration. You
 396     will be able to define() it when all the parsers it depends on are
 397     available.
 398     """
 399
 400     @Parser
 401     def f(tokens, s):
 402         raise NotImplementedError(u'you must define() a forward_decl somewhere')
 403
 404     return f
 405
 406
 407 if __name__ == '__main__':
 408     import doctest
 409     doctest.testmod()