Sign in to follow this  
thre3dee

Quick verification on AST's

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


I think you are mistaken. His tree looks correct yours does not. Evaluating a binary expression tree starts from the bottom up usually with a postorder traversal. in your case you will do 4/5 first and then multiply that result by 3.

Share this post


Link to post
Share on other sites
SoftwareGuy256 is right - the OP's first AST is in fact correct. I just ran that expression through my Java subset compiler and looked at the AST printout, and it matches what he has.

The divide being above the multiply does NOT mean that division has a higher or lower precedence than multiplication; it just means that the 3*4 is being done before the divide by 5. This implies that binary operations are left associative, which is the case in C-like languages. If you don't believe me, try running the following program and tell me what you get: (you should get a result of 2, with "three", "four", then "five" being printed out.)


int three() {
printf("three\n");
return 3;
}

int four() {
printf("four\n");
return 4;
}

int five() {
printf("five\n");
return 5;
}

int main() {
int x = three()*four()/five();
printf("%d\n", x);
return 0;


In general, if you have a sequence of binary operations with the same precedence level and you want to capture left associativity, you place the rightmost operator as the root, which is what the OP has done.

Share this post


Link to post
Share on other sites
Quote:
Original post by ITGER
SoftwareGuy256 is right - the OP's first AST is in fact correct.


Yes.

Quote:
If you don't believe me, try running the following program and tell me what you get: (you should get a result of 2, with "three", "four", then "five" being printed out.)



int x = three()*four()/five();


You're confusing precedence and order of evaluation. With only precedence rules applying, the code above could very well print "five", "three" then "four" or any other permutation of these.

However, I agree that the only way to get 2 as a result of this operation is for the OP's tree to be correct. Sneftel's would have yielded 3*(4/5) = 3*0 = 0 instead.

Share this post


Link to post
Share on other sites
Quote:
Original post by ITGER
SoftwareGuy256 is right - the OP's first AST is in fact correct. I just ran that expression through my Java subset compiler and looked at the AST printout, and it matches what he has.

The divide being above the multiply does NOT mean that division has a higher or lower precedence than multiplication; it just means that the 3*4 is being done before the divide by 5. This implies that binary operations are left associative, which is the case in C-like languages. If you don't believe me, try running the following program and tell me what you get: (you should get a result of 2, with "three", "four", then "five" being printed out.)


int three() {
printf("three\n");
return 3;
}

int four() {
printf("four\n");
return 4;
}

int five() {
printf("five\n");
return 5;
}

int main() {
int x = three()*four()/five();
printf("%d\n", x);
return 0;


In general, if you have a sequence of binary operations with the same precedence level and you want to capture left associativity, you place the rightmost operator as the root, which is what the OP has done.

Exactly. It's pretty much sorting the operations based on priority, so in theory a sort of equal priority will not change for left-associativity. Thus: 3 * 4 / 5 will evaluate the multiplication first then divide the result (which is how common math works as well).

You learn this in early math class:
1: Exponentiation
2: Multiplication and Division
3: Addition and Subtraction

Share this post


Link to post
Share on other sites
Quote:
Original post by ToohrVyk
You're confusing precedence and order of evaluation. With only precedence rules applying, the code above could very well print "five", "three" then "four" or any other permutation of these.


Oh right, now that I think about it, the C standard doesn't specify a particular order in which subexpressions are evaluated.

Share this post


Link to post
Share on other sites
Hey thre3dee, out of curiosity, how did you produce those pretty AST pictures? Did you draw those by hand, or write code to generate them?

Something like that would be crazy useful for debugging a code generator. Being able to graphically see your AST, in something other then textual form.

Best I've ever come up with is using a tree view to display certain expressions, but even that isn't perfect.

Share this post


Link to post
Share on other sites
Quote:
Original post by GnomeTank
Hey thre3dee, out of curiosity, how did you produce those pretty AST pictures? Did you draw those by hand, or write code to generate them?

Something like that would be crazy useful for debugging a code generator. Being able to graphically see your AST, in something other then textual form.

Best I've ever come up with is using a tree view to display certain expressions, but even that isn't perfect.


Actually I simply used MS Visio to draw them up. That'd actually be a great idea.. You could even generate an image like mine of the AST or something.

I'll just stick to MS VS2005's object info trees..

Share this post


Link to post
Share on other sites
Quote:
Original post by thre3dee
Quote:
Original post by GnomeTank
Hey thre3dee, out of curiosity, how did you produce those pretty AST pictures? Did you draw those by hand, or write code to generate them?

Something like that would be crazy useful for debugging a code generator. Being able to graphically see your AST, in something other then textual form.

Best I've ever come up with is using a tree view to display certain expressions, but even that isn't perfect.


Actually I simply used MS Visio to draw them up. That'd actually be a great idea.. You could even generate an image like mine of the AST or something.

I'll just stick to MS VS2005's object info trees..


Object Info trees? Never heard of such a thing, unless I have and I just don't know it by that name. Is it one of those magical hidden controls and/or tools in VS2005?

Share this post


Link to post
Share on other sites
Quote:
Original post by GnomeTank
Quote:
Original post by thre3dee
Quote:
Original post by GnomeTank
Hey thre3dee, out of curiosity, how did you produce those pretty AST pictures? Did you draw those by hand, or write code to generate them?

Something like that would be crazy useful for debugging a code generator. Being able to graphically see your AST, in something other then textual form.

Best I've ever come up with is using a tree view to display certain expressions, but even that isn't perfect.


Actually I simply used MS Visio to draw them up. That'd actually be a great idea.. You could even generate an image like mine of the AST or something.

I'll just stick to MS VS2005's object info trees..


Object Info trees? Never heard of such a thing, unless I have and I just don't know it by that name. Is it one of those magical hidden controls and/or tools in VS2005?


When ur debugging in VS2005 u place the mouse over a symbol in the code and it comes up with its value or subvariables etc. u can expand it through link lists as much as u want..

Share this post


Link to post
Share on other sites
Quote:
Original post by thre3dee
Quote:
Original post by GnomeTank
Quote:
Original post by thre3dee
Quote:
Original post by GnomeTank
Hey thre3dee, out of curiosity, how did you produce those pretty AST pictures? Did you draw those by hand, or write code to generate them?

Something like that would be crazy useful for debugging a code generator. Being able to graphically see your AST, in something other then textual form.

Best I've ever come up with is using a tree view to display certain expressions, but even that isn't perfect.


Actually I simply used MS Visio to draw them up. That'd actually be a great idea.. You could even generate an image like mine of the AST or something.

I'll just stick to MS VS2005's object info trees..


Object Info trees? Never heard of such a thing, unless I have and I just don't know it by that name. Is it one of those magical hidden controls and/or tools in VS2005?


When ur debugging in VS2005 u place the mouse over a symbol in the code and it comes up with its value or subvariables etc. u can expand it through link lists as much as u want..


Ahhh, the watch expansion stuff, alright. Just different terminology. Yah, I use that all the time.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this