Lib/compiler/transformer.py

   1 """Parse tree transformation module.
   2
   3 Transforms Python source code into an abstract syntax tree (AST)
   4 defined in the ast module.
   5
   6 The simplest ways to invoke this module are via parse and parseFile.
   7 parse(buf) -> AST
   8 parseFile(path) -> AST
   9 """
  10
  11 # Original version written by Greg Stein (gstein@lyra.org)
  12 #                         and Bill Tutt (rassilon@lima.mudlib.org)
  13 # February 1997.
  14 #
  15 # Modifications and improvements for Python 2.0 by Jeremy Hylton and
  16 # Mark Hammond
  17 #
  18 # Some fixes to try to have correct line number on almost all nodes
  19 # (except Module, Discard and Stmt) added by Sylvain Thenault
  20 #
  21 # Portions of this file are:
  22 # Copyright (C) 1997-1998 Greg Stein. All Rights Reserved.
  23 #
  24 # This module is provided under a BSD-ish license. See
  25 #   http://www.opensource.org/licenses/bsd-license.html
  26 # and replace OWNER, ORGANIZATION, and YEAR as appropriate.
  27
  28 from compiler.ast import *
  29 import parser
  30 import symbol
  31 import token
  32
  33 class WalkerError(StandardError):
  34     pass
  35
  36 from compiler.consts import CO_VARARGS, CO_VARKEYWORDS
  37 from compiler.consts import OP_ASSIGN, OP_DELETE, OP_APPLY
  38
  39 def parseFile(path):
  40     f = open(path, "U")
  41     # XXX The parser API tolerates files without a trailing newline,
  42     # but not strings without a trailing newline.  Always add an extra
  43     # newline to the file contents, since we're going through the string
  44     # version of the API.
  45     src = f.read() + "\n"
  46     f.close()
  47     return parse(src)
  48
  49 def parse(buf, mode="exec"):
  50     if mode == "exec" or mode == "single":
  51         return Transformer().parsesuite(buf)
  52     elif mode == "eval":
  53         return Transformer().parseexpr(buf)
  54     else:
  55         raise ValueError("compile() arg 3 must be"
  56                          " 'exec' or 'eval' or 'single'")
  57
  58 def asList(nodes):
  59     l = []
  60     for item in nodes:
  61         if hasattr(item, "asList"):
  62             l.append(item.asList())
  63         else:
  64             if type(item) is type( (None, None) ):
  65                 l.append(tuple(asList(item)))
  66             elif type(item) is type( [] ):
  67                 l.append(asList(item))
  68             else:
  69                 l.append(item)
  70     return l
  71
  72 def extractLineNo(ast):
  73     if not isinstance(ast[1], tuple):
  74         # get a terminal node
  75         return ast[2]
  76     for child in ast[1:]:
  77         if isinstance(child, tuple):
  78             lineno = extractLineNo(child)
  79             if lineno is not None:
  80                 return lineno
  81
  82 def Node(*args):
  83     kind = args[0]
  84     if kind in nodes:
  85         try:
  86             return nodes[kind](*args[1:])
  87         except TypeError:
  88             print nodes[kind], len(args), args
  89             raise
  90     else:
  91         raise WalkerError, "Can't find appropriate Node type: %s" % str(args)
  92         #return apply(ast.Node, args)
  93
  94 class Transformer:
  95     """Utility object for transforming Python parse trees.
  96
  97     Exposes the following methods:
  98         tree = transform(ast_tree)
  99         tree = parsesuite(text)
 100         tree = parseexpr(text)
 101         tree = parsefile(fileob | filename)
 102     """
 103
 104     def __init__(self):
 105         self._dispatch = {}
 106         for value, name in symbol.sym_name.items():
 107             if hasattr(self, name):
 108                 self._dispatch[value] = getattr(self, name)
 109         self._dispatch[token.NEWLINE] = self.com_NEWLINE
 110         self._atom_dispatch = {token.LPAR: self.atom_lpar,
 111                                token.LSQB: self.atom_lsqb,
 112                                token.LBRACE: self.atom_lbrace,
 113                                token.BACKQUOTE: self.atom_backquote,
 114                                token.NUMBER: self.atom_number,
 115                                token.STRING: self.atom_string,
 116                                token.NAME: self.atom_name,
 117                                }
 118         self.encoding = None
 119
 120     def transform(self, tree):
 121         """Transform an AST into a modified parse tree."""
 122         if not (isinstance(tree, tuple) or isinstance(tree, list)):
 123             tree = parser.st2tuple(tree, line_info=1)
 124         return self.compile_node(tree)
 125
 126     def parsesuite(self, text):
 127         """Return a modified parse tree for the given suite text."""
 128         return self.transform(parser.suite(text))
 129
 130     def parseexpr(self, text):
 131         """Return a modified parse tree for the given expression text."""
 132         return self.transform(parser.expr(text))
 133
 134     def parsefile(self, file):
 135         """Return a modified parse tree for the contents of the given file."""
 136         if type(file) == type(''):
 137             file = open(file)
 138         return self.parsesuite(file.read())
 139
 140     # --------------------------------------------------------------
 141     #
 142     # PRIVATE METHODS
 143     #
 144
 145     def compile_node(self, node):
 146         ### emit a line-number node?
 147         n = node[0]
 148
 149         if n == symbol.encoding_decl:
 150             self.encoding = node[2]
 151             node = node[1]
 152             n = node[0]
 153
 154         if n == symbol.single_input:
 155             return self.single_input(node[1:])
 156         if n == symbol.file_input:
 157             return self.file_input(node[1:])
 158         if n == symbol.eval_input:
 159             return self.eval_input(node[1:])
 160         if n == symbol.lambdef:
 161             return self.lambdef(node[1:])
 162         if n == symbol.funcdef:
 163             return self.funcdef(node[1:])
 164         if n == symbol.classdef:
 165             return self.classdef(node[1:])
 166
 167         raise WalkerError, ('unexpected node type', n)
 168
 169     def single_input(self, node):
 170         ### do we want to do anything about being "interactive" ?
 171
 172         # NEWLINE | simple_stmt | compound_stmt NEWLINE
 173         n = node[0][0]
 174         if n != token.NEWLINE:
 175             return self.com_stmt(node[0])
 176
 177         return Pass()
 178
 179     def file_input(self, nodelist):
 180         doc = self.get_docstring(nodelist, symbol.file_input)
 181         if doc is not None:
 182             i = 1
 183         else:
 184             i = 0
 185         stmts = []
 186         for node in nodelist[i:]:
 187             if node[0] != token.ENDMARKER and node[0] != token.NEWLINE:
 188                 self.com_append_stmt(stmts, node)
 189         return Module(doc, Stmt(stmts))
 190
 191     def eval_input(self, nodelist):
 192         # from the built-in function input()
 193         ### is this sufficient?
 194         return Expression(self.com_node(nodelist[0]))
 195
 196     def decorator_name(self, nodelist):
 197         listlen = len(nodelist)
 198         assert listlen >= 1 and listlen % 2 == 1
 199
 200         item = self.atom_name(nodelist)
 201         i = 1
 202         while i < listlen:
 203             assert nodelist[i][0] == token.DOT
 204             assert nodelist[i + 1][0] == token.NAME
 205             item = Getattr(item, nodelist[i + 1][1])
 206             i += 2
 207
 208         return item
 209
 210     def decorator(self, nodelist):
 211         # '@' dotted_name [ '(' [arglist] ')' ]
 212         assert len(nodelist) in (3, 5, 6)
 213         assert nodelist[0][0] == token.AT
 214         assert nodelist[-1][0] == token.NEWLINE
 215
 216         assert nodelist[1][0] == symbol.dotted_name
 217         funcname = self.decorator_name(nodelist[1][1:])
 218
 219         if len(nodelist) > 3:
 220             assert nodelist[2][0] == token.LPAR
 221             expr = self.com_call_function(funcname, nodelist[3])
 222         else:
 223             expr = funcname
 224
 225         return expr
 226
 227     def decorators(self, nodelist):
 228         # decorators: decorator ([NEWLINE] decorator)* NEWLINE
 229         items = []
 230         for dec_nodelist in nodelist:
 231             assert dec_nodelist[0] == symbol.decorator
 232             items.append(self.decorator(dec_nodelist[1:]))
 233         return Decorators(items)
 234
 235     def decorated(self, nodelist):
 236         assert nodelist[0][0] == symbol.decorators
 237         if nodelist[1][0] == symbol.funcdef:
 238             n = [nodelist[0]] + list(nodelist[1][1:])
 239             return self.funcdef(n)
 240         elif nodelist[1][0] == symbol.classdef:
 241             decorators = self.decorators(nodelist[0][1:])
 242             cls = self.classdef(nodelist[1][1:])
 243             cls.decorators = decorators
 244             return cls
 245         raise WalkerError()
 246
 247     def funcdef(self, nodelist):
 248         #                    -6   -5    -4         -3  -2    -1
 249         # funcdef: [decorators] 'def' NAME parameters ':' suite
 250         # parameters: '(' [varargslist] ')'
 251
 252         if len(nodelist) == 6:
 253             assert nodelist[0][0] == symbol.decorators
 254             decorators = self.decorators(nodelist[0][1:])
 255         else:
 256             assert len(nodelist) == 5
 257             decorators = None
 258
 259         lineno = nodelist[-4][2]
 260         name = nodelist[-4][1]
 261         args = nodelist[-3][2]
 262
 263         if args[0] == symbol.varargslist:
 264             names, defaults, flags = self.com_arglist(args[1:])
 265         else:
 266             names = defaults = ()
 267             flags = 0
 268         doc = self.get_docstring(nodelist[-1])
 269
 270         # code for function
 271         code = self.com_node(nodelist[-1])
 272
 273         if doc is not None:
 274             assert isinstance(code, Stmt)
 275             assert isinstance(code.nodes[0], Discard)
 276             del code.nodes[0]
 277         return Function(decorators, name, names, defaults, flags, doc, code,
 278                      lineno=lineno)
 279
 280     def lambdef(self, nodelist):
 281         # lambdef: 'lambda' [varargslist] ':' test
 282         if nodelist[2][0] == symbol.varargslist:
 283             names, defaults, flags = self.com_arglist(nodelist[2][1:])
 284         else:
 285             names = defaults = ()
 286             flags = 0
 287
 288         # code for lambda
 289         code = self.com_node(nodelist[-1])
 290
 291         return Lambda(names, defaults, flags, code, lineno=nodelist[1][2])
 292     old_lambdef = lambdef
 293
 294     def classdef(self, nodelist):
 295         # classdef: 'class' NAME ['(' [testlist] ')'] ':' suite
 296
 297         name = nodelist[1][1]
 298         doc = self.get_docstring(nodelist[-1])
 299         if nodelist[2][0] == token.COLON:
 300             bases = []
 301         elif nodelist[3][0] == token.RPAR:
 302             bases = []
 303         else:
 304             bases = self.com_bases(nodelist[3])
 305
 306         # code for class
 307         code = self.com_node(nodelist[-1])
 308
 309         if doc is not None:
 310             assert isinstance(code, Stmt)
 311             assert isinstance(code.nodes[0], Discard)
 312             del code.nodes[0]
 313
 314         return Class(name, bases, doc, code, lineno=nodelist[1][2])
 315
 316     def stmt(self, nodelist):
 317         return self.com_stmt(nodelist[0])
 318
 319     small_stmt = stmt
 320     flow_stmt = stmt
 321     compound_stmt = stmt
 322
 323     def simple_stmt(self, nodelist):
 324         # small_stmt (';' small_stmt)* [';'] NEWLINE
 325         stmts = []
 326         for i in range(0, len(nodelist), 2):
 327             self.com_append_stmt(stmts, nodelist[i])
 328         return Stmt(stmts)
 329
 330     def parameters(self, nodelist):
 331         raise WalkerError
 332
 333     def varargslist(self, nodelist):
 334         raise WalkerError
 335
 336     def fpdef(self, nodelist):
 337         raise WalkerError
 338
 339     def fplist(self, nodelist):
 340         raise WalkerError
 341
 342     def dotted_name(self, nodelist):
 343         raise WalkerError
 344
 345     def comp_op(self, nodelist):
 346         raise WalkerError
 347
 348     def trailer(self, nodelist):
 349         raise WalkerError
 350
 351     def sliceop(self, nodelist):
 352         raise WalkerError
 353
 354     def argument(self, nodelist):
 355         raise WalkerError
 356
 357     # --------------------------------------------------------------
 358     #
 359     # STATEMENT NODES  (invoked by com_node())
 360     #
 361
 362     def expr_stmt(self, nodelist):
 363         # augassign testlist | testlist ('=' testlist)*
 364         en = nodelist[-1]
 365         exprNode = self.lookup_node(en)(en[1:])
 366         if len(nodelist) == 1:
 367             return Discard(exprNode, lineno=exprNode.lineno)
 368         if nodelist[1][0] == token.EQUAL:
 369             nodesl = []
 370             for i in range(0, len(nodelist) - 2, 2):
 371                 nodesl.append(self.com_assign(nodelist[i], OP_ASSIGN))
 372             return Assign(nodesl, exprNode, lineno=nodelist[1][2])
 373         else:
 374             lval = self.com_augassign(nodelist[0])
 375             op = self.com_augassign_op(nodelist[1])
 376             return AugAssign(lval, op[1], exprNode, lineno=op[2])
 377         raise WalkerError, "can't get here"
 378
 379     def print_stmt(self, nodelist):
 380         # print ([ test (',' test)* [','] ] | '>>' test [ (',' test)+ [','] ])
 381         items = []
 382         if len(nodelist) == 1:
 383             start = 1
 384             dest = None
 385         elif nodelist[1][0] == token.RIGHTSHIFT:
 386             assert len(nodelist) == 3 \
 387                    or nodelist[3][0] == token.COMMA
 388             dest = self.com_node(nodelist[2])
 389             start = 4
 390         else:
 391             dest = None
 392             start = 1
 393         for i in range(start, len(nodelist), 2):
 394             items.append(self.com_node(nodelist[i]))
 395         if nodelist[-1][0] == token.COMMA:
 396             return Print(items, dest, lineno=nodelist[0][2])
 397         return Printnl(items, dest, lineno=nodelist[0][2])
 398
 399     def del_stmt(self, nodelist):
 400         return self.com_assign(nodelist[1], OP_DELETE)
 401
 402     def pass_stmt(self, nodelist):
 403         return Pass(lineno=nodelist[0][2])
 404
 405     def break_stmt(self, nodelist):
 406         return Break(lineno=nodelist[0][2])
 407
 408     def continue_stmt(self, nodelist):
 409         return Continue(lineno=nodelist[0][2])
 410
 411     def return_stmt(self, nodelist):
 412         # return: [testlist]
 413         if len(nodelist) < 2:
 414             return Return(Const(None), lineno=nodelist[0][2])
 415         return Return(self.com_node(nodelist[1]), lineno=nodelist[0][2])
 416
 417     def yield_stmt(self, nodelist):
 418         expr = self.com_node(nodelist[0])
 419         return Discard(expr, lineno=expr.lineno)
 420
 421     def yield_expr(self, nodelist):
 422         if len(nodelist) > 1:
 423             value = self.com_node(nodelist[1])
 424         else:
 425             value = Const(None)
 426         return Yield(value, lineno=nodelist[0][2])
 427
 428     def raise_stmt(self, nodelist):
 429         # raise: [test [',' test [',' test]]]
 430         if len(nodelist) > 5:
 431             expr3 = self.com_node(nodelist[5])
 432         else:
 433             expr3 = None
 434         if len(nodelist) > 3:
 435             expr2 = self.com_node(nodelist[3])
 436         else:
 437             expr2 = None
 438         if len(nodelist) > 1:
 439             expr1 = self.com_node(nodelist[1])
 440         else:
 441             expr1 = None
 442         return Raise(expr1, expr2, expr3, lineno=nodelist[0][2])
 443
 444     def import_stmt(self, nodelist):
 445         # import_stmt: import_name | import_from
 446         assert len(nodelist) == 1
 447         return self.com_node(nodelist[0])
 448
 449     def import_name(self, nodelist):
 450         # import_name: 'import' dotted_as_names
 451         return Import(self.com_dotted_as_names(nodelist[1]),
 452                       lineno=nodelist[0][2])
 453
 454     def import_from(self, nodelist):
 455         # import_from: 'from' ('.'* dotted_name | '.') 'import' ('*' |
 456         #    '(' import_as_names ')' | import_as_names)
 457         assert nodelist[0][1] == 'from'
 458         idx = 1
 459         while nodelist[idx][1] == '.':
 460             idx += 1
 461         level = idx - 1
 462         if nodelist[idx][0] == symbol.dotted_name:
 463             fromname = self.com_dotted_name(nodelist[idx])
 464             idx += 1
 465         else:
 466             fromname = ""
 467         assert nodelist[idx][1] == 'import'
 468         if nodelist[idx + 1][0] == token.STAR:
 469             return From(fromname, [('*', None)], level,
 470                         lineno=nodelist[0][2])
 471         else:
 472             node = nodelist[idx + 1 + (nodelist[idx + 1][0] == token.LPAR)]
 473             return From(fromname, self.com_import_as_names(node), level,
 474                         lineno=nodelist[0][2])
 475
 476     def global_stmt(self, nodelist):
 477         # global: NAME (',' NAME)*
 478         names = []
 479         for i in range(1, len(nodelist), 2):
 480             names.append(nodelist[i][1])
 481         return Global(names, lineno=nodelist[0][2])
 482
 483     def exec_stmt(self, nodelist):
 484         # exec_stmt: 'exec' expr ['in' expr [',' expr]]
 485         expr1 = self.com_node(nodelist[1])
 486         if len(nodelist) >= 4:
 487             expr2 = self.com_node(nodelist[3])
 488             if len(nodelist) >= 6:
 489                 expr3 = self.com_node(nodelist[5])
 490             else:
 491                 expr3 = None
 492         else:
 493             expr2 = expr3 = None
 494
 495         return Exec(expr1, expr2, expr3, lineno=nodelist[0][2])
 496
 497     def assert_stmt(self, nodelist):
 498         # 'assert': test, [',' test]
 499         expr1 = self.com_node(nodelist[1])
 500         if (len(nodelist) == 4):
 501             expr2 = self.com_node(nodelist[3])
 502         else:
 503             expr2 = None
 504         return Assert(expr1, expr2, lineno=nodelist[0][2])
 505
 506     def if_stmt(self, nodelist):
 507         # if: test ':' suite ('elif' test ':' suite)* ['else' ':' suite]
 508         tests = []
 509         for i in range(0, len(nodelist) - 3, 4):
 510             testNode = self.com_node(nodelist[i + 1])
 511             suiteNode = self.com_node(nodelist[i + 3])
 512             tests.append((testNode, suiteNode))
 513
 514         if len(nodelist) % 4 == 3:
 515             elseNode = self.com_node(nodelist[-1])
 516 ##      elseNode.lineno = nodelist[-1][1][2]
 517         else:
 518             elseNode = None
 519         return If(tests, elseNode, lineno=nodelist[0][2])
 520
 521     def while_stmt(self, nodelist):
 522         # 'while' test ':' suite ['else' ':' suite]
 523
 524         testNode = self.com_node(nodelist[1])
 525         bodyNode = self.com_node(nodelist[3])
 526
 527         if len(nodelist) > 4:
 528             elseNode = self.com_node(nodelist[6])
 529         else:
 530             elseNode = None
 531
 532         return While(testNode, bodyNode, elseNode, lineno=nodelist[0][2])
 533
 534     def for_stmt(self, nodelist):
 535         # 'for' exprlist 'in' exprlist ':' suite ['else' ':' suite]
 536
 537         assignNode = self.com_assign(nodelist[1], OP_ASSIGN)
 538         listNode = self.com_node(nodelist[3])
 539         bodyNode = self.com_node(nodelist[5])
 540
 541         if len(nodelist) > 8:
 542             elseNode = self.com_node(nodelist[8])
 543         else:
 544             elseNode = None
 545
 546         return For(assignNode, listNode, bodyNode, elseNode,
 547                    lineno=nodelist[0][2])
 548
 549     def try_stmt(self, nodelist):
 550         return self.com_try_except_finally(nodelist)
 551
 552     def with_stmt(self, nodelist):
 553         return self.com_with(nodelist)
 554
 555     def with_var(self, nodelist):
 556         return self.com_with_var(nodelist)
 557
 558     def suite(self, nodelist):
 559         # simple_stmt | NEWLINE INDENT NEWLINE* (stmt NEWLINE*)+ DEDENT
 560         if len(nodelist) == 1:
 561             return self.com_stmt(nodelist[0])
 562
 563         stmts = []
 564         for node in nodelist:
 565             if node[0] == symbol.stmt:
 566                 self.com_append_stmt(stmts, node)
 567         return Stmt(stmts)
 568
 569     # --------------------------------------------------------------
 570     #
 571     # EXPRESSION NODES  (invoked by com_node())
 572     #
 573
 574     def testlist(self, nodelist):
 575         # testlist: expr (',' expr)* [',']
 576         # testlist_safe: test [(',' test)+ [',']]
 577         # exprlist: expr (',' expr)* [',']
 578         return self.com_binary(Tuple, nodelist)
 579
 580     testlist_safe = testlist # XXX
 581     testlist1 = testlist
 582     exprlist = testlist
 583
 584     def testlist_gexp(self, nodelist):
 585         if len(nodelist) == 2 and nodelist[1][0] == symbol.gen_for:
 586             test = self.com_node(nodelist[0])
 587             return self.com_generator_expression(test, nodelist[1])
 588         return self.testlist(nodelist)
 589
 590     def test(self, nodelist):
 591         # or_test ['if' or_test 'else' test] | lambdef
 592         if len(nodelist) == 1 and nodelist[0][0] == symbol.lambdef:
 593             return self.lambdef(nodelist[0])
 594         then = self.com_node(nodelist[0])
 595         if len(nodelist) > 1:
 596             assert len(nodelist) == 5
 597             assert nodelist[1][1] == 'if'
 598             assert nodelist[3][1] == 'else'
 599             test = self.com_node(nodelist[2])
 600             else_ = self.com_node(nodelist[4])
 601             return IfExp(test, then, else_, lineno=nodelist[1][2])
 602         return then
 603
 604     def or_test(self, nodelist):
 605         # and_test ('or' and_test)* | lambdef
 606         if len(nodelist) == 1 and nodelist[0][0] == symbol.lambdef:
 607             return self.lambdef(nodelist[0])
 608         return self.com_binary(Or, nodelist)
 609     old_test = or_test
 610
 611     def and_test(self, nodelist):
 612         # not_test ('and' not_test)*
 613         return self.com_binary(And, nodelist)
 614
 615     def not_test(self, nodelist):
 616         # 'not' not_test | comparison
 617         result = self.com_node(nodelist[-1])
 618         if len(nodelist) == 2:
 619             return Not(result, lineno=nodelist[0][2])
 620         return result
 621
 622     def comparison(self, nodelist):
 623         # comparison: expr (comp_op expr)*
 624         node = self.com_node(nodelist[0])
 625         if len(nodelist) == 1:
 626             return node
 627
 628         results = []
 629         for i in range(2, len(nodelist), 2):
 630             nl = nodelist[i-1]
 631
 632             # comp_op: '<' | '>' | '=' | '>=' | '<=' | '<>' | '!=' | '=='
 633             #          | 'in' | 'not' 'in' | 'is' | 'is' 'not'
 634             n = nl[1]
 635             if n[0] == token.NAME:
 636                 type = n[1]
 637                 if len(nl) == 3:
 638                     if type == 'not':
 639                         type = 'not in'
 640                     else:
 641                         type = 'is not'
 642             else:
 643                 type = _cmp_types[n[0]]
 644
 645             lineno = nl[1][2]
 646             results.append((type, self.com_node(nodelist[i])))
 647
 648         # we need a special "compare" node so that we can distinguish
 649         #   3 < x < 5   from    (3 < x) < 5
 650         # the two have very different semantics and results (note that the
 651         # latter form is always true)
 652
 653         return Compare(node, results, lineno=lineno)
 654
 655     def expr(self, nodelist):
 656         # xor_expr ('|' xor_expr)*
 657         return self.com_binary(Bitor, nodelist)
 658
 659     def xor_expr(self, nodelist):
 660         # xor_expr ('^' xor_expr)*
 661         return self.com_binary(Bitxor, nodelist)
 662
 663     def and_expr(self, nodelist):
 664         # xor_expr ('&' xor_expr)*
 665         return self.com_binary(Bitand, nodelist)
 666
 667     def shift_expr(self, nodelist):
 668         # shift_expr ('<<'|'>>' shift_expr)*
 669         node = self.com_node(nodelist[0])
 670         for i in range(2, len(nodelist), 2):
 671             right = self.com_node(nodelist[i])
 672             if nodelist[i-1][0] == token.LEFTSHIFT:
 673                 node = LeftShift([node, right], lineno=nodelist[1][2])
 674             elif nodelist[i-1][0] == token.RIGHTSHIFT:
 675                 node = RightShift([node, right], lineno=nodelist[1][2])
 676             else:
 677                 raise ValueError, "unexpected token: %s" % nodelist[i-1][0]
 678         return node
 679
 680     def arith_expr(self, nodelist):
 681         node = self.com_node(nodelist[0])
 682         for i in range(2, len(nodelist), 2):
 683             right = self.com_node(nodelist[i])
 684             if nodelist[i-1][0] == token.PLUS:
 685                 node = Add([node, right], lineno=nodelist[1][2])
 686             elif nodelist[i-1][0] == token.MINUS:
 687                 node = Sub([node, right], lineno=nodelist[1][2])
 688             else:
 689                 raise ValueError, "unexpected token: %s" % nodelist[i-1][0]
 690         return node
 691
 692     def term(self, nodelist):
 693         node = self.com_node(nodelist[0])
 694         for i in range(2, len(nodelist), 2):
 695             right = self.com_node(nodelist[i])
 696             t = nodelist[i-1][0]
 697             if t == token.STAR:
 698                 node = Mul([node, right])
 699             elif t == token.SLASH:
 700                 node = Div([node, right])
 701             elif t == token.PERCENT:
 702                 node = Mod([node, right])
 703             elif t == token.DOUBLESLASH:
 704                 node = FloorDiv([node, right])
 705             else:
 706                 raise ValueError, "unexpected token: %s" % t
 707             node.lineno = nodelist[1][2]
 708         return node
 709
 710     def factor(self, nodelist):
 711         elt = nodelist[0]
 712         t = elt[0]
 713         node = self.lookup_node(nodelist[-1])(nodelist[-1][1:])
 714         # need to handle (unary op)constant here...
 715         if t == token.PLUS:
 716             return UnaryAdd(node, lineno=elt[2])
 717         elif t == token.MINUS:
 718             return UnarySub(node, lineno=elt[2])
 719         elif t == token.TILDE:
 720             node = Invert(node, lineno=elt[2])
 721         return node
 722
 723     def power(self, nodelist):
 724         # power: atom trailer* ('**' factor)*
 725         node = self.com_node(nodelist[0])
 726         for i in range(1, len(nodelist)):
 727             elt = nodelist[i]
 728             if elt[0] == token.DOUBLESTAR:
 729                 return Power([node, self.com_node(nodelist[i+1])],
 730                              lineno=elt[2])
 731
 732             node = self.com_apply_trailer(node, elt)
 733
 734         return node
 735
 736     def atom(self, nodelist):
 737         return self._atom_dispatch[nodelist[0][0]](nodelist)
 738
 739     def atom_lpar(self, nodelist):
 740         if nodelist[1][0] == token.RPAR:
 741             return Tuple((), lineno=nodelist[0][2])
 742         return self.com_node(nodelist[1])
 743
 744     def atom_lsqb(self, nodelist):
 745         if nodelist[1][0] == token.RSQB:
 746             return List((), lineno=nodelist[0][2])
 747         return self.com_list_constructor(nodelist[1])
 748
 749     def atom_lbrace(self, nodelist):
 750         if nodelist[1][0] == token.RBRACE:
 751             return Dict((), lineno=nodelist[0][2])
 752         return self.com_dictmaker(nodelist[1])
 753
 754     def atom_backquote(self, nodelist):
 755         return Backquote(self.com_node(nodelist[1]))
 756
 757     def atom_number(self, nodelist):
 758         ### need to verify this matches compile.c
 759         k = eval(nodelist[0][1])
 760         return Const(k, lineno=nodelist[0][2])
 761
 762     def decode_literal(self, lit):
 763         if self.encoding:
 764             # this is particularly fragile & a bit of a
 765             # hack... changes in compile.c:parsestr and
 766             # tokenizer.c must be reflected here.
 767             if self.encoding not in ['utf-8', 'iso-8859-1']:
 768                 lit = unicode(lit, 'utf-8').encode(self.encoding)
 769             return eval("# coding: %s\n%s" % (self.encoding, lit))
 770         else:
 771             return eval(lit)
 772
 773     def atom_string(self, nodelist):
 774         k = ''
 775         for node in nodelist:
 776             k += self.decode_literal(node[1])
 777         return Const(k, lineno=nodelist[0][2])
 778
 779     def atom_name(self, nodelist):
 780         return Name(nodelist[0][1], lineno=nodelist[0][2])
 781
 782     # --------------------------------------------------------------
 783     #
 784     # INTERNAL PARSING UTILITIES
 785     #
 786
 787     # The use of com_node() introduces a lot of extra stack frames,
 788     # enough to cause a stack overflow compiling test.test_parser with
 789     # the standard interpreter recursionlimit.  The com_node() is a
 790     # convenience function that hides the dispatch details, but comes
 791     # at a very high cost.  It is more efficient to dispatch directly
 792     # in the callers.  In these cases, use lookup_node() and call the
 793     # dispatched node directly.
 794
 795     def lookup_node(self, node):
 796         return self._dispatch[node[0]]
 797
 798     def com_node(self, node):
 799         # Note: compile.c has handling in com_node for del_stmt, pass_stmt,
 800         #       break_stmt, stmt, small_stmt, flow_stmt, simple_stmt,
 801         #       and compound_stmt.
 802         #       We'll just dispatch them.
 803         return self._dispatch[node[0]](node[1:])
 804
 805     def com_NEWLINE(self, *args):
 806         # A ';' at the end of a line can make a NEWLINE token appear
 807         # here, Render it harmless. (genc discards ('discard',
 808         # ('const', xxxx)) Nodes)
 809         return Discard(Const(None))
 810
 811     def com_arglist(self, nodelist):
 812         # varargslist:
 813         #     (fpdef ['=' test] ',')* ('*' NAME [',' '**' NAME] | '**' NAME)
 814         #   | fpdef ['=' test] (',' fpdef ['=' test])* [',']
 815         # fpdef: NAME | '(' fplist ')'
 816         # fplist: fpdef (',' fpdef)* [',']
 817         names = []
 818         defaults = []
 819         flags = 0
 820
 821         i = 0
 822         while i < len(nodelist):
 823             node = nodelist[i]
 824             if node[0] == token.STAR or node[0] == token.DOUBLESTAR:
 825                 if node[0] == token.STAR:
 826                     node = nodelist[i+1]
 827                     if node[0] == token.NAME:
 828                         names.append(node[1])
 829                         flags = flags | CO_VARARGS
 830                         i = i + 3
 831
 832                 if i < len(nodelist):
 833                     # should be DOUBLESTAR
 834                     t = nodelist[i][0]
 835                     if t == token.DOUBLESTAR:
 836                         node = nodelist[i+1]
 837                     else:
 838                         raise ValueError, "unexpected token: %s" % t
 839                     names.append(node[1])
 840                     flags = flags | CO_VARKEYWORDS
 841
 842                 break
 843
 844             # fpdef: NAME | '(' fplist ')'
 845             names.append(self.com_fpdef(node))
 846
 847             i = i + 1
 848             if i < len(nodelist) and nodelist[i][0] == token.EQUAL:
 849                 defaults.append(self.com_node(nodelist[i + 1]))
 850                 i = i + 2
 851             elif len(defaults):
 852                 # we have already seen an argument with default, but here
 853                 # came one without
 854                 raise SyntaxError, "non-default argument follows default argument"
 855
 856             # skip the comma
 857             i = i + 1
 858
 859         return names, defaults, flags
 860
 861     def com_fpdef(self, node):
 862         # fpdef: NAME | '(' fplist ')'
 863         if node[1][0] == token.LPAR:
 864             return self.com_fplist(node[2])
 865         return node[1][1]
 866
 867     def com_fplist(self, node):
 868         # fplist: fpdef (',' fpdef)* [',']
 869         if len(node) == 2:
 870             return self.com_fpdef(node[1])
 871         list = []
 872         for i in range(1, len(node), 2):
 873             list.append(self.com_fpdef(node[i]))
 874         return tuple(list)
 875
 876     def com_dotted_name(self, node):
 877         # String together the dotted names and return the string
 878         name = ""
 879         for n in node:
 880             if type(n) == type(()) and n[0] == 1:
 881                 name = name + n[1] + '.'
 882         return name[:-1]
 883
 884     def com_dotted_as_name(self, node):
 885         assert node[0] == symbol.dotted_as_name
 886         node = node[1:]
 887         dot = self.com_dotted_name(node[0][1:])
 888         if len(node) == 1:
 889             return dot, None
 890         assert node[1][1] == 'as'
 891         assert node[2][0] == token.NAME
 892         return dot, node[2][1]
 893
 894     def com_dotted_as_names(self, node):
 895         assert node[0] == symbol.dotted_as_names
 896         node = node[1:]
 897         names = [self.com_dotted_as_name(node[0])]
 898         for i in range(2, len(node), 2):
 899             names.append(self.com_dotted_as_name(node[i]))
 900         return names
 901
 902     def com_import_as_name(self, node):
 903         assert node[0] == symbol.import_as_name
 904         node = node[1:]
 905         assert node[0][0] == token.NAME
 906         if len(node) == 1:
 907             return node[0][1], None
 908         assert node[1][1] == 'as', node
 909         assert node[2][0] == token.NAME
 910         return node[0][1], node[2][1]
 911
 912     def com_import_as_names(self, node):
 913         assert node[0] == symbol.import_as_names
 914         node = node[1:]
 915         names = [self.com_import_as_name(node[0])]
 916         for i in range(2, len(node), 2):
 917             names.append(self.com_import_as_name(node[i]))
 918         return names
 919
 920     def com_bases(self, node):
 921         bases = []
 922         for i in range(1, len(node), 2):
 923             bases.append(self.com_node(node[i]))
 924         return bases
 925
 926     def com_try_except_finally(self, nodelist):
 927         # ('try' ':' suite
 928         #  ((except_clause ':' suite)+ ['else' ':' suite] ['finally' ':' suite]
 929         #   | 'finally' ':' suite))
 930
 931         if nodelist[3][0] == token.NAME:
 932             # first clause is a finally clause: only try-finally
 933             return TryFinally(self.com_node(nodelist[2]),
 934                               self.com_node(nodelist[5]),
 935                               lineno=nodelist[0][2])
 936
 937         #tryexcept:  [TryNode, [except_clauses], elseNode)]
 938         clauses = []
 939         elseNode = None
 940         finallyNode = None
 941         for i in range(3, len(nodelist), 3):
 942             node = nodelist[i]
 943             if node[0] == symbol.except_clause:
 944                 # except_clause: 'except' [expr [(',' | 'as') expr]] */
 945                 if len(node) > 2:
 946                     expr1 = self.com_node(node[2])
 947                     if len(node) > 4:
 948                         expr2 = self.com_assign(node[4], OP_ASSIGN)
 949                     else:
 950                         expr2 = None
 951                 else:
 952                     expr1 = expr2 = None
 953                 clauses.append((expr1, expr2, self.com_node(nodelist[i+2])))
 954
 955             if node[0] == token.NAME:
 956                 if node[1] == 'else':
 957                     elseNode = self.com_node(nodelist[i+2])
 958                 elif node[1] == 'finally':
 959                     finallyNode = self.com_node(nodelist[i+2])
 960         try_except = TryExcept(self.com_node(nodelist[2]), clauses, elseNode,
 961                                lineno=nodelist[0][2])
 962         if finallyNode:
 963             return TryFinally(try_except, finallyNode, lineno=nodelist[0][2])
 964         else:
 965             return try_except
 966
 967     def com_with(self, nodelist):
 968         # with_stmt: 'with' with_item (',' with_item)* ':' suite
 969         body = self.com_node(nodelist[-1])
 970         for i in range(len(nodelist) - 3, 0, -2):
 971             ret = self.com_with_item(nodelist[i], body, nodelist[0][2])
 972             if i == 1:
 973                 return ret
 974             body = ret
 975
 976     def com_with_item(self, nodelist, body, lineno):
 977         # with_item: test ['as' expr]
 978         if len(nodelist) == 4:
 979             var = self.com_assign(nodelist[3], OP_ASSIGN)
 980         else:
 981             var = None
 982         expr = self.com_node(nodelist[1])
 983         return With(expr, var, body, lineno=lineno)
 984
 985     def com_augassign_op(self, node):
 986         assert node[0] == symbol.augassign
 987         return node[1]
 988
 989     def com_augassign(self, node):
 990         """Return node suitable for lvalue of augmented assignment
 991
 992         Names, slices, and attributes are the only allowable nodes.
 993         """
 994         l = self.com_node(node)
 995         if l.__class__ in (Name, Slice, Subscript, Getattr):
 996             return l
 997         raise SyntaxError, "can't assign to %s" % l.__class__.__name__
 998
 999     def com_assign(self, node, assigning):
1000         # return a node suitable for use as an "lvalue"
1001         # loop to avoid trivial recursion
1002         while 1:
1003             t = node[0]
1004             if t in (symbol.exprlist, symbol.testlist, symbol.testlist_safe, symbol.testlist_gexp):
1005                 if len(node) > 2:
1006                     return self.com_assign_tuple(node, assigning)
1007                 node = node[1]
1008             elif t in _assign_types:
1009                 if len(node) > 2:
1010                     raise SyntaxError, "can't assign to operator"
1011                 node = node[1]
1012             elif t == symbol.power:
1013                 if node[1][0] != symbol.atom:
1014                     raise SyntaxError, "can't assign to operator"
1015                 if len(node) > 2:
1016                     primary = self.com_node(node[1])
1017                     for i in range(2, len(node)-1):
1018                         ch = node[i]
1019                         if ch[0] == token.DOUBLESTAR:
1020                             raise SyntaxError, "can't assign to operator"
1021                         primary = self.com_apply_trailer(primary, ch)
1022                     return self.com_assign_trailer(primary, node[-1],
1023                                                    assigning)
1024                 node = node[1]
1025             elif t == symbol.atom:
1026                 t = node[1][0]
1027                 if t == token.LPAR:
1028                     node = node[2]
1029                     if node[0] == token.RPAR:
1030                         raise SyntaxError, "can't assign to ()"
1031                 elif t == token.LSQB:
1032                     node = node[2]
1033                     if node[0] == token.RSQB:
1034                         raise SyntaxError, "can't assign to []"
1035                     return self.com_assign_list(node, assigning)
1036                 elif t == token.NAME:
1037                     return self.com_assign_name(node[1], assigning)
1038                 else:
1039                     raise SyntaxError, "can't assign to literal"
1040             else:
1041                 raise SyntaxError, "bad assignment (%s)" % t
1042
1043     def com_assign_tuple(self, node, assigning):
1044         assigns = []
1045         for i in range(1, len(node), 2):
1046             assigns.append(self.com_assign(node[i], assigning))
1047         return AssTuple(assigns, lineno=extractLineNo(node))
1048
1049     def com_assign_list(self, node, assigning):
1050         assigns = []
1051         for i in range(1, len(node), 2):
1052             if i + 1 < len(node):
1053                 if node[i + 1][0] == symbol.list_for:
1054                     raise SyntaxError, "can't assign to list comprehension"
1055                 assert node[i + 1][0] == token.COMMA, node[i + 1]
1056             assigns.append(self.com_assign(node[i], assigning))
1057         return AssList(assigns, lineno=extractLineNo(node))
1058
1059     def com_assign_name(self, node, assigning):
1060         return AssName(node[1], assigning, lineno=node[2])
1061
1062     def com_assign_trailer(self, primary, node, assigning):
1063         t = node[1][0]
1064         if t == token.DOT:
1065             return self.com_assign_attr(primary, node[2], assigning)
1066         if t == token.LSQB:
1067             return self.com_subscriptlist(primary, node[2], assigning)
1068         if t == token.LPAR:
1069             raise SyntaxError, "can't assign to function call"
1070         raise SyntaxError, "unknown trailer type: %s" % t
1071
1072     def com_assign_attr(self, primary, node, assigning):
1073         return AssAttr(primary, node[1], assigning, lineno=node[-1])
1074
1075     def com_binary(self, constructor, nodelist):
1076         "Compile 'NODE (OP NODE)*' into (type, [ node1, ..., nodeN ])."
1077         l = len(nodelist)
1078         if l == 1:
1079             n = nodelist[0]
1080             return self.lookup_node(n)(n[1:])
1081         items = []
1082         for i in range(0, l, 2):
1083             n = nodelist[i]
1084             items.append(self.lookup_node(n)(n[1:]))
1085         return constructor(items, lineno=extractLineNo(nodelist))
1086
1087     def com_stmt(self, node):
1088         result = self.lookup_node(node)(node[1:])
1089         assert result is not None
1090         if isinstance(result, Stmt):
1091             return result
1092         return Stmt([result])
1093
1094     def com_append_stmt(self, stmts, node):
1095         result = self.lookup_node(node)(node[1:])
1096         assert result is not None
1097         if isinstance(result, Stmt):
1098             stmts.extend(result.nodes)
1099         else:
1100             stmts.append(result)
1101
1102     if hasattr(symbol, 'list_for'):
1103         def com_list_constructor(self, nodelist):
1104             # listmaker: test ( list_for | (',' test)* [','] )
1105             values = []
1106             for i in range(1, len(nodelist)):
1107                 if nodelist[i][0] == symbol.list_for:
1108                     assert len(nodelist[i:]) == 1
1109                     return self.com_list_comprehension(values[0],
1110                                                        nodelist[i])
1111                 elif nodelist[i][0] == token.COMMA:
1112                     continue
1113                 values.append(self.com_node(nodelist[i]))
1114             return List(values, lineno=values[0].lineno)
1115
1116         def com_list_comprehension(self, expr, node):
1117             # list_iter: list_for | list_if
1118             # list_for: 'for' exprlist 'in' testlist [list_iter]
1119             # list_if: 'if' test [list_iter]
1120
1121             # XXX should raise SyntaxError for assignment
1122
1123             lineno = node[1][2]
1124             fors = []
1125             while node:
1126                 t = node[1][1]
1127                 if t == 'for':
1128                     assignNode = self.com_assign(node[2], OP_ASSIGN)
1129                     listNode = self.com_node(node[4])
1130                     newfor = ListCompFor(assignNode, listNode, [])
1131                     newfor.lineno = node[1][2]
1132                     fors.append(newfor)
1133                     if len(node) == 5:
1134                         node = None
1135                     else:
1136                         node = self.com_list_iter(node[5])
1137                 elif t == 'if':
1138                     test = self.com_node(node[2])
1139                     newif = ListCompIf(test, lineno=node[1][2])
1140                     newfor.ifs.append(newif)
1141                     if len(node) == 3:
1142                         node = None
1143                     else:
1144                         node = self.com_list_iter(node[3])
1145                 else:
1146                     raise SyntaxError, \
1147                           ("unexpected list comprehension element: %s %d"
1148                            % (node, lineno))
1149             return ListComp(expr, fors, lineno=lineno)
1150
1151         def com_list_iter(self, node):
1152             assert node[0] == symbol.list_iter
1153             return node[1]
1154     else:
1155         def com_list_constructor(self, nodelist):
1156             values = []
1157             for i in range(1, len(nodelist), 2):
1158                 values.append(self.com_node(nodelist[i]))
1159             return List(values, lineno=values[0].lineno)
1160
1161     if hasattr(symbol, 'gen_for'):
1162         def com_generator_expression(self, expr, node):
1163             # gen_iter: gen_for | gen_if
1164             # gen_for: 'for' exprlist 'in' test [gen_iter]
1165             # gen_if: 'if' test [gen_iter]
1166
1167             lineno = node[1][2]
1168             fors = []
1169             while node:
1170                 t = node[1][1]
1171                 if t == 'for':
1172                     assignNode = self.com_assign(node[2], OP_ASSIGN)
1173                     genNode = self.com_node(node[4])
1174                     newfor = GenExprFor(assignNode, genNode, [],
1175                                         lineno=node[1][2])
1176                     fors.append(newfor)
1177                     if (len(node)) == 5:
1178                         node = None
1179                     else:
1180                         node = self.com_gen_iter(node[5])
1181                 elif t == 'if':
1182                     test = self.com_node(node[2])
1183                     newif = GenExprIf(test, lineno=node[1][2])
1184                     newfor.ifs.append(newif)
1185                     if len(node) == 3:
1186                         node = None
1187                     else:
1188                         node = self.com_gen_iter(node[3])
1189                 else:
1190                     raise SyntaxError, \
1191                             ("unexpected generator expression element: %s %d"
1192                              % (node, lineno))
1193             fors[0].is_outmost = True
1194             return GenExpr(GenExprInner(expr, fors), lineno=lineno)
1195
1196         def com_gen_iter(self, node):
1197             assert node[0] == symbol.gen_iter
1198             return node[1]
1199
1200     def com_dictmaker(self, nodelist):
1201         # dictmaker: test ':' test (',' test ':' value)* [',']
1202         items = []
1203         for i in range(1, len(nodelist), 4):
1204             items.append((self.com_node(nodelist[i]),
1205                           self.com_node(nodelist[i+2])))
1206         return Dict(items, lineno=items[0][0].lineno)
1207
1208     def com_apply_trailer(self, primaryNode, nodelist):
1209         t = nodelist[1][0]
1210         if t == token.LPAR:
1211             return self.com_call_function(primaryNode, nodelist[2])
1212         if t == token.DOT:
1213             return self.com_select_member(primaryNode, nodelist[2])
1214         if t == token.LSQB:
1215             return self.com_subscriptlist(primaryNode, nodelist[2], OP_APPLY)
1216
1217         raise SyntaxError, 'unknown node type: %s' % t
1218
1219     def com_select_member(self, primaryNode, nodelist):
1220         if nodelist[0] != token.NAME:
1221             raise SyntaxError, "member must be a name"
1222         return Getattr(primaryNode, nodelist[1], lineno=nodelist[2])
1223
1224     def com_call_function(self, primaryNode, nodelist):
1225         if nodelist[0] == token.RPAR:
1226             return CallFunc(primaryNode, [], lineno=extractLineNo(nodelist))
1227         args = []
1228         kw = 0
1229         star_node = dstar_node = None
1230         len_nodelist = len(nodelist)
1231         i = 1
1232         while i < len_nodelist:
1233             node = nodelist[i]
1234
1235             if node[0]==token.STAR:
1236                 if star_node is not None:
1237                     raise SyntaxError, 'already have the varargs indentifier'
1238                 star_node = self.com_node(nodelist[i+1])
1239                 i = i + 3
1240                 continue
1241             elif node[0]==token.DOUBLESTAR:
1242                 if dstar_node is not None:
1243                     raise SyntaxError, 'already have the kwargs indentifier'
1244                 dstar_node = self.com_node(nodelist[i+1])
1245                 i = i + 3
1246                 continue
1247
1248             # positional or named parameters
1249             kw, result = self.com_argument(node, kw, star_node)
1250
1251             if len_nodelist != 2 and isinstance(result, GenExpr) \
1252                and len(node) == 3 and node[2][0] == symbol.gen_for:
1253                 # allow f(x for x in y), but reject f(x for x in y, 1)
1254                 # should use f((x for x in y), 1) instead of f(x for x in y, 1)
1255                 raise SyntaxError, 'generator expression needs parenthesis'
1256
1257             args.append(result)
1258             i = i + 2
1259
1260         return CallFunc(primaryNode, args, star_node, dstar_node,
1261                         lineno=extractLineNo(nodelist))
1262
1263     def com_argument(self, nodelist, kw, star_node):
1264         if len(nodelist) == 3 and nodelist[2][0] == symbol.gen_for:
1265             test = self.com_node(nodelist[1])
1266             return 0, self.com_generator_expression(test, nodelist[2])
1267         if len(nodelist) == 2:
1268             if kw:
1269                 raise SyntaxError, "non-keyword arg after keyword arg"
1270             if star_node:
1271                 raise SyntaxError, "only named arguments may follow *expression"
1272             return 0, self.com_node(nodelist[1])
1273         result = self.com_node(nodelist[3])
1274         n = nodelist[1]
1275         while len(n) == 2 and n[0] != token.NAME:
1276             n = n[1]
1277         if n[0] != token.NAME:
1278             raise SyntaxError, "keyword can't be an expression (%s)"%n[0]
1279         node = Keyword(n[1], result, lineno=n[2])
1280         return 1, node
1281
1282     def com_subscriptlist(self, primary, nodelist, assigning):
1283         # slicing:      simple_slicing | extended_slicing
1284         # simple_slicing:   primary "[" short_slice "]"
1285         # extended_slicing: primary "[" slice_list "]"
1286         # slice_list:   slice_item ("," slice_item)* [","]
1287
1288         # backwards compat slice for '[i:j]'
1289         if len(nodelist) == 2:
1290             sub = nodelist[1]
1291             if (sub[1][0] == token.COLON or \
1292                             (len(sub) > 2 and sub[2][0] == token.COLON)) and \
1293                             sub[-1][0] != symbol.sliceop:
1294                 return self.com_slice(primary, sub, assigning)
1295
1296         subscripts = []
1297         for i in range(1, len(nodelist), 2):
1298             subscripts.append(self.com_subscript(nodelist[i]))
1299         return Subscript(primary, assigning, subscripts,
1300                          lineno=extractLineNo(nodelist))
1301
1302     def com_subscript(self, node):
1303         # slice_item: expression | proper_slice | ellipsis
1304         ch = node[1]
1305         t = ch[0]
1306         if t == token.DOT and node[2][0] == token.DOT:
1307             return Ellipsis()
1308         if t == token.COLON or len(node) > 2:
1309             return self.com_sliceobj(node)
1310         return self.com_node(ch)
1311
1312     def com_sliceobj(self, node):
1313         # proper_slice: short_slice | long_slice
1314         # short_slice:  [lower_bound] ":" [upper_bound]
1315         # long_slice:   short_slice ":" [stride]
1316         # lower_bound:  expression
1317         # upper_bound:  expression
1318         # stride:       expression
1319         #
1320         # Note: a stride may be further slicing...
1321
1322         items = []
1323
1324         if node[1][0] == token.COLON:
1325             items.append(Const(None))
1326             i = 2
1327         else:
1328             items.append(self.com_node(node[1]))
1329             # i == 2 is a COLON
1330             i = 3
1331
1332         if i < len(node) and node[i][0] == symbol.test:
1333             items.append(self.com_node(node[i]))
1334             i = i + 1
1335         else:
1336             items.append(Const(None))
1337
1338         # a short_slice has been built. look for long_slice now by looking
1339         # for strides...
1340         for j in range(i, len(node)):
1341             ch = node[j]
1342             if len(ch) == 2:
1343                 items.append(Const(None))
1344             else:
1345                 items.append(self.com_node(ch[2]))
1346         return Sliceobj(items, lineno=extractLineNo(node))
1347
1348     def com_slice(self, primary, node, assigning):
1349         # short_slice:  [lower_bound] ":" [upper_bound]
1350         lower = upper = None
1351         if len(node) == 3:
1352             if node[1][0] == token.COLON:
1353                 upper = self.com_node(node[2])
1354             else:
1355                 lower = self.com_node(node[1])
1356         elif len(node) == 4:
1357             lower = self.com_node(node[1])
1358             upper = self.com_node(node[3])
1359         return Slice(primary, assigning, lower, upper,
1360                      lineno=extractLineNo(node))
1361
1362     def get_docstring(self, node, n=None):
1363         if n is None:
1364             n = node[0]
1365             node = node[1:]
1366         if n == symbol.suite:
1367             if len(node) == 1:
1368                 return self.get_docstring(node[0])
1369             for sub in node:
1370                 if sub[0] == symbol.stmt:
1371                     return self.get_docstring(sub)
1372             return None
1373         if n == symbol.file_input:
1374             for sub in node:
1375                 if sub[0] == symbol.stmt:
1376                     return self.get_docstring(sub)
1377             return None
1378         if n == symbol.atom:
1379             if node[0][0] == token.STRING:
1380                 s = ''
1381                 for t in node:
1382                     s = s + eval(t[1])
1383                 return s
1384             return None
1385         if n == symbol.stmt or n == symbol.simple_stmt \
1386            or n == symbol.small_stmt:
1387             return self.get_docstring(node[0])
1388         if n in _doc_nodes and len(node) == 1:
1389             return self.get_docstring(node[0])
1390         return None
1391
1392
1393 _doc_nodes = [
1394     symbol.expr_stmt,
1395     symbol.testlist,
1396     symbol.testlist_safe,
1397     symbol.test,
1398     symbol.or_test,
1399     symbol.and_test,
1400     symbol.not_test,
1401     symbol.comparison,
1402     symbol.expr,
1403     symbol.xor_expr,
1404     symbol.and_expr,
1405     symbol.shift_expr,
1406     symbol.arith_expr,
1407     symbol.term,
1408     symbol.factor,
1409     symbol.power,
1410     ]
1411
1412 # comp_op: '<' | '>' | '=' | '>=' | '<=' | '<>' | '!=' | '=='
1413 #             | 'in' | 'not' 'in' | 'is' | 'is' 'not'
1414 _cmp_types = {
1415     token.LESS : '<',
1416     token.GREATER : '>',
1417     token.EQEQUAL : '==',
1418     token.EQUAL : '==',
1419     token.LESSEQUAL : '<=',
1420     token.GREATEREQUAL : '>=',
1421     token.NOTEQUAL : '!=',
1422     }
1423
1424 _legal_node_types = [
1425     symbol.funcdef,
1426     symbol.classdef,
1427     symbol.stmt,
1428     symbol.small_stmt,
1429     symbol.flow_stmt,
1430     symbol.simple_stmt,
1431     symbol.compound_stmt,
1432     symbol.expr_stmt,
1433     symbol.print_stmt,
1434     symbol.del_stmt,
1435     symbol.pass_stmt,
1436     symbol.break_stmt,
1437     symbol.continue_stmt,
1438     symbol.return_stmt,
1439     symbol.raise_stmt,
1440     symbol.import_stmt,
1441     symbol.global_stmt,
1442     symbol.exec_stmt,
1443     symbol.assert_stmt,
1444     symbol.if_stmt,
1445     symbol.while_stmt,
1446     symbol.for_stmt,
1447     symbol.try_stmt,
1448     symbol.with_stmt,
1449     symbol.suite,
1450     symbol.testlist,
1451     symbol.testlist_safe,
1452     symbol.test,
1453     symbol.and_test,
1454     symbol.not_test,
1455     symbol.comparison,
1456     symbol.exprlist,
1457     symbol.expr,
1458     symbol.xor_expr,
1459     symbol.and_expr,
1460     symbol.shift_expr,
1461     symbol.arith_expr,
1462     symbol.term,
1463     symbol.factor,
1464     symbol.power,
1465     symbol.atom,
1466     ]
1467
1468 if hasattr(symbol, 'yield_stmt'):
1469     _legal_node_types.append(symbol.yield_stmt)
1470 if hasattr(symbol, 'yield_expr'):
1471     _legal_node_types.append(symbol.yield_expr)
1472
1473 _assign_types = [
1474     symbol.test,
1475     symbol.or_test,
1476     symbol.and_test,
1477     symbol.not_test,
1478     symbol.comparison,
1479     symbol.expr,
1480     symbol.xor_expr,
1481     symbol.and_expr,
1482     symbol.shift_expr,
1483     symbol.arith_expr,
1484     symbol.term,
1485     symbol.factor,
1486     ]
1487
1488 _names = {}
1489 for k, v in symbol.sym_name.items():
1490     _names[k] = v
1491 for k, v in token.tok_name.items():
1492     _names[k] = v
1493
1494 def debug_tree(tree):
1495     l = []
1496     for elt in tree:
1497         if isinstance(elt, int):
1498             l.append(_names.get(elt, elt))
1499         elif isinstance(elt, str):
1500             l.append(elt)
1501         else:
1502             l.append(debug_tree(elt))
1503     return l