source: rtems-tools/tester/rt/pygdb/spark.py @ b0fa2ae

4.105
Last change on this file since b0fa2ae was b0fa2ae, checked in by Chris Johns <chrisj@…>, on 03/03/16 at 05:46:18

Update rtems-tool to support Python 2 and 3.

Add solaris and netbsd.

Close #2619.
  • Property mode set to 100644
File size: 20.7 KB
Line 
1#  Copyright (c) 1998-2002 John Aycock
2#
3#  Permission is hereby granted, free of charge, to any person obtaining
4#  a copy of this software and associated documentation files (the
5#  "Software"), to deal in the Software without restriction, including
6#  without limitation the rights to use, copy, modify, merge, publish,
7#  distribute, sublicense, and/or sell copies of the Software, and to
8#  permit persons to whom the Software is furnished to do so, subject to
9#  the following conditions:
10#
11#  The above copyright notice and this permission notice shall be
12#  included in all copies or substantial portions of the Software.
13#
14#  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
15#  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
16#  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
17#  IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
18#  CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
19#  TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
20#  SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
21
22from __future__ import print_function
23
24__version__ = 'SPARK-0.7 (pre-alpha-7)'
25
26import re
27import sys
28import string
29
30def _namelist(instance):
31        namelist, namedict, classlist = [], {}, [instance.__class__]
32        for c in classlist:
33                for b in c.__bases__:
34                        classlist.append(b)
35                for name in list(c.__dict__.keys()):
36                        if name not in namedict:
37                                namelist.append(name)
38                                namedict[name] = 1
39        return namelist
40
41class GenericScanner:
42        def __init__(self, flags=0):
43                pattern = self.reflect()
44                self.re = re.compile(pattern, re.VERBOSE|flags)
45
46                self.index2func = {}
47                for name, number in list(self.re.groupindex.items()):
48                        self.index2func[number-1] = getattr(self, 't_' + name)
49
50        def makeRE(self, name):
51                doc = getattr(self, name).__doc__
52                rv = '(?P<%s>%s)' % (name[2:], doc)
53                return rv
54
55        def reflect(self):
56                rv = []
57                for name in _namelist(self):
58                        if name[:2] == 't_' and name != 't_default':
59                                rv.append(self.makeRE(name))
60
61                rv.append(self.makeRE('t_default'))
62                return '|'.join(rv)
63
64        def error(self, s, pos):
65                print("Lexical error at position %s" % pos)
66                raise SystemExit
67
68        def position(self, newpos=None):
69                oldpos = self.pos
70                if newpos is not None:
71                        self.pos = newpos
72                return self.string, oldpos
73
74        def tokenize(self, s):
75                self.string = s
76                self.pos = 0
77                n = len(s)
78                while self.pos < n:
79                        m = self.re.match(s, self.pos)
80                        if m is None:
81                                self.error(s, self.pos)
82
83                        groups = m.groups()
84                        self.pos = m.end()
85                        for i in range(len(groups)):
86                                if groups[i] is not None and i in self.index2func:
87                                        self.index2func[i](groups[i])
88
89        def t_default(self, s):
90                r'( . | \n )+'
91                print("Specification error: unmatched input")
92                raise SystemExit
93
94#
95#  Extracted from GenericParser and made global so that [un]picking works.
96#
97class _State:
98        def __init__(self, stateno, items):
99                self.T, self.complete, self.items = [], [], items
100                self.stateno = stateno
101
102class GenericParser:
103        #
104        #  An Earley parser, as per J. Earley, "An Efficient Context-Free
105        #  Parsing Algorithm", CACM 13(2), pp. 94-102.  Also J. C. Earley,
106        #  "An Efficient Context-Free Parsing Algorithm", Ph.D. thesis,
107        #  Carnegie-Mellon University, August 1968.  New formulation of
108        #  the parser according to J. Aycock, "Practical Earley Parsing
109        #  and the SPARK Toolkit", Ph.D. thesis, University of Victoria,
110        #  2001, and J. Aycock and R. N. Horspool, "Practical Earley
111        #  Parsing", unpublished paper, 2001.
112        #
113
114        def __init__(self, start):
115                self.rules = {}
116                self.rule2func = {}
117                self.rule2name = {}
118                self.collectRules()
119                self.augment(start)
120                self.ruleschanged = 1
121
122        _NULLABLE = '\e_'
123        _START = 'START'
124        _BOF = '|-'
125
126        #
127        #  When pickling, take the time to generate the full state machine;
128        #  some information is then extraneous, too.  Unfortunately we
129        #  can't save the rule2func map.
130        #
131        def __getstate__(self):
132                if self.ruleschanged:
133                        #
134                        #  XXX - duplicated from parse()
135                        #
136                        self.computeNull()
137                        self.newrules = {}
138                        self.new2old = {}
139                        self.makeNewRules()
140                        self.ruleschanged = 0
141                        self.edges, self.cores = {}, {}
142                        self.states = { 0: self.makeState0() }
143                        self.makeState(0, self._BOF)
144                #
145                #  XXX - should find a better way to do this..
146                #
147                changes = 1
148                while changes:
149                        changes = 0
150                        for k, v in list(self.edges.items()):
151                                if v is None:
152                                        state, sym = k
153                                        if state in self.states:
154                                                self.goto(state, sym)
155                                                changes = 1
156                rv = self.__dict__.copy()
157                for s in list(self.states.values()):
158                        del s.items
159                del rv['rule2func']
160                del rv['nullable']
161                del rv['cores']
162                return rv
163
164        def __setstate__(self, D):
165                self.rules = {}
166                self.rule2func = {}
167                self.rule2name = {}
168                self.collectRules()
169                start = D['rules'][self._START][0][1][1]        # Blech.
170                self.augment(start)
171                D['rule2func'] = self.rule2func
172                D['makeSet'] = self.makeSet_fast
173                self.__dict__ = D
174
175        #
176        #  A hook for GenericASTBuilder and GenericASTMatcher.  Mess
177        #  thee not with this; nor shall thee toucheth the _preprocess
178        #  argument to addRule.
179        #
180        def preprocess(self, rule, func):       return rule, func
181
182        def addRule(self, doc, func, _preprocess=1):
183                fn = func
184                rules = doc.split()
185
186                index = []
187                for i in range(len(rules)):
188                        if rules[i] == '::=':
189                                index.append(i-1)
190                index.append(len(rules))
191
192                for i in range(len(index)-1):
193                        lhs = rules[index[i]]
194                        rhs = rules[index[i]+2:index[i+1]]
195                        rule = (lhs, tuple(rhs))
196
197                        if _preprocess:
198                                rule, fn = self.preprocess(rule, func)
199
200                        if lhs in self.rules:
201                                self.rules[lhs].append(rule)
202                        else:
203                                self.rules[lhs] = [ rule ]
204                        self.rule2func[rule] = fn
205                        self.rule2name[rule] = func.__name__[2:]
206                self.ruleschanged = 1
207
208        def collectRules(self):
209                for name in _namelist(self):
210                        if name[:2] == 'p_':
211                                func = getattr(self, name)
212                                doc = func.__doc__
213                                self.addRule(doc, func)
214
215        def augment(self, start):
216                rule = '%s ::= %s %s' % (self._START, self._BOF, start)
217                self.addRule(rule, lambda args: args[1], 0)
218
219        def computeNull(self):
220                self.nullable = {}
221                tbd = []
222
223                for rulelist in list(self.rules.values()):
224                        lhs = rulelist[0][0]
225                        self.nullable[lhs] = 0
226                        for rule in rulelist:
227                                rhs = rule[1]
228                                if len(rhs) == 0:
229                                        self.nullable[lhs] = 1
230                                        continue
231                                #
232                                #  We only need to consider rules which
233                                #  consist entirely of nonterminal symbols.
234                                #  This should be a savings on typical
235                                #  grammars.
236                                #
237                                for sym in rhs:
238                                        if sym not in self.rules:
239                                                break
240                                else:
241                                        tbd.append(rule)
242                changes = 1
243                while changes:
244                        changes = 0
245                        for lhs, rhs in tbd:
246                                if self.nullable[lhs]:
247                                        continue
248                                for sym in rhs:
249                                        if not self.nullable[sym]:
250                                                break
251                                else:
252                                        self.nullable[lhs] = 1
253                                        changes = 1
254
255        def makeState0(self):
256                s0 = _State(0, [])
257                for rule in self.newrules[self._START]:
258                        s0.items.append((rule, 0))
259                return s0
260
261        def finalState(self, tokens):
262                #
263                #  Yuck.
264                #
265                if len(self.newrules[self._START]) == 2 and len(tokens) == 0:
266                        return 1
267                start = self.rules[self._START][0][1][1]
268                return self.goto(1, start)
269
270        def makeNewRules(self):
271                worklist = []
272                for rulelist in list(self.rules.values()):
273                        for rule in rulelist:
274                                worklist.append((rule, 0, 1, rule))
275
276                for rule, i, candidate, oldrule in worklist:
277                        lhs, rhs = rule
278                        n = len(rhs)
279                        while i < n:
280                                sym = rhs[i]
281                                if sym not in self.rules or \
282                                   not self.nullable[sym]:
283                                        candidate = 0
284                                        i = i + 1
285                                        continue
286
287                                newrhs = list(rhs)
288                                newrhs[i] = self._NULLABLE+sym
289                                newrule = (lhs, tuple(newrhs))
290                                worklist.append((newrule, i+1,
291                                                 candidate, oldrule))
292                                candidate = 0
293                                i = i + 1
294                        else:
295                                if candidate:
296                                        lhs = self._NULLABLE+lhs
297                                        rule = (lhs, rhs)
298                                if lhs in self.newrules:
299                                        self.newrules[lhs].append(rule)
300                                else:
301                                        self.newrules[lhs] = [ rule ]
302                                self.new2old[rule] = oldrule
303
304        def typestring(self, token):
305                return None
306
307        def error(self, token):
308                print("Syntax error at or near `%s' token" % token)
309                raise SystemExit
310
311        def parse(self, tokens):
312                sets = [ [(1,0), (2,0)] ]
313                self.links = {}
314
315                if self.ruleschanged:
316                        self.computeNull()
317                        self.newrules = {}
318                        self.new2old = {}
319                        self.makeNewRules()
320                        self.ruleschanged = 0
321                        self.edges, self.cores = {}, {}
322                        self.states = { 0: self.makeState0() }
323                        self.makeState(0, self._BOF)
324
325                for i in range(len(tokens)):
326                        sets.append([])
327
328                        if sets[i] == []:
329                                break
330                        self.makeSet(tokens[i], sets, i)
331                else:
332                        sets.append([])
333                        self.makeSet(None, sets, len(tokens))
334
335                #_dump(tokens, sets, self.states)
336
337                finalitem = (self.finalState(tokens), 0)
338                if finalitem not in sets[-2]:
339                        if len(tokens) > 0:
340                                self.error(tokens[i-1], i, tokens)
341                        else:
342                                self.error(None)
343
344                return self.buildTree(self._START, finalitem,
345                                      tokens, len(sets)-2)
346
347        def isnullable(self, sym):
348                #
349                #  For symbols in G_e only.  If we weren't supporting 1.5,
350                #  could just use sym.startswith().
351                #
352                return self._NULLABLE == sym[0:len(self._NULLABLE)]
353
354        def skip(self, xxx_todo_changeme, pos=0):
355                (lhs, rhs) = xxx_todo_changeme
356                n = len(rhs)
357                while pos < n:
358                        if not self.isnullable(rhs[pos]):
359                                break
360                        pos = pos + 1
361                return pos
362
363        def makeState(self, state, sym):
364                assert sym is not None
365                #
366                #  Compute \epsilon-kernel state's core and see if
367                #  it exists already.
368                #
369                kitems = []
370                for rule, pos in self.states[state].items:
371                        lhs, rhs = rule
372                        if rhs[pos:pos+1] == (sym,):
373                                kitems.append((rule, self.skip(rule, pos+1)))
374                core = kitems
375
376                core.sort()
377                tcore = tuple(core)
378                if tcore in self.cores:
379                        return self.cores[tcore]
380                #
381                #  Nope, doesn't exist.  Compute it and the associated
382                #  \epsilon-nonkernel state together; we'll need it right away.
383                #
384                k = self.cores[tcore] = len(self.states)
385                K, NK = _State(k, kitems), _State(k+1, [])
386                self.states[k] = K
387                predicted = {}
388
389                edges = self.edges
390                rules = self.newrules
391                for X in K, NK:
392                        worklist = X.items
393                        for item in worklist:
394                                rule, pos = item
395                                lhs, rhs = rule
396                                if pos == len(rhs):
397                                        X.complete.append(rule)
398                                        continue
399
400                                nextSym = rhs[pos]
401                                key = (X.stateno, nextSym)
402                                if nextSym not in rules:
403                                        if key not in edges:
404                                                edges[key] = None
405                                                X.T.append(nextSym)
406                                else:
407                                        edges[key] = None
408                                        if nextSym not in predicted:
409                                                predicted[nextSym] = 1
410                                                for prule in rules[nextSym]:
411                                                        ppos = self.skip(prule)
412                                                        new = (prule, ppos)
413                                                        NK.items.append(new)
414                        #
415                        #  Problem: we know K needs generating, but we
416                        #  don't yet know about NK.  Can't commit anything
417                        #  regarding NK to self.edges until we're sure.  Should
418                        #  we delay committing on both K and NK to avoid this
419                        #  hacky code?  This creates other problems..
420                        #
421                        if X is K:
422                                edges = {}
423
424                if NK.items == []:
425                        return k
426
427                #
428                #  Check for \epsilon-nonkernel's core.  Unfortunately we
429                #  need to know the entire set of predicted nonterminals
430                #  to do this without accidentally duplicating states.
431                #
432                core = list(predicted.keys())
433                core.sort()
434                tcore = tuple(core)
435                if tcore in self.cores:
436                        self.edges[(k, None)] = self.cores[tcore]
437                        return k
438
439                nk = self.cores[tcore] = self.edges[(k, None)] = NK.stateno
440                self.edges.update(edges)
441                self.states[nk] = NK
442                return k
443
444        def goto(self, state, sym):
445                key = (state, sym)
446                if key not in self.edges:
447                        #
448                        #  No transitions from state on sym.
449                        #
450                        return None
451
452                rv = self.edges[key]
453                if rv is None:
454                        #
455                        #  Target state isn't generated yet.  Remedy this.
456                        #
457                        rv = self.makeState(state, sym)
458                        self.edges[key] = rv
459                return rv
460
461        def gotoT(self, state, t):
462                return [self.goto(state, t)]
463
464        def gotoST(self, state, st):
465                rv = []
466                for t in self.states[state].T:
467                        if st == t:
468                                rv.append(self.goto(state, t))
469                return rv
470
471        def add(self, set, item, i=None, predecessor=None, causal=None):
472                if predecessor is None:
473                        if item not in set:
474                                set.append(item)
475                else:
476                        key = (item, i)
477                        if item not in set:
478                                self.links[key] = []
479                                set.append(item)
480                        self.links[key].append((predecessor, causal))
481
482        def makeSet(self, token, sets, i):
483                cur, next = sets[i], sets[i+1]
484
485                ttype = token is not None and self.typestring(token) or None
486                if ttype is not None:
487                        fn, arg = self.gotoT, ttype
488                else:
489                        fn, arg = self.gotoST, token
490
491                for item in cur:
492                        ptr = (item, i)
493                        state, parent = item
494                        add = fn(state, arg)
495                        for k in add:
496                                if k is not None:
497                                        self.add(next, (k, parent), i+1, ptr)
498                                        nk = self.goto(k, None)
499                                        if nk is not None:
500                                                self.add(next, (nk, i+1))
501
502                        if parent == i:
503                                continue
504
505                        for rule in self.states[state].complete:
506                                lhs, rhs = rule
507                                for pitem in sets[parent]:
508                                        pstate, pparent = pitem
509                                        k = self.goto(pstate, lhs)
510                                        if k is not None:
511                                                why = (item, i, rule)
512                                                pptr = (pitem, parent)
513                                                self.add(cur, (k, pparent),
514                                                         i, pptr, why)
515                                                nk = self.goto(k, None)
516                                                if nk is not None:
517                                                        self.add(cur, (nk, i))
518
519        def makeSet_fast(self, token, sets, i):
520                #
521                #  Call *only* when the entire state machine has been built!
522                #  It relies on self.edges being filled in completely, and
523                #  then duplicates and inlines code to boost speed at the
524                #  cost of extreme ugliness.
525                #
526                cur, next = sets[i], sets[i+1]
527                ttype = token is not None and self.typestring(token) or None
528
529                for item in cur:
530                        ptr = (item, i)
531                        state, parent = item
532                        if ttype is not None:
533                                k = self.edges.get((state, ttype), None)
534                                if k is not None:
535                                        #self.add(next, (k, parent), i+1, ptr)
536                                        #INLINED --v
537                                        new = (k, parent)
538                                        key = (new, i+1)
539                                        if new not in next:
540                                                self.links[key] = []
541                                                next.append(new)
542                                        self.links[key].append((ptr, None))
543                                        #INLINED --^
544                                        #nk = self.goto(k, None)
545                                        nk = self.edges.get((k, None), None)
546                                        if nk is not None:
547                                                #self.add(next, (nk, i+1))
548                                                #INLINED --v
549                                                new = (nk, i+1)
550                                                if new not in next:
551                                                        next.append(new)
552                                                #INLINED --^
553                        else:
554                                add = self.gotoST(state, token)
555                                for k in add:
556                                        if k is not None:
557                                                self.add(next, (k, parent), i+1, ptr)
558                                                #nk = self.goto(k, None)
559                                                nk = self.edges.get((k, None), None)
560                                                if nk is not None:
561                                                        self.add(next, (nk, i+1))
562
563                        if parent == i:
564                                continue
565
566                        for rule in self.states[state].complete:
567                                lhs, rhs = rule
568                                for pitem in sets[parent]:
569                                        pstate, pparent = pitem
570                                        #k = self.goto(pstate, lhs)
571                                        k = self.edges.get((pstate, lhs), None)
572                                        if k is not None:
573                                                why = (item, i, rule)
574                                                pptr = (pitem, parent)
575                                                #self.add(cur, (k, pparent),
576                                                #        i, pptr, why)
577                                                #INLINED --v
578                                                new = (k, pparent)
579                                                key = (new, i)
580                                                if new not in cur:
581                                                        self.links[key] = []
582                                                        cur.append(new)
583                                                self.links[key].append((pptr, why))
584                                                #INLINED --^
585                                                #nk = self.goto(k, None)
586                                                nk = self.edges.get((k, None), None)
587                                                if nk is not None:
588                                                        #self.add(cur, (nk, i))
589                                                        #INLINED --v
590                                                        new = (nk, i)
591                                                        if new not in cur:
592                                                                cur.append(new)
593                                                        #INLINED --^
594
595        def predecessor(self, key, causal):
596                for p, c in self.links[key]:
597                        if c == causal:
598                                return p
599                assert 0
600
601        def causal(self, key):
602                links = self.links[key]
603                if len(links) == 1:
604                        return links[0][1]
605                choices = []
606                rule2cause = {}
607                for p, c in links:
608                        rule = c[2]
609                        choices.append(rule)
610                        rule2cause[rule] = c
611                return rule2cause[self.ambiguity(choices)]
612
613        def deriveEpsilon(self, nt):
614                if len(self.newrules[nt]) > 1:
615                        rule = self.ambiguity(self.newrules[nt])
616                else:
617                        rule = self.newrules[nt][0]
618                #print rule
619
620                rhs = rule[1]
621                attr = [None] * len(rhs)
622
623                for i in range(len(rhs)-1, -1, -1):
624                        attr[i] = self.deriveEpsilon(rhs[i])
625                return self.rule2func[self.new2old[rule]](attr)
626
627        def buildTree(self, nt, item, tokens, k):
628                state, parent = item
629
630                choices = []
631                for rule in self.states[state].complete:
632                        if rule[0] == nt:
633                                choices.append(rule)
634                rule = choices[0]
635                if len(choices) > 1:
636                        rule = self.ambiguity(choices)
637                #print rule
638
639                rhs = rule[1]
640                attr = [None] * len(rhs)
641
642                for i in range(len(rhs)-1, -1, -1):
643                        sym = rhs[i]
644                        if sym not in self.newrules:
645                                if sym != self._BOF:
646                                        attr[i] = tokens[k-1]
647                                        key = (item, k)
648                                        item, k = self.predecessor(key, None)
649                        #elif self.isnullable(sym):
650                        elif self._NULLABLE == sym[0:len(self._NULLABLE)]:
651                                attr[i] = self.deriveEpsilon(sym)
652                        else:
653                                key = (item, k)
654                                why = self.causal(key)
655                                attr[i] = self.buildTree(sym, why[0],
656                                                         tokens, why[1])
657                                item, k = self.predecessor(key, why)
658                return self.rule2func[self.new2old[rule]](attr)
659
660        def ambiguity(self, rules):
661                #
662                #  XXX - problem here and in collectRules() if the same rule
663                #        appears in >1 method.  Also undefined results if rules
664                #        causing the ambiguity appear in the same method.
665                #
666                sortlist = []
667                name2index = {}
668                for i in range(len(rules)):
669                        lhs, rhs = rule = rules[i]
670                        name = self.rule2name[self.new2old[rule]]
671                        sortlist.append((len(rhs), name))
672                        name2index[name] = i
673                sortlist.sort()
674                list = [a_b[1] for a_b in sortlist]
675                return rules[name2index[self.resolve(list)]]
676
677        def resolve(self, list):
678                #
679                #  Resolve ambiguity in favor of the shortest RHS.
680                #  Since we walk the tree from the top down, this
681                #  should effectively resolve in favor of a "shift".
682                #
683                return list[0]
684
685#
686#  GenericASTBuilder automagically constructs a concrete/abstract syntax tree
687#  for a given input.  The extra argument is a class (not an instance!)
688#  which supports the "__setslice__" and "__len__" methods.
689#
690#  XXX - silently overrides any user code in methods.
691#
692
693class GenericASTBuilder(GenericParser):
694        def __init__(self, AST, start):
695                GenericParser.__init__(self, start)
696                self.AST = AST
697
698        def preprocess(self, rule, func):
699                rebind = lambda lhs, self=self: \
700                                lambda args, lhs=lhs, self=self: \
701                                        self.buildASTNode(args, lhs)
702                lhs, rhs = rule
703                return rule, rebind(lhs)
704
705        def buildASTNode(self, args, lhs):
706                children = []
707                for arg in args:
708                        if isinstance(arg, self.AST):
709                                children.append(arg)
710                        else:
711                                children.append(self.terminal(arg))
712                return self.nonterminal(lhs, children)
713
714        def terminal(self, token):      return token
715
716        def nonterminal(self, type, args):
717                rv = self.AST(type)
718                rv[:len(args)] = args
719                return rv
720
721#
722#  GenericASTTraversal is a Visitor pattern according to Design Patterns.  For
723#  each node it attempts to invoke the method n_<node type>, falling
724#  back onto the default() method if the n_* can't be found.  The preorder
725#  traversal also looks for an exit hook named n_<node type>_exit (no default
726#  routine is called if it's not found).  To prematurely halt traversal
727#  of a subtree, call the prune() method -- this only makes sense for a
728#  preorder traversal.  Node type is determined via the typestring() method.
729#
730
731class GenericASTTraversalPruningException:
732        pass
733
734class GenericASTTraversal:
735        def __init__(self, ast):
736                self.ast = ast
737
738        def typestring(self, node):
739                return node.type
740
741        def prune(self):
742                raise GenericASTTraversalPruningException
743
744        def preorder(self, node=None):
745                if node is None:
746                        node = self.ast
747
748                try:
749                        name = 'n_' + self.typestring(node)
750                        if hasattr(self, name):
751                                func = getattr(self, name)
752                                func(node)
753                        else:
754                                self.default(node)
755                except GenericASTTraversalPruningException:
756                        return
757
758                for kid in node:
759                        self.preorder(kid)
760
761                name = name + '_exit'
762                if hasattr(self, name):
763                        func = getattr(self, name)
764                        func(node)
765
766        def postorder(self, node=None):
767                if node is None:
768                        node = self.ast
769
770                for kid in node:
771                        self.postorder(kid)
772
773                name = 'n_' + self.typestring(node)
774                if hasattr(self, name):
775                        func = getattr(self, name)
776                        func(node)
777                else:
778                        self.default(node)
779
780
781        def default(self, node):
782                pass
783
784#
785#  GenericASTMatcher.  AST nodes must have "__getitem__" and "__cmp__"
786#  implemented.
787#
788#  XXX - makes assumptions about how GenericParser walks the parse tree.
789#
790
791class GenericASTMatcher(GenericParser):
792        def __init__(self, start, ast):
793                GenericParser.__init__(self, start)
794                self.ast = ast
795
796        def preprocess(self, rule, func):
797                rebind = lambda func, self=self: \
798                                lambda args, func=func, self=self: \
799                                        self.foundMatch(args, func)
800                lhs, rhs = rule
801                rhslist = list(rhs)
802                rhslist.reverse()
803
804                return (lhs, tuple(rhslist)), rebind(func)
805
806        def foundMatch(self, args, func):
807                func(args[-1])
808                return args[-1]
809
810        def match_r(self, node):
811                self.input.insert(0, node)
812                children = 0
813
814                for child in node:
815                        if children == 0:
816                                self.input.insert(0, '(')
817                        children = children + 1
818                        self.match_r(child)
819
820                if children > 0:
821                        self.input.insert(0, ')')
822
823        def match(self, ast=None):
824                if ast is None:
825                        ast = self.ast
826                self.input = []
827
828                self.match_r(ast)
829                self.parse(self.input)
830
831        def resolve(self, list):
832                #
833                #  Resolve ambiguity in favor of the longest RHS.
834                #
835                return list[-1]
836
837def _dump(tokens, sets, states):
838        for i in range(len(sets)):
839                print('set', i)
840                for item in sets[i]:
841                        print('\t', item)
842                        for (lhs, rhs), pos in states[item[0]].items:
843                                print('\t\t', lhs, '::=', end=' ')
844                                print(string.join(rhs[:pos]), end=' ')
845                                print('.', end=' ')
846                                print(string.join(rhs[pos:]))
847                if i < len(tokens):
848                        print()
849                        print('token', str(tokens[i]))
850                        print()
Note: See TracBrowser for help on using the repository browser.