+- Sinisterly (https://sinister.ly)
+-- Forum: Coding (https://sinister.ly/Forum-Coding)
+--- Forum: Coding (https://sinister.ly/Forum-Coding--71)
+--- Thread: Tutorial CYFPL - Part 1 - Trees, trees, and more trees (/Thread-Tutorial-CYFPL-Part-1-Trees-trees-and-more-trees)
Pages:
1
2
CYFPL - Part 1 - Trees, trees, and more trees - phyrrus9 - 01-02-2017
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]](http://media.treehugger.com/assets/images/2016/07/green-forest-trees.jpg.662x0_q70_crop-scale.jpg)
No....not those trees, syntax trees
![[Image: ch08-tree-3.png]](http://www.ling.helsinki.fi/kit/2009s/clt231/NLTK/book/tree_images/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]](http://thefw.com/files/2012/09/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]](https://i.stack.imgur.com/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)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]](http://igordejanovic.net/Arpeggio/images/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
Read Part 2 - Inception
RE: CYFPL - Part 1 - Trees, trees, and more trees - pvnk - 01-02-2017
Deforestation is a serious concern. I'm glad we're talking about trees.
RE: CYFPL - Part 1 - Trees, trees, and more trees - phyrrus9 - 01-02-2017
(01-02-2017, 03:06 AM)pvnk Wrote: Deforestation is a serious concern. I'm glad we're talking about trees.
Of course, it wouldn't be a proper SL thread unless we had some off topic humor thrown in there
RE: CYFPL - Part 1 - Trees, trees, and more trees - pvnk - 01-02-2017
(01-02-2017, 03:27 AM)phyrrus9 Wrote: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.(01-02-2017, 03:06 AM)pvnk Wrote: Deforestation is a serious concern. I'm glad we're talking about trees.
Of course, it wouldn't be a proper SL thread unless we had some off topic humor thrown in there
RE: CYFPL - Part 1 - Trees, trees, and more trees - phyrrus9 - 01-02-2017
(01-02-2017, 03:30 AM)pvnk Wrote:(01-02-2017, 03:27 AM)phyrrus9 Wrote: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.(01-02-2017, 03:06 AM)pvnk Wrote: Deforestation is a serious concern. I'm glad we're talking about trees.
Of course, it wouldn't be a proper SL thread unless we had some off topic humor thrown in there
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
RE: CYFPL - Part 1 - Trees, trees, and more trees - pvnk - 01-02-2017
(01-02-2017, 03:31 AM)phyrrus9 Wrote:I agree with your sadness as it is a justifiable sadness that you express.(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 thereOff 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.
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.
RE: CYFPL - Part 1 - Trees, trees, and more trees - Nil - 01-02-2017
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.
RE: CYFPL - Part 1 - Trees, trees, and more trees - phyrrus9 - 01-02-2017
(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
RE: CYFPL - Part 1 - Trees, trees, and more trees - Nil - 01-02-2017
(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
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.
RE: CYFPL - Part 1 - Trees, trees, and more trees - phyrrus9 - 01-02-2017
(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
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.