CSE4100 Compiler (a.k.a. Programming Language Translation)OverviewInformationObjectivesPurposeTranslate… Why?Translate… How ?InterpreterCompilerMixedSlide 11Slide 12Course structureEvaluationSix HomeworksThe Source LanguageC--C-- ExampleThe Target LanguageBut......Really ?Slide 22Compiler ClassesCompiler StructureSome Good news!Phases of compilationRelocatableAnalysisLexical analysisSyntax Analysis (parsing)What is a grammar ?Summary so far…Semantic AnalysisSlide 34Summary so far...Slide 36Intermediate CodeIR Code exampleCode OptimizationMachine Code GenerationMachine code generationAssemblersLinker & LoaderPre-processorsModern CompilersModern Compiler ExampleAheadCSE4100Compiler(a.k.a. Programming Language Translation)CSE4100Compiler(a.k.a. Programming Language Translation)Notes credit go toMe CSELaurent Michel CSEAggelos Kiayias CSESteven DemurjianCSERobert La Barre UTRC2CSE244 CompilersOverview•Objectives•Structure of the course•Evaluation•Compiler Introduction–A compiler bird’s eye view•Lexical analysis•Parsing (Syntax analysis)•Semantic analysis•Code generation•Optimization3CSE244 CompilersInformation•Course web page–Will be on HuskyCT–Currently•http://www.engr.uconn.edu/~weiwei/•Instructor–Wei Wei–[email protected]•Office hour–TuTh 3:30pm ~ 4:30pm–Wednesday 1:30pm ~ 4:30pm4CSE244 CompilersObjectives•Compilers are….–Ubiquitous in Computer Science–Central to symbolic processing–Relates to•Theory of computing•Practice of computing•Programming languages•Operating Systems•Computer Architecture5CSE244 CompilersPurpose•Simple intent–Translate•From Source Language•To Target Language6CSE244 CompilersTranslate… Why?•Languages offer–Abstractions–At different levels•From low–Good for machines….•To high–Good for humans….Let the computerDo the heavy lifting.7CSE244 CompilersTranslate… How ?•Three approaches–Interpreted–Compiled–Mixed8CSE244 CompilersInterpreter•Motivation…–Easiest to implement!•Upside ?•Downside ?•Phases–Lexical analysis–Parsing–Semantic checking–Interpretation9CSE244 CompilersCompiler•Motivation–It is natural!•Upside?•Downside?•Phases–[Interpreter]–Code Generation–Code Optimization–Link & load10CSE244 CompilersMixed•Motivation–The best of two breeds…•Upside ?•Downside?11CSE244 CompilersObjectives•Learn about compilers because…–It helps to better program–Understand the tools of the trade–Many languages are compiled•Programming Languages [C,C#,ML,LISP,…]•Communication Languages [XML,HTML,…]•Presentation Languages [CSS,SGML,…]•Hardware Languages [VHDL,…]•Formatting Languages [Postscript,troff,LaTeX,…]•Query Languages [SQL & friends]–Many assistive tools use compiler technology…•Syntax highlighting•Type assist - type completion–You may write/use compiler technology!12CSE244 CompilersOverview•Objectives•Structure of the course•Evaluation•Compiler Introduction–A compiler bird’s eye view•Lexical analysis•Parsing•Semantic analysis•Code generation•Optimization13CSE244 CompilersCourse structure•A reflection of the topic–Lexical analysis–Parsing–Semantic analysis–Midterm–Runtime structures–Intermediate code generation–Machine code generation–Optimization–Final14CSE244 CompilersEvaluation•Course evaluation–Six homeworks (50%)•5 mandatory•1 extra credit–One midterm (20%)–One final (30%)•Exams–Open book15CSE244 CompilersSix Homeworks•One project to rule them all...•Purpose–First Hand Experience with compiler technology•Six Homeworks are connected–Scanning–Parsing–Analysis–IR Code Generation–IR Optimization–Machine Code GenerationAnd in the Darkness Bind You...16CSE244 CompilersC++C++The Source LanguageCCJavaJavaC--C--17CSE244 CompilersC--•The Object Oriented Language For Dummies–C-- supports•Classes•Inheritance•Polymorphism•2 basic types•Arrays•Simple control primitives–if-then-else–while18CSE244 CompilersC-- Exampleclass Foo {int fact(int n) {return 0;}int fib(int x) { return 1;}};class Main extends Foo {Main() {int x;x = fact(5);}int fact(int n) {if (n==0)return 1;else return n * fact(n-1);}};class Foo {int fact(int n) {return 0;}int fib(int x) { return 1;}};class Main extends Foo {Main() {int x;x = fact(5);}int fact(int n) {if (n==0)return 1;else return n * fact(n-1);}};19CSE244 CompilersThe Target Language•Something realistic...•Something challenging...•Something useful...It’s True!We will generate code for a Pentium ClassMachine Running EithterWindows or Linux20CSE244 CompilersBut...... •Won’t that be hard?•No!–My C-- compiler•6000 lines of code•Written in < 10 days–Your C-- compiler•Will use some of my code...21CSE244 CompilersReally ?global mainextern printfextern mallocsection .dataD_0: dd block_0,block_1D_1: dd block_3,block_1,block_2section .textmain:push 4 ; push constantcall malloc ; call to C functionadd esp,4 ; pop argumentmov [eax], dword D_1 ; move source into destpush eax ; push variablemov eax, dword [eax] ; get the VTBLmov eax, dword [eax+8] ; get the k=2 methodcall eax ; call the methodadd esp,4 ; pop argsretblock_0:mov [esp-4], dword ebp ; save old BPmov ebp, dword esp ; set BP to SPmov [ebp-8], dword esp ; save old SPsub esp,8 ; reserve space mov eax, dword 0 ; write result in output registermov esp, dword [ebp-8] ; restore old SPmov ebp, dword [ebp-4] ; restore old BPret ; return from functionblock_1:mov [esp-4], dword ebp ; save old BPmov ebp, dword esp ; set BP to SPmov [ebp-8], dword esp ; save old SPsub esp,8 ; reserve space formov eax, dword 1 ; write result in output registermov esp, dword [ebp-8] ; restore old SPmov ebp, dword [ebp-4] ; restore old BPret ; return from functionblock_3:mov [esp-4], dword ebp ; save old BPmov ebp, dword esp ; set BP to SPmov [ebp-8], dword esp ; save old SPsub esp,20 ; reserve spacemov eax, dword [ebp+8] ; move o2 cmp eax,0 ; do the operationmov eax,0sete ahcmp eax,0 ; compare to 0 to set CCjz block_5 ; transfer to true block block_4:mov eax, dword 1 ; write result in output registerjmp block_6 ; transfer controlblock_5:mov eax, dword [ebp+8] ; move o2sub eax,1 ; do the operationpush eax ; push variablemov ebx, dword [ebp+4] ; get argument in registerpush ebx ; push variablemov ebx, dword [ebx] ; get the VTBLmov ebx, dword [ebx] ; get the k=0 methodcall ebx ; call the methodadd