Show More
@@ -1,110 +1,110 b'' | |||
|
1 | 1 | # parser.py - simple top-down operator precedence parser for mercurial |
|
2 | 2 | # |
|
3 | 3 | # Copyright 2010 Matt Mackall <mpm@selenic.com> |
|
4 | 4 | # |
|
5 | 5 | # This software may be used and distributed according to the terms of the |
|
6 | 6 | # GNU General Public License version 2 or any later version. |
|
7 | 7 | |
|
8 | 8 | # see http://effbot.org/zone/simple-top-down-parsing.htm and |
|
9 | 9 | # http://eli.thegreenplace.net/2010/01/02/top-down-operator-precedence-parsing/ |
|
10 | 10 | # for background |
|
11 | 11 | |
|
12 | 12 | # takes a tokenizer and elements |
|
13 | 13 | # tokenizer is an iterator that returns type, value pairs |
|
14 | 14 | # elements is a mapping of types to binding strength, prefix and infix actions |
|
15 | 15 | # an action is a tree node name, a tree label, and an optional match |
|
16 | 16 | # __call__(program) parses program into a labeled tree |
|
17 | 17 | |
|
18 | 18 | import error |
|
19 | 19 | from i18n import _ |
|
20 | 20 | |
|
21 | 21 | class parser(object): |
|
22 | 22 | def __init__(self, tokenizer, elements, methods=None): |
|
23 | 23 | self._tokenizer = tokenizer |
|
24 | 24 | self._elements = elements |
|
25 | 25 | self._methods = methods |
|
26 | 26 | self.current = None |
|
27 | 27 | def _advance(self): |
|
28 | 28 | 'advance the tokenizer' |
|
29 | 29 | t = self.current |
|
30 | 30 | self.current = next(self._iter, None) |
|
31 | 31 | return t |
|
32 | 32 | def _match(self, m, pos): |
|
33 | 33 | 'make sure the tokenizer matches an end condition' |
|
34 | 34 | if self.current[0] != m: |
|
35 | 35 | raise error.ParseError(_("unexpected token: %s") % self.current[0], |
|
36 | 36 | self.current[2]) |
|
37 | 37 | self._advance() |
|
38 | 38 | def _parse(self, bind=0): |
|
39 | 39 | token, value, pos = self._advance() |
|
40 | 40 | # handle prefix rules on current token |
|
41 | 41 | prefix = self._elements[token][1] |
|
42 | 42 | if not prefix: |
|
43 | 43 | raise error.ParseError(_("not a prefix: %s") % token, pos) |
|
44 | 44 | if len(prefix) == 1: |
|
45 | 45 | expr = (prefix[0], value) |
|
46 | 46 | else: |
|
47 | 47 | if len(prefix) > 2 and prefix[2] == self.current[0]: |
|
48 | 48 | self._match(prefix[2], pos) |
|
49 | 49 | expr = (prefix[0], None) |
|
50 | 50 | else: |
|
51 | 51 | expr = (prefix[0], self._parse(prefix[1])) |
|
52 | 52 | if len(prefix) > 2: |
|
53 | 53 | self._match(prefix[2], pos) |
|
54 | 54 | # gather tokens until we meet a lower binding strength |
|
55 | 55 | while bind < self._elements[self.current[0]][0]: |
|
56 | 56 | token, value, pos = self._advance() |
|
57 | 57 | e = self._elements[token] |
|
58 | 58 | # check for suffix - next token isn't a valid prefix |
|
59 | 59 | if len(e) == 4 and not self._elements[self.current[0]][1]: |
|
60 | 60 | suffix = e[3] |
|
61 | 61 | expr = (suffix[0], expr) |
|
62 | 62 | else: |
|
63 | 63 | # handle infix rules |
|
64 | 64 | if len(e) < 3 or not e[2]: |
|
65 | 65 | raise error.ParseError(_("not an infix: %s") % token, pos) |
|
66 | 66 | infix = e[2] |
|
67 | 67 | if len(infix) == 3 and infix[2] == self.current[0]: |
|
68 | 68 | self._match(infix[2], pos) |
|
69 | 69 | expr = (infix[0], expr, (None)) |
|
70 | 70 | else: |
|
71 | 71 | expr = (infix[0], expr, self._parse(infix[1])) |
|
72 | 72 | if len(infix) == 3: |
|
73 | 73 | self._match(infix[2], pos) |
|
74 | 74 | return expr |
|
75 | 75 | def parse(self, message, lookup=None): |
|
76 | 76 | 'generate a parse tree from a message' |
|
77 | 77 | if lookup: |
|
78 | 78 | self._iter = self._tokenizer(message, lookup) |
|
79 | 79 | else: |
|
80 | 80 | self._iter = self._tokenizer(message) |
|
81 | 81 | self._advance() |
|
82 | 82 | res = self._parse() |
|
83 | 83 | token, value, pos = self.current |
|
84 | 84 | return res, pos |
|
85 | 85 | def eval(self, tree): |
|
86 | 86 | 'recursively evaluate a parse tree using node methods' |
|
87 | 87 | if not isinstance(tree, tuple): |
|
88 | 88 | return tree |
|
89 | 89 | return self._methods[tree[0]](*[self.eval(t) for t in tree[1:]]) |
|
90 | 90 | def __call__(self, message): |
|
91 | 91 | 'parse a message into a parse tree and evaluate if methods given' |
|
92 | 92 | t = self.parse(message) |
|
93 | 93 | if self._methods: |
|
94 | 94 | return self.eval(t) |
|
95 | 95 | return t |
|
96 | 96 | |
|
97 | def prettyformat(tree, leafnodes): | |
|
98 | def _prettyformat(tree, level, lines): | |
|
97 | def _prettyformat(tree, leafnodes, level, lines): | |
|
99 | 98 |
|
|
100 | 99 |
|
|
101 | 100 |
|
|
102 | 101 |
|
|
103 | 102 |
|
|
104 |
|
|
|
103 | _prettyformat(s, leafnodes, level + 1, lines) | |
|
105 | 104 |
|
|
106 | 105 | |
|
106 | def prettyformat(tree, leafnodes): | |
|
107 | 107 | lines = [] |
|
108 | _prettyformat(tree, 0, lines) | |
|
108 | _prettyformat(tree, leafnodes, 0, lines) | |
|
109 | 109 | output = '\n'.join((' ' * l + s) for l, s in lines) |
|
110 | 110 | return output |
General Comments 0
You need to be logged in to leave comments.
Login now