David MacQueenDepartment of Computer ScienceSpring 2003CS226/326Compilers for Computer LanguagesWhy Study Compilers?•To learn to write compilers and interpreters for various programming languages and domain specific languagesE.g. Java, Javascript, C, C++, C#, Modula-3, Scheme, ML, Tcl, SQL, MatLab, Mathematica,Shell, Perl, Python,HTML, XML, TeX,PostScript•To enhance understanding of programming languages•To understand how programs work at the machine level•To learn useful system-building tools like Lex and Yacc•To learn interesting compiler theory and algorithms•To experience building a significant system in a modern programming language (SML)Compilers are TranslatorsTranslatorL1L2C, ML, Java, ...compilerassembly/machine codeassembly languageassemblermachine codeobject code (.o files)link loaderexecutable codemacros+textmacro processor (cpp)texttroff/TeXdocument formatterPostScript/PDFL1L2TranslatorCompilers and InterpretersGiven a program P (source code) written in language L•A compiler is simply a translator; compiling P produces the corresponding machine code (PowerPC, Sparc), also known as the object code.•An interpreter is a virtual machine (i.e. a program) for directly executing P (or some machine representtion of P).•A virtual machine-based compiler is a hybrid involving translation P into a virtual machine code M and an virtual machine interpreter that executes M (e.g. the Java Virtual Machine). Virtual machine code is sometimes called byte code.We will focus on the following:•How to characterize the source language L and the target language.•How to translate from one to the other.Compilation Phaseslexical analysis (lexer)syntax analysis (parser)semantic and type analysisintermediate code generatortyped abstract syntaxabstract syntaxsource codetoken sequencecode optimizationmachine code generatorinst. sched. & reg. alloc.machine codeintermediate code(better) intermediate code(better) machine codeProgramming Assignments(1) lexer (using ml-lex)(2,3) parser (using ml-yacc)(4) type checker(5) IR generatortyped abstract syntaxabstract syntaxsource codetoken sequencecode optimization(6) machine code generator(7) register allocationmachine codeintermediate code(better) intermediate code(better) machine codeA Tiger Program/* A program to solve the 8-queens problem */let var N := 8 type intArray = array of int var row := intArray [ N ] of 0 var col := intArray [ N ] of 0 var diag1 := intArray [N+N-1] of 0 var diag2 := intArray [N+N-1] of 0 function printboard() = (for i := 0 to N-1 do (for j := 0 to N-1 do print(if col[i]=j then " O" else " ."); print("\n")); print("\n")) function try(c:int) = if c=N then printboard() else for r := 0 to N-1 do if row[r]=0 & diag1[r+c]=0 & diag2[r+7-c]=0 then (row[r]:=1; diag1[r+c]:=1; diag2[r+7-c]:=1; col[c]:=r; try(c+1); row[r]:=0; diag1[r+c]:=0; diag2[r+7-c]:=0) in try(0)endWhy Standard ML?A language particularly suited to compiler implementation.•Efficiency•Safety•Simplicity•Higher-order functions•Static type checking with type inference•Polymorphism•Algebraic types and pattern matching•Modularity•Garbage collection•Exception handling•Libraries and tools•Type “sml” to run the SML/NJ compilerNormally installed in /usr/local/bin, which should be in your PATH.•Cntl-d exits the compiler, Cntl-c interrupts execution.•Three ways to run ML programs:1. type in code in the interactive read-eval-print loop2.edit ML code in a file, say foo.sml, then type command use “foo.sml”;3. use Compilation Manager (CM): CM.make “sources.cm”;•Template code in dir /stage/classes/current/22600-1/codeUsing the SML/NJ CompilerExpressions•Integers: 3, 54, ~3, ~54•Reals: 3.0, 3.14159, ~3.2E2•Overloaded arithmetic operators: +, -, *, /, <, <=•Booleans: true, false, not, orelse, andalso•Strings: ”abc”, “hello world\n”, x^”.sml”•Lists: [], [1,2,3], [”x”,”str”], 1::2::nil•Tuples: (), (1,true), (3,”abc”,true)•Records: {a=1,b=true}, {name=”fred”,age=21}•conditionals, function applications, let expressions, functionsML Tutorial 1ML Tutorial 2Declarations: binding a name to a valuevalue bindings val x = 3val y = x + 1function bindings fun fact n = if n = 0 then 1 else n * fact(n-1)Let expressions: local definitions let decl in expr endlet val x = 3 fun f y = (y, x*y) in f(4+x)endML Tutorial 3Function expressionsThe expression “fn var => exp” denotes a function with formal parameter var and body exp.val inc = fn x => x + 1is equivalent to fun inc x = x + 1ML Tutorial 4Compound valuesTuples: (exp1, ... , expn)(3, 4.5)val x = (”foo”, x*1.5, true)val first = #1(x)val third = #3(x)Records: {lab1 = exp1, ... , labn = expn}val car = {make = “Ford”, year = 1910}val mk = #make carval yr = #year carML Tutorial 5Patternsa form to decompose compound values, commonly used in value bindings and function argumentsval pat = exp fun f(pat) = expvariable patterns: val x = 3⇒ὗὗx = 3fun f(x) = x+2tuple and record patterns:val pair = (3,4.0)val (x,y) = pair⇒ὗὗx = 3, y = 4.0val {make=mk, year=yr} = car⇒ὗὗmk = “Ford”, yr = 1910ML Tutorial 6Patternswildcard pattern: _ (underscore)constant patterns: 3, “a”fun iszero(0) = true | iszero(_) = falseconstructor patterns:val list = [1,2,3]val fst::rest = list⇒ὗὗfst = 1, rest = [2,3]val [x,_,y] = list⇒ὗὗx = 1, y = 3ML Tutorial 7Pattern matchingmatch rule: pat => expmatch: pat1 => exp1 | ... | patn => expnWhen a match is applied to a value v, we try rules from left to right, looking for the first rule whose pattern matches v. We then bind the variables in the pattern and evaluate the expression.case expression: case exp of matchfunction expression: fn matchclausal functional defn: fun f pat1 = exp1 | f pat2 = exp2 | ... | f pat2 = exp2ML Tutorial 8Pattern matching examples (function definitions)fun length l = case l of of [] => 0 | [a] => 1 | _ :: r => 1 + length rfun length [] = 0 | length [a] = 1 | length (_ :: r) = 1 + length rfun even 0 = true | even n = odd(n-1)and odd 0 = false | odd n = even(n-1)ML Tutorial 9Typesbasic types: int, real, string, bool3 : int, true : bool, “abc” : stringfunction types: t1 -> t2even: int -> boolproduct types: t1 * t2 , unit(3,true): int * bool, (): unitrecord types: {lab1 : t1, ... , labn : tn}car: {make :