Hi, > First, there is no abstract syntax tree generated for > the whole program, except for arithmetic > expression(even for this, it is slightly different > from what you said, I will come back to this point). > The Yuan (the name of the interpreter I designed) > interpreter first scans the source script, when it see > a pattern, for example "if(a>1)", it generates a > phrase object containing the arithmetic expression and > the ID (it is determined after all phrase objects are > created) of other two phrase objects. This phrase > object has a member method "execute()", whose > execution will return one of the IDs depending on the > value of "a>1". Then the next phrase object with that > ID is executed, and so on. I don't know how is the AST > for a whole program, I think it should be more > complicated than this.
Ok, thats clearer. This whole thing sounds familiar - the technique you describe seems to resemble continuation passing style. For a brief discussion read here: http://www.ps.uni-sb.de/~duchier/python/continuations.html Python has a continuation-based interpreter implementation - its called "stackless python". Google for it. It certainly is interesting. And I don't see that the ast is more complicated, at least implementation wise - in fact, your method requires more analysis as for each statement its pollible successors have to be computed and made known to it - where an ast node only knows about its children that more or less directly stem from the syntax analysis. I have to admit that I don't know if continuation-based evaluation has inherent performance-gains. The only thing I can think of is that you don't need a stackframe in some cases as tail-recursion - useful, but not so common that one would expect significant performance gains there. But as I said - I'm not on sure ground here. > Then about arithmetic expression, indeed, it is > represented as tree. But in Yuan each node contains > all the information it need for evaluation. For > example, the leaves contains either a variable or a > constant value or a function call, and other nodes > contains the operators. So far it is more or less the > same as what you mentioned. But the evaluation is > performed on this tree directly with deep first > search, which is different from the two methods you > mentioned. The first one you mentioned is the same as > my first implementation, which results an unefficient > recursive function call. The second is the standard > way of evaluating arithmetic expressions. I guess I am > not the first one to evaluate arithmetic expression by > deep-first search on the tree (I would be surprised if > I am). Any way it is enough efficient. Can you elaborate on what you consider beeing an unefficient recursive call and where there is a difference between your method of evaluation and the ast-evaluation I mentioned? After all, the ast-evaluation is a postorder traversal which has the same complexity of a depth first search - the only difference beeing the latter one using a fifo, the forme a lifo for managing the list of untraversed nodes. I don't see any difference here. The second method I mentioned rids you of the traversal as it serialzes the nodes as simple statements in the order of choice - but the number of steps is the same. > Your further comments and discussion are welcome, I'm > not that type who is afraid of negative opinions :) > Any way I will continue to improve that interpreter, > it's an interesting thing for me. I don't have negative opinions about yuan and by no meants want to discourage you developing it. Its a nice project. -- Regards, Diez B. Roggisch -- http://mail.python.org/mailman/listinfo/python-list
