Jump to content
  • Advertisement
Sign in to follow this  
thre3dee

Quick verification on AST's

This topic is 4267 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I'm currently wrapping my brain around the nitty gritty parts of generating an abstract syntax tree for my script compiler and just wanted to confirm that i've got the tree right for a few expressions.. Are these abstract-syntax-tree'ified correctly? or am I completely wrong in parts lol

Share this post


Link to post
Share on other sites
Advertisement
For your first expression, you're showing the division having precedence over multiplication. It's more common for multiplication and division to have equal precedence and be evaluated left-to-right.

Share this post


Link to post
Share on other sites
that looks fairly logical to me...yet, I don't work with AST's yet(had several problems with my scripting engine that don't allow me to work on the compiler...therefore not requiring an AST yet...)

you know...I can't decide whether or not I want you to finish your scripting language soon or not...I mean...if you do, then I have to convert my scripting classes from AngelScript to yours.(no offense towards AngelScript at all, I have just been anticipating E...or...Gorilla Script for a while now)

on the other hand, if you don't finish it soon, then I have to wait THAT much longer to play with it...

help me decide here...which do I want?
;)

good luck!
-Wynter Woods(aka Zerotri)

Share this post


Link to post
Share on other sites
Quote:
Original post by Sneftel
For your first expression, you're showing the division having precedence over multiplication. It's more common for multiplication and division to have equal precedence and be evaluated left-to-right.


not to try and argue, since you have more experience here than I do, but it seems to me like he has it set up that the expression 1 * 2 + 3 * 4 / 5 is evaluated like so:

check the root node (+)
-it has two sub-expressions, 1:[1 * 2] and 2:[ 3 * 4 / 5]
--check node 1
---node 1 has two values, [1] and [2], which are multiplied
--check node 2
---node 2 has two sub-expressions, 3:[3 * 4] and 4 [ / 5 ]
----check node 3
-----node 3 has two values, [3] and [4], which are multiplied
----check node 4
-----node 4 divides node 3's end result by it's value [5]

so by doing it this way, he makes sure that the second multiplication is evaluated right before it is used in division. although I don't know of another way to handle showing this with the multiplication expression 'shown' being evaluated first, if his tree is parsed correctly, it looks like it would get evaluated first.

Share this post


Link to post
Share on other sites
"/ 5" isn't an expression.

The proper subtree for 3*4/5, assuming left-to-right and equal precedence (and using ~ for division to avoid graphical ambiguity), would look like

*
/ \
3 ~
/ \
4 5

Share this post


Link to post
Share on other sites
Quote:
Original post by Sneftel
"/ 5" isn't an expression.

The proper subtree for 3*4/5, assuming left-to-right and equal precedence (and using ~ for division to avoid graphical ambiguity), would look like

*
/ \
3 ~
/ \
4 5


im following the most common precedence rules. That is:

* *= / /= + += - -= in that order of priority

Share this post


Link to post
Share on other sites
Quote:
Original post by zerotri
that looks fairly logical to me...yet, I don't work with AST's yet(had several problems with my scripting engine that don't allow me to work on the compiler...therefore not requiring an AST yet...)

you know...I can't decide whether or not I want you to finish your scripting language soon or not...I mean...if you do, then I have to convert my scripting classes from AngelScript to yours.(no offense towards AngelScript at all, I have just been anticipating E...or...Gorilla Script for a while now)

on the other hand, if you don't finish it soon, then I have to wait THAT much longer to play with it...

help me decide here...which do I want?
;)

good luck!
-Wynter Woods(aka Zerotri)


While its inspiring that people are already waiting for my library to be completed I can't give you any ideas on when as I've never *ever* done this before. Theres a lot of compilation stuff thats really easy, such as identifying classes, functions, parameter types and whatnot, but when it comes to 'expressions' it looks like I've got a LONG way to go...

Share this post


Link to post
Share on other sites
Quote:
Original post by thre3dee
im following the most common precedence rules. That is:

* *= / /= + += - -= in that order of priority



I'm afraid this is not common at all. Almost all languages use a precedence system where * and / have the same precedence and are right-associative. Not only do I have trouble coming up with a language that doesn't use this convention (such as Forth), but I can't find any language that uses your version.

Share this post


Link to post
Share on other sites
With only those you've mentioned:


1. - (unary)
2. * / (left-to-right-assoc)
3. + - (left-to-right-assoc)
4. += -= *= /= (right-to-left-assoc)


At least, that's the approach of C family languages.

EDIT: found the actual english translation of associativity rules.

[Edited by - ToohrVyk on April 7, 2007 10:54:43 AM]

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!