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, primary, prefix, infix |
15 # suffix actions |
15 # and 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 _ |
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 _hasnewterm(self): |
32 def _hasnewterm(self): |
33 'True if next token may start new term' |
33 'True if next token may start new term' |
34 return bool(self._elements[self.current[0]][1]) |
34 return any(self._elements[self.current[0]][1:3]) |
35 def _match(self, m): |
35 def _match(self, m): |
36 'make sure the tokenizer matches an end condition' |
36 'make sure the tokenizer matches an end condition' |
37 if self.current[0] != m: |
37 if self.current[0] != m: |
38 raise error.ParseError(_("unexpected token: %s") % self.current[0], |
38 raise error.ParseError(_("unexpected token: %s") % self.current[0], |
39 self.current[2]) |
39 self.current[2]) |
48 self._match(m) |
48 self._match(m) |
49 return expr |
49 return expr |
50 def _parse(self, bind=0): |
50 def _parse(self, bind=0): |
51 token, value, pos = self._advance() |
51 token, value, pos = self._advance() |
52 # handle prefix rules on current token |
52 # handle prefix rules on current token |
53 prefix = self._elements[token][1] |
53 primary, prefix = self._elements[token][1:3] |
54 if not prefix: |
54 if primary: |
|
55 expr = (primary, value) |
|
56 elif prefix: |
|
57 expr = (prefix[0], self._parseoperand(*prefix[1:])) |
|
58 else: |
55 raise error.ParseError(_("not a prefix: %s") % token, pos) |
59 raise error.ParseError(_("not a prefix: %s") % token, pos) |
56 if len(prefix) == 1: |
|
57 expr = (prefix[0], value) |
|
58 else: |
|
59 expr = (prefix[0], self._parseoperand(*prefix[1:])) |
|
60 # gather tokens until we meet a lower binding strength |
60 # gather tokens until we meet a lower binding strength |
61 while bind < self._elements[self.current[0]][0]: |
61 while bind < self._elements[self.current[0]][0]: |
62 token, value, pos = self._advance() |
62 token, value, pos = self._advance() |
63 infix, suffix = self._elements[token][2:] |
63 infix, suffix = self._elements[token][3:] |
64 # check for suffix - next token isn't a valid prefix |
64 # check for suffix - next token isn't a valid prefix |
65 if suffix and not self._hasnewterm(): |
65 if suffix and not self._hasnewterm(): |
66 expr = (suffix[0], expr) |
66 expr = (suffix[0], expr) |
67 else: |
67 else: |
68 # handle infix rules |
68 # handle infix rules |