CSc 453 — Compilers and Systems Software1 : Compiler OverviewChristian CollbergDepartment of Computer ScienceUniversity of [email protected]° 2009 Christian CollbergAugust 23, 20091What does a compiler do?2 What’s a Compiler???• At the very basic level a compiler translates a computer program from source code to some kind ofexecutable code:errorsVMasmsourceCompilerx.classx.sx.javax.c• Often the source code is simply a text file and the executable code is a resulting assembly languageprogram: gcc -S x.c reads the C source file x.c and generates an assembly code file x.s. Or theoutput can be avirtual machine code: javac x.java produces x.class.3 What’s a Language Translator???• A compiler is really a special case of alanguage translator.• A translator is a program that transforms a “program” P1written in a language L1into a program P2written in another language L2.• Typically, we desire P1and P2to be semantically equivalent, i.e. they should behave identically.14 Example Language Translatorssource language translator target languageLATEXlatex2html−→ htmlPostscriptps2ascii−→ textFORTRANf2c−→ CC++cfront−→ CCgcc−→ assembly.classSourceAgain−→ Javax86 binaryfx32−→ Alpha binary5 What’s a Language???• A formal language is a notation for precisely communicating ideas.• Byformal we mean that we know exactly which “sentences” belong to the language and that everysentence has a well-defined meaning.• A language is defined by specifying itssyntax and semantics.• The syntax describes how words can be formed into sentences. The semantics describes what thosesentences mean.6 Example Languages• English is anatural, not a formal language. The sentenceMany missiles have many warheads.has multiple possible meanings.• Programming languages: FORTRAN, LISP, Java, C++,. . .• Text processing languages: LATEX, troff,. . .\begin{frame}{Example Languages}\begin{itemize}\item English is a \redtxt{natural}, not a formallanguage. The sentence\end{itemize}\end{frame}• Specification languages: VDM, Z, OBJ,. . .7 Compiler InputText File Common on Unix.Syntax Tree A structure editor uses its knowledge of the source language syntax to help the user edit &run the program. It can send a syntax tree to the compiler, relieving it of lexing & parsing.28 Compiler OutputAssembly Code Unix compilers do this. Slow, but easy for the compiler.Object Code .o-files on Unix. Faster, since we don’t have to call the assembler.Executable Code Called aload-and-go-compiler.Abstract Machine Code Serves as input to aninterpreter. Fast turnaround time.C-code Good for portability.9 Compiler TasksStatic Semantic Analysis Is the program (statically) correct? If not, produce error messages to the user.Code Generation The compiler must produce code that can be executed.Symbolic Debug Information The compiler should produce a description of the source program neededby symbolic debuggers. Try man gdb.Cross References The compiler may produce cross-referencing information. Where are identifiers de-clared & referenced?Profiler Information Where does my program spend most of its execution time? Try man gprof.10The structure of a compiler11 Compiler PhasesS Y N T H E S I SSemantic AnalysisSyntactic AnalysisLexical AnalysisIntermediate CodeGenerationCode OptimizationMachine CodeGenerationA N A L Y S I S12 Compiler Phases – Lexical analysis• The lexer reads the source file and divides the text into lexical units (tokens), such as:Reserved words BEGIN, IF,. . .identifiers x, StringTokenizer,. . .special characters +, ∗, −, ^,. . .numbers 30, 3.14,. . .comments (* text *),strings "text".3• Lexical errors (such as ’illegal character’, ’undelimited character string’, ’comment without end’) arereported.13Lexical Analysis of English• The sentenceThe boy’s cowbell won’t play.would be translated to the list of tokensthe, boy+possessive, cowbell, will, not, playLexical Analysis of Java• The sentencex = 3.14 * (9.0+y);would be translated to the list of tokens<ID,x>, EQ, <FLOAT,3.14>, STAR, LPAREN,<FLOAT,9.0>, PLUS, <ID,y>, RPAREN, SEMICOLON14 Compiler Phases – Syntactic analysis• Syntax analysis (parsing) determines the structure of a sentence.• The compiler reads the tokens produced during lexical analysis and builds anabstract syntax tree(AST), which reflects the hierarchical structure of the input program.• Syntactic errors are reported to the user:– ’missing ;’,– ’BEGIN without END’15Syntactic Analysis of English• The sentenceThe boy plays cowbell.would be parsed into the treecowbellNPSVPDet N VNNPTheboy plays• S=sentence, NP=noun phrase, VP=verb phrase, Det=determiner, N=noun, V=verb.416Syntactic Analysis of Java• The sentencex = 3.14 * (9.0+y);would be parsed into the ASTxAssignMULFLOAT3.14ADDFLOAT IDy9.0ID17 Compiler Phases – Semantic analysis• The AST produced during syntactic analysis is decorated with attributes, which are then evaluated.The attributes can represent any kind of information such as expression types.• The compiler also collects information useful for future phases.• Semantic errors are reported:– ’identifier not declared’,– ’integer type expected’.18Semantic Analysis of English• In the sentenceThe boy plays his cowbell.we determine that his refers to the boy.Semantic Analysis of Java• In the sentencestatic float luftballons = 10;void P() {int luftballons = 99;System.out.println(luftballons);}the compiler must determine– whichluftballons the print-statement refers to,– thatfloat luftballons=10 has the wrong type.519 Compiler Phases – IR Generation• From the decorated AST this phase generates intermediate code (IR).• The IR adds an extra a level of abstraction between the high level AST and the very low level assemblycode we want to generate. This simplifies code generation.• A carefully designed IR allows us to build compilers for a number of languages and machines, by mixingand matching front-ends and back-ends.20IR Generation of English• From the sentenceEvery boy has a cowbell.we could generate∀x; boy(x) ⇒ has-cowbell(x)IR Generation of Java• From the sentencex = 3.14 * (9.0+y);the compiler could generate the (stack-based) IR codepusha x, pushf 3.14, pushf 9.0,push y, add, mul, assign21 Compiler Phases – Code Optimization• The (often optional) code optimization phase transforms an IR program into an equivalent but moreefficient program.•