1 # parser.py - simple top-down operator precedence parser for mercurial

     2 #

     3 # Copyright 2010 Matt Mackall <mpm@selenic.com>

     4 #

     5 # This software may be used and distributed according to the terms of the

     6 # GNU General Public License version 2 or any later version.

     7 

     8 # see http://effbot.org/zone/simple-top-down-parsing.txt and

     9 # http://eli.thegreenplace.net/2010/01/02/top-down-operator-precedence-parsing/

    10 # for background

    11 

    12 # takes a tokenizer and elements

    13 # tokenizer is an iterator that returns type, value pairs

    14 # elements is a mapping of types to binding strength, prefix and infix actions

    15 # an action is a tree node name, a tree label, and an optional match

    16 # __call__(program) parses program into a labelled tree

    17 

    18 class parser(object):

    19     def __init__(self, tokenizer, elements, methods=None):

    20         self._tokenizer = tokenizer

    21         self._elements = elements

    22         self._methods = methods

    23     def _advance(self):

    24         'advance the tokenizer'

    25         t = self.current

    26         self.current = self._iter.next()

    27         return t

    28     def _match(self, m):

    29         'make sure the tokenizer matches an end condition'

    30         if self.current[0] != m:

    31             raise SyntaxError(self.current)

    32         self._advance()

    33     def _parse(self, bind=0):

    34         token, value = self._advance()

    35         # handle prefix rules on current token

    36         prefix = self._elements[token][1]

    37         if not prefix:

    38             raise SyntaxError("not a prefix: %s" % token)

    39         if len(prefix) == 1:

    40             expr = (prefix[0], value)

    41         else:

    42             if len(prefix) > 2 and prefix[2] == self.current[0]:

    43                 self._match(prefix[2])

    44                 expr = (prefix[0], None)

    45             else:

    46                 expr = (prefix[0], self._parse(prefix[1]))

    47                 if len(prefix) > 2:

    48                     self._match(prefix[2])

    49         # gather tokens until we meet a lower binding strength

    50         while bind < self._elements[self.current[0]][0]:

    51             token, value = self._advance()

    52             # handle infix rules

    53             infix = self._elements[token][2]

    54             if len(infix) == 3 and infix[2] == self.current[0]:

    55                 self._match(infix[2])

    56                 expr = (infix[0], expr, (None))

    57             else:

    58                 if not infix[0]:

    59                     raise SyntaxError("not an infix")

    60                 expr = (infix[0], expr, self._parse(infix[1]))

    61                 if len(infix) == 3:

    62                     self._match(infix[2])

    63         return expr

    64     def parse(self, message):

    65         'generate a parse tree from a message'

    66         self._iter = self._tokenizer(message)

    67         self.current = self._iter.next()

    68         return self._parse()

    69     def eval(self, tree):

    70         'recursively evaluate a parse tree using node methods'

    71         if not isinstance(tree, tuple):

    72             return tree

    73         return self._methods[tree[0]](*[self.eval(t) for t in tree[1:]])

    74     def __call__(self, message):

    75         'parse a message into a parse tree and evaluate if methods given'

    76         t = self.parse(message)

    77         if self._methods:

    78             return self.eval(t)

    79         return t