Author: guido.van.rossum Date: Wed Nov 29 18:38:40 2006 New Revision: 52858 Added: sandbox/trunk/2to3/ sandbox/trunk/2to3/Grammar.pickle (contents, props changed) sandbox/trunk/2to3/Grammar.txt (contents, props changed) sandbox/trunk/2to3/pgen2/ sandbox/trunk/2to3/pgen2/__init__.py (contents, props changed) sandbox/trunk/2to3/pgen2/__init__.pyc (contents, props changed) sandbox/trunk/2to3/pgen2/astnode.py (contents, props changed) sandbox/trunk/2to3/pgen2/conv.py (contents, props changed) sandbox/trunk/2to3/pgen2/driver.py (contents, props changed) sandbox/trunk/2to3/pgen2/grammar.py (contents, props changed) sandbox/trunk/2to3/pgen2/literals.py (contents, props changed) sandbox/trunk/2to3/pgen2/parse.py (contents, props changed) sandbox/trunk/2to3/pgen2/pgen.py (contents, props changed) sandbox/trunk/2to3/pgen2/python.py (contents, props changed) sandbox/trunk/2to3/pgen2/test.py (contents, props changed) sandbox/trunk/2to3/play.py (contents, props changed) sandbox/trunk/2to3/pynode.py (contents, props changed) Log: Checkpoint of alternative Python 2.x-to-3.0 conversion tool. This contains a modified copy of pgen2 which was open-sourced by Elemental Security through a contributor's agreement with the PSF. Added: sandbox/trunk/2to3/Grammar.pickle ============================================================================== Binary file. No diff available. Added: sandbox/trunk/2to3/Grammar.txt ============================================================================== --- (empty file) +++ sandbox/trunk/2to3/Grammar.txt Wed Nov 29 18:38:40 2006 @@ -0,0 +1,148 @@ +# Grammar for Python + +# Note: Changing the grammar specified in this file will most likely +# require corresponding changes in the parser module +# (../Modules/parsermodule.c). If you can't make the changes to +# that module yourself, please co-ordinate the required changes +# with someone who can; ask around on python-dev for help. Fred +# Drake <fdrake@acm.org> will probably be listening there. + +# NOTE WELL: You should also follow all the steps listed in PEP 306, +# "How to Change Python's Grammar" + +# Commands for Kees Blom's railroad program +#diagram:token NAME +#diagram:token NUMBER +#diagram:token STRING +#diagram:token NEWLINE +#diagram:token ENDMARKER +#diagram:token INDENT +#diagram:output\input python.bla +#diagram:token DEDENT +#diagram:output\textwidth 20.04cm\oddsidemargin 0.0cm\evensidemargin 0.0cm +#diagram:rules + +# Start symbols for the grammar: +# file_input is a module or sequence of commands read from an input file; +# single_input is a single interactive statement; +# eval_input is the input for the eval() and input() functions. +# NB: compound_stmt in single_input is followed by extra NEWLINE! +file_input: (NEWLINE | stmt)* ENDMARKER +single_input: NEWLINE | simple_stmt | compound_stmt NEWLINE +eval_input: testlist NEWLINE* ENDMARKER + +decorator: '@' dotted_name [ '(' [arglist] ')' ] NEWLINE +decorators: decorator+ +funcdef: [decorators] 'def' NAME parameters ':' suite +parameters: '(' [varargslist] ')' +varargslist: ((fpdef ['=' test] ',')* + ('*' NAME [',' '**' NAME] | '**' NAME) | + fpdef ['=' test] (',' fpdef ['=' test])* [',']) +fpdef: NAME | '(' fplist ')' +fplist: fpdef (',' fpdef)* [','] + +stmt: simple_stmt | compound_stmt +simple_stmt: small_stmt (';' small_stmt)* [';'] NEWLINE +small_stmt: (expr_stmt | print_stmt | del_stmt | pass_stmt | flow_stmt | + import_stmt | global_stmt | exec_stmt | assert_stmt) +expr_stmt: testlist (augassign (yield_expr|testlist) | + ('=' (yield_expr|testlist))*) +augassign: ('+=' | '-=' | '*=' | '/=' | '%=' | '&=' | '|=' | '^=' | + '<<=' | '>>=' | '**=' | '//=') +# For normal assignments, additional restrictions enforced by the interpreter +print_stmt: 'print' ( [ test (',' test)* [','] ] | + '>>' test [ (',' test)+ [','] ] ) +del_stmt: 'del' exprlist +pass_stmt: 'pass' +flow_stmt: break_stmt | continue_stmt | return_stmt | raise_stmt | yield_stmt +break_stmt: 'break' +continue_stmt: 'continue' +return_stmt: 'return' [testlist] +yield_stmt: yield_expr +raise_stmt: 'raise' [test [',' test [',' test]]] +import_stmt: import_name | import_from +import_name: 'import' dotted_as_names +import_from: ('from' ('.'* dotted_name | '.'+) + 'import' ('*' | '(' import_as_names ')' | import_as_names)) +import_as_name: NAME ['as' NAME] +dotted_as_name: dotted_name ['as' NAME] +import_as_names: import_as_name (',' import_as_name)* [','] +dotted_as_names: dotted_as_name (',' dotted_as_name)* +dotted_name: NAME ('.' NAME)* +global_stmt: 'global' NAME (',' NAME)* +exec_stmt: 'exec' expr ['in' test [',' test]] +assert_stmt: 'assert' test [',' test] + +compound_stmt: if_stmt | while_stmt | for_stmt | try_stmt | with_stmt | funcdef | classdef +if_stmt: 'if' test ':' suite ('elif' test ':' suite)* ['else' ':' suite] +while_stmt: 'while' test ':' suite ['else' ':' suite] +for_stmt: 'for' exprlist 'in' testlist ':' suite ['else' ':' suite] +try_stmt: ('try' ':' suite + ((except_clause ':' suite)+ + ['else' ':' suite] + ['finally' ':' suite] | + 'finally' ':' suite)) +with_stmt: 'with' test [ with_var ] ':' suite +with_var: 'as' expr +# NB compile.c makes sure that the default except clause is last +except_clause: 'except' [test [',' test]] +suite: simple_stmt | NEWLINE INDENT stmt+ DEDENT + +# Backward compatibility cruft to support: +# [ x for x in lambda: True, lambda: False if x() ] +# even while also allowing: +# lambda x: 5 if x else 2 +# (But not a mix of the two) +testlist_safe: old_test [(',' old_test)+ [',']] +old_test: or_test | old_lambdef +old_lambdef: 'lambda' [varargslist] ':' old_test + +test: or_test ['if' or_test 'else' test] | lambdef +or_test: and_test ('or' and_test)* +and_test: not_test ('and' not_test)* +not_test: 'not' not_test | comparison +comparison: expr (comp_op expr)* +comp_op: '<'|'>'|'=='|'>='|'<='|'<>'|'!='|'in'|'not' 'in'|'is'|'is' 'not' +expr: xor_expr ('|' xor_expr)* +xor_expr: and_expr ('^' and_expr)* +and_expr: shift_expr ('&' shift_expr)* +shift_expr: arith_expr (('<<'|'>>') arith_expr)* +arith_expr: term (('+'|'-') term)* +term: factor (('*'|'/'|'%'|'//') factor)* +factor: ('+'|'-'|'~') factor | power +power: atom trailer* ['**' factor] +atom: ('(' [yield_expr|testlist_gexp] ')' | + '[' [listmaker] ']' | + '{' [dictmaker] '}' | + '`' testlist1 '`' | + NAME | NUMBER | STRING+) +listmaker: test ( list_for | (',' test)* [','] ) +testlist_gexp: test ( gen_for | (',' test)* [','] ) +lambdef: 'lambda' [varargslist] ':' test +trailer: '(' [arglist] ')' | '[' subscriptlist ']' | '.' NAME +subscriptlist: subscript (',' subscript)* [','] +subscript: '.' '.' '.' | test | [test] ':' [test] [sliceop] +sliceop: ':' [test] +exprlist: expr (',' expr)* [','] +testlist: test (',' test)* [','] +dictmaker: test ':' test (',' test ':' test)* [','] + +classdef: 'class' NAME ['(' [testlist] ')'] ':' suite + +arglist: (argument ',')* (argument [',']| '*' test [',' '**' test] | '**' test) +argument: test [gen_for] | test '=' test # Really [keyword '='] test + +list_iter: list_for | list_if +list_for: 'for' exprlist 'in' testlist_safe [list_iter] +list_if: 'if' old_test [list_iter] + +gen_iter: gen_for | gen_if +gen_for: 'for' exprlist 'in' or_test [gen_iter] +gen_if: 'if' old_test [gen_iter] + +testlist1: test (',' test)* + +# not used in grammar, but may appear in "node" passed from Parser to Compiler +encoding_decl: NAME + +yield_expr: 'yield' [testlist] Added: sandbox/trunk/2to3/pgen2/__init__.py ============================================================================== --- (empty file) +++ sandbox/trunk/2to3/pgen2/__init__.py Wed Nov 29 18:38:40 2006 @@ -0,0 +1,4 @@ +# Copyright 2004-2005 Elemental Security, Inc. All Rights Reserved. +# Licensed to PSF under a Contributor Agreement. + +"""The pgen2 package.""" Added: sandbox/trunk/2to3/pgen2/__init__.pyc ============================================================================== Binary file. No diff available. Added: sandbox/trunk/2to3/pgen2/astnode.py ============================================================================== --- (empty file) +++ sandbox/trunk/2to3/pgen2/astnode.py Wed Nov 29 18:38:40 2006 @@ -0,0 +1,434 @@ +# Copyright 2004-2005 Elemental Security, Inc. All Rights Reserved. +# Licensed to PSF under a Contributor Agreement. + +"""Syntax tree node definitions. + +There is a class or function corresponding to each terminal and +nonterminal symbol. + +The grammar is pieced together from the docstrings of the +corresponding classes and functions: text between dollar signs is +assumed to be the right-hand side of the grammar rule corresponding to +that class or function. + +We use __slots__ to make the parse tree nodes as small as possible. + +NOTE: EVERY CLASS MUST HAVE A __slots__ DEFINITION, EVEN IF EMPTY! +(If not, the instances will get a __dict__, defeating the purpose of +__slots__ in our case.) + +""" + +# Python imports +import token +import logging + +from pgen2 import grammar + +logger = logging.getLogger("pgen2.astnode") + +class Node(object): + """Abstract base class for all nodes. + + This has no attributes except a context slot which holds the lone + number (or more detailed context info). In the future this might + change this to several slots (e.g. filename, lineno, column, or + even filename, start_lineno, start_column, end_lineno, + end_column). The context is only referenced by two places: the + part of the code that sticks it it, and the part of the code that + reports errors. + + In order to reduce the amount of boilerplate code, the context is + argument is handled by __new__ rather than __init__. There are + also a few subclasses that override __new__ to sometimes avoid + constructing an instance. + + """ + + __slots__ = ["context"] + + def __new__(cls, context, *rest): + assert cls not in (Node, Nonterminal, Terminal, Constant) + obj = object.__new__(cls) + obj.context = context + return obj + + _stretch = False # Set to true to stretch the repr() vertically + + def __repr__(self, repr=repr): + stretch = self._stretch + r = [self.__class__.__name__] + if stretch: + r.append("(\n ") + else: + r.append("(") # ")" -- crutch for Emacs python-mode :-( + cls = self.__class__ + # Get nearest non-empty slots __slots__. This assumes + # *something* has non-empty __slots__ before we reach object + # (which has no __slots__). The class hierarchy guarantees + # this. + slots = cls.__slots__ + while not slots: + cls = cls.__base__ + slots = cls.__slots__ + first = True + for name in slots: + if name == "context": + continue # Skip this + if first: + first = False + else: + if stretch: + r.append(",\n ") + else: + r.append(", ") + try: + value = getattr(self, name) + except AttributeError: + continue + if stretch and isinstance(value, list): + rr = map(repr, value) + rv = "[" + ",\n ".join(rr) + "]" + else: + rv = repr(value) + if stretch: + rv = rv.replace("\n", "\n ") + r.append(rv) + r.append(")") + return "".join(r) + + def __str__(self): + return self.__repr__(repr=str) + +class Nonterminal(Node): + """Abstract base class for nonterminal symbols. + + Nothing beyond Node. + + """ + + __slots__ = [] + + _stretch = True + +class Terminal(Node): + """Abstract base class for terminal symbols. + + Nothing beyond Node. + + """ + + __slots__ = [] + +class Series(Nonterminal): + """Abstract base class for nonterminals like stmts: stmt+.""" + + __slots__ = [] + + def __new__(cls, context, *nodes): + assert cls is not Series + if len(nodes) == 0: + return None + elif len(nodes) == 1: + return nodes[0] + else: + obj = Nonterminal.__new__(cls, context) + obj.initseries(nodes) + return obj + +class Constant(Terminal): + """Abstract base class for constants (e.g. number or string). + + Attributes: + + repr -- a string giving the token, exactly as read from source + + """ + + __slots__ = ["repr"] + + def __init__(self, context, repr): + self.repr = repr + + def __str__(self): + return self.repr + +# Node classes for terminal symbols + +class Name(Terminal): + """Name (e.g. a variable name or an attribute name). + + Attributes: + + name -- a string giving the name. + + """ + + __slots__ = ["name"] + + def __init__(self, context, name): + self.name = name + + def __str__(self): + return self.name + +class Number(Constant): + """Numeric constant. + + Nothing beyond Constant. + + """ + + __slots__ = [] + +class String(Constant): + """String constant. + + Nothing beyond Constant. + + """ + + __slots__ = [] + +# Example nodes and factory functions for nonterminal symbols + +def Program(context, stmts): + """Program is a nonterminal with only one non-trivial child. + + Grammar: $ Expression ENDMARKER $ + + """ + return stmts + +class Expression(Series): + "Grammar: $ BinaryExpression ['?' BinaryExpression ':' BinaryExpression] $" + + __slots__ = ["test", "left", "right"] + + def initseries(self, nodes): + self.test, self.left, self.right = nodes + + def __str__(self): + return "%s ? %s : %s" % (self.test, self.left, self.right) + +class BinaryExpression(Series): + "Grammar: $ Operand (Operator Operand)* $" + + __slots__ = ["left", "op", "right"] + + def initseries(self, stuff): + # Stuff is a list with alternating operands and operators + if len(stuff) == 3: + self.left, self.op, self.right = stuff + return + assert len(stuff) > 1 and len(stuff) % 2 == 1 + # Find the rightmost lowest-priority operator + lowest_i = 1 + lowest_op = stuff[lowest_i] + lowest_pri = lowest_op.priority() + for i in range(3, len(stuff), 2): + op = stuff[i] + pri = op.priority() + if pri <= lowest_pri: + lowest_i = i + lowest_op = op + lowest_pri = pri + self.left = self.__class__(self.context, *stuff[:lowest_i]) + self.op = lowest_op + self.right = self.__class__(self.context, *stuff[lowest_i+1:]) + + def __str__(self): + return "(%s %s %s)" % (self.left, self.op, self.right) + +def Operand(context, arg): + """Operand is a nonterminal with one child. + + Grammar: $ Atom | UnaryExpression $ + + """ + return arg + +class UnaryExpression(Nonterminal): + "Grammar: $ UnaryOperator Operand $" + + __slots__ = ["op", "arg"] + + def __init__(self, context, op, arg): + self.op = op + self.arg = arg + + def __str__(self): + return "%s%s" % (self.op, self.arg) + +def UnaryOperator(context, op): + "Grammar: $ 'not' | '-' $" + return op + +class Operator(Nonterminal): + """Operator. + + This has a repr slot and a priority() method. + + The __new__ method implements a sort-of singleton pattern: there's + only one instance per repr value. (Yes, this means the context is + not useful. Therefore we set it to None.) + + Grammar: $ '**' | '*' | '/' | '+' | '-' | '&' | '^' | '|' | + ['not'] 'in' | '==' | '<' | '>' | '!=' | '<=' | '>=' | + 'and' | 'or' $ + + """ + + __slots__ = ["repr"] + + _stretch = False + + _cache = {} + + def __new__(cls, context, *args): + repr = " ".join(args) + # For "not in", the argument should be the string "not in" + obj = cls._cache.get(repr) + if obj is None: + obj = Terminal.__new__(cls, None) + obj.repr = repr + return obj + + def __str__(self): + return self.repr + + def priority(self): + return self._priorities[self.repr] + + _priorities = { + "or": 0, + "and": 1, + "in": 2, + "not in": 2, + "<": 2, + ">": 2, + "==": 2, + "<=": 2, + ">=": 2, + "!=": 2, + "|": 3, + "^": 4, + "&": 5, + "+": 6, + "-": 6, + "*": 7, + "/": 7, + "**": 8, + } + +def Atom(context, arg): + """ Grammar: $ NAME | STRING | NUMBER | ParenthesizedExpression $ + """ + return arg + +def ParenthesizedExpression(context, expr): + "Grammar: $ '(' Expression ')' $" + return expr + + +# Conversion from concrete to abstract syntax trees + +def vanish(context, value): + return None + +token_mapping = { + # Tokens that become parse tree nodes + # (token.NAME is special-cased in the code) + token.NUMBER: Number, + token.STRING: String, + + # Tokens that vanish + token.DOT: vanish, + token.LPAR: vanish, + token.RPAR: vanish, + token.COLON: vanish, + token.COMMA: vanish, + token.EQUAL: vanish, + token.DEDENT: vanish, + token.INDENT: vanish, + token.LBRACE: vanish, + token.RBRACE: vanish, + token.NEWLINE: vanish, + token.ENDMARKER: vanish, + + # All other tokens return the token's string value (e.g. "+") + } + +vanishing_keywords = { + # E.g. "def": True, + } + +def convert(grammar, node): + type, value, context, children = node + # Is it a non-terminal symbol? + if type in grammar.number2symbol: + symbol = grammar.number2symbol[type] + factory = globals().get(symbol) + if factory is None: + raise RuntimeError("can't find factory for %s (line %s)" % + (symbol, context)) + # Debug variation: + try: + return factory(context, *children) + except: + logger.debug("%s %s", factory.__name__, "(") + for child in children: + logger.debug("%s %s", "==>", child) + logger.debug(")") + logger.debug("# Did you remember to declare a 'context' arg?") + raise + return factory(context, *children) + + # Must be a terminal symbol. + if type == token.NAME: + # Name or keyword. Special-case the snot out of this. + if value in grammar.keywords: + # Keywords become strings, like operators + if value in vanishing_keywords: + return None + else: + return value + else: + return Name(context, value) + + # Look for a handler in the token_mapping table. + assert type in token.tok_name + factory = token_mapping.get(type) + if factory: + return factory(context, value) + else: + return value + + +# Support code + +def generate_grammar(stream): + """Extract the grammar rules from this module's doc strings.""" + import re + from types import ModuleType + lines = [] + startline = None + for name, obj in globals().items(): + if hasattr(obj, "__doc__") and not isinstance(obj, ModuleType): + m = re.search(r"Grammar:\s*\$([^$]+)\$", obj.__doc__ or "") + if m: + rule = obj.__name__, " ".join(m.group(1).split()) + if rule[0] == "Program": + assert not startline + startline = rule + else: + lines.append(rule) + lines.sort() + # The start symbol *must* be the first rule + lines.insert(0, startline) + for name, rhs in lines: + stream.write("%s: %s\n" % (name, rhs)) + +if __name__ == '__main__': + import sys + generate_grammar(sys.stdout) Added: sandbox/trunk/2to3/pgen2/conv.py ============================================================================== --- (empty file) +++ sandbox/trunk/2to3/pgen2/conv.py Wed Nov 29 18:38:40 2006 @@ -0,0 +1,256 @@ +# Copyright 2004-2005 Elemental Security, Inc. All Rights Reserved. +# Licensed to PSF under a Contributor Agreement. + +"""Convert graminit.[ch] spit out by pgen to Python code. + +Pgen is the Python parser generator. It is useful to quickly create a +parser from a grammar file in Python's grammar notation. But I don't +want my parsers to be written in C (yet), so I'm translating the +parsing tables to Python data structures and writing a Python parse +engine. + +Note that the token numbers are constants determined by the standard +Python tokenizer. The standard token module defines these numbers and +their names (the names are not used much). The token numbers are +hardcoded into the Python tokenizer and into pgen. A Python +implementation of the Python tokenizer is also available, in the +standard tokenize module. + +On the other hand, symbol numbers (representing the grammar's +non-terminals) are assigned by pgen based on the actual grammar +input. + +Note: this module is pretty much obsolete; the pgen module generates +equivalent grammar tables directly from the Grammar.txt input file +without having to invoke the Python pgen C program. + +""" + +# Python imports +import re +import token + +from pgen2 import grammar + +class Converter(grammar.Grammar): + """Grammar subclass that reads classic pgen output files. + + The run() method reads the tables as produced by the pgen parser + generator, typically contained in two C files, graminit.h and + graminit.c. The other methods are for internal use only. + + See the base class for more documentation. + + """ + + def run(self, graminit_h, graminit_c): + """Load the grammar tables from the text files written by pgen.""" + self.parse_graminit_h(graminit_h) + self.parse_graminit_c(graminit_c) + self.finish_off() + + def parse_graminit_h(self, filename): + """Parse the .h file writen by pgen. (Internal) + + This file is a sequence of #define statements defining the + nonterminals of the grammar as numbers. We build two tables + mapping the numbers to names and back. + + """ + try: + f = open(filename) + except IOError, err: + print "Can't open %s: %s" % (filename, err) + return False + self.symbol2number = {} + self.number2symbol = {} + lineno = 0 + for line in f: + lineno += 1 + mo = re.match(r"^#define\s+(\w+)\s+(\d+)$", line) + if not mo and line.strip(): + print "%s(%s): can't parse %s" % (filename, lineno, + line.strip()) + else: + symbol, number = mo.groups() + number = int(number) + assert symbol not in self.symbol2number + assert number not in self.number2symbol + self.symbol2number[symbol] = number + self.number2symbol[number] = symbol + return True + + def parse_graminit_c(self, filename): + """Parse the .c file writen by pgen. (Internal) + + The file looks as follows. The first two lines are always this: + + #include "pgenheaders.h" + #include "grammar.h" + + After that come four blocks: + + 1) one or more state definitions + 2) a table defining dfas + 3) a table defining labels + 4) a struct defining the grammar + + A state definition has the following form: + - one or more arc arrays, each of the form: + static arc arcs_<n>_<m>[<k>] = { + {<i>, <j>}, + ... + }; + - followed by a state array, of the form: + static state states_<s>[<t>] = { + {<k>, arcs_<n>_<m>}, + ... + }; + + """ + try: + f = open(filename) + except IOError, err: + print "Can't open %s: %s" % (filename, err) + return False + # The code below essentially uses f's iterator-ness! + lineno = 0 + + # Expect the two #include lines + lineno, line = lineno+1, f.next() + assert line == '#include "pgenheaders.h"\n', (lineno, line) + lineno, line = lineno+1, f.next() + assert line == '#include "grammar.h"\n', (lineno, line) + + # Parse the state definitions + lineno, line = lineno+1, f.next() + allarcs = {} + states = [] + while line.startswith("static arc "): + while line.startswith("static arc "): + mo = re.match(r"static arc arcs_(\d+)_(\d+)\[(\d+)\] = {$", + line) + assert mo, (lineno, line) + n, m, k = map(int, mo.groups()) + arcs = [] + for _ in range(k): + lineno, line = lineno+1, f.next() + mo = re.match(r"\s+{(\d+), (\d+)},$", line) + assert mo, (lineno, line) + i, j = map(int, mo.groups()) + arcs.append((i, j)) + lineno, line = lineno+1, f.next() + assert line == "};\n", (lineno, line) + allarcs[(n, m)] = arcs + lineno, line = lineno+1, f.next() + mo = re.match(r"static state states_(\d+)\[(\d+)\] = {$", line) + assert mo, (lineno, line) + s, t = map(int, mo.groups()) + assert s == len(states), (lineno, line) + state = [] + for _ in range(t): + lineno, line = lineno+1, f.next() + mo = re.match(r"\s+{(\d+), arcs_(\d+)_(\d+)},$", line) + assert mo, (lineno, line) + k, n, m = map(int, mo.groups()) + arcs = allarcs[n, m] + assert k == len(arcs), (lineno, line) + state.append(arcs) + states.append(state) + lineno, line = lineno+1, f.next() + assert line == "};\n", (lineno, line) + lineno, line = lineno+1, f.next() + self.states = states + + # Parse the dfas + dfas = {} + mo = re.match(r"static dfa dfas\[(\d+)\] = {$", line) + assert mo, (lineno, line) + ndfas = int(mo.group(1)) + for i in range(ndfas): + lineno, line = lineno+1, f.next() + mo = re.match(r'\s+{(\d+), "(\w+)", (\d+), (\d+), states_(\d+),$', + line) + assert mo, (lineno, line) + symbol = mo.group(2) + number, x, y, z = map(int, mo.group(1, 3, 4, 5)) + assert self.symbol2number[symbol] == number, (lineno, line) + assert self.number2symbol[number] == symbol, (lineno, line) + assert x == 0, (lineno, line) + state = states[z] + assert y == len(state), (lineno, line) + lineno, line = lineno+1, f.next() + mo = re.match(r'\s+("(?:\\\d\d\d)*")},$', line) + assert mo, (lineno, line) + first = {} + rawbitset = eval(mo.group(1)) + for i, c in enumerate(rawbitset): + byte = ord(c) + for j in range(8): + if byte & (1<<j): + first[i*8 + j] = 1 + dfas[number] = (state, first) + lineno, line = lineno+1, f.next() + assert line == "};\n", (lineno, line) + self.dfas = dfas + + # Parse the labels + labels = [] + lineno, line = lineno+1, f.next() + mo = re.match(r"static label labels\[(\d+)\] = {$", line) + assert mo, (lineno, line) + nlabels = int(mo.group(1)) + for i in range(nlabels): + lineno, line = lineno+1, f.next() + mo = re.match(r'\s+{(\d+), (0|"\w+")},$', line) + assert mo, (lineno, line) + x, y = mo.groups() + x = int(x) + if y == "0": + y = None + else: + y = eval(y) + labels.append((x, y)) + lineno, line = lineno+1, f.next() + assert line == "};\n", (lineno, line) + self.labels = labels + + # Parse the grammar struct + lineno, line = lineno+1, f.next() + assert line == "grammar _PyParser_Grammar = {\n", (lineno, line) + lineno, line = lineno+1, f.next() + mo = re.match(r"\s+(\d+),$", line) + assert mo, (lineno, line) + ndfas = int(mo.group(1)) + assert ndfas == len(self.dfas) + lineno, line = lineno+1, f.next() + assert line == "\tdfas,\n", (lineno, line) + lineno, line = lineno+1, f.next() + mo = re.match(r"\s+{(\d+), labels},$", line) + assert mo, (lineno, line) + nlabels = int(mo.group(1)) + assert nlabels == len(self.labels), (lineno, line) + lineno, line = lineno+1, f.next() + mo = re.match(r"\s+(\d+)$", line) + assert mo, (lineno, line) + start = int(mo.group(1)) + assert start in self.number2symbol, (lineno, line) + self.start = start + lineno, line = lineno+1, f.next() + assert line == "};\n", (lineno, line) + try: + lineno, line = lineno+1, f.next() + except StopIteration: + pass + else: + assert 0, (lineno, line) + + def finish_off(self): + """Create additional useful structures. (Internal).""" + self.keywords = {} # map from keyword strings to arc labels + self.tokens = {} # map from numeric token values to arc labels + for ilabel, (type, value) in enumerate(self.labels): + if type == token.NAME and value is not None: + self.keywords[value] = ilabel + elif value is None: + self.tokens[type] = ilabel Added: sandbox/trunk/2to3/pgen2/driver.py ============================================================================== --- (empty file) +++ sandbox/trunk/2to3/pgen2/driver.py Wed Nov 29 18:38:40 2006 @@ -0,0 +1,105 @@ +# Copyright 2004-2005 Elemental Security, Inc. All Rights Reserved. +# Licensed to PSF under a Contributor Agreement. + +# Modifications: +# Copyright 2006 Python Software Foundation. All Rights Reserved. + +"""Parser driver. + +This provides a high-level interface to parse a file into a syntax tree. + +""" + +__author__ = "Guido van Rossum <guido@python.org>" + +__all__ = ["Driver", "load_grammar"] + +# Python imports +import os +import token +import logging +import tokenize + +# Pgen imports +from pgen2 import parse +from pgen2 import astnode +from pgen2 import grammar + +class Driver(object): + + def __init__(self, grammar, convert=None, logger=None): + self.grammar = grammar + if logger is None: + logger = logging.getLogger() + self.logger = logger + self.convert = convert + + def parse_stream_raw(self, stream, debug=False): + """Parse a stream and return the concrete syntax tree.""" + p = parse.Parser(self.grammar, self.convert) + p.setup() + t = v = x = None + # (t, v, x, y, z) == (type, value, start, end, line) + for t, v, x, y, z in tokenize.generate_tokens(stream.readline): + if t in (tokenize.COMMENT, tokenize.NL): + continue + if t == token.OP: + t = grammar.opmap[v] + if debug: + self.logger.debug("%s %r", token.tok_name[t], v) + if p.addtoken(t, v, x): + if debug: + self.logger.debug("Stop.") + break + else: + # We never broke out -- EOF is too soon (how can this happen???) + raise parse.ParseError("incomplete input", t, v, x) + return p.rootnode + + def parse_stream(self, stream, debug=False): + """Parse a stream and return the syntax tree.""" + return self.parse_stream_raw(stream, debug) + + def parse_file(self, filename, debug=False): + """Parse a file and return the syntax tree.""" + stream = open(filename) + try: + return self.parse_stream(stream, debug) + finally: + stream.close() + + def parse_string(self, text, debug=False): + """Parse a string and return the syntax tree.""" + from StringIO import StringIO + stream = StringIO(text) + return self.parse_stream(stream, debug) + +def load_grammar(gt="Grammar.txt", gp=None, + save=True, force=False, logger=None): + """Load the grammar (maybe from a pickle).""" + if logger is None: + logger = logging.getLogger() + if gp is None: + head, tail = os.path.splitext(gt) + if tail == ".txt": + tail = "" + gp = head + tail + ".pickle" + if force or not _newer(gp, gt): + logger.info("Generating grammar tables from %s", gt) + from pgen2 import pgen + g = pgen.generate_grammar(gt) + if save: + logger.info("Writing grammar tables to %s", gp) + g.dump(gp) + else: + g = grammar.Grammar() + g.load(gp) + return g + +def _newer(a, b): + """Inquire whether file a was written since file b.""" + if not os.path.exists(a): + return False + if not os.path.exists(b): + return True + return os.path.getmtime(a) >= os.path.getmtime(b) Added: sandbox/trunk/2to3/pgen2/grammar.py ============================================================================== --- (empty file) +++ sandbox/trunk/2to3/pgen2/grammar.py Wed Nov 29 18:38:40 2006 @@ -0,0 +1,167 @@ +# Copyright 2004-2005 Elemental Security, Inc. All Rights Reserved. +# Licensed to PSF under a Contributor Agreement. + +"""This module defines the data structures used to represent a grammar. + +These are a bit arcane because they are derived from the data +structures used by Python's 'pgen' parser generator. + +There's also a table here mapping operators to their names in the +token module; the Python tokenize module reports all operators as the +fallback token code OP, but the parser needs the actual token code. + +""" + +# Python imports +import token, tokenize +import cPickle as pickle + +class Grammar(object): + """Pgen parsing tables tables conversion class. + + Once initialized, this class supplies the grammar tables for the + parsing engine implemented by parse.py. The parsing engine + accesses the instance variables directly. The class here does not + provide initialization of the tables; several subclasses exist to + do this (see the conv and pgen modules). + + The load() method reads the tables from a pickle file, which is + much faster than the other ways offered by subclasses. The pickle + file is written by calling dump() (after loading the grammar + tables using a subclass). The report() method prints a readable + representation of the tables to stdout, for debugging. + + The instance variables are as follows: + + symbol2number -- a dict mapping symbol names to numbers. Symbol + numbers are always 256 or higher, to distinguish + them from token numbers, which are between 0 and + 255 (inclusive). + + number2symbol -- a dict mapping numbers to symbol names; + these two are each other's inverse. + + states -- a list of DFAs, where each DFA is a list of + states, each state is is a list of arcs, and each + arc is a (i, j) pair where i is a label and j is + a state number. The DFA number is the index into + this list. (This name is slightly confusing.) + Final states are represented by a special arc of + the form (0, j) where j is its own state number. + + dfas -- a dict mapping symbol numbers to (DFA, first) + pairs, where DFA is an item from the states list + above, and first is a set of tokens that can + begin this grammar rule (represented by a dict + whose values are always 1). + + labels -- a list of (x, y) pairs where x is either a token + number or a symbol number, and y is either None + or a string; the strings are keywords. The label + number is the index in this list; label numbers + are used to mark state transitions (arcs) in the + DFAs. + + start -- the number of the grammar's start symbol. + + keywords -- a dict mapping keyword strings to arc labels. + + tokens -- a dict mapping token numbers to arc labels. + + """ + + def __init__(self): + self.symbol2number = {} + self.number2symbol = {} + self.states = [] + self.dfas = {} + self.labels = [(0, "EMPTY")] + self.keywords = {} + self.tokens = {} + self.symbol2label = {} + self.start = 256 + + def dump(self, filename): + """Dump the grammar tables to a pickle file.""" + f = open(filename, "wb") + pickle.dump(self.__dict__, f, 2) + f.close() + + def load(self, filename): + """Load the grammar tables from a pickle file.""" + f = open(filename, "rb") + d = pickle.load(f) + f.close() + self.__dict__.update(d) + + def report(self): + """Dump the grammar tables to standard output, for debugging.""" + from pprint import pprint + print "s2n" + pprint(self.symbol2number) + print "n2s" + pprint(self.number2symbol) + print "states" + pprint(self.states) + print "dfas" + pprint(self.dfas) + print "labels" + pprint(self.labels) + print "start", self.start + + +# Map from operator to number (since tokenize doesn't do this) + +opmap_raw = """ +( LPAR +) RPAR +[ LSQB +] RSQB +: COLON +, COMMA +; SEMI ++ PLUS +- MINUS +* STAR +/ SLASH +| VBAR +& AMPER +< LESS +> GREATER += EQUAL +. DOT +% PERCENT +` BACKQUOTE +{ LBRACE +} RBRACE +@ AT +== EQEQUAL +!= NOTEQUAL +<> NOTEQUAL +<= LESSEQUAL +>= GREATEREQUAL +~ TILDE +^ CIRCUMFLEX +<< LEFTSHIFT +>> RIGHTSHIFT +** DOUBLESTAR ++= PLUSEQUAL +-= MINEQUAL +*= STAREQUAL +/= SLASHEQUAL +%= PERCENTEQUAL +&= AMPEREQUAL +|= VBAREQUAL +^= CIRCUMFLEXEQUAL +<<= LEFTSHIFTEQUAL +>>= RIGHTSHIFTEQUAL +**= DOUBLESTAREQUAL +// DOUBLESLASH +//= DOUBLESLASHEQUAL +""" + +opmap = {} +for line in opmap_raw.splitlines(): + if line: + op, name = line.split() + opmap[op] = getattr(token, name) Added: sandbox/trunk/2to3/pgen2/literals.py ============================================================================== --- (empty file) +++ sandbox/trunk/2to3/pgen2/literals.py Wed Nov 29 18:38:40 2006 @@ -0,0 +1,60 @@ +# Copyright 2004-2005 Elemental Security, Inc. All Rights Reserved. +# Licensed to PSF under a Contributor Agreement. + +"""Safely evaluate Python string literals without using eval().""" + +import re + +simple_escapes = {"a": "\a", + "b": "\b", + "f": "\f", + "n": "\n", + "r": "\r", + "t": "\t", + "v": "\v", + "'": "'", + '"': '"', + "\\": "\\"} + +def escape(m): + all, tail = m.group(0, 1) + assert all.startswith("\\") + esc = simple_escapes.get(tail) + if esc is not None: + return esc + if tail.startswith("x"): + hexes = tail[1:] + if len(hexes) < 2: + raise ValueError("invalid hex string escape ('\\%s')" % tail) + try: + i = int(hexes, 16) + except ValueError: + raise ValueError("invalid hex string escape ('\\%s')" % tail) + else: + try: + i = int(tail, 8) + except ValueError: + raise ValueError("invalid octal string escape ('\\%s')" % tail) + return chr(i) + +def evalString(s): + assert s.startswith("'") or s.startswith('"'), repr(s[:1]) + q = s[0] + if s[:3] == q*3: + q = q*3 + assert s.endswith(q), repr(s[-len(q):]) + assert len(s) >= 2*len(q) + s = s[len(q):-len(q)] + return re.sub(r"\\(\'|\"|\\|[abfnrtv]|x.{0,2}|[0-7]{1,3})", escape, s) + +def test(): + for i in range(256): + c = chr(i) + s = repr(c) + e = evalString(s) + if e != c: + print i, c, s, e + + +if __name__ == "__main__": + test() Added: sandbox/trunk/2to3/pgen2/parse.py ============================================================================== --- (empty file) +++ sandbox/trunk/2to3/pgen2/parse.py Wed Nov 29 18:38:40 2006 @@ -0,0 +1,199 @@ +# Copyright 2004-2005 Elemental Security, Inc. All Rights Reserved. +# Licensed to PSF under a Contributor Agreement. + +"""Parser engine for the grammar tables generated by pgen. + +The grammar table must be loaded first. + +See Parser/parser.c in the Python distribution for additional info on +how this parsing engine works. + +""" + +# Python imports +import token + +class ParseError(Exception): + """Exception to signal the parser is stuck.""" + + def __init__(self, msg, type, value, context): + Exception.__init__(self, "%s: type=%r, value=%r, context=%r" % + (msg, type, value, context)) + self.msg = msg + self.type = type + self.value = value + self.context = context + +class Parser(object): + """Parser engine. + + The proper usage sequence is: + + p = Parser(grammar, [converter]) # create instance + p.setup([start]) # prepare for parsing + <for each input token>: + if p.addtoken(...): # parse a token; may raise ParseError + break + root = p.rootnode # root of abstract syntax tree + + A Parser instance may be reused by calling setup() repeatedly. + + A Parser instance contains state pertaining to the current token + sequence, and should not be used concurrently by different threads + to parse separate token sequences. + + See driver.py for how to get input tokens by tokenizing a file or + string. + + Parsing is complete when addtoken() returns True; the root of the + abstract syntax tree can then be retrieved from the rootnode + instance variable. When a syntax error occurs, addtoken() raises + the ParseError exception. There is no error recovery; the parser + cannot be used after a syntax error was reported (but it can be + reinitialized by calling setup()). + + """ + + def __init__(self, grammar, convert=None): + """Constructor. + + The grammar argument is a grammar.Grammar instance; see the + grammar module for more information. + + The parser is not ready yet for parsing; you must call the + setup() method to get it started. + + The optional convert argument is a function mapping concrete + syntax tree nodes to abstract syntax tree nodes. If not + given, no conversion is done and the syntax tree produced is + the concrete syntax tree. If given, it must be a function of + two arguments, the first being the grammar (a grammar.Grammar + instance), and the second being the concrete syntax tree node + to be converted. The syntax tree is converted from the bottom + up. + + A concrete syntax tree node is a (type, value, context, nodes) + tuple, where type is the node type (a token or symbol number), + value is None for symbols and a string for tokens, context is + None or an opaque value used for error reporting (typically a + (lineno, offset) pair), and nodes is a list of children for + symbols, and None for tokens. + + An abstract syntax tree node may be anything; this is entirely + up to the converter function. For example, it can be an + instance of a subclass of the astnode.Node class (see the + astnode module). + + """ + self.grammar = grammar + self.convert = convert or (lambda grammar, node: node) + + def setup(self, start=None): + """Prepare for parsing. + + This *must* be called before starting to parse. + + The optional argument is an alternative start symbol; it + defaults to the grammar's start symbol. + + You can use a Parser instance to parse any number of programs; + each time you call setup() the parser is reset to an initial + state determined by the (implicit or explicit) start symbol. + + """ + if start is None: + start = self.grammar.start + # Each stack entry is a tuple: (dfa, state, node). + # A node is a tuple: (type, value, context, children), + # where children is a list of nodes or None, and context may be None. + newnode = (start, None, None, []) + stackentry = (self.grammar.dfas[start], 0, newnode) + self.stack = [stackentry] + self.rootnode = None + + def addtoken(self, type, value, context): + """Add a token; return True iff this is the end of the program.""" + # Map from token to label + ilabel = self.classify(type, value, context) + # Loop until the token is shifted; may raise exceptions + while True: + dfa, state, node = self.stack[-1] + states, first = dfa + arcs = states[state] + # Look for a state with this label + for i, newstate in arcs: + t, v = self.grammar.labels[i] + if ilabel == i: + # Look it up in the list of labels + assert t < 256 + # Shift a token; we're done with it + self.shift(type, value, newstate, context) + # Pop while we are in an accept-only state + state = newstate + while states[state] == [(0, state)]: + self.pop() + if not self.stack: + # Done parsing! + return True + dfa, state, node = self.stack[-1] + states, first = dfa + # Done with this token + return False + elif t >= 256: + # See if it's a symbol and if we're in its first set + itsdfa = self.grammar.dfas[t] + itsstates, itsfirst = itsdfa + if ilabel in itsfirst: + # Push a symbol + self.push(t, self.grammar.dfas[t], newstate, context) + break # To continue the outer while loop + else: + if (0, state) in arcs: + # An accepting state, pop it and try something else + self.pop() + if not self.stack: + # Done parsing, but another token is input + raise ParseError("too much input", + type, value, context) + else: + # No success finding a transition + raise ParseError("bad input", type, value, context) + + def classify(self, type, value, context): + """Turn a token into a label. (Internal)""" + if type == token.NAME: + # Check for reserved words + ilabel = self.grammar.keywords.get(value) + if ilabel is not None: + return ilabel + ilabel = self.grammar.tokens.get(type) + if ilabel is None: + raise ParseError("bad token", type, value, context) + return ilabel + + def shift(self, type, value, newstate, context): + """Shift a token. (Internal)""" + dfa, state, node = self.stack[-1] + newnode = (type, value, context, None) + newnode = self.convert(self.grammar, newnode) + if newnode is not None: + node[-1].append(newnode) + self.stack[-1] = (dfa, newstate, node) + + def push(self, type, newdfa, newstate, context): + """Push a nonterminal. (Internal)""" + dfa, state, node = self.stack[-1] + newnode = (type, None, context, []) + self.stack[-1] = (dfa, newstate, node) + self.stack.append((newdfa, 0, newnode)) + + def pop(self): + """Pop a nonterminal. (Internal)""" + popdfa, popstate, popnode = self.stack.pop() + newnode = self.convert(self.grammar, popnode) + if newnode is not None: + if self.stack: + dfa, state, node = self.stack[-1] + node[-1].append(newnode) + else: + self.rootnode = newnode Added: sandbox/trunk/2to3/pgen2/pgen.py ============================================================================== --- (empty file) +++ sandbox/trunk/2to3/pgen2/pgen.py Wed Nov 29 18:38:40 2006 @@ -0,0 +1,384 @@ +# Copyright 2004-2005 Elemental Security, Inc. All Rights Reserved. +# Licensed to PSF under a Contributor Agreement. + +# Python imports +import token +import tokenize + +# Pgen imports +from pgen2 import grammar + +class PgenGrammar(grammar.Grammar): + pass + +class ParserGenerator(object): + + def __init__(self, filename, stream=None): + if stream is None: + stream = open(filename) + self.filename = filename + self.stream = stream + self.generator = tokenize.generate_tokens(stream.readline) + self.gettoken() # Initialize lookahead + self.dfas, self.startsymbol = self.parse() + self.first = {} # map from symbol name to set of tokens + self.addfirstsets() + + def make_grammar(self): + c = PgenGrammar() + names = self.dfas.keys() + names.sort() + names.remove(self.startsymbol) + names.insert(0, self.startsymbol) + for name in names: + i = 256 + len(c.symbol2number) + c.symbol2number[name] = i + c.number2symbol[i] = name + for name in names: + dfa = self.dfas[name] + states = [] + for state in dfa: + arcs = [] + for label, next in state.arcs.iteritems(): + arcs.append((self.make_label(c, label), dfa.index(next))) + if state.isfinal: + arcs.append((0, dfa.index(state))) + states.append(arcs) + c.states.append(states) + c.dfas[c.symbol2number[name]] = (states, self.make_first(c, name)) + c.start = c.symbol2number[self.startsymbol] + return c + + def make_first(self, c, name): + rawfirst = self.first[name] + first = {} + for label in rawfirst: + ilabel = self.make_label(c, label) + ##assert ilabel not in first # XXX failed on <> ... != + first[ilabel] = 1 + return first + + def make_label(self, c, label): + # XXX Maybe this should be a method on a subclass of converter? + ilabel = len(c.labels) + if label[0].isalpha(): + # Either a symbol name or a named token + if label in c.symbol2number: + # A symbol name (a non-terminal) + if label in c.symbol2label: + return c.symbol2label[label] + else: + c.labels.append((c.symbol2number[label], None)) + c.symbol2label[label] = ilabel + return ilabel + else: + # A named token (NAME, NUMBER, STRING) + itoken = getattr(token, label, None) + assert isinstance(itoken, int), label + assert itoken in token.tok_name, label + if itoken in c.tokens: + return c.tokens[itoken] + else: + c.labels.append((itoken, None)) + c.tokens[itoken] = ilabel + return ilabel + else: + # Either a keyword or an operator + assert label[0] in ('"', "'"), label + value = eval(label) + if value[0].isalpha(): + # A keyword + if value in c.keywords: + return c.keywords[value] + else: + c.labels.append((token.NAME, value)) + c.keywords[value] = ilabel + return ilabel + else: + # An operator (any non-numeric token) + itoken = grammar.opmap[value] # Fails if unknown token + if itoken in c.tokens: + return c.tokens[itoken] + else: + c.labels.append((itoken, None)) + c.tokens[itoken] = ilabel + return ilabel + + def addfirstsets(self): + names = self.dfas.keys() + names.sort() + for name in names: + if name not in self.first: + self.calcfirst(name) + #print name, self.first[name].keys() + + def calcfirst(self, name): + dfa = self.dfas[name] + self.first[name] = None # dummy to detect left recursion + state = dfa[0] + totalset = {} + overlapcheck = {} + for label, next in state.arcs.iteritems(): + if label in self.dfas: + if label in self.first: + fset = self.first[label] + if fset is None: + raise ValueError("recursion for rule %r" % name) + else: + self.calcfirst(label) + fset = self.first[label] + totalset.update(fset) + overlapcheck[label] = fset + else: + totalset[label] = 1 + overlapcheck[label] = {label: 1} + inverse = {} + for label, itsfirst in overlapcheck.iteritems(): + for symbol in itsfirst: + if symbol in inverse: + raise ValueError("rule %s is ambiguous; %s is in the" + " first sets of %s as well as %s" % + (name, symbol, label, inverse[symbol])) + inverse[symbol] = label + self.first[name] = totalset + + def parse(self): + dfas = {} + startsymbol = None + # MSTART: (NEWLINE | RULE)* ENDMARKER + while self.type != token.ENDMARKER: + while self.type == token.NEWLINE: + self.gettoken() + # RULE: NAME ':' RHS NEWLINE + name = self.expect(token.NAME) + self.expect(token.OP, ":") + a, z = self.parse_rhs() + self.expect(token.NEWLINE) + #self.dump_nfa(name, a, z) + dfa = self.make_dfa(a, z) + #self.dump_dfa(name, dfa) + oldlen = len(dfa) + self.simplify_dfa(dfa) + newlen = len(dfa) + dfas[name] = dfa + #print name, oldlen, newlen + if startsymbol is None: + startsymbol = name + return dfas, startsymbol + + def make_dfa(self, start, finish): + # To turn an NFA into a DFA, we define the states of the DFA + # to correspond to *sets* of states of the NFA. Then do some + # state reduction. Let's represent sets as dicts with 1 for + # values. + assert isinstance(start, NFAState) + assert isinstance(finish, NFAState) + def closure(state): + base = {} + addclosure(state, base) + return base + def addclosure(state, base): + assert isinstance(state, NFAState) + if state in base: + return + base[state] = 1 + for label, next in state.arcs: + if label is None: + addclosure(next, base) + states = [DFAState(closure(start), finish)] + for state in states: # NB states grows while we're iterating + arcs = {} + for nfastate in state.nfaset: + for label, next in nfastate.arcs: + if label is not None: + addclosure(next, arcs.setdefault(label, {})) + for label, nfaset in arcs.iteritems(): + for st in states: + if st.nfaset == nfaset: + break + else: + st = DFAState(nfaset, finish) + states.append(st) + state.addarc(st, label) + return states # List of DFAState instances; first one is start + + def dump_nfa(self, name, start, finish): + print "Dump of NFA for", name + todo = [start] + for i, state in enumerate(todo): + print " State", i, state is finish and "(final)" or "" + for label, next in state.arcs: + if next in todo: + j = todo.index(next) + else: + j = len(todo) + todo.append(next) + if label is None: + print " -> %d" % j + else: + print " %s -> %d" % (label, j) + + def dump_dfa(self, name, dfa): + print "Dump of DFA for", name + for i, state in enumerate(dfa): + print " State", i, state.isfinal and "(final)" or "" + for label, next in state.arcs.iteritems(): + print " %s -> %d" % (label, dfa.index(next)) + + def simplify_dfa(self, dfa): + # This is not theoretically optimal, but works well enough. + # Algorithm: repeatedly look for two states that have the same + # set of arcs (same labels pointing to the same nodes) and + # unify them, until things stop changing. + + # dfa is a list of DFAState instances + changes = True + while changes: + changes = False + for i, state_i in enumerate(dfa): + for j in range(i+1, len(dfa)): + state_j = dfa[j] + if state_i == state_j: + #print " unify", i, j + del dfa[j] + for state in dfa: + state.unifystate(state_j, state_i) + changes = True + break + + def parse_rhs(self): + # RHS: ALT ('|' ALT)* + a, z = self.parse_alt() + if self.value != "|": + return a, z + else: + aa = NFAState() + zz = NFAState() + aa.addarc(a) + z.addarc(zz) + while self.value == "|": + self.gettoken() + a, z = self.parse_alt() + aa.addarc(a) + z.addarc(zz) + return aa, zz + + def parse_alt(self): + # ALT: ITEM+ + a, b = self.parse_item() + while (self.value in ("(", "[") or + self.type in (token.NAME, token.STRING)): + c, d = self.parse_item() + b.addarc(c) + b = d + return a, b + + def parse_item(self): + # ITEM: '[' RHS ']' | ATOM ['+' | '*'] + if self.value == "[": + self.gettoken() + a, z = self.parse_rhs() + self.expect(token.OP, "]") + a.addarc(z) + return a, z + else: + a, z = self.parse_atom() + value = self.value + if value not in ("+", "*"): + return a, z + self.gettoken() + z.addarc(a) + if value == "+": + return a, z + else: + return a, a + + def parse_atom(self): + # ATOM: '(' RHS ')' | NAME | STRING + if self.value == "(": + self.gettoken() + a, z = self.parse_rhs() + self.expect(token.OP, ")") + return a, z + elif self.type in (token.NAME, token.STRING): + a = NFAState() + z = NFAState() + a.addarc(z, self.value) + self.gettoken() + return a, z + else: + self.raise_error("expected (...) or NAME or STRING, got %s/%s", + self.type, self.value) + + def expect(self, type, value=None): + if self.type != type or (value is not None and self.value != value): + self.raise_error("expected %s/%s, got %s/%s", + type, value, self.type, self.value) + value = self.value + self.gettoken() + return value + + def gettoken(self): + tup = self.generator.next() + while tup[0] in (tokenize.COMMENT, tokenize.NL): + tup = self.generator.next() + self.type, self.value, self.begin, self.end, self.line = tup + #print token.tok_name[self.type], repr(self.value) + + def raise_error(self, msg, *args): + if args: + try: + msg = msg % args + except: + msg = " ".join([msg] + map(str, args)) + raise SyntaxError(msg, (self.filename, self.end[0], + self.end[1], self.line)) + +class NFAState(object): + + def __init__(self): + self.arcs = [] # list of (label, NFAState) pairs + + def addarc(self, next, label=None): + assert label is None or isinstance(label, str) + assert isinstance(next, NFAState) + self.arcs.append((label, next)) + +class DFAState(object): + + def __init__(self, nfaset, final): + assert isinstance(nfaset, dict) + assert isinstance(iter(nfaset).next(), NFAState) + assert isinstance(final, NFAState) + self.nfaset = nfaset + self.isfinal = final in nfaset + self.arcs = {} # map from label to DFAState + + def addarc(self, next, label): + assert isinstance(label, str) + assert label not in self.arcs + assert isinstance(next, DFAState) + self.arcs[label] = next + + def unifystate(self, old, new): + for label, next in self.arcs.iteritems(): + if next is old: + self.arcs[label] = new + + def __eq__(self, other): + # Equality test -- ignore the nfaset instance variable + assert isinstance(other, DFAState) + if self.isfinal != other.isfinal: + return False + # Can't just return self.arcs == other.arcs, because that + # would invoke this method recursively, with cycles... + if len(self.arcs) != len(other.arcs): + return False + for label, next in self.arcs.iteritems(): + if next is not other.arcs.get(label): + return False + return True + +def generate_grammar(filename="Grammar.txt"): + p = ParserGenerator(filename) + return p.make_grammar() Added: sandbox/trunk/2to3/pgen2/python.py ============================================================================== --- (empty file) +++ sandbox/trunk/2to3/pgen2/python.py Wed Nov 29 18:38:40 2006 @@ -0,0 +1,9 @@ +#!/usr/bin/python2.5 +# Copyright 2006 Python Software Foundation. All rights reserved. + +"""Full Python grammar""" + +from __future__ import with_statement + +__author__ = "Guido van Rossum <guido@python.org>" + Added: sandbox/trunk/2to3/pgen2/test.py ============================================================================== --- (empty file) +++ sandbox/trunk/2to3/pgen2/test.py Wed Nov 29 18:38:40 2006 @@ -0,0 +1,18 @@ +# Copyright 2004-2005 Elemental Security, Inc. All Rights Reserved. +# Licensed to PSF under a Contributor Agreement. + +def test(): + import sys + sys.path[0] = ".." + from pgen2 import astnode, driver + f = open("Grammar.txt", "w") + try: + astnode.generate_grammar(f) + finally: + f.close() + sample = "year<=1989 ? ('Modula-3' + ABC) ** 2 : Python" + tree = driver.parse_string(sample, True) + print tree + +if __name__ == "__main__": + test() Added: sandbox/trunk/2to3/play.py ============================================================================== --- (empty file) +++ sandbox/trunk/2to3/play.py Wed Nov 29 18:38:40 2006 @@ -0,0 +1,66 @@ +#!/usr/bin/env python2.5 +# Copyright 2006 Python Software Foundation. All Rights Reserved. + +"""XXX.""" + +from __future__ import with_statement + +__author__ = "Guido van Rossum <guido@python.org>" + +# Python imports +import os +import sys +import logging + +import pgen2 +from pgen2 import driver + +import pynode + +logging.basicConfig(level=logging.INFO) + +SAMPLE = """\ +for i in range(10): + print i +class C(object, list): + def f(a, b, c=1, *args, **kwds): + pass +""" + +def main(): + gr = driver.load_grammar("Grammar.txt") + dr = driver.Driver(gr, convert=pynode.convert) + +## tree = dr.parse_file("pynode.py", debug=True) +## print tree + +## for name in sys.modules: +## mod = sys.modules[name] +## if mod is None or not hasattr(mod, "__file__"): +## continue +## fn = mod.__file__ +## if fn.endswith(".pyc"): +## fn = fn[:-1] +## if not fn.endswith(".py"): +## continue +## print >>sys.stderr, "Parsing", fn +## dr.parse_file(fn, debug=True) + + for dir in reversed(sys.path): + try: + names = os.listdir(dir) + except os.error: + continue + print >>sys.stderr, "Scanning", dir, "..." + for name in names: + if not name.endswith(".py"): + continue + print >>sys.stderr, "Parsing", name + try: + dr.parse_file(os.path.join(dir, name), debug=True) + except pgen2.parse.ParseError, err: + print "ParseError:", err + + +if __name__ == "__main__": + main() Added: sandbox/trunk/2to3/pynode.py ============================================================================== --- (empty file) +++ sandbox/trunk/2to3/pynode.py Wed Nov 29 18:38:40 2006 @@ -0,0 +1,698 @@ +# Copyright 2004-2005 Elemental Security, Inc. All Rights Reserved. +# Licensed to PSF under a Contributor Agreement. + +# Modifications: +# Copyright 2006 Python Software Foundation. All Rights Reserved. + +"""Syntax tree node definitions. + +There is a class or function corresponding to each terminal and +nonterminal symbol. + +The grammar is pieced together from the docstrings of the +corresponding classes and functions: text between dollar signs is +assumed to be the right-hand side of the grammar rule corresponding to +that class or function. + +We use __slots__ to make the parse tree nodes as small as possible. + +NOTE: EVERY CLASS MUST HAVE A __slots__ DEFINITION, EVEN IF EMPTY! +(If not, the instances will get a __dict__, defeating the purpose of +__slots__ in our case.) +""" + +__author__ = "Guido van Rossum <guido@python.org>" + +# Python imports +import token +import logging + +# Pgen imports +from pgen2 import grammar + +# Custom logger +logger = logging.getLogger() + +class Node(object): + """Abstract base class for all nodes. + + This has no attributes except a context slot which holds the line + number (or more detailed context info). In the future this might + change this to several slots (e.g. filename, lineno, column, or + even filename, start_lineno, start_column, end_lineno, + end_column). The context is only referenced by two places: the + part of the code that sticks it in, and the part of the code that + reports errors. + + In order to reduce the amount of boilerplate code, the context is + argument is handled by __new__ rather than __init__. There are + also a few subclasses that override __new__ to sometimes avoid + constructing an instance. + + """ + + __slots__ = ["context"] + + def __new__(cls, context, *rest): + assert cls not in (Node, Nonterminal, Terminal, Constant) + obj = object.__new__(cls) + obj.context = context + return obj + + _stretch = False # Set to true to stretch the repr() vertically + + def __repr__(self, repr=repr): + stretch = self._stretch + r = [self.__class__.__name__] + if stretch: + r.append("(\n ") + else: + r.append("(") # ")" -- crutch for Emacs python-mode :-( + cls = self.__class__ + # Get nearest non-empty slots __slots__. This assumes + # *something* has non-empty __slots__ before we reach object + # (which has no __slots__). The class hierarchy guarantees + # this. + slots = cls.__slots__ + while not slots: + cls = cls.__base__ + slots = cls.__slots__ + first = True + for name in slots: + if name == "context": + continue # Skip this + if first: + first = False + else: + if stretch: + r.append(",\n ") + else: + r.append(", ") + try: + value = getattr(self, name) + except AttributeError: + continue + if stretch and isinstance(value, list): + rr = map(repr, value) + rv = "[" + ",\n ".join(rr) + "]" + else: + rv = repr(value) + if stretch: + rv = rv.replace("\n", "\n ") + r.append(rv) + r.append(")") + return "".join(r) + + def __str__(self): + return self.__repr__(repr=str) + +class Nonterminal(Node): + """Abstract base class for nonterminal symbols. + + Nothing beyond Node. + + """ + + __slots__ = [] + + _stretch = True + +class Terminal(Node): + """Abstract base class for terminal symbols. + + Nothing beyond Node. + + """ + + __slots__ = [] + +class Series(Nonterminal): + """Abstract base class for nonterminals like stmts: stmt+.""" + + __slots__ = [] + + def __new__(cls, context, *nodes): + assert cls is not Series + if len(nodes) == 0: + return None + elif len(nodes) == 1: + return nodes[0] + else: + obj = Nonterminal.__new__(cls, context) + obj.initseries(nodes) + return obj + +class Constant(Terminal): + """Abstract base class for constants (e.g. number or string). + + Attributes: + + repr -- a string giving the token, exactly as read from source + + """ + + __slots__ = ["repr"] + + def __init__(self, context, repr): + self.repr = repr + + def __str__(self): + return self.repr + +# Node classes for terminal symbols + +class Name(Terminal): + """Name (e.g. a variable name or an attribute name). + + Attributes: + + name -- a string giving the name. + + """ + + __slots__ = ["name"] + + def __init__(self, context, name): + self.name = name + + def __str__(self): + return self.name + +class Number(Constant): + """Numeric constant. + + Nothing beyond Constant. + + """ + + __slots__ = [] + +class String(Constant): + """String constant. + + Nothing beyond Constant. + + """ + + __slots__ = [] + +# Nodes and factory functions for Python grammar + +class VanishingNonterminal(Nonterminal): + __slots__ = [] + def __new__(cls, context, node): + return node + +class GenericSeries(Series): + __slots__ = ["nodes"] + def initseries(self, nodes): + self.nodes = nodes + +class atom(GenericSeries): + __slots__ = [] + +class power(GenericSeries): + __slots__ = [] + +class factor(GenericSeries): + __slots__ = [] + +class term(GenericSeries): + __slots__ = [] + +class arith_expr(GenericSeries): + __slots__ = [] + +class shift_expr(GenericSeries): + __slots__ = [] + +class and_expr(GenericSeries): + __slots__ = [] + +class xor_expr(GenericSeries): + __slots__ = [] + +class or_expr(GenericSeries): + __slots__ = [] + +class expr(GenericSeries): + __slots__ = [] + +class comparison(GenericSeries): + __slots__ = [] + +class not_test(GenericSeries): + __slots__ = [] + +class and_test(GenericSeries): + __slots__ = [] + +class or_test(GenericSeries): + __slots__ = [] + +class test(GenericSeries): + __slots__ = [] + +class testlist(GenericSeries): + __slots__ = [] + +class expr_stmt(GenericSeries): + __slots__ = [] + +class trailer(GenericSeries): + __slots__ = [] + +class argument(GenericSeries): + __slots__ = [] + +class arglist(GenericSeries): + __slots__ = [] + +class subscript(GenericSeries): + __slots__ = [] + +class subscriptlist(GenericSeries): + __slots__ = [] + +class listmaker(GenericSeries): + __slots__ = [] + +class testlist_gexp(GenericSeries): + __slots__ = [] + +class suite(GenericSeries): + __slots__ = [] + +class if_stmt(GenericSeries): + __slots__ = [] + +class compound_stmt(GenericSeries): + __slots__ = [] + +class parameters(GenericSeries): + __slots__ = [] + +class funcdef(GenericSeries): + __slots__ = [] + +class fpdef(GenericSeries): + __slots__ = [] + +class varargslist(GenericSeries): + __slots__ = [] + +class classdef(GenericSeries): + __slots__ = [] + +class exprlist(GenericSeries): + __slots__ = [] + +class print_stmt(GenericSeries): + __slots__ = [] + +class for_stmt(GenericSeries): + __slots__ = [] + +class dotted_name(GenericSeries): + __slots__ = [] + +class dotted_as_name(GenericSeries): + __slots__ = [] + +class dotted_as_names(GenericSeries): + __slots__ = [] + +class import_as_names(GenericSeries): + __slots__ = [] + +class import_as_name(GenericSeries): + __slots__ = [] + +class import_name(GenericSeries): + __slots__ = [] + +class import_from(GenericSeries): + __slots__ = [] + +class import_stmt(GenericSeries): + __slots__ = [] + +class comp_op(GenericSeries): + __slots__ = [] + +class assert_stmt(GenericSeries): + __slots__ = [] + +class return_stmt(GenericSeries): + __slots__ = [] + +class continue_stmt(GenericSeries): + __slots__ = [] + +class break_stmt(GenericSeries): + __slots__ = [] + +class flow_stmt(GenericSeries): + __slots__ = [] + +class while_stmt(GenericSeries): + __slots__ = [] + +class except_clause(GenericSeries): + __slots__ = [] + +class try_stmt(GenericSeries): + __slots__ = [] + +class dictmaker(GenericSeries): + __slots__ = [] + +class raise_stmt(GenericSeries): + __slots__ = [] + +class del_stmt(GenericSeries): + __slots__ = [] + +class exec_stmt(GenericSeries): + __slots__ = [] + +class augassign(GenericSeries): + __slots__ = [] + +class global_stmt(GenericSeries): + __slots__ = [] + +class fplist(GenericSeries): + __slots__ = [] + +class lambdef(GenericSeries): + __slots__ = [] + +class old_test(GenericSeries): + __slots__ = [] + +class testlist_safe(GenericSeries): + __slots__ = [] + +class list_for(GenericSeries): + __slots__ = [] + +class decorator(GenericSeries): + __slots__ = [] + +class decorators(GenericSeries): + __slots__ = [] + +class yield_expr(GenericSeries): + __slots__ = [] + +class yield_stmt(GenericSeries): + __slots__ = [] + +class list_if(GenericSeries): + __slots__ = [] + +class list_iter(GenericSeries): + __slots__ = [] + +class gen_for(GenericSeries): + __slots__ = [] + +class gen_iter(GenericSeries): + __slots__ = [] + +class gen_if(GenericSeries): + __slots__ = [] + +class with_var(GenericSeries): + __slots__ = [] + +class with_stmt(GenericSeries): + __slots__ = [] + +class sliceop(GenericSeries): + __slots__ = [] + +class testlist1(GenericSeries): + __slots__ = [] + + +def _transparent(context, node, *rest): + assert rest == (), (context, node, rest) + return node + +pass_stmt = _transparent +small_stmt = _transparent +stmt = _transparent + +class simple_stmt(GenericSeries): + __slots__ = [] + +class file_input(GenericSeries): + __slots__ = [] + + +# Example nodes and factory functions for nonterminal symbols +# XXX: get rid of these + +def Program(context, stmts): + """Program is a nonterminal with only one non-trivial child. + + Grammar: $ Expression ENDMARKER $ + + """ + return stmts + +class Expression(Series): + "Grammar: $ BinaryExpression ['?' BinaryExpression ':' BinaryExpression] $" + + __slots__ = ["test", "left", "right"] + + def initseries(self, nodes): + self.test, self.left, self.right = nodes + + def __str__(self): + return "%s ? %s : %s" % (self.test, self.left, self.right) + +class BinaryExpression(Series): + "Grammar: $ Operand (Operator Operand)* $" + + __slots__ = ["left", "op", "right"] + + def initseries(self, stuff): + # Stuff is a list with alternating operands and operators + if len(stuff) == 3: + self.left, self.op, self.right = stuff + return + assert len(stuff) > 1 and len(stuff) % 2 == 1 + # Find the rightmost lowest-priority operator + lowest_i = 1 + lowest_op = stuff[lowest_i] + lowest_pri = lowest_op.priority() + for i in range(3, len(stuff), 2): + op = stuff[i] + pri = op.priority() + if pri <= lowest_pri: + lowest_i = i + lowest_op = op + lowest_pri = pri + self.left = self.__class__(self.context, *stuff[:lowest_i]) + self.op = lowest_op + self.right = self.__class__(self.context, *stuff[lowest_i+1:]) + + def __str__(self): + return "(%s %s %s)" % (self.left, self.op, self.right) + +def Operand(context, arg): + """Operand is a nonterminal with one child. + + Grammar: $ Atom | UnaryExpression $ + + """ + return arg + +class UnaryExpression(Nonterminal): + "Grammar: $ UnaryOperator Operand $" + + __slots__ = ["op", "arg"] + + def __init__(self, context, op, arg): + self.op = op + self.arg = arg + + def __str__(self): + return "%s%s" % (self.op, self.arg) + +def UnaryOperator(context, op): + "Grammar: $ 'not' | '-' $" + return op + +class Operator(Nonterminal): + """Operator. + + This has a repr slot and a priority() method. + + The __new__ method implements a sort-of singleton pattern: there's + only one instance per repr value. (Yes, this means the context is + not useful. Therefore we set it to None.) + + Grammar: $ '**' | '*' | '/' | '+' | '-' | '&' | '^' | '|' | + ['not'] 'in' | '==' | '<' | '>' | '!=' | '<=' | '>=' | + 'and' | 'or' $ + + """ + + __slots__ = ["repr"] + + _stretch = False + + _cache = {} + + def __new__(cls, context, *args): + repr = " ".join(args) + # For "not in", the argument should be the string "not in" + obj = cls._cache.get(repr) + if obj is None: + obj = Terminal.__new__(cls, None) + obj.repr = repr + return obj + + def __str__(self): + return self.repr + + def priority(self): + return self._priorities[self.repr] + + _priorities = { + "or": 0, + "and": 1, + "in": 2, + "not in": 2, + "<": 2, + ">": 2, + "==": 2, + "<=": 2, + ">=": 2, + "!=": 2, + "|": 3, + "^": 4, + "&": 5, + "+": 6, + "-": 6, + "*": 7, + "/": 7, + "**": 8, + } + +def Atom(context, arg): + """ Grammar: $ NAME | STRING | NUMBER | ParenthesizedExpression $ + """ + return arg + +def ParenthesizedExpression(context, expr): + "Grammar: $ '(' Expression ')' $" + return expr + + +# Conversion from concrete to abstract syntax trees + +def vanish(context, value): + return None + +token_mapping = { + # Tokens that become parse tree nodes + # (token.NAME is special-cased in the code) + token.NUMBER: Number, + token.STRING: String, + +## # Tokens that vanish +## token.DOT: vanish, +## token.LPAR: vanish, +## token.RPAR: vanish, +## token.COLON: vanish, +## token.COMMA: vanish, +## token.EQUAL: vanish, +## token.DEDENT: vanish, +## token.INDENT: vanish, +## token.LBRACE: vanish, +## token.RBRACE: vanish, +## token.NEWLINE: vanish, + token.ENDMARKER: vanish, +## grammar.QUESTIONMARK: vanish, + + # All other tokens return the token's string value (e.g. "+") + } + +vanishing_keywords = { + # E.g. "def": True, + } + +def convert(grammar, node): + type, value, context, children = node + # Is it a non-terminal symbol? + if type in grammar.number2symbol: + symbol = grammar.number2symbol[type] + factory = globals().get(symbol) + if factory is None: + raise RuntimeError("can't find factory for %s (line %s)" % + (symbol, context)) + # Debug variation: + try: + return factory(context, *children) + except: + logger.debug("%s %s", factory.__name__, "(") + for child in children: + logger.debug("%s %s", "==>", child) + logger.debug(")") + logger.debug("# Did you remember to declare a 'context' arg?") + raise + return factory(context, *children) + + # Must be a terminal symbol. + if type == token.NAME: + # Name or keyword. Special-case the snot out of this. + if value in grammar.keywords: + # Keywords become strings, like operators + if value in vanishing_keywords: + return None + else: + return value + else: + return Name(context, value) + + # Look for a handler in the token_mapping table. + assert type in token.tok_name + factory = token_mapping.get(type) + if factory: + return factory(context, value) + else: + return value + + +# Support code + +def generate_grammar(stream): + """Extract the grammar rules from this module's doc strings.""" + import re + from types import ModuleType + lines = [] + startline = None + for name, obj in globals().items(): + if hasattr(obj, "__doc__") and not isinstance(obj, ModuleType): + m = re.search(r"Grammar:\s*\$([^$]+)\$", obj.__doc__ or "") + if m: + rule = obj.__name__, " ".join(m.group(1).split()) + if rule[0] == "Program": + assert not startline + startline = rule + else: + lines.append(rule) + lines.sort() + # The start symbol *must* be the first rule + lines.insert(0, startline) + for name, rhs in lines: + stream.write("%s: %s\n" % (name, rhs)) + +if __name__ == '__main__': + import sys + generate_grammar(sys.stdout)