diff -r 5ff1fc726848 -r c6bca38c1cbf eggs/mercurial-1.7.3-py2.6-linux-x86_64.egg/mercurial/parser.py --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/eggs/mercurial-1.7.3-py2.6-linux-x86_64.egg/mercurial/parser.py Sat Jan 08 11:20:57 2011 +0530 @@ -0,0 +1,91 @@ +# parser.py - simple top-down operator precedence parser for mercurial +# +# Copyright 2010 Matt Mackall +# +# This software may be used and distributed according to the terms of the +# GNU General Public License version 2 or any later version. + +# see http://effbot.org/zone/simple-top-down-parsing.htm and +# http://eli.thegreenplace.net/2010/01/02/top-down-operator-precedence-parsing/ +# for background + +# takes a tokenizer and elements +# tokenizer is an iterator that returns type, value pairs +# elements is a mapping of types to binding strength, prefix and infix actions +# an action is a tree node name, a tree label, and an optional match +# __call__(program) parses program into a labelled tree + +import error + +class parser(object): + def __init__(self, tokenizer, elements, methods=None): + self._tokenizer = tokenizer + self._elements = elements + self._methods = methods + def _advance(self): + 'advance the tokenizer' + t = self.current + try: + self.current = self._iter.next() + except StopIteration: + pass + return t + def _match(self, m, pos): + 'make sure the tokenizer matches an end condition' + if self.current[0] != m: + raise error.ParseError("unexpected token: %s" % self.current[0], + self.current[2]) + self._advance() + def _parse(self, bind=0): + token, value, pos = self._advance() + # handle prefix rules on current token + prefix = self._elements[token][1] + if not prefix: + raise error.ParseError("not a prefix: %s" % token, pos) + if len(prefix) == 1: + expr = (prefix[0], value) + else: + if len(prefix) > 2 and prefix[2] == self.current[0]: + self._match(prefix[2], pos) + expr = (prefix[0], None) + else: + expr = (prefix[0], self._parse(prefix[1])) + if len(prefix) > 2: + self._match(prefix[2], pos) + # gather tokens until we meet a lower binding strength + while bind < self._elements[self.current[0]][0]: + token, value, pos = self._advance() + e = self._elements[token] + # check for suffix - next token isn't a valid prefix + if len(e) == 4 and not self._elements[self.current[0]][1]: + suffix = e[3] + expr = (suffix[0], expr) + else: + # handle infix rules + if len(e) < 3 or not e[2]: + raise error.ParseError("not an infix: %s" % token, pos) + infix = e[2] + if len(infix) == 3 and infix[2] == self.current[0]: + self._match(infix[2], pos) + expr = (infix[0], expr, (None)) + else: + expr = (infix[0], expr, self._parse(infix[1])) + if len(infix) == 3: + self._match(infix[2], pos) + return expr + def parse(self, message): + 'generate a parse tree from a message' + self._iter = self._tokenizer(message) + self.current = self._iter.next() + return self._parse() + def eval(self, tree): + 'recursively evaluate a parse tree using node methods' + if not isinstance(tree, tuple): + return tree + return self._methods[tree[0]](*[self.eval(t) for t in tree[1:]]) + def __call__(self, message): + 'parse a message into a parse tree and evaluate if methods given' + t = self.parse(message) + if self._methods: + return self.eval(t) + return t