🔥 BCS613C Module 4 Compiler Design | Overview + Important Topics + MQP & PYQ Answers 💯 #vtu #bcs316c

Added: 2026-06-03

[00:00:01]So, hi, hello, everyone. Welcome back to the our channel.

[00:00:05]So far, we have completed the module one, module two, and module three of this compiler design, the subject code BCS613C.

[00:00:13]In this video, we are going to discussing about the module four based on the previous year question paper and the model question paper questions. I have collected and for those question, I have listed the answers over in this PDF, okay? Without wasting time, let's start one by one.

[00:00:30]So, here, you need to you know, if we see the syllabus copy of this module four, there are two chapters again, introduction to LR parsing and the syntax directed definition. So, in the second chapter, it is a very small chapter and here you need to draw the diagrams. Diagrams in the sense those you know, like a trees.

[00:00:55]Syntax directed graph like diagrams will be there. You need to draw. Let's start first question. Write an SDD for a simple desk calculator. Show annotated annotated parse tree for the expression 3 * 5 + 4n. This question has been there since you know, I I have referred two question paper. Out of there in the two question paper, I think it is there.

[00:01:21]So, it is a one of the important question. Let's Let's see the answer.

[00:01:25]So, for the simple desk calculator, there is a standard format is there, table. You need to draw that production and along with the semantic rules. So, the production here for this simple desk calculator, there are seven productions are there. First one is the L tends to E capital E N. So, for that for that production, we have a semantic rule. So, for this L, we are adding the value. So, L value equals to E value.

[00:01:54]Here, we are ignoring the N. And in the second production, E tends to E1 plus T.

[00:01:59]So, here again we are adding the semantic rules for this production. E both for the in the left side left-hand side and right-hand side we are adding the value. Okay, so how it will be there?

[00:02:12]Once we after adding the value, E.val = E1.val + T1.val. Like that only, third production E tends to T is there. So, for this we have after the adding of this value, it will be like this. E.value = T.val. Like that only other you know, four, five, six, seven productions are there. We are just adding the semantic rules. So, this is the syntax directed definition of a simple desk calculator.

[00:02:45]Then comes the annotated pass three for the three star five, you know?

[00:02:51]Three star five plus four and. So, they have given this example and most of the time they will give like the this kind of example. Only two three standard examples are also there. They will ask those those example itself because uh they they also don't take a risk while evaluating, okay?

[00:03:14]That's why they These are the standard example. You You people are You people can practice, okay? So, let's see the next question. What is the dependency graph? Write the dependency graph for the expression three star five with a suitable top-down approach.

[00:03:32]Okay, this question question is from from the model question paper. Yeah, here it is. See, write a dependency graph write a What What is the dependency graph? Write a dependency graph for the expression three star five with the suitable top-down grammar. For this you need to answer uh your of the dependency graph you need to write. So, the definition is a dependency graph depicts the flow of information among the attribute instances in a particular parse tree. An edge from a one attribute instance, the first is needed to the compute the second computed to the second. So, that is what definition of this dependent graph T.

[00:04:15]And the edge expression constant implied implied by the semantic rules. Here the edge expressions constants are implemented by this semantic rules.

[00:04:25]Again, here productions and semantic rules are there. Most of the syntax directed definition questions, they have a production and semantic. Wherever you can see, guys, this is also a syntax directed translation. It It has a production and rules semantic rules like like the like that only. For this question also, for the three star five.

[00:04:46]Here semantic production and semantic rules is there. Here as that question it's like that only. Here they have a in different rules. Like they have adding inheritance and value. Here the dependency graph have a inheritance and the val. So, it is a INCH stands for inheritance.

[00:05:06]VAL stands for val and SYN stands for synthesis. So, synthesis is a under the inheritance, right? So, that is what Here see, once the once it will start with a T, right? So, uh yeah, once it starts with a T, so this T have a two two sub-productions for that T production.

[00:05:31]It is having a F and T T dash. So, you are going to write F and T dash here, okay? So, again, so once you see here for the F uh you you have written F and T dash, right? See, for the F uh >> [snorts] >> Uh yeah.

[00:05:53]See, for the F you have only one digit.

[00:05:56]So, that is two.

[00:05:58]Only one digit, right? You need to write a digit here.

[00:06:02]I will explain after this. Digit you need to write. Then comes here T dash.

[00:06:06]So, here T dash is there, right? For the T dash, the magnetic rules are two passages there. So, that is T1.

[00:06:13]Inheritance and synthesis. Two inheritance and synthesis will come for the T dash. You need to write a inheritance and synthesis. Okay? Then comes the for the T dash T dash. So, again T dash um For the T dash again it will have a three options like a star, F F and T1 dash. T1 dash is nothing but a T dash itself.

[00:06:38]They have I think it's a dotted pen ink. I think so. So, you need to write the star. Then F, then T for the T dash. Again, you need to write the for the F and T dash there's a inheritance um Sorry, for the F digit is there. For F you need to write a digit. Then for the T T again for the T dash it is having a inheritance and synthesis. Once you write this all those things, here digit digit is equals to what What is there?

[00:07:14]Digit dot next value. So, the digit dot next value here we are taking a example three star five, right? You need to write the here three. So, once three is there and it will fall into a star we will get then comes a Then comes a five. So, here five is written.

[00:07:34]Right? So, here five is written. We need a three five three cross five, right?

[00:07:39]So, this This the flow it will come and another part it will be the empty.

[00:07:44]That's it about the dependency graph with an three star five and this is the annotated parse tree example. Let's see the next question.

[00:07:54]Write a SDD for a simple type declaration. Also write a dependency graph for a declaration in a ID ID2 ID1 ID2 ID3. Same as it is production and semantic rules are there. You just go through this tabular column and along with this uh dependency graph. You must have to draw the dependency graph because if you are you know, if you see the um schema of evaluation for this subject, they have mentioned uh the uh you know, the syntax directed definition for a simple type declaration tabular column uh five marks and the uh diagram for the five marks. For it is a 10 marks question, so that's why you must have to write this and you need to explain production and the semantic rules how it will works.

[00:08:41]Okay? That's it. Uh here I have given a description. You if you read this, you you will understand.

[00:08:48]Right? Then moving on to the fourth one. Uh consider the grammar S tends to C A D and S tends to A B and A.

[00:08:59]So here what what they're asking? Uh construct the canonical set of LR of zero item and the construct the SLR parsing table. So SLR parsing table here you will see the SLR parsing table LR of LR LR of zero then LR LR of one.

[00:09:21]These are the things uh you need to know about in this module. Uh let's see the let's consider the given example. This is a S tends to C A and D and A tends to A B bar D. And here you You to understand that the capital letters all are non-terminal non-terminals and the small letters all are terminals. Include operators, operations, operators. Okay?

[00:09:45]So, here it starts with a small terminal and here a non-terminal and it is terminal. Let's Let's you know construct the augmented grammar. So, this is a grammar given by the given in the question. You need to you know do the augmented form augmented format.

[00:10:05]Augmented format is nothing but a simply you just have to add the initial S' with the S. So, it is a starts with the S, right? So, for this you need to add the S' that is tends to S. So, again simple same as After that you need to write as it is S tends to CAD. Then here A tends to AB.

[00:10:25]Here it is the bar. So, this bar represents the two production from the A itself. We have a two production. That is A tends to AB. This is a one production. Then A tends to A is a another production. See here it is there A tends to AB and A tends to A.

[00:10:42]This is the augmented grammar. After that you need to add the dot dot dot for from the start. So, then canonical set of LR is of zero is there.

[00:10:52]It will starts with the first iteration.

[00:10:54]So, here LL LR of zero is nothing but you need to uh add the dot in the at the end of the production. You have to form. So, initially the dot is in front of the year you know terminal non-terminal and terminal values. You need to uh shift the that dot into the at the end of that production. Okay? That is what the thing you will you need to do here. See, we have added the dot. Our work is to push the dots at the end of the step. Here are some products some rules are there whatever rules are in this sense while shifting the you know dot if you have a you know after shifting of that dot if it is having a terminal value you need to stop there only. If you have a non-terminal value again you need to write the uh that terminal production. I will explain here. See, first one is S S tends to dot S is there right? S tends to dot S and second one S tends to dot CAD is there.

[00:12:07]We have written In the first iteration what we will do?

[00:12:12]We will shift the directly in front of the S dot. So I have written here see in the first iteration the transit for S I have you know written.

[00:12:26]Now iteration one is completed because after that there is no anything here it is completed it is accepted. In the second iteration what we will do?

[00:12:36]Sorry I will take S tends to dot CAD.

[00:12:39]Here I will shift the this dot.

[00:12:42]This dot of the after the C I have written here see.

[00:12:46]Here I have written dot so C dot A. As I already told in front of the dot if it is having a non-terminal value you need to write that terminal you know non-terminal productions.

[00:13:01]So here we have a again whatever A productions are there you need to write. So A tends to dot AB and A tends to dot dot A. I have written here. This is what in the iteration two.

[00:13:13]Next comes the iteration three.

[00:13:16]Where I have written? Yeah.

[00:13:19]Iteration three here it is.

[00:13:21]It is these are the numbers step numbers. These are this is the iteration three. Again, iteration three it is this second Yeah, again it's here itself this dot is red. I'm moving into the next one. So, I will the dot will come in front of behind the D.

[00:13:43]D right? So, that is what I have written here.

[00:13:49]Okay, so it is a D. I think it is contained there. That's that's okay.

[00:13:56]C dot D. Okay, then iteration four same.

[00:14:03]Iteration four we are shifting the dot.

[00:14:05]This this one dot in front of the B.

[00:14:10]In front of the A. Okay, so I have shifted. Then similarly this one also I have shifted. Again in the iteration five we are taking this which one uh Yeah, this iteration. Third iteration so here D is there. Again I'm shifting into the in front of D that will be the end of the this production. Like that only finally we we will shift this iteration four.

[00:14:36]Again this dot will be shifted into the B. Iteration six. And whatever we have done the iteration no, those iteration you need to write here like the state zero with the C that is a S2. Here S stands for nothing but iteration itself.

[00:14:52]Here I have written as a I1 I2 I3 like that. Here the instead of I here taking as a S because we need to represent the state that's why S2 S4 S6 like that is I will one one example I will give you see.

[00:15:08]From from zero state to C which state it will it will be there it will be two I think. Yeah, yeah, yeah, yes it is a two. See.

[00:15:20]From zero to zero to two.

[00:15:25]Zero to two it is a S2.

[00:15:28]Yeah, I have written S2 right? Like that their construction. If you will simply you know observe this tabular column you will understand that this procedure if you understand that you will then you will be able to write this tabular column as well. Let's see the again a lot of zero is there. Whatever I have explained that is something wrong in this diagram. Next comes the construction of a lot of zero item and parsing table for the following grammar.

[00:15:57]Here they have given a S tends to CC, C tends to small c capital C. Here it is a small one it is a capital one means it is a terminal it is a non-terminal. C tends to D is there.

[00:16:09]Again we need to write the argumented argumented production grammar argumented after the after the argumented it will be looks like a looks like this.

[00:16:25]Look like this. S dash tends to dot S, S tends to dot CC and once we have write this all the grammar then we need to start the production. Just simply fine or shifting the dot until the reaches the end of that production.

[00:16:41]That's it. You just understand that's right. So this is this dot is shifted into here that is the first first iteration. I ignored here. All right guys this is iteration not zero, iteration one.

[00:16:55]Like that only this is iteration two.

[00:16:58]Iteration two also by taking this dot in front of this dot I have written. So we got the terminal non-terminal as a C. So whatever the C production are there you need to write again here. Then this is a third iteration.

[00:17:15]And again it is a fourth iteration.

[00:17:19]Yeah, I have written here, right?

[00:17:22]Second first zero iteration, first iteration, second iteration, third iteration, fourth iteration, fifth and sixth iteration. Those are the nothing here.

[00:17:31]This is a third iteration, okay? So, this is a third iteration. This is a fourth one and similarly, fifth and sixth is there.

[00:17:41]Again, first and follow you need to draw that to to draw the past table. Then comes the sixth one. As like a same question here, a lot of zero is there. Here, a lot of one. A lot of one here, a lot of one, it is a same as like a a lot of zero.

[00:17:59]Plus, it it will include the What we can say that?

[00:18:06]Look ahead. Yes, look ahead. So, a lot of one is nothing but it is a addition of a lot of zero plus look ahead buffer.

[00:18:17]Uh It is a say as like a lot of zero itself, you need to draw the a lot of one. You know, with the adding a look ahead. So, look ahead nothing but dollar symbol is there, right? So, initially, we need to write a dollar.

[00:18:33]So, look ahead is nothing but the first of the whatever the variable is there in the production, that is all comes under look ahead. Out of there, you need to consider the first of that symbol. That is what? It is also exactly You need you exactly as like a this diagram itself, but here it's it is little bit a change because we have a dollar and look ahead look ahead symbol included here. In in that a lot of zero, it is not there.

[00:19:06]So, yeah.

[00:19:07]And again, L SLR of one question is there.

[00:19:13]Augmented matrix kernel a lot of zeros there. So here a few standard examples are there. You just have to practice those those all.

[00:19:22]Here I have a drawn this diagram.

[00:19:26]You just go through this PDF, okay?

[00:19:28]That's it all about in this video, guys.

[00:19:30]Hope you people are uh got the idea of this from this module four, whatever the questions are there and how you need to answer, okay?

[00:19:41]That's it. If you have any query, just let me know in the comment box.

[00:19:44]Uh yeah, thank you.