[Python-3000] Refactoring tool available (work in progress)

[Guido van Rossum]

Look at the WildcardPattern class in pytree.py. It generates all the
matches like you say. I don't think it's worth trying to optimize this
much; I'm just doing a very naive non-greedy expansion and so far it
works fine, mostly because it only needs to match at one level in the
tree, which in most cases is pretty limited.

The example you give works slightly different for us because the
Python grammar defines an arith_expr as term ('+' term)* (rather than
the customary arith_expr ['+' term], since our poor LL(1) pgen can't
handle left-recursive rules). To match an arbitrary number of terms
you'd use a pattern like this: arith_expr<any ('+' any)*>.

--Guido

On 12/15/06, Talin <talin at acm.org> wrote:
> Guido van Rossum wrote:
> > I'm not sure how thinking about it as an algebraic solver helps -- is
> > there any existing code I can borrow?
>
> I suppose it depends on how complex your rules are going to be. The
> matching algorithms used in solvers are specialized for some fairly
> difficult cases. Two examples I can think of are (a) where the
> 'constants' of the match expression are leaves, rather than roots of the
> expression being matched, and (b) where subtrees of the match expression
> have multiple ambiguous matches.
>
> An example of the latter is handling the associative rule, i.e.:
>
>    "?a + ?b"
>
> can against:
>
>    x + y + z
>
> either as:
>
>    (x + y) + z
>
> or as:
>
>    x + (y + z)
>
> However, if you aren't dealing with those kinds of cases, then probably
> you don't need to go that route.
>
> Code-wise, I wouldn't want to offer what I have, because it's pretty
> rough and unformed. But the general theory is that the matcher for each
> sub-expression returns a generator of all possible matches. So for
> example, in the expression '?a + ?b', the '?a' matcher returns a
> generator that yields the series ({a=x}, {a=x+y}). The '+' matcher then
> passes this generator to the '?b' matcher, which essentially filters the
> output of '?a' - that is, it either removes results from the list that
> are inconsistent with its own situation, or returns results augmented
> with its own bindings. In this case, it would yield ({a=x,b=y+z},
> {a=x+y,b=z}). The '+' matcher then yields the output of '?b' to the
> caller. If the entire expression doesn't match, then the result is
> generator that immediately ends, yielding no values.
>
> (Also, the code I have could be greatly improved by porting to 2.5, with
> the new 'yield as expression' feature. It would require a total rewrite
> though.)
>
> -- Talin
>
> _______________________________________________
> Python-3000 mailing list
> Python-3000 at python.org
> http://mail.python.org/mailman/listinfo/python-3000
> Unsubscribe: http://mail.python.org/mailman/options/python-3000/guido%40python.org
>


-- 
--Guido van Rossum (home page: http://www.python.org/~guido/)