\section{\module{parser} ---         Access Python parse trees} % Copyright 1995 Virginia Polytechnic Institute and State University% and Fred L. Drake, Jr.  This copyright notice must be distributed on% all copies, but this document otherwise may be distributed as part% of the Python distribution.  No fee may be charged for this document% in any representation, either on paper or electronically.  This% restriction does not affect other elements in a distributed package% in any way. \declaremodule{builtin}{parser}\modulesynopsis{Access parse trees for Python source code.}\moduleauthor{Fred L. Drake, Jr.}{fdrake@acm.org}\sectionauthor{Fred L. Drake, Jr.}{fdrake@acm.org}  \index{parsing!Python source code} The \module{parser} module provides an interface to Python's internalparser and byte-code compiler.  The primary purpose for this interfaceis to allow Python code to edit the parse tree of a Python expressionand create executable code from this.  This is better than tryingto parse and modify an arbitrary Python code fragment as a stringbecause parsing is performed in a manner identical to the codeforming the application.  It is also faster. There are a few things to note about this module which are importantto making use of the data structures created.  This is not a tutorialon editing the parse trees for Python code, but some examples of usingthe \module{parser} module are presented. Most importantly, a good understanding of the Python grammar processedby the internal parser is required.  For full information on thelanguage syntax, refer to the \citetitle[../ref/ref.html]{PythonLanguage Reference}.  The parser itself is created from a grammarspecification defined in the file \file{Grammar/Grammar} in thestandard Python distribution.  The parse trees stored in the ASTobjects created by this module are the actual output from the internalparser when created by the \function{expr()} or \function{suite()}functions, described below.  The AST objects created by\function{sequence2ast()} faithfully simulate those structures.  Beaware that the values of the sequences which are considered``correct'' will vary from one version of Python to another as theformal grammar for the language is revised.  However, transportingcode from one Python version to another as source text will alwaysallow correct parse trees to be created in the target version, withthe only restriction being that migrating to an older version of theinterpreter will not support more recent language constructs.  Theparse trees are not typically compatible from one version to another,whereas source code has always been forward-compatible. Each element of the sequences returned by \function{ast2list()} or\function{ast2tuple()} has a simple form.  Sequences representingnon-terminal elements in the grammar always have a length greater thanone.  The first element is an integer which identifies a production inthe grammar.  These integers are given symbolic names in the C headerfile \file{Include/graminit.h} and the Python module\refmodule{symbol}.  Each additional element of the sequence representsa component of the production as recognized in the input string: theseare always sequences which have the same form as the parent.  Animportant aspect of this structure which should be noted is thatkeywords used to identify the parent node type, such as the keyword\keyword{if} in an \constant{if_stmt}, are included in the node tree withoutany special treatment.  For example, the \keyword{if} keyword isrepresented by the tuple \code{(1, 'if')}, where \code{1} is thenumeric value associated with all \constant{NAME} tokens, includingvariable and function names defined by the user.  In an alternate formreturned when line number information is requested, the same tokenmight be represented as \code{(1, 'if', 12)}, where the \code{12}represents the line number at which the terminal symbol was found. Terminal elements are represented in much the same way, but withoutany child elements and the addition of the source text which wasidentified.  The example of the \keyword{if} keyword above isrepresentative.  The various types of terminal symbols are defined inthe C header file \file{Include/token.h} and the Python module\refmodule{token}. The AST objects are not required to support the functionality of thismodule, but are provided for three purposes: to allow an applicationto amortize the cost of processing complex parse trees, to provide aparse tree representation which conserves memory space when comparedto the Python list or tuple representation, and to ease the creationof additional modules in C which manipulate parse trees.  A simple``wrapper'' class may be created in Python to hide the use of ASTobjects. The \module{parser} module defines functions for a few distinctpurposes.  The most important purposes are to create AST objects andto convert AST objects to other representations such as parse treesand compiled code objects, but there are also functions which serve toquery the type of parse tree represented by an AST object.  \begin{seealso}  \seemodule{symbol}{Useful constants representing internal nodes of                     the parse tree.}  \seemodule{token}{Useful constants representing leaf nodes of the                    parse tree and functions for testing node values.}\end{seealso}  \subsection{Creating AST Objects \label{Creating ASTs}} AST objects may be created from source code or from a parse tree.When creating an AST object from source, different functions are usedto create the \code{'eval'} and \code{'exec'} forms. \begin{funcdesc}{expr}{source}The \function{expr()} function parses the parameter \var{source}as if it were an input to \samp{compile(\var{source}, 'file.py','eval')}.  If the parse succeeds, an AST object is created to hold theinternal parse tree representation, otherwise an appropriate exceptionis thrown.\end{funcdesc} \begin{funcdesc}{suite}{source}The \function{suite()} function parses the parameter \var{source}as if it were an input to \samp{compile(\var{source}, 'file.py','exec')}.  If the parse succeeds, an AST object is created to hold theinternal parse tree representation, otherwise an appropriate exceptionis thrown.\end{funcdesc} \begin{funcdesc}{sequence2ast}{sequence}This function accepts a parse tree represented as a sequence andbuilds an internal representation if possible.  If it can validatethat the tree conforms to the Python grammar and all nodes are validnode types in the host version of Python, an AST object is createdfrom the internal representation and returned to the called.  If thereis a problem creating the internal representation, or if the treecannot be validated, a \exception{ParserError} exception is thrown.  An ASTobject created this way should not be assumed to compile correctly;normal exceptions thrown by compilation may still be initiated whenthe AST object is passed to \function{compileast()}.  This may indicateproblems not related to syntax (such as a \exception{MemoryError}exception), but may also be due to constructs such as the result ofparsing \code{del f(0)}, which escapes the Python parser but ischecked by the bytecode compiler. Sequences representing terminal tokens may be represented as eithertwo-element lists of the form \code{(1, 'name')} or as three-elementlists of the form \code{(1, 'name', 56)}.  If the third element ispresent, it is assumed to be a valid line number.  The line numbermay be specified for any subset of the terminal symbols in the inputtree.\end{funcdesc} \begin{funcdesc}{tuple2ast}{sequence}This is the same function as \function{sequence2ast()}.  This entry pointis maintained for backward compatibility.\end{funcdesc}  \subsection{Converting AST Objects \label{Converting ASTs}} AST objects, regardless of the input used to create them, may beconverted to parse trees represented as list- or tuple- trees, or maybe compiled into executable code objects.  Parse trees may beextracted with or without line numbering information. \begin{funcdesc}{ast2list}{ast\optional{, line_info}}This function accepts an AST object from the caller in\var{ast} and returns a Python list representing theequivalent parse tree.  The resulting list representation can be usedfor inspection or the creation of a new parse tree in list form.  Thisfunction does not fail so long as memory is available to build thelist representation.  If the parse tree will only be used forinspection, \function{ast2tuple()} should be used instead to reduce memoryconsumption and fragmentation.  When the list representation isrequired, this function is significantly faster than retrieving atuple representation and converting that to nested lists. If \var{line_info} is true, line number information will beincluded for all terminal tokens as a third element of the listrepresenting the token.  Note that the line number provided specifiesthe line on which the token \emph{ends}.  This information isomitted if the flag is false or omitted.\end{funcdesc} \begin{funcdesc}{ast2tuple}{ast\optional{, line_info}}This function accepts an AST object from the caller in\var{ast} and returns a Python tuple representing theequivalent parse tree.  Other than returning a tuple instead of alist, this function is identical to \function{ast2list()}. If \var{line_info} is true, line number information will beincluded for all terminal tokens as a third element of the listrepresenting the token.  This information is omitted if the flag isfalse or omitted.\end{funcdesc} \begin{funcdesc}{compileast}{ast\optional{, filename\code{ = '<ast>'}}}The Python byte compiler can be invoked on an AST object to producecode objects which can be used as part of an \keyword{exec} statement ora call to the built-in \function{eval()}\bifuncindex{eval} function.This function provides the interface to the compiler, passing theinternal parse tree from \var{ast} to the parser, using thesource file name specified by the \var{filename} parameter.The default value supplied for \var{filename} indicates thatthe source was an AST object. Compiling an AST object may result in exceptions related tocompilation; an example would be a \exception{SyntaxError} caused by theparse tree for \code{del f(0)}: this statement is considered legalwithin the formal grammar for Python but is not a legal languageconstruct.  The \exception{SyntaxError} raised for this condition isactually generated by the Python byte-compiler normally, which is whyit can be raised at this point by the \module{parser} module.  Mostcauses of compilation failure can be diagnosed programmatically byinspection of the parse tree.\end{funcdesc}  \subsection{Queries on AST Objects \label{Querying ASTs}} Two functions are provided which allow an application to determine ifan AST was created as an expression or a suite.  Neither of thesefunctions can be used to determine if an AST was created from sourcecode via \function{expr()} or \function{suite()} or from a parse treevia \function{sequence2ast()}. \begin{funcdesc}{isexpr}{ast}When \var{ast} represents an \code{'eval'} form, this functionreturns true, otherwise it returns false.  This is useful, since codeobjects normally cannot be queried for this information using existingbuilt-in functions.  Note that the code objects created by\function{compileast()} cannot be queried like this either, and areidentical to those created by the built-in\function{compile()}\bifuncindex{compile} function.\end{funcdesc}  \begin{funcdesc}{issuite}{ast}This function mirrors \function{isexpr()} in that it reports whether anAST object represents an \code{'exec'} form, commonly known as a``suite.''  It is not safe to assume that this function is equivalentto \samp{not isexpr(\var{ast})}, as additional syntactic fragments maybe supported in the future.\end{funcdesc}  \subsection{Exceptions and Error Handling \label{AST Errors}} The parser module defines a single exception, but may also pass otherbuilt-in exceptions from other portions of the Python runtimeenvironment.  See each function for information about the exceptionsit can raise. \begin{excdesc}{ParserError}Exception raised when a failure occurs within the parser module.  Thisis generally produced for validation failures rather than the built in\exception{SyntaxError} thrown during normal parsing.The exception argument is either a string describing the reason of thefailure or a tuple containing a sequence causing the failure from a parsetree passed to \function{sequence2ast()} and an explanatory string.  Calls to\function{sequence2ast()} need to be able to handle either type of exception,while calls to other functions in the module will only need to beaware of the simple string values.\end{excdesc} Note that the functions \function{compileast()}, \function{expr()}, and\function{suite()} may throw exceptions which are normally thrown by theparsing and compilation process.  These include the built inexceptions \exception{MemoryError}, \exception{OverflowError},\exception{SyntaxError}, and \exception{SystemError}.  In these cases, theseexceptions carry all the meaning normally associated with them.  Referto the descriptions of each function for detailed information.  \subsection{AST Objects \label{AST Objects}} Ordered and equality comparisons are supported between AST objects.Pickling of AST objects (using the \refmodule{pickle} module) is alsosupported. \begin{datadesc}{ASTType}The type of the objects returned by \function{expr()},\function{suite()} and \function{sequence2ast()}.\end{datadesc}  AST objects have the following methods:  \begin{methoddesc}[AST]{compile}{\optional{filename}}Same as \code{compileast(\var{ast}, \var{filename})}.\end{methoddesc} \begin{methoddesc}[AST]{isexpr}{}Same as \code{isexpr(\var{ast})}.\end{methoddesc} \begin{methoddesc}[AST]{issuite}{}Same as \code{issuite(\var{ast})}.\end{methoddesc} \begin{methoddesc}[AST]{tolist}{\optional{line_info}}Same as \code{ast2list(\var{ast}, \var{line_info})}.\end{methoddesc} \begin{methoddesc}[AST]{totuple}{\optional{line_info}}Same as \code{ast2tuple(\var{ast}, \var{line_info})}.\end{methoddesc}  \subsection{Examples \label{AST Examples}} The parser modules allows operations to be performed on the parse treeof Python source code before the bytecode is generated, and providesfor inspection of the parse tree for information gathering purposes.Two examples are presented.  The simple example demonstrates emulationof the \function{compile()}\bifuncindex{compile} built-in function andthe complex example shows the use of a parse tree for informationdiscovery. \subsubsection{Emulation of \function{compile()}} While many useful operations may take place between parsing andbytecode generation, the simplest operation is to do nothing.  Forthis purpose, using the \module{parser} module to produce anintermediate data structure is equivalent to the code \begin{verbatim}>>> code = compile('a + 5', 'file.py', 'eval')>>> a = 5>>> eval(code)10\end{verbatim} The equivalent operation using the \module{parser} module is somewhatlonger, and allows the intermediate internal parse tree to be retainedas an AST object: \begin{verbatim}>>> import parser>>> ast = parser.expr('a + 5')>>> code = ast.compile('file.py')>>> a = 5>>> eval(code)10\end{verbatim} An application which needs both AST and code objects can package thiscode into readily available functions: \begin{verbatim}import parser def load_suite(source_string):    ast = parser.suite(source_string)    return ast, ast.compile() def load_expression(source_string):    ast = parser.expr(source_string)    return ast, ast.compile()\end{verbatim} \subsubsection{Information Discovery} Some applications benefit from direct access to the parse tree.  Theremainder of this section demonstrates how the parse tree providesaccess to module documentation defined indocstrings\index{string!documentation}\index{docstrings} withoutrequiring that the code being examined be loaded into a runninginterpreter via \keyword{import}.  This can be very useful forperforming analyses of untrusted code. Generally, the example will demonstrate how the parse tree may betraversed to distill interesting information.  Two functions and a setof classes are developed which provide programmatic access to highlevel function and class definitions provided by a module.  Theclasses extract information from the parse tree and provide access tothe information at a useful semantic level, one function provides asimple low-level pattern matching capability, and the other functiondefines a high-level interface to the classes by handling fileoperations on behalf of the caller.  All source files mentioned herewhich are not part of the Python installation are located in the\file{Demo/parser/} directory of the distribution. The dynamic nature of Python allows the programmer a great deal offlexibility, but most modules need only a limited measure of this whendefining classes, functions, and methods.  In this example, the onlydefinitions that will be considered are those which are defined in thetop level of their context, e.g., a function defined by a \keyword{def}statement at column zero of a module, but not a function definedwithin a branch of an \keyword{if} ... \keyword{else} construct, thoughthere are some good reasons for doing so in some situations.  Nestingof definitions will be handled by the code developed in the example. To construct the upper-level extraction methods, we need to know whatthe parse tree structure looks like and how much of it we actuallyneed to be concerned about.  Python uses a moderately deep parse treeso there are a large number of intermediate nodes.  It is important toread and understand the formal grammar used by Python.  This isspecified in the file \file{Grammar/Grammar} in the distribution.Consider the simplest case of interest when searching for docstrings:a module consisting of a docstring and nothing else.  (See file\file{docstring.py}.) \begin{verbatim}"""Some documentation."""\end{verbatim} Using the interpreter to take a look at the parse tree, we find abewildering mass of numbers and parentheses, with the documentationburied deep in nested tuples. \begin{verbatim}>>> import parser>>> import pprint>>> ast = parser.suite(open('docstring.py').read())>>> tup = ast.totuple()>>> pprint.pprint(tup)(257, (264,  (265,   (266,    (267,     (307,      (287,       (288,        (289,         (290,          (292,           (293,            (294,             (295,              (296,               (297,                (298,                 (299,                  (300, (3, '"""Some documentation.\n"""'))))))))))))))))),   (4, ''))), (4, ''), (0, ''))\end{verbatim} The numbers at the first element of each node in the tree are the nodetypes; they map directly to terminal and non-terminal symbols in thegrammar.  Unfortunately, they are represented as integers in theinternal representation, and the Python structures generated do notchange that.  However, the \refmodule{symbol} and \refmodule{token} modulesprovide symbolic names for the node types and dictionaries which mapfrom the integers to the symbolic names for the node types. In the output presented above, the outermost tuple contains fourelements: the integer \code{257} and three additional tuples.  Nodetype \code{257} has the symbolic name \constant{file_input}.  Each ofthese inner tuples contains an integer as the first element; theseintegers, \code{264}, \code{4}, and \code{0}, represent the node types\constant{stmt}, \constant{NEWLINE}, and \constant{ENDMARKER},respectively.Note that these values may change depending on the version of Pythonyou are using; consult \file{symbol.py} and \file{token.py} fordetails of the mapping.  It should be fairly clear that the outermostnode is related primarily to the input source rather than the contentsof the file, and may be disregarded for the moment.  The \constant{stmt}node is much more interesting.  In particular, all docstrings arefound in subtrees which are formed exactly as this node is formed,with the only difference being the string itself.  The associationbetween the docstring in a similar tree and the defined entity (class,function, or module) which it describes is given by the position ofthe docstring subtree within the tree defining the describedstructure. By replacing the actual docstring with something to signify a variablecomponent of the tree, we allow a simple pattern matching approach tocheck any given subtree for equivalence to the general pattern fordocstrings.  Since the example demonstrates information extraction, wecan safely require that the tree be in tuple form rather than listform, allowing a simple variable representation to be\code{['variable_name']}.  A simple recursive function can implementthe pattern matching, returning a Boolean and a dictionary of variablename to value mappings.  (See file \file{example.py}.) \begin{verbatim}from types import ListType, TupleType def match(pattern, data, vars=None):    if vars is None:        vars = {}    if type(pattern) is ListType:        vars[pattern[0]] = data        return 1, vars    if type(pattern) is not TupleType:        return (pattern == data), vars    if len(data) != len(pattern):        return 0, vars    for pattern, data in map(None, pattern, data):        same, vars = match(pattern, data, vars)        if not same:            break    return same, vars\end{verbatim} Using this simple representation for syntactic variables and the symbolicnode types, the pattern for the candidate docstring subtrees becomes

Lines 1–500 of 711. Load more