Show More
@@ -1,213 +1,215 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, pos) tuples |
|
14 | 14 | # elements is a mapping of types to binding strength, primary, prefix, infix |
|
15 | 15 | # and suffix actions |
|
16 | 16 | # an action is a tree node name, a tree label, and an optional match |
|
17 | 17 | # __call__(program) parses program into a labeled tree |
|
18 | 18 | |
|
19 | import error | |
|
20 | from i18n import _ | |
|
19 | from __future__ import absolute_import | |
|
20 | ||
|
21 | from .i18n import _ | |
|
22 | from . import error | |
|
21 | 23 | |
|
22 | 24 | class parser(object): |
|
23 | 25 | def __init__(self, elements, methods=None): |
|
24 | 26 | self._elements = elements |
|
25 | 27 | self._methods = methods |
|
26 | 28 | self.current = None |
|
27 | 29 | def _advance(self): |
|
28 | 30 | 'advance the tokenizer' |
|
29 | 31 | t = self.current |
|
30 | 32 | self.current = next(self._iter, None) |
|
31 | 33 | return t |
|
32 | 34 | def _hasnewterm(self): |
|
33 | 35 | 'True if next token may start new term' |
|
34 | 36 | return any(self._elements[self.current[0]][1:3]) |
|
35 | 37 | def _match(self, m): |
|
36 | 38 | 'make sure the tokenizer matches an end condition' |
|
37 | 39 | if self.current[0] != m: |
|
38 | 40 | raise error.ParseError(_("unexpected token: %s") % self.current[0], |
|
39 | 41 | self.current[2]) |
|
40 | 42 | self._advance() |
|
41 | 43 | def _parseoperand(self, bind, m=None): |
|
42 | 44 | 'gather right-hand-side operand until an end condition or binding met' |
|
43 | 45 | if m and self.current[0] == m: |
|
44 | 46 | expr = None |
|
45 | 47 | else: |
|
46 | 48 | expr = self._parse(bind) |
|
47 | 49 | if m: |
|
48 | 50 | self._match(m) |
|
49 | 51 | return expr |
|
50 | 52 | def _parse(self, bind=0): |
|
51 | 53 | token, value, pos = self._advance() |
|
52 | 54 | # handle prefix rules on current token, take as primary if unambiguous |
|
53 | 55 | primary, prefix = self._elements[token][1:3] |
|
54 | 56 | if primary and not (prefix and self._hasnewterm()): |
|
55 | 57 | expr = (primary, value) |
|
56 | 58 | elif prefix: |
|
57 | 59 | expr = (prefix[0], self._parseoperand(*prefix[1:])) |
|
58 | 60 | else: |
|
59 | 61 | raise error.ParseError(_("not a prefix: %s") % token, pos) |
|
60 | 62 | # gather tokens until we meet a lower binding strength |
|
61 | 63 | while bind < self._elements[self.current[0]][0]: |
|
62 | 64 | token, value, pos = self._advance() |
|
63 | 65 | # handle infix rules, take as suffix if unambiguous |
|
64 | 66 | infix, suffix = self._elements[token][3:] |
|
65 | 67 | if suffix and not (infix and self._hasnewterm()): |
|
66 | 68 | expr = (suffix[0], expr) |
|
67 | 69 | elif infix: |
|
68 | 70 | expr = (infix[0], expr, self._parseoperand(*infix[1:])) |
|
69 | 71 | else: |
|
70 | 72 | raise error.ParseError(_("not an infix: %s") % token, pos) |
|
71 | 73 | return expr |
|
72 | 74 | def parse(self, tokeniter): |
|
73 | 75 | 'generate a parse tree from tokens' |
|
74 | 76 | self._iter = tokeniter |
|
75 | 77 | self._advance() |
|
76 | 78 | res = self._parse() |
|
77 | 79 | token, value, pos = self.current |
|
78 | 80 | return res, pos |
|
79 | 81 | def eval(self, tree): |
|
80 | 82 | 'recursively evaluate a parse tree using node methods' |
|
81 | 83 | if not isinstance(tree, tuple): |
|
82 | 84 | return tree |
|
83 | 85 | return self._methods[tree[0]](*[self.eval(t) for t in tree[1:]]) |
|
84 | 86 | def __call__(self, tokeniter): |
|
85 | 87 | 'parse tokens into a parse tree and evaluate if methods given' |
|
86 | 88 | t = self.parse(tokeniter) |
|
87 | 89 | if self._methods: |
|
88 | 90 | return self.eval(t) |
|
89 | 91 | return t |
|
90 | 92 | |
|
91 | 93 | def buildargsdict(trees, funcname, keys, keyvaluenode, keynode): |
|
92 | 94 | """Build dict from list containing positional and keyword arguments |
|
93 | 95 | |
|
94 | 96 | Invalid keywords or too many positional arguments are rejected, but |
|
95 | 97 | missing arguments are just omitted. |
|
96 | 98 | """ |
|
97 | 99 | if len(trees) > len(keys): |
|
98 | 100 | raise error.ParseError(_("%(func)s takes at most %(nargs)d arguments") |
|
99 | 101 | % {'func': funcname, 'nargs': len(keys)}) |
|
100 | 102 | args = {} |
|
101 | 103 | # consume positional arguments |
|
102 | 104 | for k, x in zip(keys, trees): |
|
103 | 105 | if x[0] == keyvaluenode: |
|
104 | 106 | break |
|
105 | 107 | args[k] = x |
|
106 | 108 | # remainder should be keyword arguments |
|
107 | 109 | for x in trees[len(args):]: |
|
108 | 110 | if x[0] != keyvaluenode or x[1][0] != keynode: |
|
109 | 111 | raise error.ParseError(_("%(func)s got an invalid argument") |
|
110 | 112 | % {'func': funcname}) |
|
111 | 113 | k = x[1][1] |
|
112 | 114 | if k not in keys: |
|
113 | 115 | raise error.ParseError(_("%(func)s got an unexpected keyword " |
|
114 | 116 | "argument '%(key)s'") |
|
115 | 117 | % {'func': funcname, 'key': k}) |
|
116 | 118 | if k in args: |
|
117 | 119 | raise error.ParseError(_("%(func)s got multiple values for keyword " |
|
118 | 120 | "argument '%(key)s'") |
|
119 | 121 | % {'func': funcname, 'key': k}) |
|
120 | 122 | args[k] = x[2] |
|
121 | 123 | return args |
|
122 | 124 | |
|
123 | 125 | def _prettyformat(tree, leafnodes, level, lines): |
|
124 | 126 | if not isinstance(tree, tuple) or tree[0] in leafnodes: |
|
125 | 127 | lines.append((level, str(tree))) |
|
126 | 128 | else: |
|
127 | 129 | lines.append((level, '(%s' % tree[0])) |
|
128 | 130 | for s in tree[1:]: |
|
129 | 131 | _prettyformat(s, leafnodes, level + 1, lines) |
|
130 | 132 | lines[-1:] = [(lines[-1][0], lines[-1][1] + ')')] |
|
131 | 133 | |
|
132 | 134 | def prettyformat(tree, leafnodes): |
|
133 | 135 | lines = [] |
|
134 | 136 | _prettyformat(tree, leafnodes, 0, lines) |
|
135 | 137 | output = '\n'.join((' ' * l + s) for l, s in lines) |
|
136 | 138 | return output |
|
137 | 139 | |
|
138 | 140 | def simplifyinfixops(tree, targetnodes): |
|
139 | 141 | """Flatten chained infix operations to reduce usage of Python stack |
|
140 | 142 | |
|
141 | 143 | >>> def f(tree): |
|
142 | 144 | ... print prettyformat(simplifyinfixops(tree, ('or',)), ('symbol',)) |
|
143 | 145 | >>> f(('or', |
|
144 | 146 | ... ('or', |
|
145 | 147 | ... ('symbol', '1'), |
|
146 | 148 | ... ('symbol', '2')), |
|
147 | 149 | ... ('symbol', '3'))) |
|
148 | 150 | (or |
|
149 | 151 | ('symbol', '1') |
|
150 | 152 | ('symbol', '2') |
|
151 | 153 | ('symbol', '3')) |
|
152 | 154 | >>> f(('func', |
|
153 | 155 | ... ('symbol', 'p1'), |
|
154 | 156 | ... ('or', |
|
155 | 157 | ... ('or', |
|
156 | 158 | ... ('func', |
|
157 | 159 | ... ('symbol', 'sort'), |
|
158 | 160 | ... ('list', |
|
159 | 161 | ... ('or', |
|
160 | 162 | ... ('or', |
|
161 | 163 | ... ('symbol', '1'), |
|
162 | 164 | ... ('symbol', '2')), |
|
163 | 165 | ... ('symbol', '3')), |
|
164 | 166 | ... ('negate', |
|
165 | 167 | ... ('symbol', 'rev')))), |
|
166 | 168 | ... ('and', |
|
167 | 169 | ... ('symbol', '4'), |
|
168 | 170 | ... ('group', |
|
169 | 171 | ... ('or', |
|
170 | 172 | ... ('or', |
|
171 | 173 | ... ('symbol', '5'), |
|
172 | 174 | ... ('symbol', '6')), |
|
173 | 175 | ... ('symbol', '7'))))), |
|
174 | 176 | ... ('symbol', '8')))) |
|
175 | 177 | (func |
|
176 | 178 | ('symbol', 'p1') |
|
177 | 179 | (or |
|
178 | 180 | (func |
|
179 | 181 | ('symbol', 'sort') |
|
180 | 182 | (list |
|
181 | 183 | (or |
|
182 | 184 | ('symbol', '1') |
|
183 | 185 | ('symbol', '2') |
|
184 | 186 | ('symbol', '3')) |
|
185 | 187 | (negate |
|
186 | 188 | ('symbol', 'rev')))) |
|
187 | 189 | (and |
|
188 | 190 | ('symbol', '4') |
|
189 | 191 | (group |
|
190 | 192 | (or |
|
191 | 193 | ('symbol', '5') |
|
192 | 194 | ('symbol', '6') |
|
193 | 195 | ('symbol', '7')))) |
|
194 | 196 | ('symbol', '8'))) |
|
195 | 197 | """ |
|
196 | 198 | if not isinstance(tree, tuple): |
|
197 | 199 | return tree |
|
198 | 200 | op = tree[0] |
|
199 | 201 | if op not in targetnodes: |
|
200 | 202 | return (op,) + tuple(simplifyinfixops(x, targetnodes) for x in tree[1:]) |
|
201 | 203 | |
|
202 | 204 | # walk down left nodes taking each right node. no recursion to left nodes |
|
203 | 205 | # because infix operators are left-associative, i.e. left tree is deep. |
|
204 | 206 | # e.g. '1 + 2 + 3' -> (+ (+ 1 2) 3) -> (+ 1 2 3) |
|
205 | 207 | simplified = [] |
|
206 | 208 | x = tree |
|
207 | 209 | while x[0] == op: |
|
208 | 210 | l, r = x[1:] |
|
209 | 211 | simplified.append(simplifyinfixops(r, targetnodes)) |
|
210 | 212 | x = l |
|
211 | 213 | simplified.append(simplifyinfixops(x, targetnodes)) |
|
212 | 214 | simplified.append(op) |
|
213 | 215 | return tuple(reversed(simplified)) |
General Comments 0
You need to be logged in to leave comments.
Login now