CSc 520Principles of Programming Languages2: TranslatorsChristian CollbergDepartment of Computer ScienceUniversity of [email protected] 2005 Christian CollbergApril 22, 20051 What’s a Compiler???• At the very basic level a compiler translates a computer program from source code to some kind ofexecutable code:VMasmsourceCompilerx.classx.sx.javax.cerrors• 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 a virtual machine code: javac x.java produces x.class.2 What’s a Language Translator???• A compiler is really a special case of a language 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.13 Example Language Translatorssource language translator target languageLATEXlatex2html−→ htmlPostscriptps2ascii−→ textFORTRANf2c−→ CC++cfront−→ CCgcc−→ assembly.classSourceAgain−→ Javax86 binaryfx32−→ Alpha binary4 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.5 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 a load-and-go-compiler.Abstract Machine Code Serves as input to an interpreter. Fast turnaround time.C-code Good for portability.6 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. Tryman 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 .27 Compiler PhasesSemantic AnalysisSyntactic AnalysisLexical AnalysisIntermediate CodeGenerationCode OptimizationMachine CodeGenerationA N A L Y S I S S Y N T H E S I S8 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".• Lexical errors (such as ’illegal character’, ’undelimited character string’, ’comment without end’) arereported.9 Lexical analysis — ExampleLexical 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, SEMICOLON310 Compiler Phases – Syntactic analysis• Syntax analysis (parsing) determines the structure of a sentence.• The compiler reads the tokens produced during lexical analysis and builds an abstract syntax tree(AST), which reflects the hierarchical structure of the input program.• Syntactic errors are reported to the user:– ’missing ;’,– ’BEGIN without END’11 Syntactic analysis — ExampleSyntactic Analysis of English• The sentenceThe boy plays cowbell.would be parsed into the treeNPSVPDet N VNNPTheboy plays cowbell• S=sentence, NP=noun phrase, VP=verb phrase, Det=determiner, N=noun, V=verb.12 Syntactic analysis — ExampleSyntactic Analysis of Java• The sentencex = 3.14 * (9.0+y);would be parsed into the ASTAssignMULFLOAT3.14ADDFLOAT IDy9.0IDx413 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’.14 Semantic analysis — ExampleSemantic 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– which luftballons the print-statement refers to,– that float luftballons=10 has the wrong type.15 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.16 IR Generation — ExampleIR Generation of English• From the sentenceEvery boy has a cowbell.we could generate∀x; boy(x) ⇒ has-cowbell(x)5IR 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, assign17 Compiler Phases – Code Optimization• The (often optional) code optimization phase transforms an IR program into an equivalent but moreefficient program.• Typical transformations includecommon subexpression elimination only compute an expression once, even if it occurs more thanonce in the source),inline expansion insert a procedure’s code at the call site to reduce call overhead,algebraic transformations A := A + A is faster than A := A ∗ 2.18 Compiler Phases – Code Generation• The last compilation phase transforms the intermediate code into machine code, usually assembly codeor link modules.• Alternatively, the compiler generates Virtual Machine Code (VM), i.e. code for a software definedarchitecture. Java compilers, for example, generate class files containing bytecodes for the Java VM.19 Multi-pass Compilation• The next slide shows the outline of a typical compiler. In a
View Full Document
Unlocking...