How are Languages Implemented Two major strategies Interpreters LISP bash java Introduction to Compilers Compilers gcc javac Interpreters run programs as is Little preprocessing Carry out the meaning of a program Compilers do extensive preprocessing Transform a program in a higher level language into an efficient program in a lowerlevel language preserving the meaning Adapted from Lectures by Profs Alex Aiken and George Necula University of California at Berkeley Lectures by Prof Saman Amarasinghe Massachusetts Institute of Technology CS780 Prasad L1Intro 1 CS780 Prasad L1Intro 2 Anatomy of a Compiler Standard Text Books Program character stream Lexical Analyzer Scanner Dragon Book Alfred Aho Ravi Sethi and Jeffrey Ullman Tiger Book Andrew Appel Whale Book Steve Muchnick Token Stream Syntax Analyzer Parser Symbol Table Parse Tree Intermediate Code Generator Intermediate Representation Intermediate Code Optimizer Optimized Intermediate Representation Code Generator CS780 Prasad L1Intro 3 CS780 Prasad Assembly code 4 1 Running the program Structure of the Compiler vis a vis the two Courses Preprocess and Compile gcc c a c b c gcc o myc o c c Source files to object files Link gcc a o b o myc o Object files to an executable file a out 1 Lexical Analysis 2 Parsing 3 Semantic Analysis 4 Optimization 5 Code Generation Symbol Resolution and Relocation Shared Libraries CS780 deals with the theory and the practice of 1 2 and if time permitting 3 CS781 deals with the theory and the practice of 3 4 and 5 Static Linking e g I O Dynamic Linking e g DLLs lib so Java Load and Execute a out Move binaries from disk to memory and run Relocation and Dynamic linking CS780 Prasad L1Intro 5 Lexical Analysis L1Intro 6 Parsing Diagramming a Sentence Recognize words This is a sentence Note the Capital T start of sentence symbol Blank word separator Period end of sentence symbol This adjective Lexical analyzer divides program text into tokens If x y then z 1 else z 2 Units if x y then z 1 else z 2 CS780 Prasad CS780 Prasad L1Intro line is a longer noun verb article adjective subject sentence noun object sentence 7 CS780 Prasad L1Intro 8 2 Parsing Programs Semantic Analysis in English A parser recognizes higher level structure from a token sequence Consider If x y then z 1 else z 2 Diagrammed x y z 1 z 2 relation assign assign predicate then stmt else stmt Even worse Jack said Jack left his assignment at home How many Jacks are there Which one left the assignment if then else CS780 Prasad L1Intro 9 Semantic Analysis in Programming Programming languages define strict rules to avoid such ambiguities Scope Rules This C code prints 4 the inner definition is used Understanding meaning and performing consistency checks Example Jack said Jerry left his assignment at home What does his refer to Jack or Jerry CS780 Prasad Compilers perform many semantic checks besides variable bindings Example Jack left his homework at home Jack left her homework at home A type mismatch between her and Jack we know they are different people Presumably Jack is male Example int Jack 3 int Jack 4 cout Jack L1Intro 10 More Semantic Analysis int i j float x CS780 Prasad L1Intro 11 CS780 Prasad j int i j x L1Intro 12 3 Optimization Code Generation Produces assembly code usually Many compilers perform translations between successive intermediate forms All but the first and the last are ILs internal to the compiler typically ordered in descending level of abstraction No strong counterpart in English but akin to editing Automatically modify programs so that the equivalent program Runs faster Uses less memory In general conserves some resource Simple Example X Y Y is the same as X 2 Y Implemented as arithmetic left shift operation CS780 Prasad L1Intro Highest is the source language Lowest is the assembly language Lower levels expose features such as registers memory layouts etc hidden by higher levels Lower levels obscure high level meaning 13 Example Source and Translation Unoptimized Code 33 lda 30 32 30 stq 26 0 30 stq 15 8 30 bis 30 30 15 bis 16 16 1 stl 1 16 15 lds f1 16 15 sts f1 24 15 ldl 5 24 15 bis 5 5 2 s4addq 2 0 3 ldl 4 16 15 mull 4 3 2 ldl 3 16 15 addq 3 1 4 mull 2 4 2 ldl 3 16 15 addq 3 1 4 mull 2 4 2 stl 2 20 15 ldl 0 20 15 br 31 33 CS780 Prasad 14 Example How are errors detected and diagnosed Error recovery Language design has big impact on compiler Determines what is easy and hard to compile Source Code Lexical Analysis in FORTRAN PL I vs the same in Pascal Java Many trade offs in language design Optimized Code Pointers Multiple Inheritance in C vs Strong Typing Garbage Collection in Java s4addq 16 0 0 mull 16 0 0 addq 16 1 16 mull 0 16 0 mull 0 16 0 ret 31 26 1 L1Intro L1Intro Other Issues int expr int n int d d 4 n n n 1 n 1 return d bis 15 15 30 ldq 26 0 30 ldq 15 8 30 addq 30 32 30 ret 31 26 1 CS780 Prasad 15 CS780 Prasad L1Intro 16 4