The PEAK Developers' Center   PEAK-Rules/AST-Builder UserPreferences
HelpContents Search Diffs Info Edit Subscribe XML Print View Up
The following 436 words could not be found in the dictionary of 50 words (including 50 LocalSpellingWords) and are highlighted below:
Access   Add   An   And   As   Attribute   Backquote   Bin   Binary   Bitand   Bitor   Bitxor   Builder   Builders   Building   By   Call   Calls   Comp   Compare   Comparisons   Comprehensions   Conditional   Const   Contents   Dict   Dictionaries   Div   Each   Ellipsis   Else   Error   Expr   Expressions   False   Floor   For   Func   Gen   Generator   Getattr   If   In   Instead   Invert   Left   List   Lists   Many   Minus   Miscellaneous   Mod   Most   Mul   Name   No   None   Normally   Not   Note   Op   Operators   Or   Otherwise   Parse   Plus   Power   Python   Right   Shift   Simple   Slice   Slice2   Slice3   Slicing   Sub   Subscript   Syntax   Table   Tests   The   There   These   This   Tokens   Traceback   Trees   True   Tuple   Tuples   Unary   Val   Way   While   With   You   abc   abcxyz   accept   accepts   accessed   actions   actual   addition   additional   adjacent   after   allows   also   an   and   any   append   applied   arbitrary   are   arg   argname   args   argument   arguments   as   assignments   associative   associativity   ast   attr   attribute   automatically   bar   base   be   because   binary   body   both   bound   build   builder   building   but   by   call   called   calls   can   case   certain   class   clause   clauses   code   compared   comparison   comparisons   compiler   complex   condition   const   constants   contents   convenience   converted   correct   correspond   corresponding   create   created   creating   currently   data   def   default   delay   delimited   describes   design   desired   different   directly   do   document   does   don   done   dramatically   driven   dstar   each   effectively   either   else   errors   etc   even   example   explicitly   expr   expression   expressions   false   feature   first   five   flag   fmt   followed   for   from   func   function   functions   generate   generating   grammar   handle   handled   has   have   high   if   implementation   implements   import   in   information   init   instance   instead   integer   interesting   interface   intermediate   into   invoke   invoked   is   isn   it   item   items   itself   join   just   keep   key   keys   keyword   kind   kw   lambdas   last   left   level   library   like   list   ll   lookups   lots   low   make   merged   method   methods   might   mind   mk   module   more   most   multi   must   name   names   navigate   need   new   no   node   nodelist   nodelists   nodes   non   normal   not   object   of   offer   older   on   one   only   op   operates   operations   operator   operators   or   order   other   output   own   package   pair   pairs   parens   parse   parser   parsing   part   particular   parts   passed   passing   pat   pe   peak   perform   positional   possible   power   precedence   print   process   processing   programs   provides   quickly   quirk   read   receive   receives   recent   recursively   redundant   repeat   repr   represent   representing   respectively   rest   result   return   right   rules   second   see   sees   self   sep   sequence   set   shortcut   shorthand   should   similar   simple   simplifies   simplify   single   skip   slice   some   standard   star   start   statements   stdlib   step   stop   stride   string   structure   subsequent   subset   subtree   subtrees   supply   support   supports   sure   syntax   sys   take   takes   tests   than   that   the   there   these   this   three   thus   to   token   trap   traversals   tree   trees   true   tuple   tuples   two   unary   unless   unpacking   up   use   used   val   value   values   version   versions   very   virtual   visit   want   was   way   we   what   when   where   which   will   with   within   without   would   xyz   yield   you   your  

Clear message

Building Expressions from Python Syntax Trees

The ast_builder module allows you to quickly navigate a Python syntax tree and perform operations on it. While Python 2.5 has a new "AST" feature that provides a high-level syntax tree, older Python versions offer a very low-level interface that provides complex tuple trees with lots of redundant information. The ast_builder module simplifies these trees dramatically, without creating an intermediate AST data structure (the way the stdlib compiler package does). Instead, it allows you to effectively "visit" a virtual AST structure and generate your desired output directly. In addition, it allows you to skip, delay, or repeat traversals of arbitrary subtrees.

This document describes the design (and tests the implementation) of the ast_builder module. You don't need to read it unless you want to use this module directly in your own programs. If you do want to use it directly, you should keep in mind that it currently only implements a subset of Python expression syntax: it does not support lambdas, yield expressions, or any kind of statements.

Table of Contents

Parse Trees and Builders

ast_builder operates on parse tuple trees, as created by the standard library parser module. The two API functions it provides are build and parse_expr:

>>> from peak.rules.ast_builder import build, parse_expr

The build() function accepts two arguments, a "builder" and a "nodelist". A "builder" is an object that you supply that will perform actions on nodes in the parse tree. The "nodelist" is a parse tuple tree. As a shortcut, you can use parse_expr() to parse a string into a nodelist and invoke build() in one step.

A simple example:

>>> class Builder:
...     def Const(self, const):
...         print const

>>> parse_expr("1", Builder())

>>> parse_expr("'foo'", Builder())

As you can see, the builder's Const() method is invoked for integer and string constants, and it receives an actual value. Many other method names are used for more complex operations:

>>> class Builder:
...     def Const(self, const):
...         return repr(const)
...     def Add(self, left, right):
...         return "Add(%s, %s)" % (build(self,left), build(self,right))

>>> parse_expr("1+2", Builder())
'Add(1, 2)'

>>> parse_expr("'foo'+'bar'", Builder())
"Add('foo', 'bar')"

Most builder methods accept nodelists as arguments. These nodelists can be recursively passed to build() in order to process expression subtrees. This is not done automatically, because it's possible you might want to skip processing of a particular subtree, or need to process a subtree with a different builder than the one currently in use, or even process a subtree with more than one builder (e.g. a builder that sees what names are bound within a function body, and a second builder to generate code).

For convenience in the rest of this document, we'll use a shorthand function to create a Builder(), parse an expression, and print the result:

>>> def pe(expr):
...     print parse_expr(expr, Builder())


The Const and Name methods receive token values for constants and names respectively:

>>> class Builder:
...     def Const(self, const):
...         return repr(const)
...     def Name(self, name):
...         return name

>>> pe("a")
>>> pe("b")
>>> pe("123")
>>> pe("'xyz'")

Note that adjacent string constants are automatically merged:

>>> pe("'abc' 'xyz'")

Unary Operators

There are five "unary" operator methods, that take a single argument: an AST tuple representing the expression the operator is applied to:

>>> class Builder(Builder):
...     def unaryOp(fmt):
...         def method(self,expr):
...             return fmt % build(self,expr)
...         return method
...     UnaryPlus  = unaryOp('Plus(%s)')
...     UnaryMinus = unaryOp('Minus(%s)')
...     Invert     = unaryOp('Invert(%s)')
...     Backquote  = unaryOp('repr(%s)')
...     Not        = unaryOp('Not(%s)')

>>> pe("not - + ~`x`")

Attribute Access

The Getattr() method is called with a node and a string; the node is the base expression, and the string is the attribute that was accessed:

>>> class Builder(Builder):
...     def Getattr(self, expr, attr):
...         return 'Getattr(%s,%r)' % (build(self,expr), attr)

>>> pe("a.b")

>>> pe("a.b.c")

Simple Binary Operators

There are 10 "simple" binary operator methods, that take a pair of left and right nodelists as arguments:

>>> class Builder(Builder):
...     def mkBinOp(op):
...         pat = op + '(%s,%s)'
...         def method(self, left, right):
...             return pat % (build(self,left), build(self,right))
...         return method
...     Add        = mkBinOp('Add')
...     Sub        = mkBinOp('Sub')
...     Mul        = mkBinOp('Mul')
...     Div        = mkBinOp('Div')
...     Mod        = mkBinOp('Mod')
...     FloorDiv   = mkBinOp('FloorDiv')
...     Power      = mkBinOp('Power')
...     LeftShift  = mkBinOp('LeftShift')
...     RightShift = mkBinOp('RightShift')
...     Subscript  = mkBinOp('Subscript')

Most of these operators correspond to normal Python binary operators:

>>> pe("a+b")
>>> pe("b-a")
>>> pe("c*d")
>>> pe("c/d")
>>> pe("c%d")
>>> pe("c//d")
>>> pe("a**b")
>>> pe("a<<b")
>>> pe("a>>b")

>>> pe("a[1]")
>>> pe("a[1][2]")

By the way, Ellipsis is also handled by the Const method, in the case where you have an expression like foo[...]:

>>> pe("a[...]")

"List" Operators

The 7 "list operator" methods take a single argument: a sequence of nodes that represent a list of expressions delimited by the corresponding operator:

>>> class Builder(Builder):
...     def multiOp(fmt,sep=','):
...         def method(self,items):
...             return fmt % sep.join([build(self,item) for item in items])
...         return method
...     And        = multiOp('And(%s)')
...     Or         = multiOp('Or(%s)')
...     Tuple      = multiOp('Tuple(%s)')
...     List       = multiOp('List(%s)')
...     Bitor      = multiOp('Bitor(%s)')
...     Bitxor     = multiOp('Bitxor(%s)')
...     Bitand     = multiOp('Bitand(%s)')

>>> pe("a and b")
>>> pe("a or b")
>>> pe("a and b and c")
>>> pe("a or b or c")
>>> pe("a and b and c and d")
>>> pe("a or b or c or d")

>>> pe("a&b&c")
>>> pe("a|b|c")
>>> pe("a^b^c")

>>> pe("a&b&c&d")
>>> pe("a|b|c|d")
>>> pe("a^b^c^d")


No parens:

>>> pe("a,")
>>> pe("a,b")
>>> pe("a,b,c")
>>> pe("a,b,c,")

With parens:

>>> pe("()")
>>> pe("(a)")
>>> pe("(a,)")
>>> pe("(a,b)")
>>> pe("(a,b,)")
>>> pe("(a,b,c)")
>>> pe("(a,b,c,)")


>>> pe("[]")
>>> pe("[a]")
>>> pe("[a,]")
>>> pe("[a,b]")
>>> pe("[a,b,]")
>>> pe("[a,b,c]")
>>> pe("[a,b,c,]")


The Slice2 method takes two arguments: a start and stop value. Each is either a node list or None (in which case there is no expression for that part of the slice):

>>> class Builder(Builder):
...     def Slice2(self,start,stop):
...         txt = 'Slice('
...         if start:
...             txt += build(self, start)
...         txt += ':'
...         if stop:
...             txt += build(self, stop)
...         return txt+')'

>>> pe("a[:]")

>>> pe("a[1:2]")

>>> pe("a[1:]")

>>> pe("a[:2]")

The Slice3 method is similar, but takes three arguments:

>>> class Builder(Builder):
...     def Slice3(self,start,stop,stride):
...         txt = 'Slice('
...         if start:
...             txt += build(self, start)
...         txt += ':'
...         if stop:
...             txt += build(self, stop)
...         txt += ':'
...         if stride:
...             txt += build(self, stride)
...         return txt+')'

>>> pe("a[::]")

>>> pe("a[1::]")

>>> pe("a[:2:]")

>>> pe("a[1:2:]")

>>> pe("a[::3]")

>>> pe("a[1::3]")

>>> pe("a[:2:3]")

>>> pe("a[1:2:3]")

Comparisons and Conditional Expressions

The Compare method receives two arguments: a node for the first expression to be compared, followed by a list of (op, expr) tuples for subsequent comparisons. The op value is a string representing the comparison operator used, and each expr is a node:

>>> class Builder(Builder):
...     def Compare(self,initExpr,comparisons):
...         data = [build(self,initExpr)]
...         for op,val in comparisons:
...             data.append(op)
...             data.append(build(self,val))
...         return 'Compare(%s)' % ' '.join(data)

>>> pe("a>b")
Compare(a > b)
>>> pe("a>=b")
Compare(a >= b)
>>> pe("a<b")
Compare(a < b)
>>> pe("a<=b")
Compare(a <= b)
>>> pe("a<>b")
Compare(a <> b)
>>> pe("a!=b")
Compare(a != b)
>>> pe("a==b")
Compare(a == b)
>>> pe("a in b")
Compare(a in b)
>>> pe("a is b")
Compare(a is b)
>>> pe("a not in b")
Compare(a not in b)
>>> pe("a is not b")
Compare(a is not b)

N-Way Comparisons

If you don't want to have to process N-way comparisons in your builder, you can set the simplify_comparisons flag on your class to True, and N-way comparisons will be converted to and expressions:

>>> Builder.simplify_comparisons = True

>>> pe("1<2<3")
And(Compare(1 < 2),Compare(2 < 3))

Otherwise, you can set the flag to False, and you will receive N-way comparisons as additional values in the list of (op, expr) tuples:

>>> Builder.simplify_comparisons = False

>>> pe("1<2<3")
Compare(1 < 2 < 3)

>>> pe("a>=b>c<d")
Compare(a >= b > c < d)

Note that you must explicitly set simplify_comparisons to either a true or false value; there is no default.

Conditional Expressions

The IfElse method receives three arguments: a node for the "true" value, a node for the condition, and a node for the "false" value:

>>> class Builder(Builder):
...     def IfElse(self, trueVal, condition, falseVal):
...         return 'IfElse(%s, %s, %s)' % (
...             build(self, trueVal), build(self, condition),
...             build(self, falseVal)
...         )

>>> import sys
>>> if sys.version>='2.5':
...     pe("a if b else c")
... else:
...     print "IfElse(a, b, c)"
IfElse(a, b, c)

List Comprehensions and Generator Expressions

The ListComp and GenExpr methods receive two arguments: a node for the output expression, and a list of (op, node) tuples, where op is the name of an operator (either "for", "in", or "if"), and node is the node corresponding to the operator's argument:

>>> class Builder(Builder):
...     def ListComp(self, initExpr, clauses):
...         data = [build(self,initExpr)]
...         for op,val in clauses:
...             data.append(op)
...             data.append(build(self,val))
...         return 'ListComp(%s)' % ' '.join(data)
...     def GenExpr(self, initExpr, clauses):
...         data = [build(self,initExpr)]
...         for op,val in clauses:
...             data.append(op)
...             data.append(build(self,val))
...         return 'GenExpr(%s)' % ' '.join(data)

>>> pe("[x for x in y if z]")
ListComp(x for x in y if z)

>>> pe("[(x+1, 42) for x in y for y in z if q>z]")
ListComp(Tuple(Add(x,1),42) for x in y for y in z if Compare(q > z))

>>> pe("[x+1 for x in y if x in z for y in q if r if p]")
ListComp(Add(x,1) for x in y if Compare(x in z) for y in q if r if p)

>>> if sys.version>='2.4':
...     pe("(x for x in y if z)")
... else:
...     print "GenExpr(x for x in y if z)"
GenExpr(x for x in y if z)

Note, by the way, that when you are building the "for" clause assignments, you'll need to handle arbitrary assignments (e.g. tuple unpacking):

>>> pe("[x for y, x in z]")
ListComp(x for Tuple(y,x) in z)

>>> pe("[x.y for x.y in z]")
ListComp(Getattr(x,'y') for Getattr(x,'y') in z)

>>> pe("[x[y] for x[y] in z]")
ListComp(Subscript(x,y) for Subscript(x,y) in z)

(Normally, you would handle this by passing the "for" clauses to a different builder instance that's set up to handle calls to Name, Getattr, Tuple, etc. by generating assignments instead of lookups.)


The Dict method takes one argument: a list of (key, value) tuples, where both the keys and values are expression nodes:

>>> class Builder(Builder):
...     def Dict(self, items):
...         return '{%s}' % ','.join([
...             '%s:%s' % (build(self,k),build(self,v)) for k,v in items
...         ])

>>> pe("{ (a,b):c+d, e:[f,g]  }")


The CallFunc method takes five arguments:

The expression to be called.
A list of positional argument expression nodes.
A list of (argname, value) expression node pairs
The node for the *args expression, or None if there isn't one.

The node for the *kw expression, or None if there isn't one.

>>> class Builder(Builder):
...     def CallFunc(self, func, args, kw, star_node, dstar_node):
...         if star_node:
...             star_node=build(self, star_node)
...         else:
...             star_node = 'None'
...         if dstar_node:
...             dstar_node=build(self, dstar_node)
...         else:
...             dstar_node = 'None'
...         return 'Call(%s,%s,%s,%s,%s)' % (
...             build(self,func), self.Tuple(args), self.Dict(kw),
...             star_node, dstar_node
...         )
>>> pe("a()")
>>> pe("a(1,2)")
>>> pe("a(1,2,)")
>>> pe("a(b=3)")
>>> pe("a(1,2,b=3)")
>>> pe("a(*x)")
>>> pe("a(1,*x)")
>>> pe("a(b=3,*x)")
>>> pe("a(1,2,b=3,*x)")
>>> pe("a(**y)")
>>> pe("a(1,**y)")
>>> pe("a(b=3,**y)")
>>> pe("a(1,2,b=3,**y)")
>>> pe("a(*x,**y)")
>>> pe("a(1,*x,**y)")
>>> pe("a(b=3,*x,**y)")
>>> pe("a(1,2,b=3,*x,**y)")
>>> if sys.version>='2.4':
...     pe("a(x for x in y if z)")
...     pe("a(x for x in y if z, q)")
... else:
...     print "Call(a,Tuple(GenExpr(x for x in y if z)),{},None,None)"
...     print "Call(a,Tuple(GenExpr(x for x in y if z),q),{},None,None)"
Call(a,Tuple(GenExpr(x for x in y if z)),{},None,None)
Call(a,Tuple(GenExpr(x for x in y if z),q),{},None,None)

Miscellaneous Tests

An interesting quirk of the AST module is that it supports parsing some calls that should be syntax errors. The ast_builder module thus has to trap these itself:

>>> pe("a(1=2)")    # expr as kw
Traceback (most recent call last):
SyntaxError: keyword can't be an expression (...)

>>> pe("a(b=2,c)")
Traceback (most recent call last):
SyntaxError: non-keyword arg after keyword arg

Most of Python's operator associativity and precedence is grammar-driven, but certain parts have to be handled by ast_builder. These are just some tests to make sure that associativity is correct:

>>> pe("a+b+c")
>>> pe("a*b*c")
>>> pe("a/b/c")
>>> pe("a//b//c")
>>> pe("a%b%c")
>>> pe("a<<b<<c")
>>> pe("a>>b>>c")
>>> pe("a()()")

>>> pe("a**b**c")   # power is right-associative

>>> pe("5*x**2 + 4*x + -1")

EditText of this page (last modified 2010-08-10 20:21:38)
FindPage by browsing, title search , text search or an index
Or try one of these actions: AttachFile, DeletePage, LikePages, LocalSiteMap, SpellCheck