Guido van Rossum | 4b73a06 | 1995-10-11 17:30:04 +0000 | [diff] [blame] | 1 | % libparser.tex |
| 2 | % |
| 3 | % Introductory documentation for the new parser built-in module. |
| 4 | % |
| 5 | % Copyright 1995 Virginia Polytechnic Institute and State University |
| 6 | % and Fred L. Drake, Jr. This copyright notice must be distributed on |
| 7 | % all copies, but this document otherwise may be distributed as part |
| 8 | % of the Python distribution. No fee may be charged for this document |
| 9 | % in any representation, either on paper or electronically. This |
| 10 | % restriction does not affect other elements in a distributed package |
| 11 | % in any way. |
| 12 | % |
| 13 | |
| 14 | \section{Built-in Module \sectcode{parser}} |
| 15 | \bimodindex{parser} |
| 16 | |
Guido van Rossum | 4b73a06 | 1995-10-11 17:30:04 +0000 | [diff] [blame] | 17 | The \code{parser} module provides an interface to Python's internal |
| 18 | parser and byte-code compiler. The primary purpose for this interface |
| 19 | is to allow Python code to edit the parse tree of a Python expression |
| 20 | and create executable code from this. This can be better than trying |
| 21 | to parse and modify an arbitrary Python code fragment as a string, and |
| 22 | ensures that parsing is performed in a manner identical to the code |
| 23 | forming the application. It's also faster. |
| 24 | |
| 25 | There are a few things to note about this module which are important |
| 26 | to making use of the data structures created. This is not a tutorial |
| 27 | on editing the parse trees for Python code. |
| 28 | |
| 29 | Most importantly, a good understanding of the Python grammar processed |
| 30 | by the internal parser is required. For full information on the |
| 31 | language syntax, refer to the Language Reference. The parser itself |
| 32 | is created from a grammar specification defined in the file |
| 33 | \code{Grammar/Grammar} in the standard Python distribution. The parse |
| 34 | trees stored in the ``AST objects'' created by this module are the |
| 35 | actual output from the internal parser when created by the |
| 36 | \code{expr()} or \code{suite()} functions, described below. The AST |
Guido van Rossum | 4747887 | 1996-08-21 14:32:37 +0000 | [diff] [blame] | 37 | objects created by \code{sequence2ast()} faithfully simulate those |
| 38 | structures. Be aware that the values of the sequences which are |
| 39 | considered ``correct'' will vary from one version of Python to another |
| 40 | as the formal grammar for the language is revised. However, |
| 41 | transporting code from one Python version to another as source text |
| 42 | will always allow correct parse trees to be created in the target |
| 43 | version, with the only restriction being that migrating to an older |
| 44 | version of the interpreter will not support more recent language |
| 45 | constructs. The parse trees are not typically compatible from one |
| 46 | version to another, whereas source code has always been |
| 47 | forward-compatible. |
Guido van Rossum | 4b73a06 | 1995-10-11 17:30:04 +0000 | [diff] [blame] | 48 | |
Guido van Rossum | 4747887 | 1996-08-21 14:32:37 +0000 | [diff] [blame] | 49 | Each element of the sequences returned by \code{ast2list} or |
| 50 | \code{ast2tuple()} has a simple form. Sequences representing |
| 51 | non-terminal elements in the grammar always have a length greater than |
| 52 | one. The first element is an integer which identifies a production in |
| 53 | the grammar. These integers are given symbolic names in the C header |
| 54 | file \code{Include/graminit.h} and the Python module |
| 55 | \code{Lib/symbol.py}. Each additional element of the sequence represents |
| 56 | a component of the production as recognized in the input string: these |
| 57 | are always sequences which have the same form as the parent. An |
| 58 | important aspect of this structure which should be noted is that |
| 59 | keywords used to identify the parent node type, such as the keyword |
| 60 | \code{if} in an \emph{if\_stmt}, are included in the node tree without |
| 61 | any special treatment. For example, the \code{if} keyword is |
Guido van Rossum | 4b73a06 | 1995-10-11 17:30:04 +0000 | [diff] [blame] | 62 | represented by the tuple \code{(1, 'if')}, where \code{1} is the |
| 63 | numeric value associated with all \code{NAME} elements, including |
Guido van Rossum | 4747887 | 1996-08-21 14:32:37 +0000 | [diff] [blame] | 64 | variable and function names defined by the user. In an alternate form |
| 65 | returned when line number information is requested, the same token |
| 66 | might be represented as \code{(1, 'if', 12)}, where the \code{12} |
| 67 | represents the line number at which the terminal symbol was found. |
Guido van Rossum | 4b73a06 | 1995-10-11 17:30:04 +0000 | [diff] [blame] | 68 | |
| 69 | Terminal elements are represented in much the same way, but without |
| 70 | any child elements and the addition of the source text which was |
| 71 | identified. The example of the \code{if} keyword above is |
| 72 | representative. The various types of terminal symbols are defined in |
| 73 | the C header file \code{Include/token.h} and the Python module |
| 74 | \code{Lib/token.py}. |
| 75 | |
| 76 | The AST objects are not actually required to support the functionality |
| 77 | of this module, but are provided for three purposes: to allow an |
| 78 | application to amortize the cost of processing complex parse trees, to |
| 79 | provide a parse tree representation which conserves memory space when |
Guido van Rossum | 4747887 | 1996-08-21 14:32:37 +0000 | [diff] [blame] | 80 | compared to the Python list or tuple representation, and to ease the |
| 81 | creation of additional modules in C which manipulate parse trees. A |
| 82 | simple ``wrapper'' module may be created in Python to hide the use of |
| 83 | AST objects. |
Guido van Rossum | 4b73a06 | 1995-10-11 17:30:04 +0000 | [diff] [blame] | 84 | |
| 85 | |
Guido van Rossum | 4b73a06 | 1995-10-11 17:30:04 +0000 | [diff] [blame] | 86 | The \code{parser} module defines the following functions: |
| 87 | |
Guido van Rossum | 4b73a06 | 1995-10-11 17:30:04 +0000 | [diff] [blame] | 88 | \renewcommand{\indexsubitem}{(in module parser)} |
| 89 | |
Guido van Rossum | 4747887 | 1996-08-21 14:32:37 +0000 | [diff] [blame] | 90 | \begin{funcdesc}{ast2list}{ast\optional{\, line\_info\code{ = 0}}} |
Guido van Rossum | 4b73a06 | 1995-10-11 17:30:04 +0000 | [diff] [blame] | 91 | This function accepts an AST object from the caller in |
Guido van Rossum | 4747887 | 1996-08-21 14:32:37 +0000 | [diff] [blame] | 92 | \code{\var{ast}} and returns a Python list representing the |
| 93 | equivelent parse tree. The resulting list representation can be used |
| 94 | for inspection or the creation of a new parse tree in list form. |
Guido van Rossum | 4b73a06 | 1995-10-11 17:30:04 +0000 | [diff] [blame] | 95 | This function does not fail so long as memory is available to build |
Guido van Rossum | 4747887 | 1996-08-21 14:32:37 +0000 | [diff] [blame] | 96 | the list representation. If a parse tree will only be used for |
| 97 | inspection, \code{ast2tuple()} should be used instead to reduce memory |
| 98 | consumption and fragmentation. When modifications are to be made to |
| 99 | the parse tree, this function is significantly faster than retrieving |
| 100 | a tuple representation and converting that to nested lists. |
| 101 | |
| 102 | If the \code{line\_info} flag is given true value, line number |
| 103 | information will be included for all terminal tokens as a third |
| 104 | element of the list representing the token. This information is |
| 105 | omitted if the flag is false or omitted. |
Guido van Rossum | 4b73a06 | 1995-10-11 17:30:04 +0000 | [diff] [blame] | 106 | \end{funcdesc} |
| 107 | |
Guido van Rossum | 4747887 | 1996-08-21 14:32:37 +0000 | [diff] [blame] | 108 | \begin{funcdesc}{ast2tuple}{ast\optional{\, line\_info\code{ = 0}}} |
| 109 | This function accepts an AST object from the caller in |
| 110 | \code{\var{ast}} and returns a Python tuple representing the |
| 111 | equivelent parse tree. Other than returning a tuple instead of a |
| 112 | list, this function is identical to \code{ast2list()}. |
Guido van Rossum | 4b73a06 | 1995-10-11 17:30:04 +0000 | [diff] [blame] | 113 | |
Guido van Rossum | 4747887 | 1996-08-21 14:32:37 +0000 | [diff] [blame] | 114 | If the \code{line\_info} flag is given true value, line number |
| 115 | information will be included for all terminal tokens as a third |
| 116 | element of the list representing the token. This information is |
| 117 | omitted if the flag is false or omitted. |
| 118 | \end{funcdesc} |
| 119 | |
| 120 | \begin{funcdesc}{compileast}{ast\optional{\, filename\code{ = '<ast>'}}} |
Guido van Rossum | 4b73a06 | 1995-10-11 17:30:04 +0000 | [diff] [blame] | 121 | The Python byte compiler can be invoked on an AST object to produce |
| 122 | code objects which can be used as part of an \code{exec} statement or |
| 123 | a call to the built-in \code{eval()} function. This function provides |
| 124 | the interface to the compiler, passing the internal parse tree from |
| 125 | \code{\var{ast}} to the parser, using the source file name specified |
| 126 | by the \code{\var{filename}} parameter. The default value supplied |
| 127 | for \code{\var{filename}} indicates that the source was an AST object. |
Guido van Rossum | 4747887 | 1996-08-21 14:32:37 +0000 | [diff] [blame] | 128 | |
| 129 | Compiling an AST object may result in exceptions related to |
| 130 | compilation; an example would be a \code{SyntaxError} caused by the |
| 131 | parse tree for \code{del f(0)}; this statement is considered legal |
| 132 | within the formal grammar for Python but is not a legal language |
| 133 | construct. The \code{SyntaxError} raised for this condition is |
| 134 | actually generated by the Python byte-compiler normally, which is why |
| 135 | it can be raised at this point by the \code{parser} module. Most |
| 136 | causes of compilation failure can be diagnosed programmatically by |
| 137 | inspection of the parse tree. |
Guido van Rossum | 4b73a06 | 1995-10-11 17:30:04 +0000 | [diff] [blame] | 138 | \end{funcdesc} |
| 139 | |
| 140 | |
| 141 | \begin{funcdesc}{expr}{string} |
| 142 | The \code{expr()} function parses the parameter \code{\var{string}} |
| 143 | as if it were an input to \code{compile(\var{string}, 'eval')}. If |
| 144 | the parse succeeds, an AST object is created to hold the internal |
| 145 | parse tree representation, otherwise an appropriate exception is |
| 146 | thrown. |
| 147 | \end{funcdesc} |
| 148 | |
| 149 | |
| 150 | \begin{funcdesc}{isexpr}{ast} |
| 151 | When \code{\var{ast}} represents an \code{'eval'} form, this function |
| 152 | returns a true value (\code{1}), otherwise it returns false |
| 153 | (\code{0}). This is useful, since code objects normally cannot be |
| 154 | queried for this information using existing built-in functions. Note |
| 155 | that the code objects created by \code{compileast()} cannot be queried |
| 156 | like this either, and are identical to those created by the built-in |
| 157 | \code{compile()} function. |
| 158 | \end{funcdesc} |
| 159 | |
| 160 | |
| 161 | \begin{funcdesc}{issuite}{ast} |
| 162 | This function mirrors \code{isexpr()} in that it reports whether an |
| 163 | AST object represents a suite of statements. It is not safe to assume |
| 164 | that this function is equivelent to \code{not isexpr(\var{ast})}, as |
| 165 | additional syntactic fragments may be supported in the future. |
| 166 | \end{funcdesc} |
| 167 | |
| 168 | |
| 169 | \begin{funcdesc}{suite}{string} |
| 170 | The \code{suite()} function parses the parameter \code{\var{string}} |
| 171 | as if it were an input to \code{compile(\var{string}, 'exec')}. If |
| 172 | the parse succeeds, an AST object is created to hold the internal |
| 173 | parse tree representation, otherwise an appropriate exception is |
| 174 | thrown. |
| 175 | \end{funcdesc} |
| 176 | |
| 177 | |
Guido van Rossum | 4747887 | 1996-08-21 14:32:37 +0000 | [diff] [blame] | 178 | \begin{funcdesc}{sequence2ast}{sequence} |
| 179 | This function accepts a parse tree represented as a sequence and |
| 180 | builds an internal representation if possible. If it can validate |
| 181 | that the tree conforms to the Python grammar and all nodes are valid |
| 182 | node types in the host version of Python, an AST object is created |
| 183 | from the internal representation and returned to the called. If there |
| 184 | is a problem creating the internal representation, or if the tree |
| 185 | cannot be validated, a \code{ParserError} exception is thrown. An AST |
| 186 | object created this way should not be assumed to compile correctly; |
| 187 | normal exceptions thrown by compilation may still be initiated when |
| 188 | the AST object is passed to \code{compileast()}. This will normally |
| 189 | indicate problems not related to syntax (such as a \code{MemoryError} |
| 190 | exception), but may also be due to constructs such as the result of |
| 191 | parsing \code{del f(0)}, which escapes the Python parser but is |
| 192 | checked by the bytecode compiler. |
| 193 | |
| 194 | Sequences representing terminal tokens may be represented as either |
| 195 | two-element lists of the form \code{(1, 'name')} or as three-element |
| 196 | lists of the form \code{(1, 'name', 56)}. If the third element is |
| 197 | present, it is assumed to be a valid line number. The line number |
| 198 | may be specified for any subset of the terminal symbols in the input |
| 199 | tree. |
| 200 | \end{funcdesc} |
| 201 | |
| 202 | \begin{funcdesc}{tuple2ast}{sequence} |
| 203 | This is the same function as \code{sequence2ast}. This entry point is |
| 204 | maintained for backward compatibility. |
Guido van Rossum | 4b73a06 | 1995-10-11 17:30:04 +0000 | [diff] [blame] | 205 | \end{funcdesc} |
| 206 | |
| 207 | |
Guido van Rossum | 4b73a06 | 1995-10-11 17:30:04 +0000 | [diff] [blame] | 208 | \subsection{Exceptions and Error Handling} |
| 209 | |
| 210 | The parser module defines a single exception, but may also pass other |
| 211 | built-in exceptions from other portions of the Python runtime |
| 212 | environment. See each function for information about the exceptions |
| 213 | it can raise. |
| 214 | |
| 215 | \begin{excdesc}{ParserError} |
| 216 | Exception raised when a failure occurs within the parser module. This |
| 217 | is generally produced for validation failures rather than the built in |
| 218 | \code{SyntaxError} thrown during normal parsing. |
| 219 | The exception argument is either a string describing the reason of the |
Guido van Rossum | 4747887 | 1996-08-21 14:32:37 +0000 | [diff] [blame] | 220 | failure or a tuple containing a sequence causing the failure from a parse |
| 221 | tree passed to \code{sequence2ast()} and an explanatory string. Calls to |
| 222 | \code{sequence2ast()} need to be able to handle either type of exception, |
Guido van Rossum | 4b73a06 | 1995-10-11 17:30:04 +0000 | [diff] [blame] | 223 | while calls to other functions in the module will only need to be |
| 224 | aware of the simple string values. |
| 225 | \end{excdesc} |
| 226 | |
| 227 | Note that the functions \code{compileast()}, \code{expr()}, and |
| 228 | \code{suite()} may throw exceptions which are normally thrown by the |
| 229 | parsing and compilation process. These include the built in |
| 230 | exceptions \code{MemoryError}, \code{OverflowError}, |
| 231 | \code{SyntaxError}, and \code{SystemError}. In these cases, these |
| 232 | exceptions carry all the meaning normally associated with them. Refer |
| 233 | to the descriptions of each function for detailed information. |
| 234 | |
Guido van Rossum | 4b73a06 | 1995-10-11 17:30:04 +0000 | [diff] [blame] | 235 | |
Guido van Rossum | 4747887 | 1996-08-21 14:32:37 +0000 | [diff] [blame] | 236 | \subsection{AST Objects} |
| 237 | |
| 238 | AST objects (returned by \code{expr()}, \code{suite()}, and |
Guido van Rossum | 8206fb9 | 1996-08-26 00:33:29 +0000 | [diff] [blame] | 239 | \code{sequence2ast()}, described above) have no methods of their own. |
Guido van Rossum | 4747887 | 1996-08-21 14:32:37 +0000 | [diff] [blame] | 240 | Some of the functions defined which accept an AST object as their |
| 241 | first argument may change to object methods in the future. |
| 242 | |
| 243 | Ordered and equality comparisons are supported between AST objects. |
| 244 | |
| 245 | |
Guido van Rossum | 8206fb9 | 1996-08-26 00:33:29 +0000 | [diff] [blame] | 246 | \subsection{Examples} |
Guido van Rossum | 4b73a06 | 1995-10-11 17:30:04 +0000 | [diff] [blame] | 247 | |
Guido van Rossum | 4747887 | 1996-08-21 14:32:37 +0000 | [diff] [blame] | 248 | The parser modules allows operations to be performed on the parse tree |
| 249 | of Python source code before the bytecode is generated, and provides |
| 250 | for inspection of the parse tree for information gathering purposes as |
Guido van Rossum | 8206fb9 | 1996-08-26 00:33:29 +0000 | [diff] [blame] | 251 | well. Two examples are presented. The simple example demonstrates |
| 252 | emulation of the \code{compile()} built-in function and the complex |
| 253 | example shows the use of a parse tree for information discovery. |
| 254 | |
| 255 | \subsubsection{Emulation of {\tt compile()}} |
| 256 | |
| 257 | While many useful operations may take place between parsing and |
Guido van Rossum | 4747887 | 1996-08-21 14:32:37 +0000 | [diff] [blame] | 258 | bytecode generation, the simplest operation is to do nothing. For |
| 259 | this purpose, using the \code{parser} module to produce an |
| 260 | intermediate data structure is equivelent to the code |
| 261 | |
| 262 | \begin{verbatim} |
| 263 | >>> code = compile('a + 5', 'eval') |
| 264 | >>> a = 5 |
| 265 | >>> eval(code) |
| 266 | 10 |
| 267 | \end{verbatim} |
| 268 | |
| 269 | The equivelent operation using the \code{parser} module is somewhat |
| 270 | longer, and allows the intermediate internal parse tree to be retained |
| 271 | as an AST object: |
Guido van Rossum | 4b73a06 | 1995-10-11 17:30:04 +0000 | [diff] [blame] | 272 | |
| 273 | \begin{verbatim} |
| 274 | >>> import parser |
| 275 | >>> ast = parser.expr('a + 5') |
| 276 | >>> code = parser.compileast(ast) |
| 277 | >>> a = 5 |
| 278 | >>> eval(code) |
| 279 | 10 |
| 280 | \end{verbatim} |
| 281 | |
Guido van Rossum | 8206fb9 | 1996-08-26 00:33:29 +0000 | [diff] [blame] | 282 | An application which needs both AST and code objects can package this |
| 283 | code into readily available functions: |
| 284 | |
| 285 | \begin{verbatim} |
| 286 | import parser |
| 287 | |
| 288 | def load_suite(source_string): |
| 289 | ast = parser.suite(source_string) |
| 290 | code = parser.compileast(ast) |
| 291 | return ast, code |
| 292 | |
| 293 | def load_expression(source_string): |
| 294 | ast = parser.expr(source_string) |
| 295 | code = parser.compileast(ast) |
| 296 | return ast, code |
| 297 | \end{verbatim} |
| 298 | |
| 299 | \subsubsection{Information Discovery} |
| 300 | |
Guido van Rossum | 4747887 | 1996-08-21 14:32:37 +0000 | [diff] [blame] | 301 | Some applications can benfit from access to the parse tree itself, and |
| 302 | can take advantage of the intermediate data structure provided by the |
| 303 | \code{parser} module. The remainder of this section of examples will |
| 304 | demonstrate how the intermediate data structure can provide access to |
| 305 | module documentation defined in docstrings without requiring that the |
| 306 | code being examined be imported into a running interpreter. This can |
| 307 | be very useful for performing analyses of untrusted code. |
Guido van Rossum | 4b73a06 | 1995-10-11 17:30:04 +0000 | [diff] [blame] | 308 | |
Guido van Rossum | 4747887 | 1996-08-21 14:32:37 +0000 | [diff] [blame] | 309 | Generally, the example will demonstrate how the parse tree may be |
| 310 | traversed to distill interesting information. Two functions and a set |
| 311 | of classes is developed which provide programmatic access to high |
| 312 | level function and class definitions provided by a module. The |
| 313 | classes extract information from the parse tree and provide access to |
| 314 | the information at a useful semantic level, one function provides a |
| 315 | simple low-level pattern matching capability, and the other function |
| 316 | defines a high-level interface to the classes by handling file |
| 317 | operations on behalf of the caller. All source files mentioned here |
| 318 | which are not part of the Python installation are located in the |
| 319 | \file{Demo/parser} directory of the distribution. |
Guido van Rossum | 4b73a06 | 1995-10-11 17:30:04 +0000 | [diff] [blame] | 320 | |
Guido van Rossum | 8206fb9 | 1996-08-26 00:33:29 +0000 | [diff] [blame] | 321 | The dynamic nature of Python allows the programmer a great deal of |
| 322 | flexibility, but most modules need only a limited measure of this when |
| 323 | defining classes, functions, and methods. In this example, the only |
| 324 | definitions that will be considered are those which are defined in the |
| 325 | top level of their context, e.g., a function defined by a \code{def} |
| 326 | statement at column zero of a module, but not a function defined |
| 327 | within a branch of an \code{if} ... \code{else} construct, thought |
| 328 | there are some good reasons for doing so in some situations. Nesting |
| 329 | of definitions will be handled by the code developed in the example. |
| 330 | |
Guido van Rossum | 4747887 | 1996-08-21 14:32:37 +0000 | [diff] [blame] | 331 | To construct the upper-level extraction methods, we need to know what |
| 332 | the parse tree structure looks like and how much of it we actually |
| 333 | need to be concerned about. Python uses a moderately deep parse tree, |
| 334 | so there are a large number of intermediate nodes. It is important to |
| 335 | read and understand the formal grammar used by Python. This is |
| 336 | specified in the file \file{Grammar/Grammar} in the distribution. |
| 337 | Consider the simplest case of interest when searching for docstrings: |
Guido van Rossum | 8206fb9 | 1996-08-26 00:33:29 +0000 | [diff] [blame] | 338 | a module consisting of a docstring and nothing else. (See file |
| 339 | \file{docstring.py}.) |
Guido van Rossum | 4b73a06 | 1995-10-11 17:30:04 +0000 | [diff] [blame] | 340 | |
Guido van Rossum | 4747887 | 1996-08-21 14:32:37 +0000 | [diff] [blame] | 341 | \begin{verbatim} |
| 342 | """Some documentation. |
| 343 | """ |
| 344 | \end{verbatim} |
Guido van Rossum | 4b73a06 | 1995-10-11 17:30:04 +0000 | [diff] [blame] | 345 | |
Guido van Rossum | 4747887 | 1996-08-21 14:32:37 +0000 | [diff] [blame] | 346 | Using the interpreter to take a look at the parse tree, we find a |
| 347 | bewildering mass of numbers and parentheses, with the documentation |
| 348 | buried deep in the nested tuples: |
Guido van Rossum | 4b73a06 | 1995-10-11 17:30:04 +0000 | [diff] [blame] | 349 | |
Guido van Rossum | 4747887 | 1996-08-21 14:32:37 +0000 | [diff] [blame] | 350 | \begin{verbatim} |
| 351 | >>> import parser |
| 352 | >>> import pprint |
| 353 | >>> ast = parser.suite(open('docstring.py').read()) |
| 354 | >>> tup = parser.ast2tuple(ast) |
| 355 | >>> pprint.pprint(tup) |
| 356 | (257, |
| 357 | (264, |
| 358 | (265, |
| 359 | (266, |
| 360 | (267, |
| 361 | (307, |
| 362 | (287, |
| 363 | (288, |
| 364 | (289, |
| 365 | (290, |
| 366 | (292, |
| 367 | (293, |
| 368 | (294, |
| 369 | (295, |
| 370 | (296, |
| 371 | (297, |
| 372 | (298, |
| 373 | (299, |
| 374 | (300, (3, '"""Some documentation.\012"""'))))))))))))))))), |
| 375 | (4, ''))), |
| 376 | (4, ''), |
| 377 | (0, '')) |
| 378 | \end{verbatim} |
| 379 | |
| 380 | The numbers at the first element of each node in the tree are the node |
| 381 | types; they map directly to terminal and non-terminal symbols in the |
| 382 | grammar. Unfortunately, they are represented as integers in the |
| 383 | internal representation, and the Python structures generated do not |
| 384 | change that. However, the \code{symbol} and \code{token} modules |
| 385 | provide symbolic names for the node types and dictionaries which map |
| 386 | from the integers to the symbolic names for the node types. |
| 387 | |
| 388 | In the output presented above, the outermost tuple contains four |
| 389 | elements: the integer \code{257} and three additional tuples. Node |
| 390 | type \code{257} has the symbolic name \code{file_input}. Each of |
| 391 | these inner tuples contains an integer as the first element; these |
| 392 | integers, \code{264}, \code{4}, and \code{0}, represent the node types |
| 393 | \code{stmt}, \code{NEWLINE}, and \code{ENDMARKER}, respectively. |
| 394 | Note that these values may change depending on the version of Python |
| 395 | you are using; consult \file{symbol.py} and \file{token.py} for |
| 396 | details of the mapping. It should be fairly clear that the outermost |
| 397 | node is related primarily to the input source rather than the contents |
| 398 | of the file, and may be disregarded for the moment. The \code{stmt} |
| 399 | node is much more interesting. In particular, all docstrings are |
| 400 | found in subtrees which are formed exactly as this node is formed, |
| 401 | with the only difference being the string itself. The association |
| 402 | between the docstring in a similar tree and the defined entity (class, |
| 403 | function, or module) which it describes is given by the position of |
| 404 | the docstring subtree within the tree defining the described |
| 405 | structure. |
| 406 | |
| 407 | By replacing the actual docstring with something to signify a variable |
| 408 | component of the tree, we allow a simple pattern matching approach may |
| 409 | be taken to checking any given subtree for equivelence to the general |
| 410 | pattern for docstrings. Since the example demonstrates information |
| 411 | extraction, we can safely require that the tree be in tuple form |
| 412 | rather than list form, allowing a simple variable representation to be |
| 413 | \code{['variable\_name']}. A simple recursive function can implement |
| 414 | the pattern matching, returning a boolean and a dictionary of variable |
Guido van Rossum | 8206fb9 | 1996-08-26 00:33:29 +0000 | [diff] [blame] | 415 | name to value mappings. (See file \file{example.py}.) |
Guido van Rossum | 4747887 | 1996-08-21 14:32:37 +0000 | [diff] [blame] | 416 | |
| 417 | \begin{verbatim} |
| 418 | from types import ListType, TupleType |
| 419 | |
| 420 | def match(pattern, data, vars=None): |
| 421 | if vars is None: |
| 422 | vars = {} |
| 423 | if type(pattern) is ListType: |
| 424 | vars[pattern[0]] = data |
| 425 | return 1, vars |
| 426 | if type(pattern) is not TupleType: |
| 427 | return (pattern == data), vars |
| 428 | if len(data) != len(pattern): |
| 429 | return 0, vars |
| 430 | for pattern, data in map(None, pattern, data): |
| 431 | same, vars = match(pattern, data, vars) |
| 432 | if not same: |
| 433 | break |
| 434 | return same, vars |
| 435 | \end{verbatim} |
| 436 | |
| 437 | Using this simple recursive pattern matching function and the symbolic |
Guido van Rossum | 8206fb9 | 1996-08-26 00:33:29 +0000 | [diff] [blame] | 438 | node types, the pattern for the candidate docstring subtrees becomes |
| 439 | fairly readable. (See file \file{example.py}.) |
Guido van Rossum | 4747887 | 1996-08-21 14:32:37 +0000 | [diff] [blame] | 440 | |
| 441 | \begin{verbatim} |
Guido van Rossum | 8206fb9 | 1996-08-26 00:33:29 +0000 | [diff] [blame] | 442 | import symbol |
| 443 | import token |
| 444 | |
| 445 | DOCSTRING_STMT_PATTERN = ( |
| 446 | symbol.stmt, |
| 447 | (symbol.simple_stmt, |
| 448 | (symbol.small_stmt, |
| 449 | (symbol.expr_stmt, |
| 450 | (symbol.testlist, |
| 451 | (symbol.test, |
| 452 | (symbol.and_test, |
| 453 | (symbol.not_test, |
| 454 | (symbol.comparison, |
| 455 | (symbol.expr, |
| 456 | (symbol.xor_expr, |
| 457 | (symbol.and_expr, |
| 458 | (symbol.shift_expr, |
| 459 | (symbol.arith_expr, |
| 460 | (symbol.term, |
| 461 | (symbol.factor, |
| 462 | (symbol.power, |
| 463 | (symbol.atom, |
| 464 | (token.STRING, ['docstring']) |
| 465 | )))))))))))))))), |
| 466 | (token.NEWLINE, '') |
| 467 | )) |
Guido van Rossum | 4747887 | 1996-08-21 14:32:37 +0000 | [diff] [blame] | 468 | \end{verbatim} |
| 469 | |
| 470 | Using the \code{match()} function with this pattern, extracting the |
| 471 | module docstring from the parse tree created previously is easy: |
| 472 | |
| 473 | \begin{verbatim} |
| 474 | >>> found, vars = match(DOCSTRING_STMT_PATTERN, tup[1]) |
| 475 | >>> found |
| 476 | 1 |
| 477 | >>> vars |
| 478 | {'docstring': '"""Some documentation.\012"""'} |
| 479 | \end{verbatim} |
| 480 | |
| 481 | Once specific data can be extracted from a location where it is |
| 482 | expected, the question of where information can be expected |
| 483 | needs to be answered. When dealing with docstrings, the answer is |
| 484 | fairly simple: the docstring is the first \code{stmt} node in a code |
| 485 | block (\code{file_input} or \code{suite} node types). A module |
| 486 | consists of a single \code{file_input} node, and class and function |
| 487 | definitions each contain exactly one \code{suite} node. Classes and |
| 488 | functions are readily identified as subtrees of code block nodes which |
| 489 | start with \code{(stmt, (compound_stmt, (classdef, ...} or |
| 490 | \code{(stmt, (compound_stmt, (funcdef, ...}. Note that these subtrees |
| 491 | cannot be matched by \code{match()} since it does not support multiple |
| 492 | sibling nodes to match without regard to number. A more elaborate |
| 493 | matching function could be used to overcome this limitation, but this |
| 494 | is sufficient for the example. |
| 495 | |
Guido van Rossum | 8206fb9 | 1996-08-26 00:33:29 +0000 | [diff] [blame] | 496 | Given the ability to determine whether a statement might be a |
| 497 | docstring and extract the actual string from the statement, some work |
| 498 | needs to be performed to walk the parse tree for an entire module and |
| 499 | extract information about the names defined in each context of the |
| 500 | module and associate any docstrings with the names. The code to |
| 501 | perform this work is not complicated, but bears some explanation. |
| 502 | |
| 503 | The public interface to the classes is straightforward and should |
| 504 | probably be somewhat more flexible. Each ``major'' block of the |
| 505 | module is described by an object providing several methods for inquiry |
| 506 | and a constructor which accepts at least the subtree of the complete |
| 507 | parse tree which it represents. The \code{ModuleInfo} constructor |
| 508 | accepts an optional \code{\var{name}} parameter since it cannot |
| 509 | otherwise determine the name of the module. |
| 510 | |
| 511 | The public classes include \code{ClassInfo}, \code{FunctionInfo}, |
| 512 | and \code{ModuleInfo}. All objects provide the |
| 513 | methods \code{get_name()}, \code{get_docstring()}, |
| 514 | \code{get_class_names()}, and \code{get_class_info()}. The |
| 515 | \code{ClassInfo} objects support \code{get_method_names()} and |
| 516 | \code{get_method_info()} while the other classes provide |
| 517 | \code{get_function_names()} and \code{get_function_info()}. |
| 518 | |
| 519 | Within each of the forms of code block that the public classes |
| 520 | represent, most of the required information is in the same form and is |
| 521 | access in the same way, with classes having the distinction that |
| 522 | functions defined at the top level are referred to as ``methods.'' |
| 523 | Since the difference in nomenclature reflects a real semantic |
| 524 | distinction from functions defined outside of a class, our |
| 525 | implementation needs to maintain the same measure of distinction. |
| 526 | Hence, most of the functionality of the public classes can be |
| 527 | implemented in a common base class, \code{SuiteInfoBase}, with the |
| 528 | accessors for function and method information provided elsewhere. |
| 529 | Note that there is only one class which represents function and method |
| 530 | information; this mirrors the use of the \code{def} statement to |
| 531 | define both types of functions. |
| 532 | |
| 533 | Most of the accessor functions are declared in \code{SuiteInfoBase} |
| 534 | and do not need to be overriden by subclasses. More importantly, the |
| 535 | extraction of most information from a parse tree is handled through a |
| 536 | method called by the \code{SuiteInfoBase} constructor. The example |
| 537 | code for most of the classes is clear when read alongside the formal |
| 538 | grammar, but the method which recursively creates new information |
| 539 | objects requires further examination. Here is the relevant part of |
| 540 | the \code{SuiteInfoBase} definition from \file{example.py}: |
| 541 | |
| 542 | \begin{verbatim} |
| 543 | class SuiteInfoBase: |
| 544 | _docstring = '' |
| 545 | _name = '' |
| 546 | |
| 547 | def __init__(self, tree = None): |
| 548 | self._class_info = {} |
| 549 | self._function_info = {} |
| 550 | if tree: |
| 551 | self._extract_info(tree) |
| 552 | |
| 553 | def _extract_info(self, tree): |
| 554 | # extract docstring |
| 555 | if len(tree) == 2: |
| 556 | found, vars = match(DOCSTRING_STMT_PATTERN[1], tree[1]) |
| 557 | else: |
| 558 | found, vars = match(DOCSTRING_STMT_PATTERN, tree[3]) |
| 559 | if found: |
| 560 | self._docstring = eval(vars['docstring']) |
| 561 | # discover inner definitions |
| 562 | for node in tree[1:]: |
| 563 | found, vars = match(COMPOUND_STMT_PATTERN, node) |
| 564 | if found: |
| 565 | cstmt = vars['compound'] |
| 566 | if cstmt[0] == symbol.funcdef: |
| 567 | name = cstmt[2][1] |
| 568 | self._function_info[name] = FunctionInfo(cstmt) |
| 569 | elif cstmt[0] == symbol.classdef: |
| 570 | name = cstmt[2][1] |
| 571 | self._class_info[name] = ClassInfo(cstmt) |
| 572 | \end{verbatim} |
| 573 | |
| 574 | After initializing some internal state, the constructor calls the |
| 575 | \code{_extract_info()} method. This method performs the bulk of the |
| 576 | information extraction which takes place in the entire example. The |
| 577 | extraction has two distinct phases: the location of the docstring for |
| 578 | the parse tree passed in, and the discovery of additional definitions |
| 579 | within the code block represented by the parse tree. |
| 580 | |
| 581 | The initial \code{if} test determines whether the nested suite is of |
| 582 | the ``short form'' or the ``long form.'' The short form is used when |
| 583 | the code block is on the same line as the definition of the code |
| 584 | block, as in |
| 585 | |
| 586 | \begin{verbatim} |
| 587 | def square(x): "Square an argument."; return x ** 2 |
| 588 | \end{verbatim} |
| 589 | |
| 590 | while the long form uses an indented block and allows nested |
| 591 | definitions: |
| 592 | |
| 593 | \begin{verbatim} |
| 594 | def make_power(exp): |
| 595 | "Make a function that raises an argument to the exponent `exp'." |
| 596 | def raiser(x, y=exp): |
| 597 | return x ** y |
| 598 | return raiser |
| 599 | \end{verbatim} |
| 600 | |
| 601 | When the short form is used, the code block may contain a docstring as |
| 602 | the first, and possibly only, \code{small_stmt} element. The |
| 603 | extraction of such a docstring is slightly different and requires only |
| 604 | a portion of the complete pattern used in the more common case. As |
| 605 | given in the code, the docstring will only be found if there is only |
| 606 | one \code{small_stmt} node in the \code{simple_stmt} node. Since most |
| 607 | functions and methods which use the short form do not provide |
| 608 | docstring, this may be considered sufficient. The extraction of the |
| 609 | docstring proceeds using the \code{match()} function as described |
| 610 | above, and the value of the docstring is stored as an attribute of the |
| 611 | \code{SuiteInfoBase} object. |
| 612 | |
| 613 | After docstring extraction, the operates a simple definition discovery |
| 614 | algorithm on the \code{stmt} nodes of the \code{suite} node. The |
| 615 | special case of the short form is not tested; since there are no |
| 616 | \code{stmt} nodes in the short form, the algorithm will silently skip |
| 617 | the single \code{simple_stmt} node and correctly not discover any |
| 618 | nested definitions. |
| 619 | |
| 620 | Each statement in the code block bing examined is categorized as being |
| 621 | a class definition, function definition (including methods), or |
| 622 | something else. For the definition statements, the name of the |
| 623 | element being defined is extracted and representation object |
| 624 | appropriate to the definition is created with the defining subtree |
| 625 | passed as an argument to the constructor. The repesentation objects |
| 626 | are stored in instance variables and may be retrieved by name using |
| 627 | the appropriate accessor methods. |
| 628 | |
| 629 | The public classes provide any accessors required which are more |
| 630 | specific than those provided by the \code{SuiteInfoBase} class, but |
| 631 | the real extraction algorithm remains common to all forms of code |
| 632 | blocks. A high-level function can be used to extract the complete set |
| 633 | of information from a source file: |
| 634 | |
| 635 | \begin{verbatim} |
| 636 | def get_docs(fileName): |
| 637 | source = open(fileName).read() |
| 638 | import os |
| 639 | basename = os.path.basename(os.path.splitext(fileName)[0]) |
| 640 | import parser |
| 641 | ast = parser.suite(source) |
| 642 | tup = parser.ast2tuple(ast) |
| 643 | return ModuleInfo(tup, basename) |
| 644 | \end{verbatim} |
| 645 | |
| 646 | This provides an easy-to-use interface to the documentation of a |
| 647 | module. If information is required which is not extracted by the code |
| 648 | of this example, the code may be extended at clearly defined points to |
| 649 | provide additional capabilities. |
Guido van Rossum | 4747887 | 1996-08-21 14:32:37 +0000 | [diff] [blame] | 650 | |
| 651 | |
| 652 | %% |
| 653 | %% end of file |