Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Python > Re: How is Python designed?

Reply
Thread Tools

Re: How is Python designed?

 
 
Limin Fu
Guest
Posts: n/a
 
      12-06-2004
Hi,

> So I guess you don't use classic parser techniques
> then?


You are right. The Yuan interpreter scans the tokens
resulted from lexical analysis and matches them to the
syntax patterns. There are 3 basic patterns defined in
Yuan: arithmetic "a*b+c", chain (as I called it)
"objs[i]->func()" and regular expression "/\d*[abc]/",
each of which is represented by a class. And the other
patterns are a combination of these 3 basic pattern,
e.g. array enumeration "a=[1,a+1,func()]" etc. There
are functions responsible to parse the token patterns
to phrase objects. After all phrase objects are
generated, logical and loop controls are checked, so
that each phrase object "knows" if it should "step to"
the next phrase object or "jump to" another one when
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.

> I'm still not sure what you mean by "recursive" - to
> me, recursion is the
> act of a function calling itself until some
> condition is met that markes
> the end (or actually begin I think) of the
> recursion, like this:
>
> def fac(n):
> if n == 1:
> return 1
> return n * fac(n-1)
>
> Thats recursion.


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.

> If you mean by recursion that the top-node is called
> for evaluation which
> then delegates the evaluation to its children -


Ah, yes. That's exactly what I mean.

> well, that's unavoidable -


That's avoidable, using depth first seach.

> but also in both cases. As I mentioned before, the
> only difference I see is
> the order of evaluation - but that is invariant, as
> long as for all
> expression's their respective sub-expressions are
> evaluated beforehand.


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.

>
> I'm not upset - I feared you were And I perceive


Ok, since non of us is upseted, let's forget it

Best,

Limin





__________________________________
Do you Yahoo!?
Yahoo! Mail - Helps protect you from nasty viruses.
http://promotions.yahoo.com/new_mail
 
Reply With Quote
 
 
 
 
Diez B. Roggisch
Guest
Posts: n/a
 
      12-07-2004
Hi,

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

--
Regards,

Diez B. Roggisch
 
Reply With Quote
 
 
 
 
LutherRevisited
Guest
Posts: n/a
 
      12-08-2004
Kinda off subject, just thought I'd add that 0! = 1 for that recursion example,
since that wasn't considered. Nice post though.
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Re: How include a large array? Edward A. Falk C Programming 1 04-04-2013 08:07 PM
Re: [Python-Dev] [python-committers] [RELEASED] Python 3.2 rc 1 Senthil Kumaran Python 0 01-17-2011 10:31 AM
Re: [Python-Dev] [Python-3000] RELEASED Python 2.6a1 and 3.0a3 Martin v. L÷wis Python 0 03-01-2008 10:51 PM
Re: [Python-Dev] [Python-3000] RELEASED Python 2.6a1 and 3.0a3 Paul Moore Python 0 03-01-2008 10:39 PM
Searching comp.lang.python/python-list@python.org (was: UTF-8) skip@pobox.com Python 0 03-10-2007 02:50 PM



Advertisments