Archived

This topic is now archived and is closed to further replies.

DeCrypted

parse tree

Recommended Posts

DeCrypted    122
Can someone explain how a parse tree works in a scripting system.I have the Tree object written, I just dont really understand how the tree stucture is set up within the compiler, how the tokens from the script are arranged and how the final structure of the tree ends up looking. Please get as graphic as possible;-) Thanks JK

Share this post


Link to post
Share on other sites
skap20    122
If you specifically require using a tree then ignore this post. But if you want a much easier way to parse an expression, check out the recursive descent parser in the back of C++: The Complete Reference.

That particular implementation is, in my opinion, very easy to learn from. Its structure is also designed in such a way that it is really easy to add rules to it.

--------------------
Nicholas Skapura
skapura.2@wright.edu
http://skap.8k.com
AIM: skap35

Share this post


Link to post
Share on other sites
Rob The Bloke    122
quote:
Original post by DeCrypted
Can someone explain how a parse tree works in a scripting system.I have the Tree object written, I just dont really understand how the tree stucture is set up within the compiler, how the tokens from the script are arranged and how the final structure of the tree ends up looking.

Please get as graphic as possible;-)

Thanks
JK


A parse tree isn''t ever actually used. You are kind of "wrong" in trying to impliment a tree structure for it I''m afraid. (not that anyone is ever wrong in code, just a bit slower...)

At every point where you use a tree/recursion , you can replace it with a stack to increase performance. For example, glPushMatrix / glPopMatrix.

I''ll write a longer (more visual) post when I''m a bit less drunk, unless someone beats me to it...

Share this post


Link to post
Share on other sites
flangazor    516
First, you need the bnf for your language. Then you determine how to read in each token. Then you read in the stream, token by token and on each token you determine what kind of token you have read and determine what the next tokens may look like. (e.g. in C++ token ''int'' followed by '';'' is not valid, but token ''int'' followed by tokens ''x'' and '';'' are valid.

When you find an appropriate token, push it onto your tree in the valid position -if its not sugar. e.g. '';'' in C++ and Java is sugar.

This is essentially the basis of chapters 1 and 2 of the Dragon Book. I suggest getting it. (I am recalling it from memory from when I had it from the library... I may be off a bit).

Share this post


Link to post
Share on other sites