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 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 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 on other sites
Quote:
 Original post by SneftelFor 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 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 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 on other sites
Quote:
 Original post by zerotrithat 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 on other sites
Quote:
 Original post by thre3deeim 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.

1: * *= / /=
2: + +=
3: - -=

?

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 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 on other sites
Quote:
 Original post by thre3dee1: * *= / /=2: + +=3: - -=?

Where did you get this, and why do you think this is common?

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 on other sites
Quote:
 Original post by ITGERSoftwareGuy256 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 on other sites
Quote:
 Original post by ITGERSoftwareGuy256 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

Share on other sites
Quote:
 Original post by ToohrVykYou'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 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 on other sites
Quote:
 Original post by GnomeTankHey 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 on other sites
Quote:
Original post by thre3dee
Quote:
 Original post by GnomeTankHey 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 on other sites
Quote:
Original post by GnomeTank
Quote:
Original post by thre3dee
Quote:
 Original post by GnomeTankHey 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 on other sites
Quote:
Original post by thre3dee
Quote:
Original post by GnomeTank
Quote:
Original post by thre3dee
Quote:
 Original post by GnomeTankHey 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 on other sites
yeh i forgot what all that was called lol

Create an account

Register a new account

• Forum Statistics

• Total Topics
628379
• Total Posts
2982349

• 10
• 9
• 15
• 24
• 11