Skip to main content
Loading Explore guides…
Compiler Components · Acedra
Home
Explore
Computer Science
Compiler Components
Sign in to save
Chat
If YouTube asks you to sign in, open the video on YouTube.
Watch on YouTube
Reload player
Transcript
126 segments
Copy
Hide video
0:03
>> Today's lecture is going to be an overview of compilers. Last time the last lecture was Lecture Zero, so we did a very brief and very vague overview of compilers. Today we'll be trying to make it clearer. In the last lecture, Lecture Zero, I wanted to give just enough information about compilers so that the syllabus makes sense. You know, because I wanted to go through the syllabus, so I wanted you to understand, you know, what the terms in the syllabus mean.
0:43
In today's lecture we will be trying to gain a better understanding of the different components of a compiler. In fact, this is not something that we will finish today. It's going to take a few lectures. In this course, we will have an extended overview of compilers, which will take about two weeks of lectures to have, you know, an overview of compilers so that we understand the big picture, the main parts of the compiler, the main components, and what each component does.
1:25
So this is what we will be trying to do in today's lecture and in the next three lectures. We will be trying to understand the different parts of the compiler, what each part, what each component or phase does.
1:40
But we will not cover how it does that. So we will be trying to understand, you know, what the scanner does, but how does it do that? This is something that we will be studying
1:56
when we start covering the individual components of a compiler, the individual phases. So the scanning phase, there will be, you know, a couple of weeks on scanning and three weeks on parsing. So each one of these parts we will be spending weeks on trying to understand how it does what it does and how here, you know, in computer science, the answer to the how question is what. You know, generally speaking in computer science when we say how, how does the compiler do this,
2:35
how does the operating system do that, the answer is an algorithm. All right, so the answer to the question how in computer science is usually an algorithm. The algorithm that, you know, allows a certain system to do something. So let's redraw the picture that we drew last time of an optimizing compiler. So last time we said that there are three main parts or three main phases of an optimizing compiler.
3:20
So there is a front end, and the optimizer, and the backend,
3:34
which what does the backend do? >> It's the code generator. >> Yeah, exactly.
3:45
Okay. So these are the three main parts
3:50
of an optimizing compiler.
3:54
And of course this is the conceptual view. I mean, different compilers have different designs. So this doesn't necessarily mean that, you know, every compiler is divided into these three main pieces. And it doesn't mean that every compiler will have, for example, you know, three different executables. You know, some compilers do have, you know, three different executables, one executable for the front end, a separate executable for the optimizer, and a separate executable for the backend.
4:25
And they are all linked together. There's a driver that connects them together and that wraps the whole thing. But other compilers may have a different design. So this is just a conceptual view of compilers. So the front end will take, you know,
4:48
the high level representation, the source code, like X equals A plus B. And then what will the front end produce?
5:02
>> Abstract syntax tree. >> An intermediate format. And what's the specific intermediate format or intermediate representation that we mentioned last time? >> AST. Abstract syntax tree. >> Yep, the abstract syntax tree. So the abstract syntax tree--
5:28
-- or AST is one
5:34
of the intermediate representations that compilers use. It's one of them. It's not the only one. And in fact, you know, a single compiler may use multiple intermediate representations to represent the code and to do the code generation process. If you think about it, you know, the code generation process is going from a high level language to machine language and compilers don't do this in one step. So there are multiple steps and phases that are involved to get
6:10
from high level to assembly code, you know. For example, in this case, you know, the assembly code may look like load A into a register, load B into another register, add A and B and put the result in a third register, and then what? >> Add the registers. >> Hmm? >> It probably would add the registers, A and B. >> Oh yeah, you are right. Thank you. Adding R1 and R2 and then? >> Storing. Store. >> Storing R3. >> Into C. >> Into C. So we're not worried about the syntax at this point
6:56
of the assembly, but with the understanding that these As and Bs, these are variable names.
7:07
So this is what we call symbolic information. You know, variable names we refer to them as symbolic information because it's symbolic information.
7:24
And in real assembly language, in real assembly language for a specific processor, we don't have symbolic information. We don't have variable names. So instead of having variable names, we will have what? >> Addresses. >> Memory addresses, because, you know, for each variable the compiler will allocate some space and memory for that variable. So in general, in most cases, we're going to assume that these variable names are local variables and they're on the stack.
7:58
And each variable has an offset in this stack. So it could be, for example, that variable A is at offset zero, variable B is at offset 4, and variable C is at offset 8 assuming each one of them is 32 bits. In reality, this A is going to be an offset relative to a certain base and the base is the base address of the stack or the frame for that particular program, which is a frame or activation record. So it's a pointer to the activation record, the stack frame for that particular function,
8:42
for the current function that we are currently compiling.
8:48
Okay? So anyway, we will say more about this later. But for now, just I wanted to make sure that you understand that real assembly doesn't have variable names, doesn't have symbolic information. In fact, you know, once the compiler forms the abstract syntax tree, it no longer needs the symbolic information. The abstract syntax tree for this is going to be just A added with B and then assigning the result to X. So the operations that are involved here, the addition operation
9:37
and the assignment operation, this is our abstract syntax tree.
9:46
Now I said that, you know, in theory once the compiler constructs this abstract syntax tree, it no longer needs to keep the symbolic information, like the variable names. But in practice, there are reasons for keeping symbolic information throughout the entire compilation process. So can you think of a reason for keeping symbolic information? Yeah. >> Debuggers. >> Yeah, exactly, debugging. So for debugging purposes, the compiler will, you know, will keep symbolic information and, you know,
10:29
for each variable, which in fact becomes a node in this tree, it will keep the symbolic information, the corresponding variable names, so that it can implement the debugging functionality. But without that, we don't need it. Or in other words, if you just want to generate code, once you build a tree like this you don't need the symbolic information. Now this is the big picture. In fact, today we're going to focus on this front end. Again, understanding what the front end does,
11:11
but we will not learn how to do this, how the front end does this, until we get to the detailed treatment of the front end. So, getting from this to this is from this expression or assignment to this abstract syntax tree is going to take roughly 60% of the time of this course.
11:39
Okay, 60% of this course is going to be, you know, dedicated to understanding how we can get from this to this. It looks easy, right? You know, for this example it's very easy. But we want to do this for a general expression and we also want to do this code generation for the basic language constructs, including conditionals and loops. Okay? So now the first phase in this front end that converts this to this, that converts high level language to abstract syntax tree, is scanning or lexing.
12:25
You know, sometimes it's called lexing. So now what does scanning mean? It means the following.
12:39
So it's a low level analysis of the input program. By the way, you can view, you know, for compilation purposes, you can view the whole program as one big string. So no matter how big your program is, you can view it as just a single string. And the scanner will look at this program even if it's a million line program. It will look at it as a string that consists of these characters and it will divide it up into tokens or lexemes. So, for example, to be specific, if we have something
13:23
like X12 equals A3 plus B45. If you have something like this, what the scanner does,
13:46
it will identify the different tokens, the different words that this string consists of. And in this case, you know, the first token or word is going to be this, you know, this first variable name. So it's going to say, okay X12 is the first token or lexeme. Then the second one is what?
14:12
>> Equals. >> Equal. So it's the second token. Now how did it know that? How did it know to divide it up this way? How did it know that this point is the end of the first token and the start of the next token? >> Because it's an equal sign. >> Okay. >> The space. >> No. Even if we don't have space. You know, many languages do not require space here. Requiring space makes the compiler's job easier, but it makes the programmer's job harder. Yes? >> Looking for special symbols or characters
14:52
that mean certain things, for example the equal sign. It's reserved for assignment operators. >> Yeah. Okay. Yes. So this is reserved, but how did it know that this equal sign is not part of the variable name? Yes. >> Because only letters or numbers are valid variable names. So when it sees equals or a space, that-- >> Okay. >> -- the end of the variable name. >> Okay. Exactly. So it knew that this is the end of this based on a certain rule. Of course, you know, we will be studying these rules.
15:26
And these rules, as we will see, will be defined in the form of regular expression. So we will be defining these rules as regular expressions. So there is a regular expression that defines, you know, what a variable name may consist of. And in that tool that defines what a variable name consists of, in that tool, that tool does not allow an equal sign in the variable name. So letters and numbers are allowed in variable names, but the equal sign is not allowed.
16:03
So it knew that these three characters constitute one token, which is a variable name, but this does not belong to that variable name, so this must belong to a different token. And there is no other, you know, part of speech in the programming language that starts with an equal sign. So it identified this equal sign, the operator, as a token by itself. You know, there is no part of speech in a programming language, there is no rule that says, that has something which starts with an equal sign.
16:40
So it knew that this is the end of this token and this cannot be, you know, for example, you know, equal A3. Cannot be a token by itself.
16:52
This is not a valid token because there is no rule. So in order for the compiler to recognize this, it has to have certain rules that define, you know, what the parts of speech of this language are, what the words are.
17:08
Okay. So in this case it's going to say equal A3 plus B45 and semicolon.
17:19
So this is exactly, you know, what the scanner or lexer does.
17:27
Okay? How does it do that? We will be studying this later. We will define this using regular expressions and the implementation will require using finite state automata, the implementation of this.
17:42
Okay? So this is what the scan. Any questions on this? Okay. So the next part is the parser. So, parsing or syntactic analysis.
18:17
Parsing it basically builds words. It builds sentences out of words. So the scanner produces a bunch of words and the scanner takes these words and tries to build sentences out of these words. You know, in a regular human language we talk about the sentence.
18:47
The sentence. So, you know, the equivalent of this in a programming language is what? >> A statement. >> A statement. Yeah.
19:04
And the equivalent of the word is the, you know, token or lexeme. So this is human language.
19:18
This is programming language. So the tokens can be viewed as words and statements can be viewed as sentences.
19:32
So now this, you know, the scanner or the lexical analyzer divided this up into these tokens. So the first token is in a variable name or an identifier. This is an equal. This is another identifier or a variable name. Identifier is the name of a variable or a name of a function, plus another identifier, plus the semicolon, the end of statement. So the scanner said, okay we have an identifier equals an identifier plus another identifier. Is there a rule in the language that allows us
20:16
to build a sentence, a valid sentence? Well, in the languages that you are familiar with yes there is a rule where this identifier on the left is the identifier that we are assigning to. And whatever appears on the right is the expression. So this is an expression.
20:41
So we are computing an expression and we are assigning an expression to an identifier, the left hand side of this assignment statement. So in this case, you know, if there is a rule that says that you can have this, this would be a valid statement in the programming language, just, you know, a valid sentence in a human language. Right? Now these rules, how do you think these rules are defined in the construction of compilers?
21:14
Yeah. >> As a grammar. >> Grammars, exactly. So a grammar is a rule that we will be using to define, you know, the syntax of the different legal statements in a programming language. So there will be a rule that will tell us that you can assign an expression to an identifier. But if we have something like, you know, for example,
21:42
X equals A plus B times divide something like this, there will be no rule in the programming language, you know, in the grammars for this programming language. There will be no rule that will allow you to have an expression that consists of A plus B times multiply and nothing. So this an invalid statement syntactically. How do we define what is valid and what's invalid? By defining the right grammars. So this is one of the main concepts in this course.
22:28
This is going to be one of the main concepts, how to write the right grammars, to define the syntax of a programming language. So we will have a rule that will say this is good syntax. This is valid. This is a syntax error.
22:46
Because this doesn't match any of the rules, any of the rules in the grammar that defines this language.
22:57
Okay? Any questions on this? Okay. So basically scanners are built using regular expressions and finite automata and parsers are built using grammars.
23:13
So we will be studying different algorithms for doing parsing. Okay? Parsing is one of the central topics in this course and in compiler construction.
23:27
Okay. Any questions on this? Okay. Now the third part of the front end of the compiler is the semantic analyzer.
23:41
So number one, scanner, number two, parser, number three, semantic analysis.
23:52
Now, just like in human languages, a sentence may be grammatically correct, but meaningless.
24:01
You know, like saying the room drives the car. So when you say the room drives the car,
24:11
grammatically this is correct. This is correct syntax. But semantically this is meaningless. And in programming languages, it's the same. So, you know, if we remove this bad stuff here, this is a valid statement. This is a simple expression assigned to a variable. So this is a valid statement, but in fact, it will only be valid if these types, if the types of these variables are consistent. So if we have integer A, B, X, all of them are integers, then this is perfectly meaningful.
24:59
Right? But if instead of having them integers, you know, we have, you know, X is an object, you know, A is an object of class student and B is an object of class, you know, car, and X is an integer. So in this case, the types are not matching. They are not consistent and this is meaningless unless you have in your language, you are defining what it means to add a student to a car. And then what does it mean to assign this to an integer? So here the types do not match,
25:51
which means that this statement is syntactically correct, but semantically it's not meaningful, doesn't have any meaning, which means that the compiler will not know how to generate code for this. So the compiler can generate code only for meaningful statements. If the statement is meaningless, it will not be able to generate code for it. So this is what compilers do in the semantic analysis phase, which follows the parsing. So if your program passes scanning,
26:26
it means that all the tokens, all the parts of speech are correct. If it passes parsing, it means that it's syntactically correct, but we haven't yet checked if the semantics are good or not. Then only after it passes semantic analysis, it will be a valid program. An important part of semantic analysis is making sure that, you know, the types match. And as you can see, parsing or checking syntax, can be done locally. So we just look at this and match it up with one
27:02
of the rules in the grammar that defines the language. But in order to check semantics, we have to do a deeper and a more global kind of analysis. So we have to link, you know, this assignment statement with these declarations,
27:24
which may have appeared much earlier in the code. So we have to link something, you know, that got declared at some point. And between this declaration and this statement, we may have a whole bunch of code.
27:38
Right? So now the compiler needs to link to find for each variable that is used here the corresponding type.
27:50
And in order for compilers to do this,
27:54
when they process a declaration, they're going to create an entry for each variable in what we call the symbol table. So there is a symbol table.
28:10
So these declarations go into the symbol table. So that symbol table is going to have information about each declared variable, its type, its scope, all the different information that the compiler needs. And then when this variable is used, the compiler's going to look up that variable in the symbol table and see, you know, what type of variable that is. And based on those types, it will be able to decide whether this statement is semantically correct or not,
28:49
whether this statement is meaningful or not.
28:53
Okay? All right. So, you know, this is going to be, like I said, we'll spend more than half the time in this course, you know, doing this, studying algorithms for doing this, the front end.
29:13
Now we will move to the optimizer. Then the backend. So any questions on the front end? So the front end takes this and gives us this. And of course it will gives us an abstract syntax tree only if the program passes all three phases. If the scanning is correct, you know, if it passes scanning, if it passes parsing, if it passes semantic analysis. If it fails one of them, you will get an error message. The compiler is going to generate an error message.
29:47
Okay.
29:57
So now what does the compiler do in the optimization phase? Now here we are at the intermediate level. We have the code represented as an abstract syntax tree or some other intermediate representation. By the way, the abstract syntax tree is not the only intermediate representation. Sometimes some compilers may convert the abstract syntax tree into some linear intermediate representation. You know, compilers vary in the intermediate representations that they use.
30:32
Okay. Now in this optimization phase, the compiler will be applying some transformations to improve the quality of the code, but in theory the optimizations that are applied here or the transformations that are applied here, they should be machine independent. So they're independent of the target machine that we are generating code for. Okay. So everything that is machine specific, that is specific to the machine that we are trying to generate code for, should be ideally done here.
31:06
And I say ideally because sometimes some machine specific stuff ends up being here. But ideally this should be machine independent.
31:18
Okay, maybe I should note here
31:22
that many compilers generate code for multiple machines, you know, for multiple processors, multiple targets. So the extreme example is GCC. You know, the GCC compiler, it generates code for many, many different machines and many, many different processors. So it's one compiler that generates code for many different processors, which means that the backend is complicated. Or you can think of it, for a good design there will be multiple backends or this backend will be organized in a way
31:56
in which we have some common stuff that applies to all machines, to all processors and then some processor specific stuff. So you may look at, you know, the backend may be divided into abstract or general stuff that applies to all processors. And then this is specific to target number one. This is specific to target number two. This is specific to target number three. And so forth. So these targets are target processors, you know, for example, Intel X86 is a target,
32:32
ARM architecture is a target, GPU is a target, imbedded processors, many, many different kinds of processors.
32:44
Okay. So here in the optimizer, I will just give an example of an optimization that is done here, one of the common optimizations. And this common optimization is called common
33:00
subexpression elimination.
33:10
Common subexpression elimination.
33:13
And I will just illustrate this by example. So if we have something like X equals A plus B plus C and Y equals D divided by A plus B. So now given the name, common subexpression elimination, what transformation do you think a compiler may apply on these two statements to make them, you know, to make the code hopefully more efficient? >> A plus B is common between the two of them. >> Okay. So given the name, common subexpression elimination, A plus B is a common subexpression, right?
34:06
So a compiler may do this. So common subexpression elimination will just compute A plus B and put it in some temporary. And again, don't worry about the syntax here. This is conceptual. This is the conceptual presentation. T equals A plus B. X equals T plus C and Y equals what?
34:41
>> D over T? >> Hmm? It equals D divided by T. So this is a transformation that may make the code faster. This will not necessarily make the code faster. Generally speaking, you know, there is no compiler optimization. There is no transformation that the compiler applies
35:10
that is guaranteed 100% to make things faster because it may make things better from one aspect, but it may make something else worse. So in this case, for example, you know, this will not necessarily improve the code because, you know, sometimes it's, you know, recomputing the subexpression maybe faster than, you know, here, for example, loading this from memory. So this will improve performance assuming that this T, this temporary that holds A plus B, that T will in a register, not in memory.
35:56
If this T is going to be in memory and we are going to load it here and load it here, loading it from memory, loading from memory if it's not in the cache, is orders of magnitude slower than recomputing A plus B. A plus B is just, you know, an add operation that can be computed in a single cycle. But if we have to load this T, you know, from memory, well it's unlikely here because it's going to be in the cache, right, assuming that this will immediately follow this.
36:28
So this T is going to be in the cache. But if we have a bunch of code in between,
36:36
then this T may not be in the cache and we may have to bring it from main memory. Definitely if this is in main memory, you know, this transformation will make things worse. But even if this is in the cache, bringing this from the cache may take more time than recomputing A plus B. And even if it's in the storage location that is faster than the cache, which is what? What's the storage location that is faster than the cache? >> The register. >> The register.
37:09
Even if it's in the register-- so if it's in the register here, this will work well, but this will require this T to be reserving a register for a long time. And with this variable reserving a register for a long time, other variables may not have the chance to be stored in a register. So when this variable takes this register for this many instruction-- because we may have some instructions in between here, right? So keeping T in a register for this long time,
37:46
this is reserving a precious resource, which is the register, which means that some other variables may not get to be in a register, so they will be in memory and there will be a slowness when using those other variables. So we victimized other variables. So just, you know, the point here is that any optimization, any transformation, I hate to say optimization because it's not guaranteed to make things even better, you know, not to mention optimally.
38:18
It's not even guaranteed to make things better. It could make things worse.
38:23
But compilers do optimizations in the hope that they will make things better.
38:29
You know, in a good optimizing compiler, compiler optimizations make things better most of the time.
38:39
Okay? So this is only one example of those transformations that are implemented in the optimizer, in the optimization phase. This is just one example, just to give you an idea. And the point here is that this kind of transformation, even though it appears to be machine independent, so in principle it's machine independent, but if you think about it deeply, it will not be 100% machine independent. Because when you start talking about memory, caching,
39:19
registers, whether this will be good or bad will depend on how much cache we have, how many registers do we have, and parameters like this. That's why in a real compiler, in this middle optimizer, even though it's supposed to be machine independent, you will often find some machine dependent parameters. You know, for example, common subexpression elimination is an optimization that requires variables to stay in registers for a long time and this will be beneficial if you have enough registers.
39:58
Okay? So on a machine that doesn't have very many registers, this may not be a good optimization.
40:06
Okay? Now, the backend is the part that is truly machine dependent. It's the part in which we do instruction selection
40:22
and instruction scheduling and register allocation. So today I will just, you know, in the remaining ten minutes I will give a brief overview of these, but in fact these are, you know, we'll spend two or three more lectures on these trying to understand, well at least three more lectures, trying to understand, you know, what these compiler optimizations do.
40:56
So instruction selection is selecting instructions.
41:04
So to go from, you know, an abstract syntax tree
41:12
to assembly, maybe let's write an expression that is more interesting. So let's write a more interesting example like X equals A times B plus C times D. And in this case, the abstract syntax tree is going to be this, A multiplied with B right? And C multiplied with D and then what?
41:54
>> Add. >> Add these.
41:57
So the abstract syntax tree is very logical, you know, a logical, hierarchical representation of this expression computation and assignment.
42:07
And then we are assigning this to X. Okay. Now the assembly for this is going to be loading,
42:25
well what kind of assembly? That's going to depend on the machine.
42:29
So it's common to first generate some abstract assembly, some generic assembly like, you know, the assembly for some risk machine because risk machines do not have very many instructions. So you are generating basic assembly. That is the instructions you are using are likely to be almost on all processors. All processors will have a load and an add. So using the basic operations, loading A into register R1, loading B into register R2, then multiplying what? >> R1.
43:19
>> R1 and R2 and putting the result in? >> R3. >> R3 and then loading C into register R4 and loading D into register R5. Then multiplying what? >> R4 and R5. >> R4 and R5. >> And putting it in R6. >> And putting that in R6. Then? >> Adding R3 and R6. >> Exactly. Adding R3 and R6. >> Putting it into R7. >> In R7. >> And then storing R7 into X. >> Storing R7 into X. The first observation here is that we are assuming that we have as many registers as we want.
44:10
So this is obviously a nonrealistic assumption. So we are just, you know, taking the liberty to use as many registers as we want and compilers do this at some point before they get to register allocation. So before they get to register allocation, before it gets to register allocation, the compiler assumes that it has an infinite number of registers, which is obviously not true. There is no machine that has an infinite number of registers. The job of the register allocator is
44:42
to take these registers here, these virtual registers.
44:47
So these are virtual registers. They are not real yet. They are not real registers yet. So the job of the register allocator is to take these virtual registers and map them into real registers or physical registers.
45:08
Okay? And of course we'll say more about register allocation in the next lecture. So register allocation is something that we need to understand. We need to understand the problem of register allocation.
45:20
So this is one observation.
45:23
So this is something that is done in the backend, mapping virtual registers into physical registers. Questions?
45:33
Okay. So another observation is that, you know, here we are generating this code sequence multiplying, you know, loading A into a register, loading B into a register, then multiplying the registers. But on some machines, there are complex instructions that may operate on memory operators. In fact, if you have a memory operation and a multiply operation that, you know, multiplies A and B, which are memory locations, memory addresses, and putting that in could be in memory
46:17
and it could be in a register. So on [inaudible] machines, you may have other options. You can replace this sequence of three instructions, load, load, and multiply, with one instruction that operates directly on memory operands. And maybe put this in R1. In fact, the machine may have an arithmetic operation that takes two memory operands and puts the result in a memory operand. And that's a [inaudible] instruction, a complex instruction, that in the machine itself consists
46:54
of multiple risk simple instructions. Okay. So what's the point here? The point here is that which instruction will get selected and what's the most efficient sequence of instruction is the job of which phase do you think? Which phase does this? >> Instruction selection. >> Instruction selection. Yeah. So this instruction selection does just that. It selects the best sequence of instructions for this, you know, intermediate representation.
47:33
So you can think of the abstract syntax tree as a high level intermediate representation.
47:40
This abstract assembly as a lower level intermediate representation, which is not quite machine code yet, but when it goes through instruction selection, instruction selection will select real instructions, actual instructions. So as you can see, we are making things more real. You know, we start with virtual and abstract things and little by little, gradually we make them more real to end up with real code that will run on a real machine.
48:12
Okay? So this is instruction selection. Questions on the concept of instruction selection? Okay. So we know what instruction selection is. We know what register allocation is. It remains to say something about instruction scheduling. And instruction scheduling is given this sequence of instructions, this is not necessarily the best ordering for executing these instructions.
48:45
Why? Because here, for example.
48:51
So let's go back to this.
49:02
Load instructions in particular have latencies. So a load instruction may take a few cycles to execute.
49:09
So when you get to this multiply, you will have to wait for the load, for the result of this load, to become available. And this can waste two or three or four cycles, depending on the machine. But what if we instead of wasting these cycles, what if we put this load here to use this time to hide the latency of this load and execute another load for this multiply. So to hide latencies we can reorder instructions to hide latencies and get better performance. We will say more about this next time.
49:54
Okay? So next time we'll say more about instruction scheduling.
Here to help you learn
Sign in to keep a private conversation with your course tutor.
Ask me anything about the material…
Sign in to chat