chevron_left chevron_right
Login Register invert_colors photo_library


Stay updated and chat with others! - Join the Discord!
Thread Rating:
  • 0 Vote(s) - 0 Average


Tutorial CYFPL - Part 1 - Trees, trees, and more trees filter_list
Author
Message
CYFPL - Part 1 - Trees, trees, and more trees #1
Firstly, I'm abbreviating the phrase 'Creating Your First Programming Language' to 'CYFPL', just so you know where that came from.

CYFPL - Part 1
Trees, trees, and more trees

Welcome to part 1 of the CYFPL series, if you couldn't guess by the title, we're going to take a very deep look into trees.
[Image: green-forest-trees.jpg.662x0_q70_crop-scale.jpg]
No....not those trees, syntax trees

[Image: ch08-tree-3.png]

Think of this part as more of a 'getting to know you and your new programming language' than the meat and potatoes of the series. Even though we won't cover any actual code in this part, it is still important. This is the bread on your big mac. If you miss any of this, it's not going to be a very good sandwich. Speaking of which, have you ever seen a big mac without bread?
[Image: protein-style-Neeta-Lind.jpg]
I'm going to be honest with you, that is not a sandwich I would eat, and nobody wants a no-bun programming language, so let's get started.



What is a syntax tree?
A syntax tree is a collection of [let's call them for now] objects that describes the exact flow, order, and method of execution of a program to a compiler (or interpreter). I realize this is a really shitty definition, but I will try my best to help it make sense (I'm really good at the hard stuff but really bad at explaining the stuff I learned so long ago, bear with me).

What is a syntax tree made of?
Tokens. Let's use the English language as a reference. Pretend that a sentence is a statement, or one instruction. Underneath that, we will have words that make it up, these are our tokens.

What is a  token made of?
Back to our English analogy, if a word is a token, then it's made up with letters. By themselves, we can't make any sense of the letters until we group them into tokens. Your compiler will do the same. This is probably the most important part, because without the ability to make tokens, we will be stuck with a bunch of if statements that have to deal with whitespace, double operators, etc. If you've ever wondered why the C compiler is so tolerant of how you format your code, it's because it never sees your code. The first thing it does is reformat it into its own style (you can see this by running gcc -E -c <file>). This format is designed so that each token has been identified and all that needs to happen is it be sent through a code generator.

Alright dude...finish your shitty analogy
So, if letters (digits) make words (tokens), which make  sentences (statements), then another subcategory we will have is the expression. Those are little groups of words that make sense on their own, but require the sentence for structure.
An example of that would be: "This is great, nice job on the sauce!". That has two expressions, both would be perfectly understandable on their own, but when put together they make a complete thought. Above that, we will have the procedure. This is your paragraph. It's a marked place that you can always jump back to very easily.

The basics of the Abstract Syntax tree
Let's have a look at one (for a RDP aka Recursive Descent Parser)
[Image: SyonV.png]
As you can see, if you follow it from left to right, you can figure out the whole program as[/size]
Code:
x = 1
y = 2
3 * (x + y)
Now, we will spend a lot of time building this tree, but our program will never see it. I will explain that once we get into the code, just trust me for now.
Pay careful attention to how that tree is laid out. There are a few confusing bits (even for me), it's not the best example, but it captures the language very well.

So, what's next?
Next, let's figure out classes of tokens. These will become important.
We have our non terminals (really important term).
These are our Statements, Expressions, and Factors. Let's have a look at an AST with those labeled a little better (this is a big tree, but it covers all of the use cases)
[Image: calc_parse_tree.dot.png]
That first node, labeled calc is our statement. each statement gets its own tree

After that, we have our terminals
These are:
add-op (operators + and -)
mult-op (operators *, /, and %)
ident (names of things)
digit-seq (any number)

Finally, we have keywords
These aren't going to be important for quite a while, and we will cover them again then
These are things that do stuff, like calling functions, creating and deleting variables, and interacting with the user.

Wrap up
So, coming to conclusion, you should have a basic understanding of the following vocabulary
Syntax trees
Statements
Expressions
Factors
Tokens
Non-terminals
terminals
keywords
In part 2, we will start defining our language structure.



Last notes:
This language will need a name at some point, so as an incentive to get people talking on this thread I want you guys to come up with a name.
Finally, feel free to discuss here, and if you like these threads don't be afraid to throw some rep my way, I want to make that list on the bottom of the forum Tongue



Read Part 2 - Inception
(This post was last modified: 01-02-2017, 08:32 PM by phyrrus9.)

[+] 3 users Like phyrrus9's post
Reply

RE: CYFPL - Part 1 - Trees, trees, and more trees #2
Deforestation is a serious concern. I'm glad we're talking about trees.

Smile Smile Wink

Reply

RE: CYFPL - Part 1 - Trees, trees, and more trees #3
(01-02-2017, 03:06 AM)pvnk Wrote: Deforestation is a serious concern. I'm glad we're talking about trees.

Smile Smile Wink

Of course, it wouldn't be a proper SL thread unless we had some off topic humor thrown in there

Reply

RE: CYFPL - Part 1 - Trees, trees, and more trees #4
(01-02-2017, 03:27 AM)phyrrus9 Wrote:
(01-02-2017, 03:06 AM)pvnk Wrote: Deforestation is a serious concern. I'm glad we're talking about trees.

Smile Smile Wink

Of course, it wouldn't be a proper SL thread unless we had some off topic humor thrown in there
Off topic? I'm not quite sure whom you're referring to. However, I do appreciate your thread. Thank you once again for this informative content. Blush Blush Blush

Reply

RE: CYFPL - Part 1 - Trees, trees, and more trees #5
(01-02-2017, 03:30 AM)pvnk Wrote:
(01-02-2017, 03:27 AM)phyrrus9 Wrote:
(01-02-2017, 03:06 AM)pvnk Wrote: Deforestation is a serious concern. I'm glad we're talking about trees.

Smile Smile Wink

Of course, it wouldn't be a proper SL thread unless we had some off topic humor thrown in there
Off topic? I'm not quite sure whom you're referring to. However, I do appreciate your thread. Thank you once again for this informative content. Blush Blush Blush

There's plenty more to come. It saddens me that they no longer teach compiler theory at most universities anymore, it really helped me understand how everything fit together
(This post was last modified: 03-13-2017, 09:35 PM by phyrrus9.)

Reply

RE: CYFPL - Part 1 - Trees, trees, and more trees #6
(01-02-2017, 03:31 AM)phyrrus9 Wrote:
(01-02-2017, 03:30 AM)pvnk Wrote:
(01-02-2017, 03:27 AM)phyrrus9 Wrote: Of course, it wouldn't be a proper SL thread unless we had some off topic humor thrown in there
Off topic? I'm not quite sure whom you're referring to. However, I do appreciate your thread. Thank you once again for this informative content.  Blush  Blush  Blush

There's plenty more to come. It saddens me that they no longer teach compiler theory at most universities anymore, it really helped me understand how everything fit together.
I agree with your sadness as it is a justifiable sadness that you express. Stressed Stressed Stressed

Reply

RE: CYFPL - Part 1 - Trees, trees, and more trees #7
Thank you for this phyrrus. I will be reading it again soon. I for one had no compiler class at uni so I am a total noob. And lastly, I love you.
"If you look for the light, you can often find it. But if you look for the dark, that is all you will ever see.”


Reply

RE: CYFPL - Part 1 - Trees, trees, and more trees #8
(01-02-2017, 03:53 AM)God Wrote: Thank you for this phyrrus. I will be reading it again soon. I for one had no compiler class at uni so I am a total noob. And lastly, I love you.

The uni i went to had a policy that if 7 or more students requested a class they had to teach it the following term, if you're still attending that might be something you could look into. Love you too

Reply

RE: CYFPL - Part 1 - Trees, trees, and more trees #9
(01-02-2017, 03:58 AM)phyrrus9 Wrote:
(01-02-2017, 03:53 AM)God Wrote: Thank you for this phyrrus. I will be reading it again soon. I for one had no compiler class at uni so I am a total noob. And lastly, I love you.

The uni i went to had a policy that if 7 or more students requested a class they had to teach it the following term, if you're still attending that might be something you could look into. Love you too

Too late for me now Wink2
We've had people request classes before but it just doesn't work that way there. Too small of a school and even smaller of a department. Just got stuck with whatever electives were being taught.
"If you look for the light, you can often find it. But if you look for the dark, that is all you will ever see.”


Reply

RE: CYFPL - Part 1 - Trees, trees, and more trees #10
(01-02-2017, 04:12 AM)God Wrote:
(01-02-2017, 03:58 AM)phyrrus9 Wrote:
(01-02-2017, 03:53 AM)God Wrote: Thank you for this phyrrus. I will be reading it again soon. I for one had no compiler class at uni so I am a total noob. And lastly, I love you.

The uni i went to had a policy that if 7 or more students requested a class they had to teach it the following term, if you're still attending that might be something you could look into. Love you too

Too late for me now Wink2
We've had people request classes before but it just doesn't work that way there. Too small of a school and even smaller of a department. Just got stuck with whatever electives were being taught.

Well that's no fun. I'm open to doing tutorials on other compiler methods as long as I can keep a group of more than 4 people interested. It's a little difficult for me to write up a major tutorial and only get like 1 interested party.

Reply






Users browsing this thread: 1 Guest(s)