1CS780(Prasad) L1Intro 1Introduction to CompilersAdapted 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 2How are Languages Implemented?• Two major strategies:¾Interpreters LISP, bash, java, …¾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 (lower-level) language, preserving the meaning.CS780(Prasad) L1Intro 3Standard Text Books• Dragon Book¾Alfred Aho, Ravi Sethi, and Jeffrey Ullman• Tiger Book¾Andrew Appel• Whale Book¾Steve MuchnickCS780(Prasad) 4Anatomy of a CompilerIntermediate Code OptimizerCode GeneratorOptimized Intermediate RepresentationAssembly codeIntermediate Code GeneratorIntermediate RepresentationLexical Analyzer (Scanner)Syntax Analyzer (Parser)Token StreamParse TreeProgram (character stream)SymbolTable2CS780(Prasad) L1Intro 5Structure of the Compiler vis a vis the two Courses1. Lexical Analysis2. Parsing3. Semantic Analysis4. Optimization5. Code Generation• 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).CS780(Prasad) L1Intro 6Running the program• 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)Symbol Resolution (and Relocation)Shared Libraries 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 7Lexical Analysis• Recognize words.This is a sentence.•Note the¾ Capital “T” (start of sentence symbol)¾ Blank “ ” (word separator)¾ Period “.” (end of sentence symbol)• 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) L1Intro 8Parsing: Diagramming a SentenceThis line is a longer sentence.verbadjectivenoun article adjective nounsubject objectsentence3CS780(Prasad) L1Intro 9Parsing ProgramsA parser recognizes higher-level structure from a token sequence.• Consider:If x == y then z = 1; else z = 2;• Diagrammed:if-then-elsexyz1z2==assignrelation assignpredicate else-stmtthen-stmtCS780(Prasad) L1Intro 10Semantic Analysis in English• Understanding meaning and performing consistency checks.•Example:Jack said Jerry left his assignment at home.What does “his” refer to? Jack or Jerry?• Even worse:Jack said Jack left his assignment at home?How many Jacks are there?Which one left the assignment?CS780(Prasad) L1Intro 11Semantic Analysis in Programming• Programming languages define strict rules to avoid such ambiguities¾Scope Rules• This C++ code prints “4”; the inner definition is used{int Jack = 3;{int Jack = 4;cout << Jack;}}CS780(Prasad) L1Intro 12More Semantic Analysis• 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 i, j; float x; j = (int) ((i + j) * x);4CS780(Prasad) L1Intro 13Optimization• 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 14Code 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.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.CS780(Prasad) L1Intro 15Example (Source and Translation)lda $30,-32($30)stq $26,0($30)stq $15,8($30)bis $30,$30,$15bis $16,$16,$1stl $1,16($15)lds $f1,16($15)sts $f1,24($15)ldl $5,24($15)bis $5,$5,$2s4addq $2,0,$3ldl $4,16($15)mull $4,$3,$2ldl $3,16($15)addq $3,1,$4mull $2,$4,$2ldl $3,16($15)addq $3,1,$4mull $2,$4,$2stl $2,20($15)ldl $0,20($15)br $31,$33$33:bis $15,$15,$30ldq $26,0($30)ldq $15,8($30)addq $30,32,$30ret $31,($26),1Optimized Codes4addq $16,0,$0mull $16,$0,$0addq $16,1,$16mull $0,$16,$0mull $0,$16,$0ret $31,($26),1Unoptimized CodeSource Codeint expr(int n) {int d;d = 4 * n * n * (n + 1) * (n + 1);return d;} CS780(Prasad) L1Intro 16Other Issues• Example: How are errors detected and diagnosed? Error recovery?• Language design has big impact on compiler.¾ Determines what is easy and hard to compile.Lexical Analysis in FORTRAN/PL-I vs the same in Pascal/Java¾ Many trade-offs in language design.Pointers, Multiple Inheritance,… in C++ vsStrong Typing, Garbage Collection,… in