Day 130 | 8.5 Hours of Compiler Design | GATE CSE 2027 Study Vlog | Consistency Wins

[00:00:02]Hi all, welcome back to my channel. I hope everyone is doing fine. I hope everyone is doing great. Uh I hope everyone has completed their respective task regarding studies uh yesterday or studying right now. So I'm recording this day 130th of my GTCS prep uh which was yesterday. I could not record it because of some reason. I had some work and I was really tired in the night. So uh I completed 6 hours yesterday and 2 and 1/2 hours right now. So total 8:30 hours I have studied for yesterday including all compiler design only. Now I'm left with only 6 hours of uh last part of compiler design. So I'll be doing that and my regular data structure lecture which are uploaded. So these both things will be doing today. That's my target.

[00:00:56]So yesterday I have only studied uh C because I had to complete that second part actually second part there is six third last part is six hours and I'll be completing that also today. So let me show you what I've studied yesterday regarding compiler design. So this is like started with one example. First we know find the augmented grammar then closure and like first we have to find the first of this thing then this is also like uh grammar is given then augmented grammar we need to find and then closure after that go to uh we have to find it.

[00:01:43]This was a big example I have taken here. You can see I cannot explain each and everything like how I have made it. But I'm going to make different videos on this thing also. That would be my revision and it would be in detail explanation how uh it got formed this diagram. You can see DFA and then parse table. Parse table is very easy to create. I feel I will like for each of this separate separate part I'll make uh different videos so that it will be crystal clear and it will be for my sake also.

[00:02:23]So this is CLR1 parse table free from multiple entries. So about grammar is CLR1.

[00:02:30]Then conflict in CLR1 parser. So how to check in SR conflict? How to check SR conflict in CLR1 parser? So you can see if this A comes then SR conflict in CLR1 and this is DFA like of SR conflict then there is parse table and SR conflicts or you can say multiple entries then RR conflict this is like if this kind of things come then RR conflict in CLR one then this is example which is like showing RR conflict and then parse table this is also multiple entries are coming. So there there are some important points I think theoretical for every grammar if SLR1 parser can be constructed then LR1 parser can also be constructed but if LR1 parser can be constructed for grammar then SLR1 parser may or may not be constructed that is every SLR1 grammar is a CLR1 but every CLR1 grammar need not to be SLR1. [snorts] So I feel like again these are the part of subject that you need to clearly remember it like memorize it. So direct questions are possible and they have come in previous gate also. So better you should memorize this. Then CLR1 parser is more powerful than any other parser and more costly also. So medium level companies will not prefer this kind of mechanism to construct parser in compiler project.

[00:03:59]So CLR1 are most powerful and cost costliest. So medium companies cannot afford it. Basically note at time look at time look ahead part is the subject subset of follow part my bad sorry then you can see this diagram SLR0 is subset of CLR1 LR0 is subset of SLR1 and then LR0 it's subset of SLR1 and CLR1 so CLR1 is basically more powerful than any other then this is LR1 parser the DFA of CLR1 contains some state which contains the item with the same production part and different look ahead part. Now combine the state with the common production part and different look ahead part in single state and construct parse table. If the parse table free from multiple entries then free from SR and RR conflict the grammar is LL R1 grammar need to remember it. So these are some like you know we are merging I3 and I6 just plain merging you can see here for I I47 I8 and I 9 also states in LLR1 the all seven states they have uh combined it then some important points are like number of states in LR0 SLR1 LR1 are same shift entries are identical In LR0, SLR1 and LR1, go to parts are identical in LR0, SLR1 and LR1. Reduce entries may be different in LR0, SLR1 and LLR1.

[00:05:33]Action part may be different in LR0, SLR1 and LR1. Number of entries in LR0 parse table greater than equal to number of entries in SLR 1. Parse table greater than equal to number of entries in LLR 1 parse table. So total number of entries in LR0, SLR 1, LR1 are like N1, N1 greater than equal to N2, N2 greater than equal to N3 and N1 greater than equal to N3. So N1 is greater than equal to N_sub_2 greater than equal to N3. So these are also point need to directly memorize it for above grammar like these are states then this is generalized for any grammar. LR0 slr1 lr1 clr1 n1 state n2 state n3 state n4 state so n1 equal to n2 equal to n3 less than or equal to n4 this point needs to be memorized. So if DFA of CLR1 parser does not contain more than one state with common production part and different look ahead part then grammar is CLR1 and LLR1. If DFA of CLR1 parser contains more than one state with common production part and different look ahead part then grammar may or may not be LR1. Conflict can uh be done after combining.

[00:06:55]So you can see here after merging this is RR conflict in LLR1 table.

[00:07:03][clears throat] So since we can construct CLR1 which would uh and not LL1. So CLR1 obviously will be greater than LL1. So every LL1 grammar is CLR1 but every CLR1 grammar need not be LL1. So this is the diagram.

[00:07:25]This is very important diagram you need to remember. Like CLR1 is highest then LR1, SLR1 and LR0.

[00:07:35]This is same relation they have done it.

[00:07:38]So if grammar is LR0 then it is SLR1, LR1 and CLR1. If grammar not STL1 then it is not LR0 because it's very obvious.

[00:07:48]If if higher part is not then then how the subset will would exist right. So that's they have written in sentence sentential [snorts] form.

[00:07:59]So every SLR1 grammar is LLR1 but every LLR1 grammar need not be SLR1 that is LLR1 more powerful than SLR1 [clears throat] conflict in LLR1. If there are no SR conflict in CLR1 then no SR conflict in LLR1 also you can see that if there is no SR conflict here then no SR conflict in CLR1.

[00:08:24]So no SR conflict in LLR1 also.

[00:08:28]If there is no error conflict in CLR1 these may be error conflict in LLR1 grammar. If grammar not one then not LLR1 not SLR1 and not LR0.

[00:08:43]These are very important point. Every LLR0 is LR0. Every LL LL1 is LR1 or CLR1. So every LR LL0 is LL1. Every LL0 is LR of 0. SLR1 LLR 1. LR1 and LR of K.

[00:09:06]So from here there are few gate PYQ's.

[00:09:09]Um we need to find a true statement here.

[00:09:14]So first is SLR parser more powerful than LLR which is wrong.

[00:09:20]So again the diagram comes in picture.

[00:09:23]If you remember this diagram you will answer this very easily. CLR you can see the third statement is right which is canonical LR parser more powerful than LLR parser which is right.

[00:09:34]Second is like the relation assume that SLR parser for grammar G has N1 state LLR parser for G has N2 state relationship between N1 and N2 is N1= to N2= to N3 less than equal to 4 that's the relation if you find that would be um correct option but I think they have not given okay they have given N1 is necessarily equal to N_sub_2 which is right out of all the options And an LLR1 parser for grammar G can have shift reduce conflicts if [snorts] and only if the LR1 parser for G has SR conflict CLR1.

[00:10:16]Which of following statement about parser is are correct?

[00:10:21]Again we can answer from this diagram.

[00:10:27]CLR more powerful than SLR which is true. SLR is more powerful than LR false. SLR more powerful than um [snorts] canonical CLR false.

[00:10:43]So here grammar is given and we need to find the correct um statement. So first first of anything we need to find like first of a is and if uh intersection is five then it's ll1 and for all the three grammar intersection are five so it's ll1 and every ll1 is clr1 or lr1 so it's both ll1 and lr1 that's the answer and consider grammar shown below again we need to find the first intersection of like D and D and M is five.

[00:11:23]So it's LL1. Similar to this question like we need to find LR0, SLR 1, LLR1 and CLR 1.

[00:11:36]So consider SLR1 and LLR1 parsing table for context CFG. Which of following statement are true? Like go to part of both table may be different which is false. Shift entries are identical in SLR1 and LLR1 zero. Shift entries are identical in both tables which is true. Reduce entries in table may be different. True.

[00:11:54][snorts] Error entries in table may be different. Empty or empty cell. True.

[00:12:00]Which of following most powerful parsing method which is CLR. Direct answer.

[00:12:06]Merging state with common core may produce dash conflict and does not produce dash conflict in an LR. R R and SR are the answers.

[00:12:19]This is P YQ. Consider follow two sets.

[00:12:22]Which of following statement related to merging of two set in the corresponding LLR parser?

[00:12:27]We need to merge this and there is no reduce item in this. So we need to find false statements here.

[00:12:37]Wherever like you can see cannot merge.

[00:12:39]It's very visible. We can merge it. So first is false.

[00:12:44]Uh there is no conflict here if you can see. So there is no if you see SR conflict or RR conflict just cross that cannot be merged. It's it is it can be merged. So all are false in this. So we need to consider the grammar and states are N1 N2 N3 for SLR LR and LLR.

[00:13:04]Uh we need to find the relation for this.

[00:13:08]So the relation we got from the grammar or parsing method are n1 equal to n3 less than or equal to n_sub_2. But in option either less or equal to is given.

[00:13:19]So we need to solve this. And after solving like llr will have less states than clr.

[00:13:28]So less option like [snorts] less option would be correct here.

[00:13:39]I think these are again some pyqus you need to solve it. I really need to understand this. So once I understand I'll explain in like other different short videos.

[00:13:53]So like a few times happens right in the night I'm not able to record it and I'm not able to achieve those number of hours that I've decided for for myself.

[00:14:03]So I've completed in the morning and then I record it. So the yesterday was the same for me. I have studied around 8:30 hours yesterday and today morning right till now of CD.

[00:14:17]So that was my day 130th of GATE CS prep. So I think um yeah today also I already shared my target. I'll be doing that after 1 hour of break and yeah [clears throat] I'll I'll record it today. Thank you all for subscribing and thank you for showing support to my channel.