How is Python designed?

Diez B. Roggisch deetsNOSPAM at
Tue Dec 7 18:00:02 CET 2004


> it is executed. In this technique, indeed, checking
> patterns is a little complicated. In Yuan this part is
> not optimally implemented, somethings have to be
> improved or changed.

why did you choose that technique and not a common parser generator? The
kind of parsing you use is somewhat oldfashioned - back in the times where
parsing theory wasn't evolved enough. The disadvantage is that without a
proper theory and a grammar explaining what statements are legal and
meaningful and which not is uneccessary complicated.

Look into the python language reference how use is made of a grammar to
explain language constructs.

> I supposed you would have done like:
> class node{
> ...
> char oper;
> node *left,*right;
> void compute();
> };
> void node::compute()
> {
>    if(left) left->compute();
>    if(right) right->compute();
>    if(oper=='+'){
>       ....
>    }else if(...){
>       ....
>    }
> }
> This is a kind of recursive evaluation of arithmetic
> tree. Now I believe that's not what you have used.
> Ah, yes. That's exactly what I mean.

That is what I meant. But thats not recursive - the compute-calls account
for the tree-traversal. Nothing recursive there. 

> That's avoidable, using depth first seach.

No. Traversal is traversal. A tree of size n needs O(n) to be traversed -
otherwise you missed some nodes. 

You can of course cache the results of a tree traversal in a list, and call
the compute method then in a loop:

for node in nodelist:
    ??? = node.compute()

But then you need to explicitely deal with where to store the resulting
values of that computation, so you can access them lateron. That will most
probably eat up the time saved by using that cache.

> It seemed to me that it made much difference in
> efficiency so that I reimplemented it by depth-first
> search. Maybe because I didn't implement the recursive
> evaluation properly :), I will check.

As I said before: AST traversal is post-order with a stack/lifo as node
container, deepth-first is using a queue/fifo instead - but there is _no_
gain in terms of speed here - both have to visit all nodes.

There is no reason to change you running system - but your hopes for more
performance that way aren't fulfilled either.


Diez B. Roggisch

More information about the Python-list mailing list