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