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_comp(self, nodelist):
 585         # test ( comp_for | (',' test)* [','] )
 586         assert nodelist[0][0] == symbol.test
 587         if len(nodelist) == 2 and nodelist[1][0] == symbol.comp_for:
 588             test = self.com_node(nodelist[0])
 589             return self.com_generator_expression(test, nodelist[1])
 590         return self.testlist(nodelist)
 591
 592     def test(self, nodelist):
 593         # or_test ['if' or_test 'else' test] | lambdef
 594         if len(nodelist) == 1 and nodelist[0][0] == symbol.lambdef:
 595             return self.lambdef(nodelist[0])
 596         then = self.com_node(nodelist[0])
 597         if len(nodelist) > 1:
 598             assert len(nodelist) == 5
 599             assert nodelist[1][1] == 'if'
 600             assert nodelist[3][1] == 'else'
 601             test = self.com_node(nodelist[2])
 602             else_ = self.com_node(nodelist[4])
 603             return IfExp(test, then, else_, lineno=nodelist[1][2])
 604         return then
 605
 606     def or_test(self, nodelist):
 607         # and_test ('or' and_test)* | lambdef
 608         if len(nodelist) == 1 and nodelist[0][0] == symbol.lambdef:
 609             return self.lambdef(nodelist[0])
 610         return self.com_binary(Or, nodelist)
 611     old_test = or_test
 612
 613     def and_test(self, nodelist):
 614         # not_test ('and' not_test)*
 615         return self.com_binary(And, nodelist)
 616
 617     def not_test(self, nodelist):
 618         # 'not' not_test | comparison
 619         result = self.com_node(nodelist[-1])
 620         if len(nodelist) == 2:
 621             return Not(result, lineno=nodelist[0][2])
 622         return result
 623
 624     def comparison(self, nodelist):
 625         # comparison: expr (comp_op expr)*
 626         node = self.com_node(nodelist[0])
 627         if len(nodelist) == 1:
 628             return node
 629
 630         results = []
 631         for i in range(2, len(nodelist), 2):
 632             nl = nodelist[i-1]
 633
 634             # comp_op: '<' | '>' | '=' | '>=' | '<=' | '<>' | '!=' | '=='
 635             #          | 'in' | 'not' 'in' | 'is' | 'is' 'not'
 636             n = nl[1]
 637             if n[0] == token.NAME:
 638                 type = n[1]
 639                 if len(nl) == 3:
 640                     if type == 'not':
 641                         type = 'not in'
 642                     else:
 643                         type = 'is not'
 644             else:
 645                 type = _cmp_types[n[0]]
 646
 647             lineno = nl[1][2]
 648             results.append((type, self.com_node(nodelist[i])))
 649
 650         # we need a special "compare" node so that we can distinguish
 651         #   3 < x < 5   from    (3 < x) < 5
 652         # the two have very different semantics and results (note that the
 653         # latter form is always true)
 654
 655         return Compare(node, results, lineno=lineno)
 656
 657     def expr(self, nodelist):
 658         # xor_expr ('|' xor_expr)*
 659         return self.com_binary(Bitor, nodelist)
 660
 661     def xor_expr(self, nodelist):
 662         # xor_expr ('^' xor_expr)*
 663         return self.com_binary(Bitxor, nodelist)
 664
 665     def and_expr(self, nodelist):
 666         # xor_expr ('&' xor_expr)*
 667         return self.com_binary(Bitand, nodelist)
 668
 669     def shift_expr(self, nodelist):
 670         # shift_expr ('<<'|'>>' shift_expr)*
 671         node = self.com_node(nodelist[0])
 672         for i in range(2, len(nodelist), 2):
 673             right = self.com_node(nodelist[i])
 674             if nodelist[i-1][0] == token.LEFTSHIFT:
 675                 node = LeftShift([node, right], lineno=nodelist[1][2])
 676             elif nodelist[i-1][0] == token.RIGHTSHIFT:
 677                 node = RightShift([node, right], lineno=nodelist[1][2])
 678             else:
 679                 raise ValueError, "unexpected token: %s" % nodelist[i-1][0]
 680         return node
 681
 682     def arith_expr(self, nodelist):
 683         node = self.com_node(nodelist[0])
 684         for i in range(2, len(nodelist), 2):
 685             right = self.com_node(nodelist[i])
 686             if nodelist[i-1][0] == token.PLUS:
 687                 node = Add([node, right], lineno=nodelist[1][2])
 688             elif nodelist[i-1][0] == token.MINUS:
 689                 node = Sub([node, right], lineno=nodelist[1][2])
 690             else:
 691                 raise ValueError, "unexpected token: %s" % nodelist[i-1][0]
 692         return node
 693
 694     def term(self, nodelist):
 695         node = self.com_node(nodelist[0])
 696         for i in range(2, len(nodelist), 2):
 697             right = self.com_node(nodelist[i])
 698             t = nodelist[i-1][0]
 699             if t == token.STAR:
 700                 node = Mul([node, right])
 701             elif t == token.SLASH:
 702                 node = Div([node, right])
 703             elif t == token.PERCENT:
 704                 node = Mod([node, right])
 705             elif t == token.DOUBLESLASH:
 706                 node = FloorDiv([node, right])
 707             else:
 708                 raise ValueError, "unexpected token: %s" % t
 709             node.lineno = nodelist[1][2]
 710         return node
 711
 712     def factor(self, nodelist):
 713         elt = nodelist[0]
 714         t = elt[0]
 715         node = self.lookup_node(nodelist[-1])(nodelist[-1][1:])
 716         # need to handle (unary op)constant here...
 717         if t == token.PLUS:
 718             return UnaryAdd(node, lineno=elt[2])
 719         elif t == token.MINUS:
 720             return UnarySub(node, lineno=elt[2])
 721         elif t == token.TILDE:
 722             node = Invert(node, lineno=elt[2])
 723         return node
 724
 725     def power(self, nodelist):
 726         # power: atom trailer* ('**' factor)*
 727         node = self.com_node(nodelist[0])
 728         for i in range(1, len(nodelist)):
 729             elt = nodelist[i]
 730             if elt[0] == token.DOUBLESTAR:
 731                 return Power([node, self.com_node(nodelist[i+1])],
 732                              lineno=elt[2])
 733
 734             node = self.com_apply_trailer(node, elt)
 735
 736         return node
 737
 738     def atom(self, nodelist):
 739         return self._atom_dispatch[nodelist[0][0]](nodelist)
 740
 741     def atom_lpar(self, nodelist):
 742         if nodelist[1][0] == token.RPAR:
 743             return Tuple((), lineno=nodelist[0][2])
 744         return self.com_node(nodelist[1])
 745
 746     def atom_lsqb(self, nodelist):
 747         if nodelist[1][0] == token.RSQB:
 748             return List((), lineno=nodelist[0][2])
 749         return self.com_list_constructor(nodelist[1])
 750
 751     def atom_lbrace(self, nodelist):
 752         if nodelist[1][0] == token.RBRACE:
 753             return Dict((), lineno=nodelist[0][2])
 754         return self.com_dictorsetmaker(nodelist[1])
 755
 756     def atom_backquote(self, nodelist):
 757         return Backquote(self.com_node(nodelist[1]))
 758
 759     def atom_number(self, nodelist):
 760         ### need to verify this matches compile.c
 761         k = eval(nodelist[0][1])
 762         return Const(k, lineno=nodelist[0][2])
 763
 764     def decode_literal(self, lit):
 765         if self.encoding:
 766             # this is particularly fragile & a bit of a
 767             # hack... changes in compile.c:parsestr and
 768             # tokenizer.c must be reflected here.
 769             if self.encoding not in ['utf-8', 'iso-8859-1']:
 770                 lit = unicode(lit, 'utf-8').encode(self.encoding)
 771             return eval("# coding: %s\n%s" % (self.encoding, lit))
 772         else:
 773             return eval(lit)
 774
 775     def atom_string(self, nodelist):
 776         k = ''
 777         for node in nodelist:
 778             k += self.decode_literal(node[1])
 779         return Const(k, lineno=nodelist[0][2])
 780
 781     def atom_name(self, nodelist):
 782         return Name(nodelist[0][1], lineno=nodelist[0][2])
 783
 784     # --------------------------------------------------------------
 785     #
 786     # INTERNAL PARSING UTILITIES
 787     #
 788
 789     # The use of com_node() introduces a lot of extra stack frames,
 790     # enough to cause a stack overflow compiling test.test_parser with
 791     # the standard interpreter recursionlimit.  The com_node() is a
 792     # convenience function that hides the dispatch details, but comes
 793     # at a very high cost.  It is more efficient to dispatch directly
 794     # in the callers.  In these cases, use lookup_node() and call the
 795     # dispatched node directly.
 796
 797     def lookup_node(self, node):
 798         return self._dispatch[node[0]]
 799
 800     def com_node(self, node):
 801         # Note: compile.c has handling in com_node for del_stmt, pass_stmt,
 802         #       break_stmt, stmt, small_stmt, flow_stmt, simple_stmt,
 803         #       and compound_stmt.
 804         #       We'll just dispatch them.
 805         return self._dispatch[node[0]](node[1:])
 806
 807     def com_NEWLINE(self, *args):
 808         # A ';' at the end of a line can make a NEWLINE token appear
 809         # here, Render it harmless. (genc discards ('discard',
 810         # ('const', xxxx)) Nodes)
 811         return Discard(Const(None))
 812
 813     def com_arglist(self, nodelist):
 814         # varargslist:
 815         #     (fpdef ['=' test] ',')* ('*' NAME [',' '**' NAME] | '**' NAME)
 816         #   | fpdef ['=' test] (',' fpdef ['=' test])* [',']
 817         # fpdef: NAME | '(' fplist ')'
 818         # fplist: fpdef (',' fpdef)* [',']
 819         names = []
 820         defaults = []
 821         flags = 0
 822
 823         i = 0
 824         while i < len(nodelist):
 825             node = nodelist[i]
 826             if node[0] == token.STAR or node[0] == token.DOUBLESTAR:
 827                 if node[0] == token.STAR:
 828                     node = nodelist[i+1]
 829                     if node[0] == token.NAME:
 830                         names.append(node[1])
 831                         flags = flags | CO_VARARGS
 832                         i = i + 3
 833
 834                 if i < len(nodelist):
 835                     # should be DOUBLESTAR
 836                     t = nodelist[i][0]
 837                     if t == token.DOUBLESTAR:
 838                         node = nodelist[i+1]
 839                     else:
 840                         raise ValueError, "unexpected token: %s" % t
 841                     names.append(node[1])
 842                     flags = flags | CO_VARKEYWORDS
 843
 844                 break
 845
 846             # fpdef: NAME | '(' fplist ')'
 847             names.append(self.com_fpdef(node))
 848
 849             i = i + 1
 850             if i < len(nodelist) and nodelist[i][0] == token.EQUAL:
 851                 defaults.append(self.com_node(nodelist[i + 1]))
 852                 i = i + 2
 853             elif len(defaults):
 854                 # we have already seen an argument with default, but here
 855                 # came one without
 856                 raise SyntaxError, "non-default argument follows default argument"
 857
 858             # skip the comma
 859             i = i + 1
 860
 861         return names, defaults, flags
 862
 863     def com_fpdef(self, node):
 864         # fpdef: NAME | '(' fplist ')'
 865         if node[1][0] == token.LPAR:
 866             return self.com_fplist(node[2])
 867         return node[1][1]
 868
 869     def com_fplist(self, node):
 870         # fplist: fpdef (',' fpdef)* [',']
 871         if len(node) == 2:
 872             return self.com_fpdef(node[1])
 873         list = []
 874         for i in range(1, len(node), 2):
 875             list.append(self.com_fpdef(node[i]))
 876         return tuple(list)
 877
 878     def com_dotted_name(self, node):
 879         # String together the dotted names and return the string
 880         name = ""
 881         for n in node:
 882             if type(n) == type(()) and n[0] == 1:
 883                 name = name + n[1] + '.'
 884         return name[:-1]
 885
 886     def com_dotted_as_name(self, node):
 887         assert node[0] == symbol.dotted_as_name
 888         node = node[1:]
 889         dot = self.com_dotted_name(node[0][1:])
 890         if len(node) == 1:
 891             return dot, None
 892         assert node[1][1] == 'as'
 893         assert node[2][0] == token.NAME
 894         return dot, node[2][1]
 895
 896     def com_dotted_as_names(self, node):
 897         assert node[0] == symbol.dotted_as_names
 898         node = node[1:]
 899         names = [self.com_dotted_as_name(node[0])]
 900         for i in range(2, len(node), 2):
 901             names.append(self.com_dotted_as_name(node[i]))
 902         return names
 903
 904     def com_import_as_name(self, node):
 905         assert node[0] == symbol.import_as_name
 906         node = node[1:]
 907         assert node[0][0] == token.NAME
 908         if len(node) == 1:
 909             return node[0][1], None
 910         assert node[1][1] == 'as', node
 911         assert node[2][0] == token.NAME
 912         return node[0][1], node[2][1]
 913
 914     def com_import_as_names(self, node):
 915         assert node[0] == symbol.import_as_names
 916         node = node[1:]
 917         names = [self.com_import_as_name(node[0])]
 918         for i in range(2, len(node), 2):
 919             names.append(self.com_import_as_name(node[i]))
 920         return names
 921
 922     def com_bases(self, node):
 923         bases = []
 924         for i in range(1, len(node), 2):
 925             bases.append(self.com_node(node[i]))
 926         return bases
 927
 928     def com_try_except_finally(self, nodelist):
 929         # ('try' ':' suite
 930         #  ((except_clause ':' suite)+ ['else' ':' suite] ['finally' ':' suite]
 931         #   | 'finally' ':' suite))
 932
 933         if nodelist[3][0] == token.NAME:
 934             # first clause is a finally clause: only try-finally
 935             return TryFinally(self.com_node(nodelist[2]),
 936                               self.com_node(nodelist[5]),
 937                               lineno=nodelist[0][2])
 938
 939         #tryexcept:  [TryNode, [except_clauses], elseNode)]
 940         clauses = []
 941         elseNode = None
 942         finallyNode = None
 943         for i in range(3, len(nodelist), 3):
 944             node = nodelist[i]
 945             if node[0] == symbol.except_clause:
 946                 # except_clause: 'except' [expr [(',' | 'as') expr]] */
 947                 if len(node) > 2:
 948                     expr1 = self.com_node(node[2])
 949                     if len(node) > 4:
 950                         expr2 = self.com_assign(node[4], OP_ASSIGN)
 951                     else:
 952                         expr2 = None
 953                 else:
 954                     expr1 = expr2 = None
 955                 clauses.append((expr1, expr2, self.com_node(nodelist[i+2])))
 956
 957             if node[0] == token.NAME:
 958                 if node[1] == 'else':
 959                     elseNode = self.com_node(nodelist[i+2])
 960                 elif node[1] == 'finally':
 961                     finallyNode = self.com_node(nodelist[i+2])
 962         try_except = TryExcept(self.com_node(nodelist[2]), clauses, elseNode,
 963                                lineno=nodelist[0][2])
 964         if finallyNode:
 965             return TryFinally(try_except, finallyNode, lineno=nodelist[0][2])
 966         else:
 967             return try_except
 968
 969     def com_with(self, nodelist):
 970         # with_stmt: 'with' with_item (',' with_item)* ':' suite
 971         body = self.com_node(nodelist[-1])
 972         for i in range(len(nodelist) - 3, 0, -2):
 973             ret = self.com_with_item(nodelist[i], body, nodelist[0][2])
 974             if i == 1:
 975                 return ret
 976             body = ret
 977
 978     def com_with_item(self, nodelist, body, lineno):
 979         # with_item: test ['as' expr]
 980         if len(nodelist) == 4:
 981             var = self.com_assign(nodelist[3], OP_ASSIGN)
 982         else:
 983             var = None
 984         expr = self.com_node(nodelist[1])
 985         return With(expr, var, body, lineno=lineno)
 986
 987     def com_augassign_op(self, node):
 988         assert node[0] == symbol.augassign
 989         return node[1]
 990
 991     def com_augassign(self, node):
 992         """Return node suitable for lvalue of augmented assignment
 993
 994         Names, slices, and attributes are the only allowable nodes.
 995         """
 996         l = self.com_node(node)
 997         if l.__class__ in (Name, Slice, Subscript, Getattr):
 998             return l
 999         raise SyntaxError, "can't assign to %s" % l.__class__.__name__
1000
1001     def com_assign(self, node, assigning):
1002         # return a node suitable for use as an "lvalue"
1003         # loop to avoid trivial recursion
1004         while 1:
1005             t = node[0]
1006             if t in (symbol.exprlist, symbol.testlist, symbol.testlist_safe, symbol.testlist_comp):
1007                 if len(node) > 2:
1008                     return self.com_assign_tuple(node, assigning)
1009                 node = node[1]
1010             elif t in _assign_types:
1011                 if len(node) > 2:
1012                     raise SyntaxError, "can't assign to operator"
1013                 node = node[1]
1014             elif t == symbol.power:
1015                 if node[1][0] != symbol.atom:
1016                     raise SyntaxError, "can't assign to operator"
1017                 if len(node) > 2:
1018                     primary = self.com_node(node[1])
1019                     for i in range(2, len(node)-1):
1020                         ch = node[i]
1021                         if ch[0] == token.DOUBLESTAR:
1022                             raise SyntaxError, "can't assign to operator"
1023                         primary = self.com_apply_trailer(primary, ch)
1024                     return self.com_assign_trailer(primary, node[-1],
1025                                                    assigning)
1026                 node = node[1]
1027             elif t == symbol.atom:
1028                 t = node[1][0]
1029                 if t == token.LPAR:
1030                     node = node[2]
1031                     if node[0] == token.RPAR:
1032                         raise SyntaxError, "can't assign to ()"
1033                 elif t == token.LSQB:
1034                     node = node[2]
1035                     if node[0] == token.RSQB:
1036                         raise SyntaxError, "can't assign to []"
1037                     return self.com_assign_list(node, assigning)
1038                 elif t == token.NAME:
1039                     return self.com_assign_name(node[1], assigning)
1040                 else:
1041                     raise SyntaxError, "can't assign to literal"
1042             else:
1043                 raise SyntaxError, "bad assignment (%s)" % t
1044
1045     def com_assign_tuple(self, node, assigning):
1046         assigns = []
1047         for i in range(1, len(node), 2):
1048             assigns.append(self.com_assign(node[i], assigning))
1049         return AssTuple(assigns, lineno=extractLineNo(node))
1050
1051     def com_assign_list(self, node, assigning):
1052         assigns = []
1053         for i in range(1, len(node), 2):
1054             if i + 1 < len(node):
1055                 if node[i + 1][0] == symbol.list_for:
1056                     raise SyntaxError, "can't assign to list comprehension"
1057                 assert node[i + 1][0] == token.COMMA, node[i + 1]
1058             assigns.append(self.com_assign(node[i], assigning))
1059         return AssList(assigns, lineno=extractLineNo(node))
1060
1061     def com_assign_name(self, node, assigning):
1062         return AssName(node[1], assigning, lineno=node[2])
1063
1064     def com_assign_trailer(self, primary, node, assigning):
1065         t = node[1][0]
1066         if t == token.DOT:
1067             return self.com_assign_attr(primary, node[2], assigning)
1068         if t == token.LSQB:
1069             return self.com_subscriptlist(primary, node[2], assigning)
1070         if t == token.LPAR:
1071             raise SyntaxError, "can't assign to function call"
1072         raise SyntaxError, "unknown trailer type: %s" % t
1073
1074     def com_assign_attr(self, primary, node, assigning):
1075         return AssAttr(primary, node[1], assigning, lineno=node[-1])
1076
1077     def com_binary(self, constructor, nodelist):
1078         "Compile 'NODE (OP NODE)*' into (type, [ node1, ..., nodeN ])."
1079         l = len(nodelist)
1080         if l == 1:
1081             n = nodelist[0]
1082             return self.lookup_node(n)(n[1:])
1083         items = []
1084         for i in range(0, l, 2):
1085             n = nodelist[i]
1086             items.append(self.lookup_node(n)(n[1:]))
1087         return constructor(items, lineno=extractLineNo(nodelist))
1088
1089     def com_stmt(self, node):
1090         result = self.lookup_node(node)(node[1:])
1091         assert result is not None
1092         if isinstance(result, Stmt):
1093             return result
1094         return Stmt([result])
1095
1096     def com_append_stmt(self, stmts, node):
1097         result = self.lookup_node(node)(node[1:])
1098         assert result is not None
1099         if isinstance(result, Stmt):
1100             stmts.extend(result.nodes)
1101         else:
1102             stmts.append(result)
1103
1104     def com_list_constructor(self, nodelist):
1105         # listmaker: test ( list_for | (',' test)* [','] )
1106         values = []
1107         for i in range(1, len(nodelist)):
1108             if nodelist[i][0] == symbol.list_for:
1109                 assert len(nodelist[i:]) == 1
1110                 return self.com_list_comprehension(values[0],
1111                                                    nodelist[i])
1112             elif nodelist[i][0] == token.COMMA:
1113                 continue
1114             values.append(self.com_node(nodelist[i]))
1115         return List(values, lineno=values[0].lineno)
1116
1117     def com_list_comprehension(self, expr, node):
1118         return self.com_comprehension(expr, None, node, 'list')
1119
1120     def com_comprehension(self, expr1, expr2, node, type):
1121         # list_iter: list_for | list_if
1122         # list_for: 'for' exprlist 'in' testlist [list_iter]
1123         # list_if: 'if' test [list_iter]
1124
1125         # XXX should raise SyntaxError for assignment
1126         # XXX(avassalotti) Set and dict comprehensions should have generator
1127         #                  semantics. In other words, they shouldn't leak
1128         #                  variables outside of the comprehension's scope.
1129
1130         lineno = node[1][2]
1131         fors = []
1132         while node:
1133             t = node[1][1]
1134             if t == 'for':
1135                 assignNode = self.com_assign(node[2], OP_ASSIGN)
1136                 compNode = self.com_node(node[4])
1137                 newfor = ListCompFor(assignNode, compNode, [])
1138                 newfor.lineno = node[1][2]
1139                 fors.append(newfor)
1140                 if len(node) == 5:
1141                     node = None
1142                 elif type == 'list':
1143                     node = self.com_list_iter(node[5])
1144                 else:
1145                     node = self.com_comp_iter(node[5])
1146             elif t == 'if':
1147                 test = self.com_node(node[2])
1148                 newif = ListCompIf(test, lineno=node[1][2])
1149                 newfor.ifs.append(newif)
1150                 if len(node) == 3:
1151                     node = None
1152                 elif type == 'list':
1153                     node = self.com_list_iter(node[3])
1154                 else:
1155                     node = self.com_comp_iter(node[3])
1156             else:
1157                 raise SyntaxError, \
1158                       ("unexpected comprehension element: %s %d"
1159                        % (node, lineno))
1160         if type == 'list':
1161             return ListComp(expr1, fors, lineno=lineno)
1162         elif type == 'set':
1163             return SetComp(expr1, fors, lineno=lineno)
1164         elif type == 'dict':
1165             return DictComp(expr1, expr2, fors, lineno=lineno)
1166         else:
1167             raise ValueError("unexpected comprehension type: " + repr(type))
1168
1169     def com_list_iter(self, node):
1170         assert node[0] == symbol.list_iter
1171         return node[1]
1172
1173     def com_comp_iter(self, node):
1174         assert node[0] == symbol.comp_iter
1175         return node[1]
1176
1177     def com_generator_expression(self, expr, node):
1178         # comp_iter: comp_for | comp_if
1179         # comp_for: 'for' exprlist 'in' test [comp_iter]
1180         # comp_if: 'if' test [comp_iter]
1181
1182         lineno = node[1][2]
1183         fors = []
1184         while node:
1185             t = node[1][1]
1186             if t == 'for':
1187                 assignNode = self.com_assign(node[2], OP_ASSIGN)
1188                 genNode = self.com_node(node[4])
1189                 newfor = GenExprFor(assignNode, genNode, [],
1190                                     lineno=node[1][2])
1191                 fors.append(newfor)
1192                 if (len(node)) == 5:
1193                     node = None
1194                 else:
1195                     node = self.com_comp_iter(node[5])
1196             elif t == 'if':
1197                 test = self.com_node(node[2])
1198                 newif = GenExprIf(test, lineno=node[1][2])
1199                 newfor.ifs.append(newif)
1200                 if len(node) == 3:
1201                     node = None
1202                 else:
1203                     node = self.com_comp_iter(node[3])
1204             else:
1205                 raise SyntaxError, \
1206                         ("unexpected generator expression element: %s %d"
1207                          % (node, lineno))
1208         fors[0].is_outmost = True
1209         return GenExpr(GenExprInner(expr, fors), lineno=lineno)
1210
1211     def com_dictorsetmaker(self, nodelist):
1212         # dictorsetmaker: ( (test ':' test (comp_for | (',' test ':' test)* [','])) |
1213         #                   (test (comp_for | (',' test)* [','])) )
1214         assert nodelist[0] == symbol.dictorsetmaker
1215         nodelist = nodelist[1:]
1216         if len(nodelist) == 1 or nodelist[1][0] == token.COMMA:
1217             # set literal
1218             items = []
1219             for i in range(0, len(nodelist), 2):
1220                 items.append(self.com_node(nodelist[i]))
1221             return Set(items, lineno=items[0].lineno)
1222         elif nodelist[1][0] == symbol.comp_for:
1223             # set comprehension
1224             expr = self.com_node(nodelist[0])
1225             return self.com_comprehension(expr, None, nodelist[1], 'set')
1226         elif len(nodelist) > 3 and nodelist[3][0] == symbol.comp_for:
1227             # dict comprehension
1228             assert nodelist[1][0] == token.COLON
1229             key = self.com_node(nodelist[0])
1230             value = self.com_node(nodelist[2])
1231             return self.com_comprehension(key, value, nodelist[3], 'dict')
1232         else:
1233             # dict literal
1234             items = []
1235             for i in range(0, len(nodelist), 4):
1236                 items.append((self.com_node(nodelist[i]),
1237                               self.com_node(nodelist[i+2])))
1238             return Dict(items, lineno=items[0][0].lineno)
1239
1240     def com_apply_trailer(self, primaryNode, nodelist):
1241         t = nodelist[1][0]
1242         if t == token.LPAR:
1243             return self.com_call_function(primaryNode, nodelist[2])
1244         if t == token.DOT:
1245             return self.com_select_member(primaryNode, nodelist[2])
1246         if t == token.LSQB:
1247             return self.com_subscriptlist(primaryNode, nodelist[2], OP_APPLY)
1248
1249         raise SyntaxError, 'unknown node type: %s' % t
1250
1251     def com_select_member(self, primaryNode, nodelist):
1252         if nodelist[0] != token.NAME:
1253             raise SyntaxError, "member must be a name"
1254         return Getattr(primaryNode, nodelist[1], lineno=nodelist[2])
1255
1256     def com_call_function(self, primaryNode, nodelist):
1257         if nodelist[0] == token.RPAR:
1258             return CallFunc(primaryNode, [], lineno=extractLineNo(nodelist))
1259         args = []
1260         kw = 0
1261         star_node = dstar_node = None
1262         len_nodelist = len(nodelist)
1263         i = 1
1264         while i < len_nodelist:
1265             node = nodelist[i]
1266
1267             if node[0]==token.STAR:
1268                 if star_node is not None:
1269                     raise SyntaxError, 'already have the varargs indentifier'
1270                 star_node = self.com_node(nodelist[i+1])
1271                 i = i + 3
1272                 continue
1273             elif node[0]==token.DOUBLESTAR:
1274                 if dstar_node is not None:
1275                     raise SyntaxError, 'already have the kwargs indentifier'
1276                 dstar_node = self.com_node(nodelist[i+1])
1277                 i = i + 3
1278                 continue
1279
1280             # positional or named parameters
1281             kw, result = self.com_argument(node, kw, star_node)
1282
1283             if len_nodelist != 2 and isinstance(result, GenExpr) \
1284                and len(node) == 3 and node[2][0] == symbol.comp_for:
1285                 # allow f(x for x in y), but reject f(x for x in y, 1)
1286                 # should use f((x for x in y), 1) instead of f(x for x in y, 1)
1287                 raise SyntaxError, 'generator expression needs parenthesis'
1288
1289             args.append(result)
1290             i = i + 2
1291
1292         return CallFunc(primaryNode, args, star_node, dstar_node,
1293                         lineno=extractLineNo(nodelist))
1294
1295     def com_argument(self, nodelist, kw, star_node):
1296         if len(nodelist) == 3 and nodelist[2][0] == symbol.comp_for:
1297             test = self.com_node(nodelist[1])
1298             return 0, self.com_generator_expression(test, nodelist[2])
1299         if len(nodelist) == 2:
1300             if kw:
1301                 raise SyntaxError, "non-keyword arg after keyword arg"
1302             if star_node:
1303                 raise SyntaxError, "only named arguments may follow *expression"
1304             return 0, self.com_node(nodelist[1])
1305         result = self.com_node(nodelist[3])
1306         n = nodelist[1]
1307         while len(n) == 2 and n[0] != token.NAME:
1308             n = n[1]
1309         if n[0] != token.NAME:
1310             raise SyntaxError, "keyword can't be an expression (%s)"%n[0]
1311         node = Keyword(n[1], result, lineno=n[2])
1312         return 1, node
1313
1314     def com_subscriptlist(self, primary, nodelist, assigning):
1315         # slicing:      simple_slicing | extended_slicing
1316         # simple_slicing:   primary "[" short_slice "]"
1317         # extended_slicing: primary "[" slice_list "]"
1318         # slice_list:   slice_item ("," slice_item)* [","]
1319
1320         # backwards compat slice for '[i:j]'
1321         if len(nodelist) == 2:
1322             sub = nodelist[1]
1323             if (sub[1][0] == token.COLON or \
1324                             (len(sub) > 2 and sub[2][0] == token.COLON)) and \
1325                             sub[-1][0] != symbol.sliceop:
1326                 return self.com_slice(primary, sub, assigning)
1327
1328         subscripts = []
1329         for i in range(1, len(nodelist), 2):
1330             subscripts.append(self.com_subscript(nodelist[i]))
1331         return Subscript(primary, assigning, subscripts,
1332                          lineno=extractLineNo(nodelist))
1333
1334     def com_subscript(self, node):
1335         # slice_item: expression | proper_slice | ellipsis
1336         ch = node[1]
1337         t = ch[0]
1338         if t == token.DOT and node[2][0] == token.DOT:
1339             return Ellipsis()
1340         if t == token.COLON or len(node) > 2:
1341             return self.com_sliceobj(node)
1342         return self.com_node(ch)
1343
1344     def com_sliceobj(self, node):
1345         # proper_slice: short_slice | long_slice
1346         # short_slice:  [lower_bound] ":" [upper_bound]
1347         # long_slice:   short_slice ":" [stride]
1348         # lower_bound:  expression
1349         # upper_bound:  expression
1350         # stride:       expression
1351         #
1352         # Note: a stride may be further slicing...
1353
1354         items = []
1355
1356         if node[1][0] == token.COLON:
1357             items.append(Const(None))
1358             i = 2
1359         else:
1360             items.append(self.com_node(node[1]))
1361             # i == 2 is a COLON
1362             i = 3
1363
1364         if i < len(node) and node[i][0] == symbol.test:
1365             items.append(self.com_node(node[i]))
1366             i = i + 1
1367         else:
1368             items.append(Const(None))
1369
1370         # a short_slice has been built. look for long_slice now by looking
1371         # for strides...
1372         for j in range(i, len(node)):
1373             ch = node[j]
1374             if len(ch) == 2:
1375                 items.append(Const(None))
1376             else:
1377                 items.append(self.com_node(ch[2]))
1378         return Sliceobj(items, lineno=extractLineNo(node))
1379
1380     def com_slice(self, primary, node, assigning):
1381         # short_slice:  [lower_bound] ":" [upper_bound]
1382         lower = upper = None
1383         if len(node) == 3:
1384             if node[1][0] == token.COLON:
1385                 upper = self.com_node(node[2])
1386             else:
1387                 lower = self.com_node(node[1])
1388         elif len(node) == 4:
1389             lower = self.com_node(node[1])
1390             upper = self.com_node(node[3])
1391         return Slice(primary, assigning, lower, upper,
1392                      lineno=extractLineNo(node))
1393
1394     def get_docstring(self, node, n=None):
1395         if n is None:
1396             n = node[0]
1397             node = node[1:]
1398         if n == symbol.suite:
1399             if len(node) == 1:
1400                 return self.get_docstring(node[0])
1401             for sub in node:
1402                 if sub[0] == symbol.stmt:
1403                     return self.get_docstring(sub)
1404             return None
1405         if n == symbol.file_input:
1406             for sub in node:
1407                 if sub[0] == symbol.stmt:
1408                     return self.get_docstring(sub)
1409             return None
1410         if n == symbol.atom:
1411             if node[0][0] == token.STRING:
1412                 s = ''
1413                 for t in node:
1414                     s = s + eval(t[1])
1415                 return s
1416             return None
1417         if n == symbol.stmt or n == symbol.simple_stmt \
1418            or n == symbol.small_stmt:
1419             return self.get_docstring(node[0])
1420         if n in _doc_nodes and len(node) == 1:
1421             return self.get_docstring(node[0])
1422         return None
1423
1424
1425 _doc_nodes = [
1426     symbol.expr_stmt,
1427     symbol.testlist,
1428     symbol.testlist_safe,
1429     symbol.test,
1430     symbol.or_test,
1431     symbol.and_test,
1432     symbol.not_test,
1433     symbol.comparison,
1434     symbol.expr,
1435     symbol.xor_expr,
1436     symbol.and_expr,
1437     symbol.shift_expr,
1438     symbol.arith_expr,
1439     symbol.term,
1440     symbol.factor,
1441     symbol.power,
1442     ]
1443
1444 # comp_op: '<' | '>' | '=' | '>=' | '<=' | '<>' | '!=' | '=='
1445 #             | 'in' | 'not' 'in' | 'is' | 'is' 'not'
1446 _cmp_types = {
1447     token.LESS : '<',
1448     token.GREATER : '>',
1449     token.EQEQUAL : '==',
1450     token.EQUAL : '==',
1451     token.LESSEQUAL : '<=',
1452     token.GREATEREQUAL : '>=',
1453     token.NOTEQUAL : '!=',
1454     }
1455
1456 _legal_node_types = [
1457     symbol.funcdef,
1458     symbol.classdef,
1459     symbol.stmt,
1460     symbol.small_stmt,
1461     symbol.flow_stmt,
1462     symbol.simple_stmt,
1463     symbol.compound_stmt,
1464     symbol.expr_stmt,
1465     symbol.print_stmt,
1466     symbol.del_stmt,
1467     symbol.pass_stmt,
1468     symbol.break_stmt,
1469     symbol.continue_stmt,
1470     symbol.return_stmt,
1471     symbol.raise_stmt,
1472     symbol.import_stmt,
1473     symbol.global_stmt,
1474     symbol.exec_stmt,
1475     symbol.assert_stmt,
1476     symbol.if_stmt,
1477     symbol.while_stmt,
1478     symbol.for_stmt,
1479     symbol.try_stmt,
1480     symbol.with_stmt,
1481     symbol.suite,
1482     symbol.testlist,
1483     symbol.testlist_safe,
1484     symbol.test,
1485     symbol.and_test,
1486     symbol.not_test,
1487     symbol.comparison,
1488     symbol.exprlist,
1489     symbol.expr,
1490     symbol.xor_expr,
1491     symbol.and_expr,
1492     symbol.shift_expr,
1493     symbol.arith_expr,
1494     symbol.term,
1495     symbol.factor,
1496     symbol.power,
1497     symbol.atom,
1498     ]
1499
1500 if hasattr(symbol, 'yield_stmt'):
1501     _legal_node_types.append(symbol.yield_stmt)
1502 if hasattr(symbol, 'yield_expr'):
1503     _legal_node_types.append(symbol.yield_expr)
1504
1505 _assign_types = [
1506     symbol.test,
1507     symbol.or_test,
1508     symbol.and_test,
1509     symbol.not_test,
1510     symbol.comparison,
1511     symbol.expr,
1512     symbol.xor_expr,
1513     symbol.and_expr,
1514     symbol.shift_expr,
1515     symbol.arith_expr,
1516     symbol.term,
1517     symbol.factor,
1518     ]
1519
1520 _names = {}
1521 for k, v in symbol.sym_name.items():
1522     _names[k] = v
1523 for k, v in token.tok_name.items():
1524     _names[k] = v
1525
1526 def debug_tree(tree):
1527     l = []
1528     for elt in tree:
1529         if isinstance(elt, int):
1530             l.append(_names.get(elt, elt))
1531         elif isinstance(elt, str):
1532             l.append(elt)
1533         else:
1534             l.append(debug_tree(elt))
1535     return l