How is Python designed?

[Limin Fu]

Hi,

> why did you choose that technique and not a common
> parser generator? The

Because I didn't know the standard parse technique
when I started to implement Yuan :)

> 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 will try to read something about the standard
technique, then dicide what to do with parsing.
Approximately how many lines of C/C++ code, do you
think, are required to implement the standard parser?

> 
> > 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. 

Not true. It is not a tranvesal, it is recursive.
Because after compiling, The code I have given becomes
something like:
void compute(node *p)
{
   if(p->left) compute(p->left);
   if(p->right) compute(p->right);
   if(p->oper=='+'){
   ...
   }else if(...){
   }
}
You see it is a recursion indeed(if you don't believe,
you can check with other people). And it's unefficient
due to pushing functions into function stack.

> 
> > 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.

Temporary results can be saved in class "node" as
member data instead of cache, so there is no extra
cost of time.

Best,

Limin


__________________________________________________
Do You Yahoo!?
Tired of spam?  Yahoo! Mail has the best spam protection around 
http://mail.yahoo.com