Compiler Design-Lecture 3

Ajouté : 2026-05-11

[00:00:00]It seems uh two two days.

[00:00:05]Let me share the PPT.

[00:00:12]Okay.

[00:00:14]So, we started uh since two two days and two lectures are over on compiler design. This is the third lecture.

[00:00:23]In the yesterday lecture, what we covered actually, we we started realizing the work of to know the work of each and every phase of the compiler.

[00:00:34]Okay? In that, we took an example realize uh their work.

[00:00:42]And that was not exactly covered because of the lack of because of the time constraint. Okay?

[00:00:50]So, where we left yesterday, there only we we will start from there. Okay? So, let me uh recap on that that we started realizing the work of each and every phase of the compiler. Okay? We came across what is the what is lexical analyzer and we took an example to realize how it perform tokenization.

[00:01:12]And uh then what is the role of syntax analyzer? How it impose grammatical structure in order to identify whether the whether a particular sentence is grammatically correct or not.

[00:01:25]Then uh we came across uh we realized the role of semantic analyzer, how it perform type checking, and whether a variable is declared or not declared, uh any any redundancy declaration is there.

[00:01:42]Okay? These are the things we came across. Now, finally, what we came to know that lexical analyzer uh it it it collects, I mean, creates token and store them in the symbol table. And this syntax analyzer collect all the tokens from the symbol table and impose a grammatical structure on them. That is called as context-free grammar to realize to know whether the syntax is I mean the structure of the sentence is correct or not. Or the I mean uh the grammatically the sentence is correct or not. Then it it produces a parse tree as an output. This parse tree is passed through the syntax semantic analyzer as an input. The semantic analyzer performs some kind of checks and then it produces another kind of parse tree that is called as abstract parse tree. This abstract parse tree is now passes is passed as an input to the intermediate code generation. So, here we'll we need to start we need to realize what exactly the intermediate code generation does, okay?

[00:02:50]Okay.

[00:02:52]I made it full screen now.

[00:02:56]Okay. Here you see the intermediate code generation is the fourth phase of compiler, okay?

[00:03:03]It is generated machine independent intermediate code. Machine independent in the sense which is not dependent on the underlying architecture of the machine, okay? Like the which does not depend on the number of registers present in your system, general purpose registers, what is the instruction set, what is the addressing mode, and what is the operating system running. All these things it it does not bother, okay?

[00:03:30]Irrespective of the machine architecture, this code uh runs smoothly, okay? In any system. That is why it is called as in machine independent code or machine independent intermediate code. So, the role of intermediate code generation is generated is to break the entire source code into a particular into a different format different but particular format that is called as three address code.

[00:03:56]Okay? So, you can see in the second line the intermediate code generation phase of a compiler usually convert the source code into an intermediate representation known as IR. Okay? And one of the most commonly used or popular IR, I mean intermediate code generation intermediate representation is three address code. Three address code means that code it is a code where maximum, okay, maximum three operands can be placed.

[00:04:27]So, you can understand now maximum three operand. Okay? The So, there may be only one operand, there may be two operands, there but maximum there can be three operands not beyond that. Okay? So, such type of such type of code uh uh representation is called as three address code. Okay? You can see in the right hand side right hand side of the PPT, okay, and you try to understand or try to recall that the abstract syntax tree uh what what already produced by the semantic analyzer that is now passed as an input to the intermediate code generation.

[00:05:08]That is ID1 equals to ID2 plus uh into ID3 on the other hand into real 60.

[00:05:18]This is the abstract syntax tree. Okay, this syntax tree is now act as an input to the intermediate code generator. The intermediate code generator what it it does, it it breaks the entire syntax tree or it it breaks the entire code into three address format. Okay? How it it does? First it it allocate uh the into real into real is an operator and 60 is an operand. So, that together how many operands how many operands are there? Only one operand that is 60. And how many operators?

[00:05:49]There are two opera opera one copy operator, another one is conversion operator, implicit operator, that is called as into real. Two So first of all, what it it does, it it convert the value 60 60 integer value 60 into real, then it will place that result in the temporary register. The temp t e m p one is nothing but the temporary. Okay? So it is in this particular code uh the the compiler allocate number of temporary is to hold the value.

[00:06:20]Okay? Temporary is in the sense this these are the you can you can say there's uh these are the temporary registers.

[00:06:28]Okay? Just they hold the value for uh what? Calculation purpose.

[00:06:34]Okay? For they hold the value only for sometimes or few time. Yeah, for sometimes. Once the memory allocation occur, these temporary is will be empty. Okay? Or you may say they will be die. Okay? So the the So in this particular phase intermediate code generator it allocate it allocate number of temporary is to to hold different values. So in you can see it how it it breaks. First of all, it assign the real value 60. Okay? Real value in the sense why I'm saying real value? Because we already convert that value by using an operator called as into real. Okay? Previously it was 60, now it is converted to as into real operator has been assigned.

[00:07:23]Okay? And the role of into real operator is to convert the integer to real.

[00:07:30]The integer number 60 is now converted into real, that is 60.0.

[00:07:37]Okay? So that that is why So So first it it what it it does, it it Uh now, you can see it it allocates the real value 60 to the temporary temp one.

[00:07:50]Okay? Next, what it it does, uh in temporary two, it it allocates ID3 ID3 means identifier three into that piece of code you can analyze. ID3 into temp one. Temp one means it it holds the real value of 60. Okay? Real number 60.

[00:08:11]Okay? So, now temp two is another or new temporary which holds ID3 into temp. Now, in this code, in this particular line, how many uh operands are there? Three operands. One is temp two, second one is ID3, and third one is temp one. Okay? Now, you cannot allocate another things another operand here or any other operator here. This line is complete.

[00:08:39]Okay? Maximum three operands can be there. Okay? Now, next another temporary is has been assigned that is called as temp three. Temp three is holding the result of the temp one temp one as well as temp two.

[00:08:55]Okay? I mean, it it holds the result of ID2 plus temp two.

[00:09:00]Okay? Temp three is equals to ID2 ID2 in the sense identifier two plus What is temp two? Temp two is holding ID3 into temp one. What is temp one?

[00:09:12]Temp one is holding into real 60. Okay?

[00:09:16]So, in this uh next Finally, finally, everything is placed in temp three. But, the temp three, you cannot store the data in temp three for permanent permanent. Okay?

[00:09:27]Because that is one temporary register or simply you can say temporary variable. You cannot store the data there permanent. You need to place the data You need to place the final result in the memory. So, for that, what is the memory? Memory variable here is ID1.

[00:09:43]Okay? ID1 is the real variable which holds everything. Because we started from position position equals to initial plus rate into 60. So, the left-hand side variable is position. Now, that variable is renamed as I I mean the token type of that variable is identifier one. So, that is going to hold everything which is present in the right-hand side. Everything will be calculated and the result will place in position. That is the thing. Okay? So, the same thing, but it it divides the entire code in it in a specific format. Okay? That is called as intermediate representation. Or you may say the example you may take it as a three-address code. Okay? Three-address code is one of the best format that has been that that has been given by this intermediate code generator.

[00:10:39]Okay? So, every code need to be converted into three-address form three-address code form where maximum three operands can be there.

[00:10:50]You can see in these four lines, there are in the first line, there are only two operands. In the second line consists three operands. Third line consists three operands. Whereas last line consists only two operands.

[00:11:05]One is the source, another one is the one is the yeah, source, other one is the destination.

[00:11:14]Okay? So, here the value of destination get copied into source. What is source?

[00:11:19]ID1. What is destination variable? That is temp3.

[00:11:24]Right? Very clear. Next.

[00:11:27]Once we Now, this is the fourth the of the fourth phase of compiler that is called as intermediate uh code generator. Now, let us uh realize uh the next phase. What is the next phase? Can you tell? The next phase of the compiler is code optimization.

[00:11:45]Okay? Code optimization.

[00:11:47]And uh I as I said before, code optimization is of two types.

[00:11:52]So, uh one one is a machine dependent code optimization, other one is machine independent code optimization. Machine independent code optimization normally takes place in this time.

[00:12:07]That is just before just before the code generation phase and immediately after the intermediate code generator.

[00:12:16]You can say, "Sir, the code optimization or the machine independent code optimization is takes place in immediately after the intermediate code generator."

[00:12:32]And machine dependent code optimization takes place just after the final phase.

[00:12:38]I mean, just after the code generation phase.

[00:12:42]Okay?

[00:12:43]So, now we are as we uh we are realizing the work of each and every phase briefly with an example. We are just trying to understand. So, we'll not uh discuss much things in uh code optimization because the specific topic unit uh maybe unit five, we'll discuss that. Okay?

[00:13:08]Now, just try to understand. We here easily you can understand, but we'll not have a chance to cover more with multiple examples. But, whatever examples is present, we can easily understand what is the uh role of the phase code optimization.

[00:13:24]Okay?

[00:13:25]Here, uh you read the few functions of code optimizer. It improves the execution speed of the program.

[00:13:34]It reduces memory uses.

[00:13:37]It removes the redundant code. I told you know yesterday. Let us take one example that within a single scope, you mistakenly Okay, so let us say that you are the beginner of the beginner to the programming language.

[00:13:51]Okay? Then you can do mistake. Without mistake, you can't learn the things. You I I must suggest you that you should do the mistake.

[00:13:59]So that you can learn from that mistake.

[00:14:02]Okay? You can learn because your system is there in front of you.

[00:14:06]It will tell it will help you.

[00:14:08]You try to do the same thing multiple times. Once error occur, don't leave the system and go away.

[00:14:15]You keep doing the things.

[00:14:17]Try to understand what error the system is saying.

[00:14:20]Whether it is a syntax error.

[00:14:22]Whether it is a an exception or some other kind of error.

[00:14:27]Where you forgot to close the bracket.

[00:14:29]Open bracket is there, but you forgot to close the bracket.

[00:14:33]Then the program is I mean is not complete.

[00:14:37]There you have So you have to learn and do mistake and do learn and learn from that mistake.

[00:14:44]Particularly in coding.

[00:14:48]Now code optimizer, code optimizer as we discussed, it improves the speed of the program execution.

[00:14:57]You reduces the memory uses as well as it will remove the redundant code. If you declare mistakenly uh one variable two times, that is called as a duplicate variable.

[00:15:10]Duplicate declaration. A redundant declaration.

[00:15:14]Everything is correct logically. I mean uh for lexical analyzer, there will be no problem.

[00:15:22]If the variable is declared for two or three times. For syntax analyzer, there it won't catch that error if the variable is declared for two or three times.

[00:15:31]Because syntax analyzer it will focus on the grammatical part of the programming construct or programming structure.

[00:15:44]So, it will not it will not tell you why you kept one statement two times or three times.

[00:15:51]So, that can be catch by this code optimizer.

[00:15:58]If one variable within the same scope is declared two times, that will be called as a redundant duplicacy. That duplicacy will be removed by this code optimizer.

[00:16:10]Okay?

[00:16:13]Okay. Now, now come come to this example. The same example. Now, what output you got? You got uh temp one equals to into real 60, temp two equals to ID3 into temp one, and temp three equals to ID2 plus temp one, and ID1 equals to temp three.

[00:16:32]Okay?

[00:16:33]This is the output of intermediate code generator. This output is now act as input to the code optimizer optimizer.

[00:16:42]And code optimizer, what is the role? It will minimize the code. It will minimize in the sense what? It will optimize the code.

[00:16:51]Instead of maintaining duplicacy and writing more code, I mean complex code, it will it will try to shorten the code so that the code can occupy less memory, redundancy can be eliminated, and the code can be improved such a way that it can it can run faster.

[00:17:14]Okay? Comparing to the previous version.

[00:17:18]That is the objective of your code optimizer.

[00:17:23]Right. You can see those four lines of code how it is minimized without changing without changing the meaning of the program.

[00:17:35]Without changing the meaning of the program, without losing the information, without losing the data, okay? The same four lines of code is now reduced to two lines.

[00:17:49]And the same format is also maintained.

[00:17:51]Three address code is also maintained.

[00:17:52]What is the purpose What is What is the three address code? In three address code, maximum three operands can be there.

[00:18:02]The same thing is present here. So, here temp1, first of all, it is converted into real 60 means the operator is there to convert 60 into 60.0. So, this what the code optimizer what it does, it it directly convert through that operator, it directly convert the integer value 60 to 60.0.

[00:18:24]Okay? Now, after that, temp1 everything was placed in temp1. Now, temp1 becomes 60.0.

[00:18:32]Temp1 becomes 60.0.

[00:18:35]Okay?

[00:18:37]Now, temp1 equals to ID3 into 60.0. One line statement is over. Next, temp3 temp3 equals to ID2 plus temp2.

[00:18:47]Okay? ID2 plus temp2. What is ID1?

[00:18:53]ID1 equals to ID2 plus temp1. Because in temp1 because in temp1 you kept ID3 into 60.0.

[00:19:03]Okay? So, no need to keep Now, the second statement, okay? What is temp2 actually? Now, temp2 be temp2 is nothing but temp one because in temp two you kept ID three temp temp one already eliminated because that value directly six converted 60 to 60.0. So that it becomes a real-time constant. So that is directly placing plus along with ID three. ID three into 60.0 total value is kept in newly in temp one.

[00:19:37]Next, ID one is equals to ID two. ID two is an identifier. ID two plus temp one.

[00:19:43]So the entire four lines of code, so you see both the lines are three address code.

[00:19:49]I mean three operands are there.

[00:19:52]In both the lines. So both now those four lines is converted into two lines.

[00:19:58]That is called as that is called as code this is the this is the one snap snapshot of code optimization. Only only small example we do to understand okay to understand what is code optimization.

[00:20:14]Okay?

[00:20:16]What is the role of code optimization?

[00:20:18]When we go into that topic now number of examples are there.

[00:20:22]This is not only the rule number of from different perspective from different angles number of examples are there and very interesting this subject this particular unit is very interesting.

[00:20:37]Okay, that we'll discuss no problem.

[00:20:40]Next, let us realize the role of code generator.

[00:20:44]Once the code is optimized that this optimized code act as an input to the code generation. Okay? Or you may say code generator generation or generation or you may say code generator no problem. Okay? So this code generator phase it it takes code optimized code remember optimized code as an input and it equal it equal perform register allocation along with the instruction set present in the system. So, it allocate it perform register allocation okay to for the yeah register allocation to perform real-time calculation.

[00:21:29]And store the value in the memory. So, it produces final machine code. How the machine code can come?

[00:21:36]The machine code it comes in terms of first of all it will convert into the entire code will be converted into assembly code. This assembly code is nothing but the one output of code generator.

[00:21:48]Or sometimes okay some yeah code generator okay where it perform register allocation.

[00:21:54]So, here actual registers instead of temporary actual registers are used to store the value for temporary purpose until the entire result placed in the memory.

[00:22:07]Okay? So, how it perform register allocation using the instruction? Okay?

[00:22:13]That is move move ID3 comma R2. Move F why F is given? That is fact because in this expression 60.0 is nothing but a real-time real-time number. Okay? I mean real number. Real number that is and I as I said that position um initial and rate all others are already taken as a floating point number.

[00:22:39]So, as every the entire expression is in the form of floating point numbers that means the result in the form of floating point number or real number. That is why instead of move move F is there. That instruction F move F F indicates floating point number.

[00:22:58]Or that value the which is I mean which this instruction is dealing with that values are in real number or floating point number.

[00:23:08]Okay? Ultimately, you can say as this instruction as this expression holds floating point numbers, okay? Here all the instruction will automatically add F automatically add F into the original instruction. F indicates that the numbers are floating point numbers.

[00:23:30]I mean, here you try to understand move F ID3 {comma} R2. That means what is there in ID3?

[00:23:40]ID3 first you store in R2, then multiply Okay, MUL F multiply F 60.0 {comma} R2.

[00:23:50]What is the expression temper temp one equals to ID3 into 60.0? I mean, ID3 is nothing but one identifier where which is getting multiplied with 60.0. So, first store that identifier in a register. Then multiply the value 60.0 in that ID with the ID3. The entire value you keep in somewhere. Where? You're keeping You're multiplying and storing the value in R2. So, try to understand. First in R2 store ID3.

[00:24:28]Then what is the what is the next part?

[00:24:30]60 is multiplied with ID3. Now ID3 is present in register two. Now multiply 60. The entire value will be in the register two only. That is the second line.

[00:24:41]Okay? Then third line, move F ID2 into R1.

[00:24:46]Okay? ID2 into R1.

[00:24:49]R1 means a new register. Okay? Put ID2 in R1, then add What you are adding? Add the value of R2 in R1. Okay? Whatever the What is the present in R1 and what you already found in R2, now add the value of R2 with R1 and hold the and store the result again in R1.

[00:25:16]Okay?

[00:25:18]Now, let us say I kept five in R1.

[00:25:21]Now, I am adding six in R1. Total will be 11. That 11 will be in the same place R1. R1 is nothing but the room or the register which is holding Just Just imagine it is a room where two variables Previously, one variable was there. Now, second variable is added. All the result is also present placed in the same room. Same Similarly.

[00:25:45]Okay? Now, R1 is holding the entire result. But, my question is can we hold the result permanently in R1?

[00:25:56]No. That is why we need a place called as memory to store that value.

[00:26:02]Because the registers are very limited in the system. Okay? Very limited. And uh these registers uh but So, that is why and uh one one one process or program execute, the registers are get vacant and they allocate to another program or another process. So, that is the policy. Okay?

[00:26:23]So, that that is why we need we need a memory to store the entire result which is present in R1.

[00:26:31]So, move F R1 {comma} ID1. What is ID1?

[00:26:34]Finally, you are storing the result where? In position, the variable position. What is the ultimate name of position? The ultimate name of position is identifier one. So, identifier one is nothing but the memory, I mean the place placeholder of the memory where you are putting the entire entire result in the sense initial plus rate into 60.0 or into 60. The total right hand right side in calculate and place in left hand side. What is that left hand side? Left hand side is position. This position the ultimate name of position is ID.

[00:27:11]Okay? Is that clear? So, this is the role of code generator.

[00:27:16]So, in this class what we learn since yesterday we started to realize the role of each and every phase of the compiler with the help of an example and today we completed.

[00:27:31]Okay? Initially we observe how lexical analyzer reads the source code, how how it identify the token for each and every lexeme or word, how it replace them in the symbol table, then how lexical syntax analyzer collects them and impose on grammatical structure to identify whether the sentence is grammatically correct or not, then how it pass how it produces the I mean what is the output of syntax analyzer? The output of syntax analyzer is semantic is a syntax tree. This syntax tree is again passes to as an input to the semantic analyzer. It performs certain checks and finally it produces finally it produces abstract syntax tree. This abstract syntax tree is passed as an input to the intermediate code generator. It converts the entire source code into intermediate representation. The specific type is three address code. This three address code is again passed passed as an input to the code optimizer code optimizer. It it eliminate the redundancy, duplicacy and it fasten the code, okay? It is speed up the code, okay? Uh by optimizing the code. Okay? It is the major focus of code optimizer is to uh allocate uh is to see how the memory uses will be less and how uh the speed of the program can be improved.

[00:29:05]And then how then now we have seen that the opti- under the uh finally, the code optimizer phase produces the optimized code and this optimized code is passes through the code generator and uh the code generator uh perform register allocation, okay? And uh it produces executable instruction, okay? In the form of assembly code. And finally, this assembly code uh when it passes through the assembler, binary code get generated. Zero and Okay?

[00:29:39]Now you see the uh the other phases, the role of symbol table and error handler. You see position symbol table, it is stores different types of things. Variable names, data types, where it is stored in the memory, I mean memory location, what is the scope, okay? Suppose in function one, one variable is declared, in function two, another variable declared. So their scopes are different.

[00:30:03]Okay? So all the information stored in the symbol table. You see, when the initially the lexical analyzer breaks the entire source code, position, initial, these all are what?

[00:30:14]Identifiers. Identifier one, identifier two, identifier three, like that it is stores. It also uh what is the data type of position, what is the data type of initial, what is the uh where is the memory location, uh what is their scope, every details it is stores in the symbol table.

[00:30:32]That is one data structure.

[00:30:33]Now error handler, uh here there are many types of error.

[00:30:38]Most of the errors are normally identified by lexical phase, uh I mean lexical analyzer, syntax analyzer, and semantic analyzer.

[00:30:47]In the rest of in the intermediate code generation, code code optimizer, and code generation phase, uh the errors are almost zero.

[00:30:57]Because these are the these are the three of the upper upper layer of the compiler. Okay? Upper layer of the compiler, these three uh phases, these three phases normally identify the error. Once the program passes through semantic uh analyzer, the error is almost uh rare, almost zero.

[00:31:18]Okay? Because that is very close the Once the semantic analyzer uh produces abstract syntax tree, and abstract syntax tree passes through the intermediate code generator, once intermediate code is created, intermediate code is very very close to the target code.

[00:31:37]So, that is why the error is almost zero there. Okay?

[00:31:41]Now, diagrammatically it is shown because the the error is almost zero, rare case. That is why this phase is diagrammatically associated with all the phases.

[00:31:51]But logically, if you see, the errors are identified only by the first upper three phases.

[00:32:00]Okay?

[00:32:01]So, this is the brief discussion about I mean, brief discussion we took about uh to learn or to realize the role of each and every phase of compiler. Now, uh from today uh from next class onwards, we will be discussing unit two. Okay? This is This is all about your unit one. Unit two starts from lexical analyzer. Unit three starts from syntax analyzer. Like that we'll discuss. Okay? In-depth study of each and every phase of the compiler.

[00:32:37]Okay? So, here you can see unit two lexical analyzer. You just note down the topic.

[00:32:45]Okay? Here we'll start uh in the next from the next class almost.

[00:32:51]Okay?

[00:32:53]So, I I hope everything is I made it very clear and I repeatedly said many things and I hope it is very clear to you. Okay? And uh in in in the consequence I mean yeah, rest of the classes we'll have more interaction. We'll be because the subject is very interesting.

[00:33:15]Okay? We'll we'll be knowing the subject in depth and we'll spend some time on this uh a very interesting subject. I can suggest you that you'll be once you concentrate you'll definitely you'll do very good in compiler design.

[00:33:32]Okay?

[00:33:33]And you will you can be a master in compiler design.

[00:33:36]Okay?

[00:33:38]So, Thank you. This is the in the next class we'll discuss from the second unit almost. Okay? Thank you all.

[00:33:47]Have a nice day.

[00:33:50]Thank you once again.