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

Guido van Rossum guido at python.org
Fri Dec 15 22:19:47 CET 2006

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/)

More information about the Python-3000 mailing list