Day 129 |8 Hours of Compiler Design & Data Structures |GATE CSE 2027 Study Vlog | Daily Consistency

[00:00:01]Hi all, welcome back to my channel. I'm recording day 129 of my GATE CS prep which was yesterday. I studied but I was really tired to record it. So I thought I'll record it now. I hope everyone is doing fine and I hope everyone completed their respective task regarding studies and or have started just now studying for the [snorts] new day.

[00:00:31]So I studied 8 hours on day 128 of my gate prep.

[00:00:40]Sorry, day 128 or 129. Just pardon me for this day mistake but uh I have studied 8 hours of CD and data structures and um yeah I have already mentioned that data structure was started like in live. So yesterday a few lectures were uploaded.

[00:01:03]So I did that with notes making it was starting of data structure and a lot of things I knew it in C also but yeah still we have to do it so I've done that and CD of course that I was doing I need to speed up like I think 10 more hours of CD are remaining so we'll I'll try to finish as much as I can and DS and then I have to revise C and CN also so let Let me show you about of CT what I've studied. So there were few py of uh like if I show you regarding like there is consider you know augmented grammar given and closure is also given then we have to find the number of items in go to like this is the five items you can see it's very easy to find actually there is nothing like you have to just see the grammar and then you have to break it that's that that's how you find the number of items in go Then again here it is also like a augmented grammar is given and there are set of terminals given and we have to find the number of items in go to. So you can see here like s tends to do s then all this three same everything is same only. So eight items are in go to augmented grammar is given. Then closure is given. We have to find the number of items in go to which is again from this are nine. Then this is like augmented grammar set of terminals closure is given. Then go to this is exact items like all similar type of like questions.

[00:02:52]Easy actually not that uh difficult good thing is so this is the rule from sir like you know s dash given s is will be one production but from uh r and p there are two two productions in question if you see so total would be five so this is also again shortcut you can see [snorts] then this is gate gate pyq Q same like we have to find the same set and canonical set of item for grammar like if uh you know from the options like three options if some items are coming in any two uh same uh same two options they have given but none of it it's coming in any two options then SLR1 parser like procedure For procedure for construction of parse table of SLR1 parser is similar to LR0 parser but there is one restriction on reducing item. Whenever final item then place reduce entries under follow symbol of LHS variable. If SLR1 parse table free from multiple entries then grammar is SLR1 grammar.

[00:04:18]It should not have multiple entries.

[00:04:20]Then it would be SL SL R1 grammar [snorts] in this example there are no uh LR0 grammar. So we need to check SLR1 parse table. So we know like it's very easy to create the parse table.

[00:04:50]I1 is augmented grammar production uh reduce so write except dollar. So here I've explained like in detail if what is coming in every varial like I1 then what is coming final and non-final if it would have been final if it would have been LR0 R3 would have been in all place final if it would have been R0 but here rule is if any final item then follow the first So if any final item are there then you need to find the fall of that. You can see here I find fall of A, B, dollar and yeah then whatever final are coming you need to just find the fall of it and then symbol is coming like uh we know fall of S is start dollar symbol then you can there is one note like this is not LR0 but SLR1 so it would SLR1 would be obviously more powerful than LR0.

[00:06:03]So there are few notes like [snorts] shift entries are identical in LR0 and SLR1. Go to parts are identical in LR0 and SLR1. Reduce entries may or may not be same in LR0 and SLR1. Action part may be different in LR0 and SLR1. Number of states in LR0 equal to number of states in SLR 1. SLR1 parser can be constructed for more grammar than LR0 parser. Hence SLR1 parser more powerful than LR0.

[00:06:32]Every LR0 grammar is SLR1 but uh every SLR grammar need not to be LR0.

[00:06:39]If there is no SR and RR conflict in LR0 then there is no SR and RR conflict in SLR1 or if there is no multiple entries in LR0 parser table then there will be no multiple entries in SLR1 parse table.

[00:06:53]If there is SR or RR conflict in LR0 then there may be a [snorts] SR or RR conflict in SLR1 or if there are multiple entries in LR0 par table then there may be multiple entries in SLR1 pars table. Every L1 grammar need not be LR0 and vice versa. Every LL1 grammar need not be SLR1 and vice versa. Every LR0 SLR1 [clears throat] Then these are like some notes only like fall of B intersection X is not equal to five. It is SR conflict in LR0 and SLR1 also. If fall of B contain X then it is SR conflict in SR1 also. This is the proof of the above statement. Then uh regarding RR conflict if intersection of A and B are not equal to 0 or 50. What is written? is RR conflict I think it's it should be five I'll cross check and I'll write it again and then a proof of huh this is five they have taken follow of both and you can see in fall of a and b there is nothing common like um not equal to five there there's something it contains something so it is not equal to five so it is error conflict in SLR1 parse table you can see multiple entries are there so it's RR conflict procedure to construct LR1 parable [laughter] there are some like steps procedure to procedure of closure L that's all CD I have learned yesterday now let's go back to DS starting from start like you know Um like definition of data structure it is way of organizing the data managing data and storing data which enables efficient access and modifications or data structure is basically a kind of storage that is used to store and organize data in such way that it can be accessed and uh modified efficiently. Then types of data structure that we'll cover array link list stack Q tree graph bin algorithm hashing starting with array like arrays card uh array is collection of collection or list of element of same data types stored contiguously in memory. So you can see same data type of integer is like and they are stored continuously in memory that is r of 10 integer.

[00:09:32]Then declaration syntax is data type array name and n which is size of an array.

[00:09:42]Int m of 10 that is uh that's how you declare the array. M is an array of 10 integer. M is 1D array.

[00:09:51]How array? M will get stored in memory.

[00:09:54]Like zoom in. This is the cell. Zoom in of each cell. Here you can see. And how to find address of like first we have address is 100. We need to find second address. Address of first cell is 100.

[00:10:10]If we reach from first point to second point then we'll be able to find the address of second cell. After crossing first cell and size of each cell is four by we just need to add four byt in starting address which is 100 + 4 104.

[00:10:23]index is 0 1 2 and so on.

[00:10:26][clears throat] How to access value at each cell of an array.

[00:10:30]To store and modify value in cell for this need to know about index like m of 0 equal to 7, store 7 at zero index. Let at index five need to store value n value 9. So m of 5 equal to 9.

[00:10:44]That's how you store and modify also. If you need to modify any value in array, you can see m of 0= to 8. We are modifying the M of07 which was earlier.

[00:10:55]So that's how you store and modify.

[00:11:00]This is a note like where starting address of first cell or element of array is equal to starting address of an array. Here we call cell as element. In C programming in array element in array element of one day arrays uh one day array is cell element of two 2D array is 1D array and element of 3D array is 2D array. [snorts] But in data structure that is here we each element each cell is called as element only.

[00:11:28]Then there is question like you know 1D array is given of size 10 um and which is array of integer. What is address of element m of six and note that starting address of an array m is uh 100 and size of int is four by. So starting address is given and size of um int is four by is given. So we need to find this. So this way also you can find 100 + 0 to 5 into 4 100 is starting address 0 to 5 the number of elements we need to count and size and there are two ways to count 0 to 5. First is like separate one 0 and then count like separate 1 to five. So it would be six.

[00:12:13]Same way then last minus first + 1 that is also again formula you can either way you can count 0 to 5 and answer would be 124 that is the desired result in equation. So this is the in general for any 1D 1D array M1 the address of element of M of I is if you need to find any address like that's a general way [snorts] so rule for 1D array 2D array 3D array what is the address of cell with index K starting address of an element or started address of array plus number of element to be crossed to reach index. K into size of an int and k is a representation of index depending on type of array it would be 1 2 1 d 2D 3D.

[00:13:13]So again there is a question like 1D array is given and a 1 to 30 given assume that each index 2 byte of memory what will be an address of element a of 13. [clears throat] First element of array start at 100 you need to find 13.

[00:13:28]So again the same formula we can apply 100 + 1 to 12 into 2.

[00:13:33]There might be one question like you know start address 100 given and trying to reach till uh start address of 13 how then need to cross bite present in between y after adding and then again question why after adding total number of bytes in address 100 getting desired result. So memory is divided into bytes and each bite has an address. So when adding number of bytes in start address we are actually adding the number of addresses only that's why we are getting the uh start address of 13 might ask so better we we should be known then this is 1D array declared as follow - 8 - 7 7 it doesn't mean that each integer take two byt of memory what will be the address of an element a of five note that first element of an array starting address is 300. So this is the given array with starting at 300. Then we can see the normal way the formula we apply and 13 they have have they mentioned somewhere 13. They have mentioned 13 like we need to find not 13. Okay from count we can see it's 13.

[00:14:57]Then 2D array start of 2D array like array declaration syntax. M is number of row. N is number of column.

[00:15:05]Uh diagrammatic rep representation of 2D array. That's how we represent 2D array.

[00:15:10]Total number of cells is number of rows into number of columns is 12. How this 2D array m will get stored in memory.

[00:15:19]Row wise continuously get stored in memory in four bytes.

[00:15:23]So this is kind of like it will get stored as 1D array in memory only. First row, second row, third row stored in form of 1D array. You can see that also [clears throat] then.

[00:15:39]So these are the you know number of cell addresses uh like addresses in this representation only.

[00:15:51]index of each cell. We need to uh like find or give inside this diagrammatic representation. You can see [snorts] index starting with row index and column index 0 0 1 0 2 03 1 0 1 1 2 1 3.

[00:16:12]How to access value at each cell of an array? M like just give row and column like to access 8 0 1 to access 9 1 3 and store also you can give the same uh m of 01 798 so that's all for the DS I have learned today yesterday sorry I mean Just give me a sec. I'm trying to unlock this my maybe I think 200 roughly 200 days are remaining or almost 6 months are remaining. So we need to accelerate our prep little.

[00:17:17]Uh so I think that was day 129 of my gates prep and yeah I'll be starting my day just right now to study and thank you all for showing support to my channel and watching my videos. Uh keep supporting and thank you for subscribing my channel.