In this episode we looked at the three main phases each compiler implements - lexical analysis, syntax analysis, and code generation. For further reading you can follow the links:
Transcript
welcome to the programming podcast. Here you can learn about computers in the brief and accessible way I'm your host. I mean could get hello. Everyone in and this is the first episode of the PODCAST. Old wants to talk about compilers. I picked specifically topic for first episodes. Not only because I think in that understanding how compilers work is essential for us as software engineers but also because I have so special history with them. In my computer percents -education I had two moments in which perceivable impossible tasks became possible. The first one of course was implementing my first pro. I was thirteen or fourteen year old. I entered my first class an informatics. That's how we Has In eastern Europe and I had to implement a program which sums to numbers provided by the user. Of course. This doesn't seem like a industry greats problem to solve but for me it was fascinating because I didn't believe that more tools like me are able to implement programs and sent instructions to the computer. The second point I had was in college. I had data structures class where we had amazing very sharp. Teaching assistant isn't in one of the exercises for trees. He said that's to help us understand the data structure better. We are going to implement an interpreter. Now here I'm seeing an interpreter. Not a compiler but compilers and interpreters they share a lot of counties so if you understand how an interpreter mature works. You'll be able to probably understand how a compiler works as well so the next exercise we were supposed to implement our first interpreter her. I couldn't wait. I really wanted to see how I can do that. I thought its compilers. They're viewed by only some special people in companies. Police like Google and IBM and nobody else will be capable of implementing Quan well. I went about thirty four minutes before my class I started waiting for a teaching assistant for my devastation. He'd either short. I was really frustrated and really disappointed. And and for my even further shock. He'll show up again in any of the classes until the end of the semester. Of course I he had his own personal reasons for that so I don't blame him but that was really disappointing for me. I started looking at different websites which had tutorials and lessons lessons of how to implement our own compiler finally after weeks of reading. I implemented my own interpreter in Johor. Its name was not long because it was on education language a language of the US to educate myself you can still find Jahnke gap at gathered dot com slash. Em Get jeff flush along now. Let us see how compilers can make us better. Software engineer first and foremost by understanding how our programs are being transformed and executed. We are going to become better. Software engineers will be able to write more efficient and better software second of although sometimes we have to implement tasks which share a lot of logic with some of the faces of compilers. There are a lot of examples for that. For instance a couple of years ago I was working on a startup brownie points which we ended suspending since Egypt. Find Market in Brownie points. I had to translate a bunch of mathematical formulas to html it was supposed to be a simplified filed version of tax so I didn't want to reuse their entire ecosystem. It was supposed to be something much lightweight. Of course. When I sold this problem I decided to use regular expressions and at this moment I already had two problems regular expressions? They don't work. Obviously so I went to implementing my own compiler our compiling these mathematical formulas to html. I spent a couple of hours till I find a Grammar Orleans. Talk about drummers just a little bit after I use an abstract syntax tree for going to discuss this in a bit as well and finally translated this abstract syntax tree to html html everything worked perfectly another very common example is when you have to enforce common style and Coding Practices Within Your Organization. I had to do that multiple times. We usually achieve this by using cold for matters or winters. Well call for mattress in linter.
They share a lot of comb faces with compilers. So if you have to implement a winter you have to familiar with the process of lexical analysis and on Syntax analysis. That we're going to briefing bit now. I hope I convinced you. That Andrew standing the basics of compilers is important for you now. We're not going to dig in too many details. But I'm going to give you some good overview of what compilers are water different types of compilers. And how they work Internet in general e compiler is a computer program which accepts a program and it compiles it to a lower level language. There are many examples of compilers. We have the compiler which compiles Charles Horace Gould to buy gold. We have the bubble compiler compiles higher level programming language so just ESPN hundred fifteen to a lower level language which is five and many other for examples but sometimes we may want to compile a lower level language to a higher level. One good example is compiling Java byte code to Jaua gala there are many such examples in the jobless ecosystem as well where we're trying to compile a lower level language for example. The older version of eggnog script tipped is five to a higher level language. Use Two hundred fifteen. These compilers are called D. compilers and under very coleman one example are the so-called transpires or source to source compilers. In this case we're translating a higher level language to another high level language for example we're confiding python calls to javascript or coffee script javascript. Now we discussed discuss this a compiler what is a source to source compiler or a transfer piler and what is a decompile our now. Let us talk about individual faces which are shared between all of these different types of compilers. We discussed that. The compiler accepts some kind of input input and this input is just east drink as software engineers were just a bunch of type writers we're producing strings coastal ty- he and that's all we do. We might be able to pursue them in a very abstract an interesting way but in the end we were just writing symbols and our compiler understand what the symbols mean so whilst we pass these strings or programs as inputs the first thing that the compiler is going to do is to turn them into a bunch. Bunch of Tolkien's. This is the so-called face of lexical analysis. Where we're going to chop our program into different substrates? Each substrate is he's going to have some metadata associated with it such as its position in original program. All right this is the first phase of the compiler which is often referred where to asked Tolkien as the next stage. We're going to take this list of Tolkien's and again to pass them to the module of Syntax analysis is the Mojo six assists consumes tokens and also relies on a provided grammar. This grammar specifies. What programs programs are considered valid in our programming language? So based on the Tolkien's and the grammar the module for Syntax analysis is going to build a three. This tree is called an abstract syntax tree or eight. St Usually winters and for matters the operate they directly on this abstract syntax tree. They just traverse this abstracts indexed. Three in they find some potters in it. That are notable wink. The style August in our organization right this was the so called front end of the compiler. I we're reading our program right after that we're passing yet to the module for lexical analysis which is producing a bunch of Tolkien's and finally were passing gets to the module for Syntax analysis assist which is building an abstract extre- based on a grammar and the talking's that it received whilst we have the abstract syntax tree we're going to pass passes to the next phase of the compile which is usually related to optimization in the optimization fade the compiler is going to translate this abstracts index three to a different equivalent extre- how would it do that. We'll there are many techniques for this for example a very frequent technique that compiler issues rules is the so-called partial evaluation for example. Our Compilers GonNa try to partially evaluate some of the contracts in our program to speed up the runtime time face while does that be. Let's see that's in our program. We have one plus what we have two different options here since one plus one. It's obviously going to be too.
We can either replace samples one two as part of the butte process or we can delay this and let the final user execute while Soi which is going to be redundant right they are never going to get a different result other than to so it might be more efficient to just replace samples twenty two and perform this process of partial arshile evaluation this source code optimization is part of the so called middle and now we have a front content which is responsible for reading Howard program and turning it into a tree we have a middle end just responsible for optimizing this program and finally of course we have eh back end on the back of the compiler rigging to perform a bunch of source code generation this just reversal of the tree and generation of serse colts which could be bite called some machines tractions or translation of the ast to a higher level language and that is how compilers work we made a very high level overview of the executions faces in compilers since we only scratched the surface. If you're interested in knowing more you could take a look at the list of references associated with this episode. Thank you see you next time. Learn learned about the episode's he can pull them to at Ham. Get you the list of horses and recordings is available at podcast dot M. dot com. Thanks for listening.