Just discovered this channel just a few hours ago and already binged almost 20 videos! It's amazing how you can explain concepts so clearly and concisely that made topics I struggled on so much before look so simple and straightforward! Easily the best teaching channel I've ever found here
here because I'm building my first compiler for a new language I'm writing. went back and forth between this video, some test code I was writing in C++, and ChatGPT for supplemental learning. once I build out my TreeNode class more and get more comfortable working with trees, I'm hoping I'll be able to take the next step and actually start into the AST phase. right now all I have is a really rough lexer. wish me luck. thanks for the educational content.
I've been searching for the perfect video for the past 2 hours, at last i landed on your video, i was literally on the verge of giving up. your a life saver. keep up the great work. thank you
I have implemented simple language but it aint that much harder. It depends up on the grammar(parser) that you designed to use. Use yacc for parser. I know how to design programming language but it is not really done by one person.
@@judgeomega True, few people are going to work on traditional compiler development. But, compiler concepts (ASTs, parser generators, grammars) have a lot of applications. They're skills that you don't think you'll ever need until you acquire them and then you're surprised how often they're useful. Are there specific concepts you would like to see?
@@JacobSorber there is a lot of information already on the internet about specific structures, and i find your videos to be among the best. but iv found it really hard to find information on broad very high level concepts for complex programs; software architecture, reducing the complexity of the problem, when/ how best to utilize threads, and in general just tips for tackling big projects. also, i havent seen much in the way on information regarding event driven programming and signal interrupts. and finally; when to create your own library, when to use third party libraries, and how do you even discover libraries which might be useful?
@@JacobSorber I would be interested in the basic structure of the compiler and how you would handle program-errors and warnings (With good messages). Talking about parsing expressions could be interesting too, as there are multiple approaches.
Hi Dr. Jacob, I have a question regarding what you said: "these don't need to be allocated on the heap if we don't want. I could have them with globals, I could have them with locals." Trees are data structures that deal with an unknown number of data, which is why the heap is the best area for trees to be stored. What are the uses cases when you would implement trees using globals/locals?
The main point is that the data structure is independent of where the data is allocated. One place where this shows up is in embedded systems where you have little memory and can't risk the nondeterminism that comes with using a traditional heap. So, instead, you might declare a bunch of objects (global variables) and then hand them out as needed. You're basically preallocating your memory, to ensure that things don't crash into other things (like your stack). And, of course, you could say that I just implemented a more predictable heap implementation (fair), but I never used malloc or new, and these memory blocks were pre-allocated at compile time. Another thing that I occasionally see is a data structure where some objects are on the heap, but some are globals or allocated by someone else. For example, say I wanted to store a bunch of different communication streams (sockets, pipes, files) in a data structure. Most of these objects are things that I created, right? But, what if I want to include stdin/stdout in there. I didn't allocate those objects, and I can't guarantee where they are allocated (since libC allocated them). I can still add them to my tree/list/hash table, even though they may or may not be on the heap. But, you're right. Most nodes on most trees running in the known universe are allocated on the heap.
ASTs are used for a variety of tasks in compiler development -- such as SSA generation using Braun13, and CFG generation that helps with Data-Flow analysis. The AST itself is made from the parser, and then used to create Linear IR.
This was a good short intro. I'll have to see if you've done one on non-recursive tree walking because that would be a good one to show any newbies. If you haven't already I hope you do at some point as you would make a really good video on it where most would not, and it would give me something to recommend for others.
Here's a tree traversal function (Depth First Scan) sans recursion: 'isFwd' must be 0 for small-to-large or 1 for large-to-small (Great name, eh?) 'p' is the root of the tree 'act' is a ptr to an 'action' function to perform for each consecutive node (eg print the record's information, perhaps )... Yeah, an arbitrary 12 layers of stack is ... arbitrary... Could use realloc() to be limitless... typedef struct NODE { void *record; struct NODE *n[2]; // 0=left, 1=right } BTN_t, *pBTN_t; static void Traverse( int isFwd, pBTN_t p, void (*act)( void* ) ) { printf( " Traverse %s: ", isFwd == 0 ? "Forward" : "Reverse" ); pBTN_t stk[ 12 ]; // max 12 'generations' bool popped = false; for( int si = 0; si >= 0; ) { while( !popped && p->n[isFwd] ) stk[ si++ ] = p, p = p->n[isFwd ]; (*act)( p->record ); if( popped = ( ( p = p->n[!isFwd] ) == NULL ) ) p = stk[ --si ]; } } Here, '*n[2]' is convenient to avoid duplications that would use p->left and p->right. That should probably be a union of the 2 element array and 2 named ptrs...
@@rustycherkas8229 Okay, but I was really hoping Jacob would do a video on it so I could show anyone who asks. If it's just about having the code, I've got it multiple times over. I'd like him to walk people through it so a newbie could understand it. If I had the equipment and knew how to edit the video I could always do it myself, but people are put off by disguised voices. Also, when you want to walk a balanced tree, using a temporary space as a stack is fine, but if it's not balanced you definitely need to use parent pointers.
@@anon_y_mousse Jacob does make good videos for those interested in C and more. Regarding "parent pointers", I'm guessing you mean that nodes need another 'up' pointer back to their parent... You're welcome to try the struct and traverse function I posted here (with sparse commentary). It works as indicated, whether or not the tree is balanced. I pointed-out the small size of the stack (depth), but that's easy to change... Have fun!!
5:55 could have casted the result of of the creation of node since malloc returns a void*. Anyways, great video. I have my midterm exam of data structures in around 2 hours, this is saving me !
Hi Jacob, It would be great if you could make a video on AST specific for language parsers. I build one for a expression parser by which I add new nodes to the left and traversed then Post Order to calculate the results but I don't know how something like that would be build/implemented for language parsers like getting tokens from a Lexer and actually building the AST (which can be used later for IR). So, I would really appreciate if you could make a video on AST with regards to language parsers and how AST for those is built.
Dr. Sorber is one of the smartest, most influential professors I’ve ever had. I’ll never forget the time he told me my code was quite elegant and very well written despite the bugs. I don’t even care about the failing grade, that accolade was better than earning an A. Academia timelines aren’t your friend. The answer is always “it depends” but you better be ready to explain the dependencies (no pun intended).
Jacob Sorber likewise! I’m really enjoying your channel to review/brush up my skills! Maybe you could do one on your project ‘Watts up Doc?’ ? I always thought that project was the coolest thing ever
Hi, for the create node function, why is “return result” AFTER the if statement, unless we want the function to return NULL in the case memory allocation is unsuccessful? However, wouldn’t we want to throw an error if memory allocation fails?
5:30 I'm new to C. Was watching a design patterns video the other day. They said `T* p = malloc(sizeof(T))` was an anti-pattern because of subtle issues you can get when renaming stuff. A better approach would be `T* p = malloc(sizeof(*p))`. Thoughts and reactions?
I know this is supposed to be short and introductory, but I still missed seeing the implementation of binary trees on arrays through abstraction of indexes. Which is probably the actual general case.
Thanks. I've personally found array-tree implementations to be a little confusing right ouf of the shoot for students. So, I opted for a simple linked implementation. But, I'm planning to hit that in a future video.
i actually started to use "recursive lists" (sutrctured like in haskell, so there's no "wrapper type", and a node consists of a value and a pointer to a tail-list) in small projects (~ advent of code). is there anything particulary bad about that approach ?
Nice video. I am wondering though, why use Linked List to demonstrate an AST Traversal Tree? Programming Schools everywhere these days are teaching this which is odd and a bit backwards. However there is more to a Traversal Tree than what you're being lead to believe. How so? Well for the most part a Tree Traversal is a Lexing or Parsing or both of a File String Syntax. And as the traversal moves from top down and left to right, the syntax is then processed as an AST Tree for a compiler, a database or for a live Interpretation. Linked List are sometimes used to demonstrate data mangling as data structures as what they are, but as Tree's they are misunderstood. No Offence though because everyone is doing this these days. Linked Lists are perfect for Indexing any kinds of data including data that Parsers require while processing a syntax also. But that is a small percentage of what a Traversal Tree is and does actually. A finer example of a Tree is a "Mathematical Expression Engine" used in all Computer Languages. As math within a syntax is evaluated as tokens to catch digits for: left_left, left_right and right_left, right_right etc. and Operators such as *, /, +, - , % etc. And likewise they must also catch Precedence Operators as " ( " & " ) " which are: pre_left_left, pre_left_right and pre_right_left, pre_right_right. These all require precise conditional if else statements and links to and with many data types including structs. Just thought I'd point this out to you. Yea I'm an Old Time Hacker from Basic and C Language going way back. I like your spirit in your work. Thanks.
@@TheVertical92 C doesn't have introspection, which is what I think you're looking for. There are some rather ugly hacks you could try, but it would be CPU dependent, compiler dependent, and likely at some point to break.
@@JacobSorber Yeah i have read something about "abusing the preprocessor" to do that, but i thought maybe there is a more elegant way. Thank you for your answer 👍Stay healthy and keep it up :) Your videos (especially about C) helped me alot.
1:54 I am not crazy! I know he swapped those numbers. I knew it was 1216. One after Magna Carta. As if I could ever make such a mistake. Never. Never! I just - I just couldn’t prove it. He covered his tracks, he got that idiot at the copy shop to lie for him. You think this is something? You think this is bad? This? This chicanery?
Just discovered this channel just a few hours ago and already binged almost 20 videos! It's amazing how you can explain concepts so clearly and concisely that made topics I struggled on so much before look so simple and straightforward! Easily the best teaching channel I've ever found here
here because I'm building my first compiler for a new language I'm writing. went back and forth between this video, some test code I was writing in C++, and ChatGPT for supplemental learning. once I build out my TreeNode class more and get more comfortable working with trees, I'm hoping I'll be able to take the next step and actually start into the AST phase. right now all I have is a really rough lexer. wish me luck. thanks for the educational content.
I'm wishing you best of luck Mate 🙏, would love to connect with you , if you mind
I would definitely love to get to know more about AST's and compiler related topics
I've been searching for the perfect video for the past 2 hours, at last i landed on your video, i was literally on the verge of giving up. your a life saver. keep up the great work. thank you
would love to see that implementation of a compiler!
only a handful of people in the world really need that information, i would rather see vids on high level concepts
I have implemented simple language but it aint that much harder.
It depends up on the grammar(parser) that you designed to use. Use yacc for parser.
I know how to design programming language but it is not really done by one person.
@@judgeomega True, few people are going to work on traditional compiler development. But, compiler concepts (ASTs, parser generators, grammars) have a lot of applications. They're skills that you don't think you'll ever need until you acquire them and then you're surprised how often they're useful.
Are there specific concepts you would like to see?
@@JacobSorber there is a lot of information already on the internet about specific structures, and i find your videos to be among the best. but iv found it really hard to find information on broad very high level concepts for complex programs; software architecture, reducing the complexity of the problem, when/ how best to utilize threads, and in general just tips for tackling big projects.
also, i havent seen much in the way on information regarding event driven programming and signal interrupts.
and finally; when to create your own library, when to use third party libraries, and how do you even discover libraries which might be useful?
@@JacobSorber I would be interested in the basic structure of the compiler and how you would handle program-errors and warnings (With good messages). Talking about parsing expressions could be interesting too, as there are multiple approaches.
I hate my life
Looser
Life is a tree
Me too bud me too
skill issue ngl
me too we have so much in common let's have public humiliation
I'd love to watch a video about compilers! Your content is awesome by the way
Thanks. I'll see what I can do.
Yup! Count me in , too!
So without further ado, that was an excellent explanation! Looking forward to more DS videos!
Wow no one else explained this better .. thanks a TON
Hi Dr. Jacob,
I have a question regarding what you said:
"these don't need to be allocated on the heap if we don't want. I could have them with globals, I could have them with locals."
Trees are data structures that deal with an unknown number of data, which is why the heap is the best area for trees to be stored. What are the uses cases when you would implement trees using globals/locals?
The main point is that the data structure is independent of where the data is allocated. One place where this shows up is in embedded systems where you have little memory and can't risk the nondeterminism that comes with using a traditional heap. So, instead, you might declare a bunch of objects (global variables) and then hand them out as needed. You're basically preallocating your memory, to ensure that things don't crash into other things (like your stack). And, of course, you could say that I just implemented a more predictable heap implementation (fair), but I never used malloc or new, and these memory blocks were pre-allocated at compile time. Another thing that I occasionally see is a data structure where some objects are on the heap, but some are globals or allocated by someone else. For example, say I wanted to store a bunch of different communication streams (sockets, pipes, files) in a data structure. Most of these objects are things that I created, right? But, what if I want to include stdin/stdout in there. I didn't allocate those objects, and I can't guarantee where they are allocated (since libC allocated them). I can still add them to my tree/list/hash table, even though they may or may not be on the heap.
But, you're right. Most nodes on most trees running in the known universe are allocated on the heap.
@@JacobSorber thank you for your explanation (y)
Oh, please! I want to see a implementation of ASTs and general compiler related topics!
yes, please!!! I would definitely enjoy you going into compiler data and would love to see a video on it and other parts!!!
I've been interested in Trees for a while, but you got a Like for the Baron Harkonnen reference.
Great teacher, thank you Jacob
The best explanation I could find, thank you.
A video on compilers would be interesting !!
i would definitely to know how the compiler works with trees
ASTs are used for a variety of tasks in compiler development -- such as SSA generation using Braun13, and CFG generation that helps with Data-Flow analysis. The AST itself is made from the parser, and then used to create Linear IR.
Wow, Excellent and simple implementation ! Thanks .
A video on meta-programming would be awesome 💜
This was a good short intro. I'll have to see if you've done one on non-recursive tree walking because that would be a good one to show any newbies. If you haven't already I hope you do at some point as you would make a really good video on it where most would not, and it would give me something to recommend for others.
Here's a tree traversal function (Depth First Scan) sans recursion:
'isFwd' must be 0 for small-to-large or 1 for large-to-small (Great name, eh?)
'p' is the root of the tree
'act' is a ptr to an 'action' function to perform for each consecutive node (eg print the record's information, perhaps )...
Yeah, an arbitrary 12 layers of stack is ... arbitrary... Could use realloc() to be limitless...
typedef struct NODE {
void *record;
struct NODE *n[2]; // 0=left, 1=right
} BTN_t, *pBTN_t;
static void Traverse( int isFwd, pBTN_t p, void (*act)( void* ) )
{
printf( "
Traverse %s:
", isFwd == 0 ? "Forward" : "Reverse" );
pBTN_t stk[ 12 ]; // max 12 'generations'
bool popped = false;
for( int si = 0; si >= 0; )
{
while( !popped && p->n[isFwd] )
stk[ si++ ] = p, p = p->n[isFwd ];
(*act)( p->record );
if( popped = ( ( p = p->n[!isFwd] ) == NULL ) )
p = stk[ --si ];
}
}
Here, '*n[2]' is convenient to avoid duplications that would use p->left and p->right. That should probably be a union of the 2 element array and 2 named ptrs...
@@rustycherkas8229 Okay, but I was really hoping Jacob would do a video on it so I could show anyone who asks. If it's just about having the code, I've got it multiple times over. I'd like him to walk people through it so a newbie could understand it. If I had the equipment and knew how to edit the video I could always do it myself, but people are put off by disguised voices. Also, when you want to walk a balanced tree, using a temporary space as a stack is fine, but if it's not balanced you definitely need to use parent pointers.
@@anon_y_mousse Jacob does make good videos for those interested in C and more.
Regarding "parent pointers", I'm guessing you mean that nodes need another 'up' pointer back to their parent... You're welcome to try the struct and traverse function I posted here (with sparse commentary). It works as indicated, whether or not the tree is balanced. I pointed-out the small size of the stack (depth), but that's easy to change... Have fun!!
3:23 my favourite part of these videos.
I was really hoping you would fix that asymmetrical "-----" at some point.
3:23 that put a smile on my face :)
5:55 could have casted the result of of the creation of node since malloc returns a void*. Anyways, great video. I have my midterm exam of data structures in around 2 hours, this is saving me !
Hi Jacob, It would be great if you could make a video on AST specific for language parsers. I build one for a expression parser by which I add new nodes to the left and traversed then Post Order to calculate the results but I don't know how something like that would be build/implemented for language parsers like getting tokens from a Lexer and actually building the AST (which can be used later for IR). So, I would really appreciate if you could make a video on AST with regards to language parsers and how AST for those is built.
Please make building compiler in C series. Would love it so much.
Your videos are amazing!!! Definitely want content on compilers
you are cool, I really appreciate people who share knowledge and encourage learning ... In the future I intend to follow the same steps.
You're my favourite RUclipsr
Without further ado a surprise Mini Sorber cameo (and channel debut?) at 3:23 😆
can you make from Unix-like OS , c compiler to compile OS and all the software , hardware architecture
You might check out James Sharman's channel. He had kind of done this.
Hi, do you have a video on recursion removal using a stack?
Loved your daughter's cameo 😁
I like you t-shirts and the design of your , nice and minimalistic
Thanks. Hopefully, they will look as great on you as they do on me. 😉
Your daughter is a sharp cookie. “Without further ado” can seem trite. Good kid
Dr. Sorber is one of the smartest, most influential professors I’ve ever had. I’ll never forget the time he told me my code was quite elegant and very well written despite the bugs. I don’t even care about the failing grade, that accolade was better than earning an A. Academia timelines aren’t your friend. The answer is always “it depends” but you better be ready to explain the dependencies (no pun intended).
Hey. I remember a student, named Merica. Good times. Hope you're doing well.
Jacob Sorber likewise! I’m really enjoying your channel to review/brush up my skills! Maybe you could do one on your project ‘Watts up Doc?’ ? I always thought that project was the coolest thing ever
question, why do you keep using printf when putchar & puts would both be faster & more appropriate for some things?
Hi, for the create node function, why is “return result” AFTER the if statement, unless we want the function to return NULL in the case memory allocation is unsuccessful? However, wouldn’t we want to throw an error if memory allocation fails?
Please do make a video on ASTs
5:30 I'm new to C. Was watching a design patterns video the other day. They said `T* p = malloc(sizeof(T))` was an anti-pattern because of subtle issues you can get when renaming stuff. A better approach would be `T* p = malloc(sizeof(*p))`. Thoughts and reactions?
Can you do a video on ring buffers?
Yeah, probably. I'll add it to the list.
@@JacobSorber Awesome Jacob! Great video as always
I know this is supposed to be short and introductory, but I still missed seeing the implementation of binary trees on arrays through abstraction of indexes. Which is probably the actual general case.
Thanks. I've personally found array-tree implementations to be a little confusing right ouf of the shoot for students. So, I opted for a simple linked implementation. But, I'm planning to hit that in a future video.
What a great channel!
Than you so much
Visited here after watching a reel on instagram which says best yt channel for C programming🤣🤣
i actually started to use "recursive lists" (sutrctured like in haskell, so there's no "wrapper type", and a node consists of a value and a pointer to a tail-list) in small projects (~ advent of code). is there anything particulary bad about that approach ?
can you make a video about a tcp server with epoll
Yeah, it's on the list.
@@JacobSorber amazing
3:23 your girl made the best job here XD
What color theme is this?
Nice video. I am wondering though, why use Linked List to demonstrate an AST Traversal Tree? Programming Schools everywhere these days are teaching this which is odd and a bit backwards.
However there is more to a Traversal Tree than what you're being lead to believe. How so? Well for the most part a Tree Traversal is a Lexing or Parsing or both of a File String Syntax.
And as the traversal moves from top down and left to right, the syntax is then processed as an AST Tree for a compiler, a database or for a live Interpretation.
Linked List are sometimes used to demonstrate data mangling as data structures as what they are, but as Tree's they are misunderstood. No Offence though because everyone is doing this these days.
Linked Lists are perfect for Indexing any kinds of data including data that Parsers require while processing a syntax also. But that is a small percentage of what a Traversal Tree is and does actually.
A finer example of a Tree is a "Mathematical Expression Engine" used in all Computer Languages. As math within a syntax is evaluated as tokens to catch digits for:
left_left, left_right and right_left, right_right etc. and Operators such as *, /, +, - , % etc.
And likewise they must also catch Precedence Operators as " ( " & " ) " which are:
pre_left_left, pre_left_right and pre_right_left, pre_right_right.
These all require precise conditional if else statements and links to and with many data types including structs.
Just thought I'd point this out to you. Yea I'm an Old Time Hacker from Basic and C Language going way back. I like your spirit in your work. Thanks.
can you make video a about graph. thanks
Your videos should be on netflix!
Awesome 👏
i think u change my future
Hey quick question:
Is it somehow possible to iterate through structs in C?
Clarify what you mean by "iterate through"
@@JacobSorber Iterating through the members of a struct.
Example: Assign the same value to all struct-members with some sort of loop.
@@TheVertical92 C doesn't have introspection, which is what I think you're looking for. There are some rather ugly hacks you could try, but it would be CPU dependent, compiler dependent, and likely at some point to break.
@@JacobSorber Yeah i have read something about "abusing the preprocessor" to do that, but i thought maybe there is a more elegant way.
Thank you for your answer 👍Stay healthy and keep it up :) Your videos (especially about C) helped me alot.
Please implement an AVL Tree in C, thanks.
king
I never knew that Yoda was Chuck Norris' nephew
Many things on this channel, you can learn.
7:24 well actually, they're all trees, just of size 1! :D
Indeed.
rip headphone users @ 3:23
Great
I have been c coding for years and still don't know it all...
1:54
I am not crazy! I know he swapped those numbers. I knew it was 1216. One after Magna Carta. As if I could ever make such a mistake. Never. Never! I just - I just couldn’t prove it. He covered his tracks, he got that idiot at the copy shop to lie for him. You think this is something? You think this is bad? This? This chicanery?
"The tree is upside-down" - we're computer scientists, not botanists.
😀
I got jump scared !!!!
The tree is not upside-down, it is just encoded in little-endian up!
Where were you when I needed you? xD
I don't know. When did you need me? 😀
@@JacobSorber About a month ago 😂
~~First~~ Root
Your daughter scared the hell out of me wtf
confusing...
Really tired of without further ado pado
BUY AND HOLD $GME, FK BEARS