An Overview of a Compiler - Part 2 Y.N. Srikant DepartmentofComputerScience IndianInstituteofScience Bangalore560012 NPTEL Course on Compiler Design Y.N.Srikant CompilerOverview Outline of the Lecture 1 Compiler overview with block diagram 2 Lexical analysis with LEX 3 Parsing with YACC 4 Semantic analysis with attribute grammars 5 Intermediate code generation with syntax-directed translation 6 Code optimization examples Topics 1 to 4 have been covered in Part I of the lecture Y.N.Srikant CompilerOverview Compiler Overview Y.N.Srikant CompilerOverview Translation Overview - Lexical Analysis Y.N.Srikant CompilerOverview Translation Overview - Syntax Analysis Y.N.Srikant CompilerOverview Translation Overview - Semantic Analysis Y.N.Srikant CompilerOverview Translation Overview - Intermediate Code Generation Y.N.Srikant CompilerOverview Intermediate Code Generation While generating machine code directly from source code is possible, it entails two problems Withmlanguagesandntargetmachines,weneedtowrite m×ncompilers Thecodeoptimizerwhichisoneofthelargestand very-difficult-to-writecomponentsofanycompilercannotbe reused By converting source code to an intermediate code, a machine-independent code optimizer may be written Intermediate code must be easy to produce and easy to translate to machine code Asortofuniversalassemblylanguage Shouldnotcontainanymachine-specificparameters (registers,addresses,etc.) Usually produced during a traversal of the semantically validated syntax tree Y.N.Srikant CompilerOverview Different Types of Intermediate Code The type of intermediate code deployed is based on the application Quadruples, triples, indirect triples, abstract syntax trees are the classical forms used for machine-independent optimizations and machine code generation Static Single Assignment form (SSA) is a recent form and enables more effective optimizations Conditionalconstantpropagationandglobalvalue numberingaremoreeffectiveonSSA Program Dependence Graph (PDG) is useful in automatic parallelization, instruction scheduling, and software pipelining Y.N.Srikant CompilerOverview Translation to produce Quadruples for Expressions 1 S → id := E {idptr := search(id.name); if idptr (cid:54)= NULL then gen(idptr (cid:48) :=(cid:48) E.result else error} 2 E → E1+E2 {E.result := gentemp(); gen(E.result (cid:48) :=(cid:48) E .result (cid:48)+(cid:48)E .result)} 1 2 3 E → E1∗E2 {E.result := gentemp(); gen(E.result (cid:48) :=(cid:48) E .result (cid:48)∗(cid:48)E .result)} 1 2 4 E → −E1 {E.result := gentemp(); gen(E.result (cid:48) :=(cid:48) (cid:48)uminus(cid:48) E .result)} 1 5 E → ( E1 ) {E.result := E1.result} 6 E → id {idptr := search(id.name); if idptr (cid:54)= NULL then E.result := idptr else error} Names are stored in a symbol table; the routine search(id.name) gets a pointer to the name id.name gentemp() generates a temporary name, puts it in the symbol table, and returns a pointer to it Y.N.Srikant CompilerOverview