Re: How is Python designed?

Discussion in 'Python' started by Limin Fu, Dec 6, 2004.

  1. Limin Fu

    Limin Fu Guest

    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->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
     
    Limin Fu, Dec 6, 2004
    #1
    1. Advertising

  2. 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
     
    Diez B. Roggisch, Dec 7, 2004
    #2
    1. Advertising

  3. Kinda off subject, just thought I'd add that 0! = 1 for that recursion example,
    since that wasn't considered. Nice post though.
     
    LutherRevisited, Dec 8, 2004
    #3
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Limin Fu

    How is Python designed?

    Limin Fu, Dec 2, 2004, in forum: Python
    Replies:
    2
    Views:
    303
    Terry Reedy
    Dec 3, 2004
  2. Limin Fu

    Re: How is Python designed?

    Limin Fu, Dec 3, 2004, in forum: Python
    Replies:
    2
    Views:
    315
    Arthur Rambo
    Dec 3, 2004
  3. Limin Fu

    Re: How is Python designed?

    Limin Fu, Dec 4, 2004, in forum: Python
    Replies:
    2
    Views:
    293
    Robert
    Dec 5, 2004
  4. Limin Fu

    Re: How is Python designed?

    Limin Fu, Dec 8, 2004, in forum: Python
    Replies:
    2
    Views:
    285
    Diez B. Roggisch
    Dec 8, 2004
  5. Chris Angelico
    Replies:
    109
    Views:
    748
    Mark Lawrence
    Oct 26, 2013
Loading...

Share This Page