LARA: Laboratory for Automated Reasoning and Analysis compilation

compilation:abstract_syntax_of_while

Anonymous (anonymous@undisclosed.example.com) — 2008-09-15T00:45:55+0200

Abstract Syntax for While Abstract Syntax = concise representation of program as a data structure * ignores concrete symbols (whether we use “{” or “begin” for blocks) * maps easily to Scala's case classes For our While language: program ::= statement statement ::= print | read | assign | if | while | block print ::= string var assign ::= var expr if ::= exp statement (statement)? while ::= expr statement block ::= statement* expr ::= var | literal | expr binOp expr | unOp expr

compilation:accessing_and_storing_variables

Anonymous (anonymous@undisclosed.example.com) — 2015-04-21T17:34:55+0200

Accessing and Storing Variables Local Variables Instructions to load and store local variables: * iload * istore Assigning indices (called slots) to local variables: * in which compiler phase? * how? Function * maps variable ocurrence, not name (part of symbol table)

compilation:ahoullman

Anonymous (anonymous@undisclosed.example.com) — 2009-10-11T15:56:33+0200

The theory of parsing, translation, and compiling This excellent advanced textbook is available online from ACM * under “ACM Classic Books Series” @book{578789, author = {Alfred V. Aho and Jeffrey D. Ullman}, title = {The theory of parsing, translation, and compiling}, year = {1972}, isbn = {0-13-914556-7}, publisher = {Prentice-Hall, Inc.}, address = {Upper Saddle River, NJ, USA}, }

compilation:algorithm_for_first_and_follow_sets

Anonymous (anonymous@undisclosed.example.com) — 2008-10-04T14:30:15+0200

Algorithm for Computing First and Follow Sets Building on Recursive Descent Parsing nullable = {} foreach nonterminal X: first(X)={} follow(X)={} for each terminal Y: first(Y)={Y} repeat foreach grammar rule X ::= Y(1) ... Y(k) if k=0 or {Y(1),...,Y(k)} subset of nullable then nullable = nullable union {X} for i = 1 to k for j = i+1 to k if i=1 or {Y(1),...,Y(i-1)} subset of nullable then first(X) = first(X) union first(Y(i)) if i=k or {Y(i+1),...Y(k)}…

compilation:alternatives_to_compilation

Anonymous (anonymous@undisclosed.example.com) — 2008-09-08T11:07:36+0200

Alternatives to compilation? Interpreter is a program that reads source code and directly executes it * does not generate the translation of the source program first Advantages of compilers over interpreters: * once compiled, execution can be much faster

compilation:an_efficient_functional_map

Anonymous (anonymous@undisclosed.example.com) — 2008-10-13T02:46:46+0200

An Efficient Functional Map Balanced Binary Search Trees * update creates a new path (copying only log(n) nodes) * lookup and update in log(n) * worst-case guaranteed by balancing * rebalancing can also be done functionally on update Alternative:

compilation:an_efficient_imperative_map

Anonymous (anonymous@undisclosed.example.com) — 2008-10-13T02:48:21+0200

An Efficient Imperative Map Hashtable * compute hash of keys, determiines the bucket * storing key-value pairs in buckets * buckets as linked lists, or * buckets within the array, with a probing function that fills array * for constant time we have large enough array, collisions rare

compilation:applications_of_data-flow_analysis

Anonymous (anonymous@undisclosed.example.com) — 2008-11-25T15:12:25+0200

Applications of Data-Flow Analysis * optimization * correctness Optimization Brief list of data-flow analyses and their uses - from Tiger book, sav08, papers Checks: * initialization analysis * protocol usage analysis * array bounds checks

compilation:arm_architecture

Anonymous (anonymous@undisclosed.example.com) — 2008-12-07T16:35:37+0200

ARM Architecture A family of CPUs From article on RISC architectures: “The ARM architecture dominates the market for high performance, low power, low cost embedded systems (typically 100–500 MHz in 2008). ARM Ltd., which licenses intellectual property rather than manufacturing chips, reported 10 billion licensed chips shipped in early 2008 [7]. ARM is deployed in countless mobile devices such as:

compilation:array_manipulation

Anonymous (anonymous@undisclosed.example.com) — 2008-11-03T02:31:10+0200

Array Manipulation newarray anewarray iaload iastore arraylength

compilation:automata_for_lr_parsing_without_lookahead

Anonymous (anonymous@undisclosed.example.com) — 2015-04-21T17:34:55+0200

Automata for LR Parsing without Lookahead These automata are used to construct LR(0) and SLR parsers We describe their states and transitions LR(0) item is a dotted production * is grammar rule * some strings of terminals and non-terminals

compilation:booleans_and_data_representation

Anonymous (anonymous@undisclosed.example.com) — 2008-11-09T20:37:43+0200

Booleans and Data Representation Types in programming language: * specify length of data (how many bits) * help prevent errors * enforce program invariants In assembly and C: * possible to case integer into a pointer * enables program to write to random memory locations

compilation:bottop-up_type_checking

Anonymous (anonymous@undisclosed.example.com) — 2008-10-17T14:12:58+0200

Bottop-Up Type Checking Recall function interpExpr function in * Handling Scopes in Interpreters * Semantic Analysis as Simplified Interpretation Forget about uninitialized values for now, worry only about types We evaluate type analogously to evaluating expressions Principles: * all variables are declared with their types

compilation:branching_jvm_instructions

Anonymous (anonymous@undisclosed.example.com) — 2008-11-10T10:03:10+0200

JVM Instructions for Branching See table of JVM instructions Unconditional jumps: goto Conditional branch on comparison to zero: * if_ * by convention on booleans in Booleans and Data Representation, we can use if_eq to mean ifFalse * can use if_ne to mean ifTrue (because 1 is not equal to 0) There are also conditional branches for comparison of two operands:

compilation:building_a_pretty_printer

Anonymous (anonymous@undisclosed.example.com) — 2008-10-06T10:06:29+0200

Building a Pretty Printer A pretty printer: * parses input source * prints it, perhaps with improved formatting * e.g. HTML listing, documentation, latex Simple pretty printer is in tree.scala Operations: lex : List[Char] -> List[Token] parse : List[Token] -> Tree print : Tree -> List[Char]

compilation:building_ll_parsing_table

Anonymous (anonymous@undisclosed.example.com) — 2008-10-06T09:52:35+0200

Building LL Parsing Table Continuing summary of Recursive Descent Parsing Parsing table for LL parser is of form choice : Nonterminal -> Token -> Set[Int] We computing it for each nonterminal X by looking at all right-hand sides of X. Denote i-th right-hand side of X by p(X,i):

compilation:cafebabe-abc

Anonymous (anonymous@undisclosed.example.com) — 2011-11-21T14:17:23+0200

The Cafebabe Bytecode Generation Library IMPORTANT: This page is now outdated. Cafebabe has moved to GitHub and so has the documentation. The main Cafebabe page is here. Full examples are available here. Abstract Byte Codes Loading constant values Constant values can be pushed on the stack in several different ways. Integers in particular can be pushed using the various

compilation:cafebabe-examples

Anonymous (anonymous@undisclosed.example.com) — 2011-11-21T14:17:34+0200

The Cafebabe Bytecode Generation Library: Examples IMPORTANT: This page is now outdated. Cafebabe has moved to GitHub and so has the documentation. See also: * Cafebabe introduction page * Abstract Bytecodes Hello world The good old: class HW { public static void main(String [] args) { System.out.println("Hello world!"); } }

compilation:cafebabe

Anonymous (anonymous@undisclosed.example.com) — 2011-11-21T14:17:11+0200

The Scala Cafebabe Bytecode Generation Library IMPORTANT: This page is now outdated. Cafebabe has moved to GitHub and so has the documentation. Introduction This page is an introduction to the byte code generation library “Cafebabe”. Rather than exposing an API-like reference, we present the capabilities of the library through examples.

compilation:charstream.scala

Anonymous (anonymous@undisclosed.example.com) — 2008-09-10T17:36:43+0200

import java.io._ class EndOfInput(stream : String) extends Exception class CharStream(fileName : String) { val file = new BufferedReader(new FileReader(fileName)) var current : Char = ' ' var eof : Boolean = false def next = { if (eof) throw new EndOfInput("reading" + file) val c = file.read() eof = (c == -1) current = c.asInstanceOf[Char] } next } object Test { // test for using CharStream def main(args : Array[String]) = { val s = new CharStream(args(0)) …

compilation:collatz.while

Anonymous (anonymous@undisclosed.example.com) — 2008-09-12T00:34:54+0200

x = 13; while (x > 1) { println("x=", x); if (x % 2 == 0) { x = x / 2; } else { x = 3 * x + 1; } }

compilation:compilation_as_tree_transformation

Anonymous (anonymous@undisclosed.example.com) — 2008-11-10T02:43:16+0200

Compilation as Tree Transformation To describe this compilation we introduce an imaginary, big, instruction branch(c,nThen,nElse) Here * c is a potentially complex Java boolean expression * nThen is label to jump to when c evaluates to true *

compilation:compiled_counting_examples

Anonymous (anonymous@undisclosed.example.com) — 2008-11-02T00:01:06+0200

Compiled Counting Examples Simple Counting class CountingSimple { public static void count(int from, int to, int step) { int counter = from; while (counter < to) { counter = counter + step; } } } Bytecode: public static void count(int, int, int); Code: 0: iload_0 1: istore_3 2: iload_3 3: iload_1 4: if_icmpge 14 7: iload_3 8: iload_2 9: iadd 10: istore_3 11: goto 2 14: return LineNumberTable: line 3: 0 …

compilation:compiled_expression_examples

Anonymous (anonymous@undisclosed.example.com) — 2008-11-01T23:45:24+0200

Compiled Expression Examples Twice Java: class Expr1 { public static int twice(int x) { return x*2; } } Bytecode: javac -g Expr1.java javap -c -l Expr1 public static int twice(int); Code: 0: iload_0 // load int from var 0 to top of stack 1: iconst_2 // push 2 on top of stack 2: imul // replace two topmost elements with their product 3: ireturn // return top of stack }

compilation:compiled_factorial_example

Anonymous (anonymous@undisclosed.example.com) — 2008-11-01T19:29:05+0200

Compiled Factorial Example Factorial example: class Factorial { public int fact(int num){ int num_aux; if (num < 1) num_aux = 1 ; else num_aux = num * (this.fact(num-1)); return num_aux; } } Result of compilation with javac:

compilation:compiler_construction_by_niklaus_wirth

Anonymous (anonymous@undisclosed.example.com) — 2008-11-07T16:45:52+0200

Compiler Construction by Niklaus Wirth You can download here the textbook [Compiler Construction, by Niklaus Wirth]. Click here for Book Web Site A few Typos in Compiler Construction by Wirth

compilation:compiler_construction_tools

Anonymous (anonymous@undisclosed.example.com) — 2008-09-09T15:48:58+0200

Compiler Construction Tools JavaCC SableCC JLex + JCUP Coco/R Antlr Combinator Parsers

compilation:compiler_interface_to_garbage_collector

Anonymous (anonymous@undisclosed.example.com) — 2008-12-15T01:41:28+0200

Compiler Interface to Garbage Collector Garbage collector needs to know * reference roots * reference fields Need to generation information on * global variables * heap: tag each record with its type information, like class descriptors for dynamic method calls from

compilation:compilers_in_action

Anonymous (anonymous@undisclosed.example.com) — 2008-11-01T13:49:53+0200

Compilers in Action gcc Compilers for C Example program in C programming language #include int main(void) { int i = 0; int j = 0; while (i < 10) { printf("%d\n", j); i = i + 1; j = j + 2*i+1; } } We will pay attention to line:

compilation:compiling_conditional_expressions

Anonymous (anonymous@undisclosed.example.com) — 2008-11-19T08:27:32+0200

Compiling Conditional Expressions Expression (c ? t : e) evaluates to * t, if c is true * e, if c is false [[ c ? t : e ]] = [[ c ]] ifeq nElse [[ t ]] goto nAfter nElse: [[ e ]] nAfter: This is like Compiling If Then Else *

compilation:compiling_if_then_else

Anonymous (anonymous@undisclosed.example.com) — 2008-11-09T21:57:10+0200

Compiling If-Then-Else Compiled Factorial Example Assume that translation of c, denoted [ [ c ] ], produces a boolean value on top of the stack Then: [[ If (c) sThen else sElse ]] = [[ c ]] if_eq nAfter [[ sThen ]] goto nAfter nElse: [[ s2 ]] nAfter:

compilation:compiling_statement_sequence

Anonymous (anonymous@undisclosed.example.com) — 2015-04-21T17:34:55+0200

Compiling Statement Sequence [\![s_1 ; \ldots; s_n ]\!] = [\![s_1]\!] ::: \ldots ::: [\![s_n]\!]

compilation:compiling_while

Anonymous (anonymous@undisclosed.example.com) — 2008-11-09T22:34:53+0200

Compiling While [[ while(c) s ]] = nStart: [[c]] if_eq nAfter [[s]] goto nStart nAfter: Example Java code: class Test { static boolean condition(int n) { ... } static void work(int n) { ... } static void test() { int n = 100; while (condition(n)) { n = n - 11; work(n); } } }

compilation:computing_labels

Anonymous (anonymous@undisclosed.example.com) — 2008-11-09T21:50:34+0200

Computing Labels Labels are symbolic names for targets of branch instructions Two-Pass Approach * generate sequence of instructions with unknown destinations * once lengths of code are known, resolve all labels * emit the code Two main kinds of jumps:

compilation:concrete_execution_as_data-flow_analysis

Anonymous (anonymous@undisclosed.example.com) — 2008-11-25T17:00:31+0200

Concrete Execution as Data-Flow Analysis For a large class of properties, the most precise data-flow analysis is program execution itself * an element is a set of states (not just one state) * bottom: empty set * top: all states If program execution terminates, so does this analysis

compilation:concrete_syntax_of_while

Anonymous (anonymous@undisclosed.example.com) — 2008-09-29T15:45:24+0200

Concrete Syntax of While Language program ::= statement* statement ::= print | assign | if | while | block print ::= "println" "(" STRLIT "," var ")" ";" assign ::= var "=" expr ";" if ::= "if" "(" exp ")" statement ("else" statement)? while ::= "while" "(" expr ")" statement block ::= "{" statement* "}" expr ::= var | INTLIT | expr binOp expr | unOp expr | "(" expr ")" unOp ::= "!" | "-" binOp ::= "+" | "-" | "*" | "/" | "%" | "==" | ">" | "<" | "&&" | "||"

compilation:concreteanalysis.scala

Anonymous (anonymous@undisclosed.example.com) — 2008-11-24T02:51:18+0200

// Lattice of concrete executions of integer programs object ConcreteLattice extends Lattice { type State = Map[String,Int] // specific to this particular example type Elem = Set[State] def leq(x : Elem, y : Elem) : Boolean = x.subsetOf(y) val bottom = Set[State]() lazy val top = error("lattice element too big to compute") def join(x : Elem, y : Elem) = (x ++ y) // union def meet(x : Elem, y : Elem) = (x ** y) // intersection } import SimpleCFG._ object ConcreteTransFun extends …

compilation:constant_propagation

Anonymous (anonymous@undisclosed.example.com) — 2008-11-17T02:43:25+0200

Constant Propagation * like initialization, but keeps the value to which it is initialized \bot, C, potentially non-constantint a, b, step, i; boolean c; a = 0; b = a + 10; step = -1; if (step > 0) { i = a; } else { i = b; } c = true; while (c) { print(i); i = i + step; // can emit decrement if (step > 0) { c = (i < b); } else { c = (i > a); // can emit better instruction here // put here (a = a + step), redo analysis } }

compilation:constraint-based_type_checking

Anonymous (anonymous@undisclosed.example.com) — 2008-10-29T10:29:17+0200

Constraint-Based Type Checking and Inference Motivation for Type Inference Example: % y:int. let ((f:int->int) = % x:int. x+3) in f (f (y+5)) Bottom-up type checking concludes: y:int 5:int y+5:int x:int 3:int x+3:int (% x:int. x+3): int->int f:int->int f(y+5):int f(f (y+5)):int (% y:int. let ((f:int->int) = ...) : int->int

compilation:control-flow_graph_definition

Anonymous (anonymous@undisclosed.example.com) — 2008-11-19T10:44:02+0200

Control-Flow Graph Definition Recall Linearizing Trees with Control-Flow, Different Views of IfThenElse * control-flow graphs are the graph view Like automaton but with variables Related to traditional notion of flow charts Definition: Control-Flow Graph (CFG) is graph where

compilation:control-flow_graph_to_assembly_with_global_variables

Anonymous (anonymous@undisclosed.example.com) — 2008-12-07T22:09:40+0200

Control-Flow Graph to Assembly with Global Variables Recall SimpleCFG.scala from Lecture 11 How to compile e.g. a quadruple? x = y * z One possibility: translate each quadruple independently into machine instruction sequence such as Move(Register(r1), Memory(yAddr)) Move(Register(r2), Memory(zAddr)) Quad(Register(r1), Register(r1), Register(r2)) Move(Memory(xAddr), Register(r1))

compilation:copying_garbage_collector

Anonymous (anonymous@undisclosed.example.com) — 2008-12-15T00:25:18+0200

Copying Garbage Collector Some advantages compared to mark-and-sweep: * no fragmentation * fast allocation, as in MallocInfMem.scala * good when a lot of data allocated and thrown away (as in functional languages) Disadvantage: double space consumption * note that fragmentation can (very infriquently) mean inability to allocate block even if there is e.g. 1000 more space

compilation:course_information

Anonymous (anonymous@undisclosed.example.com) — 2008-11-01T17:30:41+0200

Course Information for Compiler Construction (CS-320) Staff Lectures: * Viktor Kuncak Practical and Theoretical Exercises: * Ruzica Piskac * Philippe Suter Assistants-Étudiants * Sebastian Gfeller * Cédric Lavanchy * Ersoy Bayramoglu Secretary: Danielle Chamberlain Schedule * Mondays 10:15-12:00 - Lectures in

compilation:cyk_parsing_algorithm

Anonymous (anonymous@undisclosed.example.com) — 2015-04-21T17:34:55+0200

CYK Parsing Algorithm for General Context-Free Grammars Given a context-free grammar , how to check if ? * recursive descent gives efficient answer when is LL(1) * we now see how to do it for arbitrary context-free grammar Conventions: * S will always denote the start symbol of the grammar

compilation:dataflowanalysis.scala

Anonymous (anonymous@undisclosed.example.com) — 2009-11-22T19:54:03+0200

// specialized to SimpleCFG import SimpleCFG._ abstract class TransferFunction[L, CFGStatement] { // L is information propagate through CFG nodes def apply(node : CFGStatement, x : L) : L // if x describes a set of states, // then apply(n,x) describes states obtained from x by executing statement n } class AnalysisAlgoritm[L,CFGStatement] (transferFun : TransferFunction[L, CFGStatement], lattice : Lattice{type Elem=L}, cfg : LabDiGraphImp[CFGStatement]) { type Vert…

compilation:designing_correct_data-flow_analyses

Anonymous (anonymous@undisclosed.example.com) — 2015-04-21T17:34:55+0200

Designing Correct Data-Flow Analyses Define Properties of Interest Define precisely what property is needed (depends on the application), e.g. * absence of errors * potentially improving code performance without changing program meaning Example: every variable assigned before being read

compilation:digraphs.scala

Anonymous (anonymous@undisclosed.example.com) — 2008-11-24T02:48:19+0200

/* Mutable Directed Graph with Labels */ abstract trait LabDiGraph[Label] { type Vertex type Edge def V : Set[Vertex] def E : Set[Edge] def newVertex : Vertex def += (from : Vertex, lab : Label, to : Vertex) def inEdges(v : Vertex) : Set[Edge] def outEdges(v : Vertex) : Set[Edge] def -= (from : Vertex, lab : Label, to : Vertex) def labelMap[NewLabel](f : Label => NewLabel) : LabDiGraph[NewLabel] } case class LVertex[L](name : String) { var in : Set[LEdge[L]] = Set[LEdge…

compilation:earley_parser

Anonymous (anonymous@undisclosed.example.com) — 2015-04-21T17:34:55+0200

Earley Parser What is Earley Parser A parser for context-free grammars * works for arbitrary, even ambiguous, grammars * runs in O(n^3) in general * unlike CYK Parsing Algorithm, it does not require Transforming to Chomsky Normal Form * for unambiguous grammars it runs in O(n^2) * for grammars handled by LR parsers, it runs in O(n)

compilation:efficient_comparison_for_identifiers

Anonymous (anonymous@undisclosed.example.com) — 2008-10-13T07:48:37+0200

Efficient Comparison for Identifiers Identifiers can be very long Comparing them directly is inefficient Lexical analyzer can immediately replace them with references to symbol objects * hash table stores mapping of strings to symbols * pointers equal iff strings equal

compilation:efficiently_emitting_code

Anonymous (anonymous@undisclosed.example.com) — 2015-04-21T17:34:55+0200

Efficiently Emitting Code Efficiency Problem Consider concatenation-based implementation Consider standard purely functional list implementation EmptyList ::: ys = ys (x::xs) ::: ys = x::(xs ::: ys) How many times is traversed in such implementation?

compilation:elanguage

Anonymous (anonymous@undisclosed.example.com) — 2008-12-10T15:31:49+0200

ELanguage start ::= e e ::= e "+" e | e "*" e | e "/" e | block | "(" e ")" | e "(" e* ")" | e "||" e | e "<" e | ident | intLiteral | floatLiteral valdef ::= fdef | "val" ident ":" type "=" e fdef ::= "def" ident "(" typedIdList ")" ":" type "=" e block ::= "{" valdef* e "}" ident ::= letter (letter | diggit)* intLiteral ::= nonZerodigit digit* | "0" | "0" "x" hexDigit+ | "0" digit* floatLiteral ::= intLiteral "." digit* type ::= "int" | "floa…

compilation:evaluating_postfix

Anonymous (anonymous@undisclosed.example.com) — 2008-11-02T19:42:23+0200

Evaluating Postfix and its Correctness sealed abstract class Expr case class Var(varID: String) extends Expr case class IntLiteral(value: Int) extends Expr case class Plus(lhs: Expr, rhs: Expr) extends Expr case class Times(lhs: Expr, rhs: Expr) extends Expr sealed abstract class Token case class ID(str : String) extends Token case class Const(c : Int) extends Token case class Add extends Token case class Mul extends Token object Print { def postfix(e : Expr) : List[Token] = e match { …

compilation:ex3-javacc-stub

Anonymous (anonymous@undisclosed.example.com) — 2008-10-01T16:52:32+0200

options { STATIC = false; } PARSER_BEGIN(WhileParser) class WhileParser { public static void main(String[] args) throws ParseException, TokenMgrError { WhileParser parser = new WhileParser(System.in); parser.Start(); } } PARSER_END(WhileParser) SKIP : { " " | "\t" | "\n" | "\r" | < "//"(~["\n", "\r"])* ("\n" | "\r" | "\r\n")> } TOKEN : { < INTLIT: "0" | ["1"-"9"](["0"-"9"])* > } TOKEN : { < STRLIT: "\"" (~["\"", "\n", "\r"])* "\"" > }TOKEN : …

compilation:example_efficient_code_for_conditionals

Anonymous (anonymous@undisclosed.example.com) — 2008-11-10T02:09:13+0200

Example Efficient Code for Conditionals class Activity { static int activityLevel = 0; static boolean action(int signals, boolean objects, int smart, int pretty) { if (smart + 2*pretty > 10 && !(signals <= 5 && objects)) { activityLevel++; return true; } else { return false; } } }

compilation:example_ocamlyacc_grammar

Anonymous (anonymous@undisclosed.example.com) — 2008-10-05T22:14:46+0200

Example Ocamlyacc Grammar The Objective Caml programming language comes with ocamlyacc LALR(1) parser generator * documented in language manual * separate tutorial Here is a Java 1.2 parser written in OcamlYacc and used in Jahob Program Verification System: * jahobparser.yy

compilation:examples_of_compiled_java

Anonymous (anonymous@undisclosed.example.com) — 2008-11-01T23:52:49+0200

Examples of Compiled Java Compiled Expression Examples Compiled Counting Examples Compiled Factorial Example

compilation:exercises_01

Anonymous (anonymous@undisclosed.example.com) — 2008-09-17T11:16:13+0200

Exercises 01 Review: State Machines from Regular Expressions Finite state machine Determinization of finite state machine Finite state machine with epsilon transitions Closure properties of finite state machines Floating point literals Floating point constants can take many forms: they are signed, may have a fractional part and may have an additional (positive or negative) integer exponent to represent an attached power of 10. Examples of such literals are: 3.1415, -7, 6.02214e23, 0.27183…

compilation:exercises_02

Anonymous (anonymous@undisclosed.example.com) — 2008-09-24T09:47:02+0200

Exercises 02 There are no exercises this week, see Lecture 02 instead.

compilation:exercises_03

Anonymous (anonymous@undisclosed.example.com) — 2008-10-01T16:53:06+0200

Exercises 03 Important update There was a bug in the stub .jj file that caused the keywords if, while, etc. to be recognized as identifiers rather than the proper tokens. It is now fixed. Make sure you use the latest version (that is, you should have

compilation:exercises_04

Anonymous (anonymous@undisclosed.example.com) — 2008-10-08T14:18:12+0200

Exercises 04 Only one exercise this week, enjoy. Hand in your assignment at the latest on Wednesday, Oct. 15th, 8:15am (note time change: it is due before labs!). Late submissions will not be graded. You can hand them in as you arrive to the lab session, or drop them off earlier at BC 363.

compilation:exercises_05

Anonymous (anonymous@undisclosed.example.com) — 2008-10-22T09:36:55+0200

Exercises 05 Please hand in your exercises before Wednesday, Oct. 22nd, 8.15am. Earley Parsing I Consider the following grammar: S' -> S $ S -> s S -> { S2 } S -> i c S S -> i c S e S S2 -> S2 S | S * Parse the following string: “icicse{ss}

compilation:exercises_06

Anonymous (anonymous@undisclosed.example.com) — 2015-04-21T17:34:55+0200

Exercises 06 Exercises Session 06 Type Checking Arrays This exercise is designed to make you think about certain aspects of Java's type system. Please hand in your exercises before Wednesday, Oct. 29th, 8.15am. A Program The following Java program defines a Cell class, which stores an integer that can only be set once, and defines its subclass

compilation:exercises_07

Anonymous (anonymous@undisclosed.example.com) — 2008-11-03T22:01:01+0200

Exercises 07 Material Done During Exercise Session Discussion of the homework assignment from Exercises 06 and summary of invariants in case of subtyping (following Proving Safety Properties using Types). Constraint-Based Type Checking Unification Homework Assignment, due 05 November 2008 at 8:15am Note: get started on this assignment early.

compilation:exercises_08

Anonymous (anonymous@undisclosed.example.com) — 2015-04-21T17:34:55+0200

Exercises 08 Material Done During Exercise Session Example of code generation /** Computes the max of two integer values */ public int max(int i, int j) { int res; res = (i > j ? i : j); return res; } Possible corresponding bytecode: 0: iload_1 1: iload_2 2: if_icmple 5 3: iload_1 4: goto 6 5: iload_2 6: istore_3 7: iload_3 8: ireturn

compilation:exercises_09

Anonymous (anonymous@undisclosed.example.com) — 2015-04-21T17:34:55+0200

Exercises 09 Material for Exercise Session Translate manually into bytecodes using the techniques in Compilation as Tree Transformation int activityLevel boolean action(int signals, boolean objects, int smart, int pretty) { if ((signals > 5 || !objects) && smart + 2*pretty > 10) { activityLevel++; return true; } else { activityLevel--; return false; } }

compilation:exercises_session_06

Anonymous (anonymous@undisclosed.example.com) — 2008-10-22T13:35:43+0200

Exercise Session 06 This summarizes activities done in class on 22 October 2008. Type checking and evaluation for simply typed lambda calculus Solved exercises: 1) Prove that the following program is type correct: class Max { int max (int x, int y) { int res; res = (x > y) ? x : y; return res; } }

compilation:final_projects_and_reports

Anonymous (anonymous@undisclosed.example.com) — 2009-01-03T12:20:27+0200

Final Projects and Reports You will submit your compiler and report through Moodle, as for homeworks. The report should have between 4 and 10 pages (depending on your formatting). You can use any software to typeset it, including Latex, OpenOffice, or a standard

compilation:free_lists_by_size

Anonymous (anonymous@undisclosed.example.com) — 2008-12-14T21:43:34+0200

Free Lists by Size Simplest solution * one free list for all sizes * each block stores its size Problem: efficiency of finding appropriate block Array of free lists: * for (almost) each size * when allocating block of size B, search in free(B), or in free(i) for i >= B

compilation:from_stack_to_register_machines

Anonymous (anonymous@undisclosed.example.com) — 2008-11-07T16:55:28+0200

From Stack to Register Machines What is a register machine? If stack depth is less than the number of general purpose registers, treat registers as stack. If SP is a stack pointer as maintained by the compiler, then we essentially emit instructions that correspond to code for

compilation:functional_versus_imperative_maps

Anonymous (anonymous@undisclosed.example.com) — 2008-10-13T01:54:57+0200

Functional versus Imperative Maps Goal is to map identifiers to definitions We need efficient operations on maps * look up identifier to obtain its definition * update map to store declarations * revert declarations Functional style * seen in

compilation:generational_garbage_collectors

Anonymous (anonymous@undisclosed.example.com) — 2008-12-15T00:50:38+0200

Generational Garbage Collectors Divide heap into generations, typically according to age of objects * how long ago was allocated When the object is collected 2-3 times, promote it from younger to older generation Newer generation about 1/2 size of old one

compilation:hand-written_scanner_for_while_language

Anonymous (anonymous@undisclosed.example.com) — 2008-09-15T10:09:23+0200

Hand-Written Lexical Analyzer for While Lexical Analyzer Also called: lexer, scanner, or tokenizer Transforms sequence of characters into sequence of tokens Interfaces for Lexer In practice, we read characters and generate tokens on demand Work with

compilation:handling_scopes_in_interpreters

Anonymous (anonymous@undisclosed.example.com) — 2008-10-13T12:35:03+0200

Handling Scopes in Interpreters An Example interpreter for language with procedures and blocks object ScopeInterpreter { type Ident = String case class Program(classes : List[ClassDef], classToRun : Ident) case class ClassDef(name : Ident, decls : List[ClassDecl]) sealed abstract class Typ case object IntType extends Typ case object BoolType extends Typ case object VoidType extends Typ case class VarDecl(name : Ident, tp : Typ) sealed abstract class ClassDecl ca…

compilation:higher-order_functions

Anonymous (anonymous@undisclosed.example.com) — 2008-12-07T20:23:04+0200

Higher-Order Functions Example of Code Compiled from Scala

compilation:idea_of_data_flow_analysis

Anonymous (anonymous@undisclosed.example.com) — 2008-11-19T10:43:02+0200

Idea of Data Flow Analysis Goal Today Introduce the ide of data-flow analysis * a form of semantic analysis Why it is useful Automatically derive information about the program Use this information for: * correctness checks (initialization, correct order of operations, absence of errors)

compilation:idea_of_garbage_collection

Anonymous (anonymous@undisclosed.example.com) — 2009-12-14T00:13:06+0200

Idea of Garbage Collection Idea: * 'free' violates memory-safety and type-safety * instead, let the run-time system automatically free memory that is guaranteed not to be used any more * memory that will not be used is called garbage * algorithms that reclaim such memory are

compilation:implementing_finite_state_machines

Anonymous (anonymous@undisclosed.example.com) — 2008-09-23T19:14:48+0200

Implementing Finite State Machines Using an Array The state of finite state machine is a mutable variable. Assume: * State - type denoting states * Char - denotes symbols of alphabet Behavior is given by a big array delta delta : Array[State,Array[Char,State]]

compilation:incremenatal_garbage_collectors

Anonymous (anonymous@undisclosed.example.com) — 2008-12-15T01:34:53+0200

Incremenatal Garbage Collectors Goal: reduce pause times Do not stop the program to do garbage collection Instead, perform steps of garbage collection as the program is running Consider this situation: * collector already processes reachable node x and its fields

compilation:initialization_analysis

Anonymous (anonymous@undisclosed.example.com) — 2015-04-21T17:34:55+0200

Initialization Analysis We follow the methodology of Designing Correct Data-Flow Analyses Defining Properties of Interest We represent program execution as a sequence of states and simple statements , starting with the initial state Given a sequence we say that variable is initialized

compilation:instruction_selection

Anonymous (anonymous@undisclosed.example.com) — 2008-12-08T03:32:10+0200

Instruction Selection A systematic way to select one of the many ways to translate basic block computations Note: * instructions can do several simple steps at once * computed expressions also do several things at once Goal: represent expressions using instructions

compilation:internal

Anonymous (anonymous@undisclosed.example.com) — 2008-12-16T19:01:28+0200

Teaching Staff Page for Compiler Construction Grading: Friday Thursday mornings Grades Groups * Burgener, Raphaël & Favre, Ludovic (#01) * Chappuis, Daniel & Testuz, Stéphane (#02) * Köksal, Ali Sinan & Kneuss, Etienne (#03) * Kviatkevitch, Ivan & Bindschaedler, Laurent (#04)

compilation:internal_grading

Anonymous (anonymous@undisclosed.example.com) — 2008-10-01T15:27:19+0200

Grades Info is partially duplicated from Moodle.

compilation:interpreter.scala

Anonymous (anonymous@undisclosed.example.com) — 2008-09-26T13:21:56+0200

package whilelang; object Interpreter { // add as many helper methods and values/variables as you want... def apply(stat: Statement): Unit = { // "runs" the program described by stat... } }

compilation:interpreting_cfg

Anonymous (anonymous@undisclosed.example.com) — 2008-11-17T02:18:51+0200

Interpreting Control-Flow Graphs Standard Execution Running i = 0; while (i < 5) { i = i + 1; } Running Collatz example A path through graph A trace for a given path: add states of variables An execution trace through control-flow graph Computing Reachable States by Execution

compilation:interpreting_control-flow_graphs

Anonymous (anonymous@undisclosed.example.com) — 2008-11-12T17:00:16+0200

Interpreting Control-Flow Graphs Here is a Scala interpreter for control-flow graphs. Standard version with program counter. Accumulating semantics version.

compilation:interpreting_ll_parsing_table

Anonymous (anonymous@undisclosed.example.com) — 2008-10-04T21:31:08+0200

Interpreting LL Parsing Table Computed parse table in 'choice' matrix, as in Building LL Parsing Table This is the top-down parser: var stack : Stack[GrammarSymbol] stack.push(EOF); stack.push(StartNonterminal); lex = new Lexer(inputFile) while (true) { X = stack.pop t = lex.curent if isTerminal(X) if (t==X) if (X==EOF) return success else lex.next // eat token t else parseError("Expected " + X) else // non-terminal cs = choice(X)(t) cs match { …

compilation:isquares.while

Anonymous (anonymous@undisclosed.example.com) — 2008-10-04T20:40:04+0200

i = 0; j = 0; while (i - 10) { i = i + 1; j = j + 2*i+1; println(j);}

compilation:jahobparser.yy

Anonymous (anonymous@undisclosed.example.com) — 2008-10-05T22:15:08+0200

/* Joust: a Java lexer, parser, and pretty-printer written in OCaml Copyright (C) 2001 Eric C. Cooper Released under the GNU General Public License */ /* LALR(1) (ocamlyacc) grammar for Java Attempts to conform to: The Java Language Specification Second Edition James Gosling, Bill Joy, Guy Steele, Gilad Bracha */ /* adapted for use with Jahob by Viktor Kuncak, 2005-2008 */ %{ (** Joust parser, generated with ocamlyacc. *) open List open Syntax %} %token <…

compilation:java_definite_assignments

Anonymous (anonymous@undisclosed.example.com) — 2008-11-25T18:50:21+0200

Java Definite Assignments Consider examples from: Definite Assignments from Java Language Specification We ignore the question of making sure that final values are initialized * focus on making sure that local variables are initialized before their first use The specification gives a particular precision of data-flow analysis that a compiler must implement to correctly report uninitialized variables

compilation:java_example_for_semantic_analysis

Anonymous (anonymous@undisclosed.example.com) — 2008-10-13T07:22:00+0200

Java Example for Semantic Analysis What does this program compute? class Example { boolean x; int y; int z; int compute(int x, int y) { int z = 3; return x + y + z; } public void main() { int res; x = true; y = 10; z = 17; res = compute(z, z+1); System.out.println(res); } }

compilation:javacc

Anonymous (anonymous@undisclosed.example.com) — 2008-09-11T19:29:53+0200

JavaCC Is a compiler compiler: generates lexers and parsers. URL: It has been used for realistic Java parsers and is used in the Tiger book.

compilation:jvm_classfile_construction_library

Anonymous (anonymous@undisclosed.example.com) — 2008-11-03T02:10:39+0200

JVM Classfile Construction Library Will be provided for the project Makes construction of class files easier * e.g. no need to know binary instruction opcodes Documentation will appear here soon

compilation:jvm_instructions

Anonymous (anonymous@undisclosed.example.com) — 2008-11-03T03:20:55+0200

JVM Instructions Reference From JVM Spec: * JVM Instruction Summary * Example instruction descriptions: * iadd * imul * iload * istore * bipush JVM Instruction Description from JavaTech book What instructions operate on: * operands that are part of instruction itself, following their op code (unique number for instruction)

compilation:jvm_spec

Anonymous (anonymous@undisclosed.example.com) — 2012-11-21T00:24:32+0200

The Java Virtual Machine Specification * The complete JVM specification. Instruction list is in Chapter 6 (as of 2012) * opcodes arranged conveniently, in particular:by function * Cafebabe documentation You can also consult Appendix B of the book: Aarne Ranta: Implementing Programming Languages, Texts in Computing 16, College Publications, 2012

compilation:lab02-compiler.scala

Anonymous (anonymous@undisclosed.example.com) — 2008-09-26T13:19:15+0200

package minijava import lexer.Lexer class Compiler extends Reporter with Lexer { import lexer.Tokens._ def printTokens: Unit = { var t: Token = Token(BAD) do { t = nextToken print(t.kind + "(" + t.row + "," + t.col + ") ") } while(t.kind != EOF) terminateIfErrors } }

compilation:lab02-factorial.java

Anonymous (anonymous@undisclosed.example.com) — 2008-09-23T21:06:54+0200

class Factorial { public static void main(String[] a) { System.out.println(new Fac().ComputeFac(10)); } } class Fac { // end-of-line comment public int ComputeFac(int num) { int num_aux; if(num < 1) /* block comment */ num_aux = 1; else num_aux = num * (this.ComputeFac(num-1)); return num_aux; } }

compilation:lab02-lexer.scala

Anonymous (anonymous@undisclosed.example.com) — 2008-09-26T13:18:58+0200

package minijava.lexer import java.io.{InputStream, IOException} trait Lexer { // This indicates to the compiler that this trait will be composed // with a Reporter. This implies that the methods from the Reporter // trait will be available at run-time. self: Reporter => import Tokens._ // the input stream private var in: InputStream = _ /** Sets the input stream to use for lexing. */ def setInputStream(input: InputStream): Unit = { in = input // ... } …

compilation:lab02-main.scala

Anonymous (anonymous@undisclosed.example.com) — 2008-09-26T13:20:57+0200

package minijava import java.io.{FileInputStream,IOException} object Main { def main(args: Array[String]) { val compUnit = new Compiler() if (args.length != 1) compUnit.fatalError("usage: scala minijava.Main ") try { val in = new FileInputStream(args(0)) compUnit.setInputStream(in) compUnit.printTokens in.close() } catch { case e: IOException => compUnit.fatalError(e.getMessage) } compUnit.terminat…

compilation:lab02-positional.scala

Anonymous (anonymous@undisclosed.example.com) — 2008-09-26T13:17:53+0200

package minijava /** This trait applies to every object to which a corresponding position * in the input source file can be associated. This information is useful * in error messages, for instance. */ trait Positional { self => var row: Int = -1 var col: Int = -1 def setPos(row: Int, col: Int): Unit = { this.row = row this.col = col } /** Copies the position from another Positional object. Returns the * object on which the setPos method was called. */ def setPos…

compilation:lab02-reporter.scala

Anonymous (anonymous@undisclosed.example.com) — 2008-09-26T13:16:45+0200

package minijava trait Reporter { private var foundErrors = false /** Simple warnings */ def warn(msg: String) = outputErrorMsg("Warning", msg) def warn(msg: String, pos: Positional) = outputErrorMsg("Warning", msg, pos) /** Non-fatal errors. The compiler should call terminateIfErrors * before the errors can have an impact (for instance at the end * of the phase). */ def error(msg: String) = { foundErrors = true; outputErrorMsg("Error", msg) } def error(msg: String, po…

compilation:lab02-tokens.scala

Anonymous (anonymous@undisclosed.example.com) — 2008-09-26T13:20:12+0200

package minijava.lexer object Tokens { sealed abstract class TokenKind case object BAD extends TokenKind /* represents incorrect tokens. */ case object EOF extends TokenKind case object SEMICOLON extends TokenKind /* ; */ /* etc. */ case class ID(value: String) extends TokenKind /* Identifiers */ /* etc. */ /* A Token is a positional wrapper around a TokenKind */ class Token(val kind: TokenKind) extends Positional /* Used to create tokens by writing simply: To…

compilation:lab04-compiler.scala

Anonymous (anonymous@undisclosed.example.com) — 2008-10-08T02:31:55+0200

package minijava import parser.Parser class Compiler extends Reporter with Parser

compilation:lab04-main.scala

Anonymous (anonymous@undisclosed.example.com) — 2008-10-08T02:30:53+0200

package minijava import java.io.{FileInputStream,IOException,ByteArrayInputStream} object Main { def main(args: Array[String]) { val compUnit = new Compiler() var parsedTree: Option[parser.Trees.Tree] = None if (args.length != 1) compUnit.fatalError("usage: scala minijava.Main ") try { val in = new FileInputStream(args(0)) parsedTree = Some(compUnit.parseInputStream(in)) println(TreePrinter(parsedTree.get)) in.close() } c…

compilation:lab04-parser.scala

Anonymous (anonymous@undisclosed.example.com) — 2008-10-08T14:20:38+0200

package minijava.parser import minijava.lexer.Lexer import java.io.{InputStream,IOException} /** LL(2) parser for the MiniJava+ grammar. */ trait Parser extends Lexer { self: Reporter => import Trees._ import minijava.lexer.Tokens._ def parseInputStream(in: InputStream): Tree = { setInputStream(in) // from Lexer /* ... */ val tree: Tree = parseGoal tree } /** Store the currentToken (first lookahead), and upcomingToken (second lookahead), as read from the…

compilation:lab04-prettyprinter.scala

Anonymous (anonymous@undisclosed.example.com) — 2008-10-08T02:29:27+0200

package minijava object TreePrinter { import parser.Trees._ def apply(t: Tree): String = { /* construct and return the appropriate string ... */ } }

compilation:lab04-tokens.scala

Anonymous (anonymous@undisclosed.example.com) — 2008-10-08T02:07:29+0200

package minijava.lexer object Tokens { sealed trait TokenClass { self => def tokenClass: self.type = self } case object IDCLASS extends TokenClass { override def toString: String = "identifier" } case object NUMLITCLASS extends TokenClass { override def toString: String = "integer literal" } case object STRLITCLASS extends TokenClass { override def toString: String = "string literal" }} sealed trait TokenInfo { def tokenClass: TokenClass } case object BAD ex…

compilation:lab04-trees.scala

Anonymous (anonymous@undisclosed.example.com) — 2008-10-08T02:11:07+0200

package minijava.parser object Trees { sealed trait Tree extends Positional case class Program(main: MainClass, classes: List[ClassDecl]) extends Tree case class MainClass(id: Identifier, mainarg: Identifier, stat: StatTree) extends Tree /* etc. */ sealed trait TypeTree extends Tree case class IntType extends TypeTree /* etc. */ sealed trait StatTree extends Tree case class Block(stats: List[StatTree]) extends StatTree /* etc. */ sealed trait ExprTree ext…

compilation:lab06analyzer

Anonymous (anonymous@undisclosed.example.com) — 2008-10-22T06:44:44+0200

package minijava.analyzer trait Analyzer { self: Reporter => import parser.Trees._ import Symbols._ def analyzeSymbols(prog: Program): GlobalScope = { val gs = collectSymbols(prog) terminateIfErrors setSymbols(prog, gs) gs } private def collectSymbols(prog: Program): GlobalScope = /* ... */ private def setSymbols(prog: Program, gs: GlobalScope): Unit = /* ... */ }

compilation:lab06compilerstub

Anonymous (anonymous@undisclosed.example.com) — 2008-10-22T06:54:53+0200

package minijava import parser.Parser import analyzer.Analyzer class Compiler extends Reporter with Parser with Analyzer { import java.io.{FileInputStream,IOException,ByteArrayInputStream} def compile(fileName: String): Unit = { import parser.Trees._ import analyzer.Symbols._ // Parsing var parsedTree: Option[Tree] = None try { val in = new FileInputStream(fileName) parsedTree = Some(parseInputStream(in)) in.close() } catch { case e: IO…

compilation:lab06mainstub

Anonymous (anonymous@undisclosed.example.com) — 2008-10-22T06:55:27+0200

package minijava object Main { def main(args: Array[String]) { val compUnit = new Compiler() var parsedTree: Option[parser.Trees.Tree] = None if (args.length != 1) compUnit.fatalError("usage: scala minijava.Main ") compUnit.compile(args(0)) } }

compilation:lab06symbols

Anonymous (anonymous@undisclosed.example.com) — 2008-10-22T08:28:51+0200

package minijava.analyzer import scala.collection.mutable.HashMap object Symbols { /** A trait for anything that refers to a symbol. */ trait Symbolic[S <: Symbol] { self => private var _sym: Option[S] = None def setSymbol(sym: S): self.type = { _sym = Some(sym) this } def getSymbol: S = _sym match { case Some(s) => s case None => scala.Predef.error("Accessing undefined symbol.") } } /** Notice that creating a symbol wi…

compilation:lab06treeprinter

Anonymous (anonymous@undisclosed.example.com) — 2008-10-22T06:54:19+0200

package minijava object TreePrinter { import parser.Trees._ /** TreePrinter(tree) will produce the same result as before. */ def apply: (Tree=>String) = apply(false)_ /** TreePrinter.withSymbolIDs(tree) will print the tree with the IDs. */ def withSymbolIDs: (Tree=>String) = apply(true)_ /** We added a parameter and currified the method to build the other two. */ private def apply(withSymbolIDs: Boolean)(t: Tree) = { /* code you had before... */ // ... // Th…

compilation:lab06trees

Anonymous (anonymous@undisclosed.example.com) — 2008-10-22T06:48:24+0200

package minijava.parser object Trees { import analyzer.Symbols._ sealed trait Tree extends Positional // You should of course not copy this file into your project. // Rather, observe how the symbols of the proper symbol types are // attached to the trees, and reproduce this by adapting it to your own AST nodes. // ... case class MainClass(id: Identifier, mainarg: Identifier, stat: StatTree) extends Tree with Symbolic[ClassSymbol] case class ClassDecl(id: Identifier, paren…

compilation:lab08-compiler

Anonymous (anonymous@undisclosed.example.com) — 2008-10-29T03:44:47+0200

package minijava import parser.Parser import analyzer.Analyzer import analyzer.TypeChecker class Compiler extends Reporter with Parser with Analyzer with TypeChecker { import java.io.{FileInputStream,IOException,ByteArrayInputStream} def compile(fileName: String): Unit = { import parser.Trees._ import analyzer.Symbols._ // Parsing var parsedTree: Option[Tree] = None try { val in = new FileInputStream(fileName) parsedTree = Some(parseInp…

compilation:lab08-typechecker

Anonymous (anonymous@undisclosed.example.com) — 2008-10-29T04:04:01+0200

package minijava.analyzer trait TypeChecker { self: Reporter => import Symbols._ import Types._ import parser.Trees._ /** Typechecking does not produce a value, but has the side effect of * attaching types to trees and potentially outputting error messages. */ def typeCheck(prog: Program, gs: GlobalScope): Unit = { /** Suggested inner function: * * Computes the type of an expression. If exp is not empty, checks that * the expression is a subtype of one i…

compilation:lab08-types

Anonymous (anonymous@undisclosed.example.com) — 2008-10-29T03:52:41+0200

package minijava.analyzer object Types { import Symbols._ sealed abstract class Type { // we suggest you implement this to make type checking easier def isSubTypeOf(tpe: Type): Boolean } // having this "bottom" class (which extends every other one) can be convenient for error recovery... case object TError extends Type { override def isSubTypeOf(tpe: Type): Boolean = true override def toString = "[error]" } // the default type for all Typed objects case ob…

compilation:lab09-codegen

Anonymous (anonymous@undisclosed.example.com) — 2008-11-10T17:23:28+0200

package minijava.code trait CodeGenerator { self: Reporter => import parser.Trees._ import analyzer.Symbols._ import analyzer.Types._ import cafebabe._ // Bytecodes import AbstractByteCodes._ import ByteCodes._ /** Writes the proper .class file in a given directory. An empty string for dir is equivalent to "./". */ def generateClassFile(gs: GlobalScope, ct: ClassDecl, dir: String): Unit = { // ... } }

compilation:lab09-compiler

Anonymous (anonymous@undisclosed.example.com) — 2008-11-10T17:24:53+0200

package minijava import parser.Parser import analyzer.Analyzer import analyzer.TypeChecker import code.CodeGenerator class Compiler extends Reporter with Parser with Analyzer with TypeChecker with CodeGenerator { import java.io.{File,FileInputStream,IOException,ByteArrayInputStream} def compile(fileName: String, classDir: String): Unit = { import parser.Trees._ import analyzer.Symbols._ val outputDir = classDir + "/" val checkDir: File = new File(…

compilation:lab09-main

Anonymous (anonymous@undisclosed.example.com) — 2008-11-10T17:25:24+0200

package minijava object Main { def main(args: Array[String]) { val compUnit = new Compiler() var parsedTree: Option[parser.Trees.Tree] = None if (args.length != 1 && args.length != 3) { compUnit.fatalError("usage: minijavac [-d outputdir]") } if(args.length == 1) { compUnit.compile(args(0), "./") } else { if(!"-d".equals(args(1))) { compUnit.fatalError("Unrecognized option: " + args(1)) } compUnit.compile…

compilation:lab11-asttocfgstub

Anonymous (anonymous@undisclosed.example.com) — 2008-11-25T17:59:15+0200

package minijava.controlflow object ASTtoCFG { import parser.Trees._ import analyzer.Symbols._ import analyzer.Types._ import CFGTrees._ /** Builds a control flow graph from a method declaration. */ def convertAST(meth: MethodDecl): CFG = { val cfg: CFG = new CFG type Vertex = cfg.Vertex /** Creates fresh variable names on demand. */ object FreshName { var count = 0 def apply(prefix: String): String = { val post = count …

compilation:lab11-cfg

Anonymous (anonymous@undisclosed.example.com) — 2008-11-25T17:53:54+0200

package minijava.controlflow import CFGTrees._ class CFG extends LabeledDirectedGraphImp[CFGStatement] { val entry: Vertex = newVertex val exit: Vertex = newVertex entry.name = "entry" exit.name = "exit" override def toString = "[>" + entry + super.toString + exit + "<]" }

compilation:lab11-cfgtrees

Anonymous (anonymous@undisclosed.example.com) — 2008-11-25T17:54:18+0200

package minijava.controlflow object CFGTrees { import analyzer.Symbols._ import analyzer.Types._ sealed abstract class CFGTree { override def toString = stringRepr(this) } sealed abstract class CFGStatement extends CFGTree case class CFGAssign(variable: CFGVariable, expr: CFGExpression) extends CFGStatement case class CFGAssignBinary(variable: CFGVariable, lhs: CFGSimpleValue, binOp: CFGBinaryOperator, …

compilation:lab11-compmods

Anonymous (anonymous@undisclosed.example.com) — 2008-11-25T18:16:49+0200

// ... def compile(fileName: String, classDir: String): Unit = { // ... // Adapt this to your class hierarchy and add it after the type checking code. // You can also comment out the class files generation for this lab to save some time. mainProg.classes.foreach(ct => { ct.methods.foreach(m => { val cfg = controlflow.ASTtoCFG.convertAST(m) cfg.writeDottyToFile(ct.getSymbol.name + "-" + m.getSymbol.name + ".dot") }) }) // ... } // ...

compilation:lab11-dfa

Anonymous (anonymous@undisclosed.example.com) — 2008-12-03T06:47:10+0200

package minijava.controlflow abstract class TransferFunction[L, CFGStatement] { def apply(node : CFGStatement, x : L) : L } class AnalysisAlgoritm[L,CFGStatement] (transferFun : TransferFunction[L, CFGStatement], lattice : Lattice{type Elem=L}, cfg : LabeledDirectedGraphImp[CFGStatement]) { type Vertex = VertexImp[CFGStatement] var facts : Map[Vertex, L] = Map[Vertex,L]() def init = { facts = Map[Vertex,L]().withDefaultValue(lattice.bottom) } def s…

compilation:lab11-labeleddirectedgraph

Anonymous (anonymous@undisclosed.example.com) — 2008-12-03T06:45:10+0200

package minijava.controlflow /** Mutable Directed Graph with Labels */ abstract trait LabeledDirectedGraph[LabelType] { /** The type of the vertices */ type Vertex /** The type of the edges */ type Edge /** The vertices */ def V: Set[Vertex] /** The edges */ def E: Set[Edge] /** Adds a new vertex to the graph */ def newVertex: Vertex /** Adds a new labeled edge between two vertices */ def += (from: Vertex, lab: LabelType, to: Vertex) /** Returns the set of incoming edg…

compilation:lab11-lattices

Anonymous (anonymous@undisclosed.example.com) — 2008-12-03T06:46:29+0200

package minijava.controlflow trait PartialOrder { type Elem def leq(x : Elem, y : Elem) : Boolean // less than or equal } trait Lattice extends PartialOrder { val top : Elem // universal set val bottom : Elem // empty set def join(x : Elem, y : Elem) : Elem // union def meet(x : Elem, y : Elem) : Elem // intersection } // there should be more elegant definition--but make sure domain of results are correct class PointwiseLattice[I,E,L …

compilation:lab11-ldg

Anonymous (anonymous@undisclosed.example.com) — 2008-11-25T17:53:19+0200

compilation:labs_01

Anonymous (anonymous@undisclosed.example.com) — 2008-09-17T08:12:38+0200

Labs 01 This week you will build an interpreter in Scala for the while language described in Lecture 01. You don't have to write a lexer/parser, as you will instead work directly on the Abstract Syntax Tree (AST) representation of programs. The language is slightly different here as we have added

compilation:labs_02

Anonymous (anonymous@undisclosed.example.com) — 2008-09-26T10:41:11+0200

Labs 02 This assignment is the first part of the MiniJava+ compiler project. Make sure you read the general project overview page first. Please also send Philippe an email as soon as possible stating who are the (two) members of your group. Test case corpus (due in one week) Write two small MiniJava+ programs per person (four per group) to constitute a corpus of test cases that we will use throughout the compiler project. We will check that all benchmarks are correct MiniJava+ programs and di…

compilation:labs_03

Anonymous (anonymous@undisclosed.example.com) — 2008-09-29T13:56:38+0200

Labs 03 Finish Labs 02.

compilation:labs_04

Anonymous (anonymous@undisclosed.example.com) — 2008-10-10T15:19:57+0200

Labs 04 This week and the next one, you'll work on the second part of the MiniJava+ Compiler Project. Your goal is to manually implement a recursive-descent parser to transform programs described by the MiniJava+ grammar into Abstract Syntax Trees. You also need to write a pretty-printer for these trees. This assignment is rather long and we can only recommend that you start early, that you make sure you understand every step and that you ask otherwise.

compilation:labs_05

Anonymous (anonymous@undisclosed.example.com) — 2008-10-11T01:34:05+0200

Labs 05 Finish Labs 04.

compilation:labs_06

Anonymous (anonymous@undisclosed.example.com) — 2008-11-04T18:03:34+0200

Labs 06 This week you will add name analysis to your MiniJava+ compiler. This will considerably ease the task of type checking that you will start next week or the week after. Your analyzer is due on Wednesday, Nov. 5th, 8.15am. The description of this assignment is rather long. Don't panic :) Most of it is to help you avoid forgetting important points, and we give you a substantial amount of code.

compilation:labs_07

Anonymous (anonymous@undisclosed.example.com) — 2008-10-27T20:02:05+0200

Labs 07 Finish labs 06 or start labs 08.

compilation:labs_08

Anonymous (anonymous@undisclosed.example.com) — 2008-11-05T10:20:27+0200

Well, for some definition of (in)valid.

compilation:labs_09

Anonymous (anonymous@undisclosed.example.com) — 2008-11-24T14:53:53+0200

Labs 09 Congratulations, your front-end is complete! You are now one step (and two weeks) away from having written a complete compiler. This week's lab description and stubs are rather short. It's not that we don't want to help you anymore, it's just that the tasks should be straightforward :)

compilation:labs_10

Anonymous (anonymous@undisclosed.example.com) — 2008-11-03T18:48:31+0200

Labs 10 Finish labs 09.

compilation:labs_11

Anonymous (anonymous@undisclosed.example.com) — 2008-11-25T20:23:13+0200

Labs 11 Today, Nov 26th, you hand in a working MiniJava+ to JVM compiler, congratulations! Hopefully it will do well in the cc08 competition. This week you will write a translation from your MiniJava+ ASTs to Control Flow Graphs (CFGs), similarly to what was shown for the while language in

compilation:labs_12

Anonymous (anonymous@undisclosed.example.com) — 2008-12-03T19:40:12+0200

Labs 12 This is the last lab, you're almost there :) Due date is Saturday, Jan. 10th, 2009. In this lab, you will implement range analysis, and will use it to try and prevent potential ArrayIndexOutOfBoundsExceptions. The lab can seem long at first, but if you follow the steps you should be just fine. The starting one (adding

compilation:labs_13

Anonymous (anonymous@undisclosed.example.com) — 2008-12-04T11:41:39+0200

Labs 13 No more labs, finish Labs 12.

compilation:labs_14

Anonymous (anonymous@undisclosed.example.com) — 2008-11-03T18:53:06+0200

Labs 14, aka. final written exam No labs this week. Answer the questions in the exam instead.

compilation:lambda_calculi_with_types

Anonymous (anonymous@undisclosed.example.com) — 2008-10-21T19:13:27+0200

Lambda Calculi with Types [Henk Barendregt: Lambda Calculi with Types]

compilation:lambda_calculus

Anonymous (anonymous@undisclosed.example.com) — 2015-04-21T17:34:55+0200

Lambda Calculus Lambda calculus is a simple and powerful notation for defining functions. Among its uses are * foundation of programming languages, especially functional languages such as Ocaml, Haskell, and Scala * basis of higher order logic

compilation:languages_using_prefix_or_postfix_only

Anonymous (anonymous@undisclosed.example.com) — 2008-11-02T19:40:59+0200

Languages using Prefix or Postfix Only Prefix: LISP LISP (1958) = * LISt Processing * Lost In Single Parentheses 50th anniversary of LISP * recursive definitions * lists as data structure for symbolic processing * widely used in AI * introduced automated memory management

compilation:lattices.scala

Anonymous (anonymous@undisclosed.example.com) — 2008-11-24T02:50:06+0200

trait PartialOrder { type Elem def leq(x : Elem, y : Elem) : Boolean // less than or equal } trait Lattice extends PartialOrder { val top : Elem // universal set val bottom : Elem // empty set def join(x : Elem, y : Elem) : Elem // union def meet(x : Elem, y : Elem) : Elem // intersection } // there should be more elegant definition--but make sure domain of results are correct class PointwiseLattice[I,E,L <: Lattice{type Elem=E}](base …

compilation:lattices_in_dataflow_analysis

Anonymous (anonymous@undisclosed.example.com) — 2008-11-17T02:53:52+0200

Lattices in Dataflow Analysis Interpreter maintains mapping from variables to states Dataflow analysis works with abstractions of sets of states--these are elements of a lattice Keep in mind that they are just representations of certain sets of states

compilation:lecture_01

Anonymous (anonymous@undisclosed.example.com) — 2008-09-15T13:45:38+0200

Lecture 01: Introduction and Lexical Analysis Course Information Compilers and Interpreters What is a Compiler Compilers in Action Phases of a Compiler Why Study Compilers Alternatives to Compilation Specifying Language Syntax While Language Abstract Syntax of While Strings and languages Regular expression Tokens (Words) of While Language Context-Free Grammars Concrete Syntax of While Lexical Analysis without Tools Why Study Lexical Analysis Hand-Written Scanner for While Langu…

compilation:lecture_02

Anonymous (anonymous@undisclosed.example.com) — 2008-09-24T12:06:21+0200

Lecture 02: Automating Lexing. Intro to Parsing Check Course Information for new resources Continuation of Lecture 01 Recall Phases of a Compiler Automating Lexical Analysis State Machines from Regular Expressions (done in exercises) Finite state machine Determinization of finite state machine Finite state machine with epsilon transitions Closure properties of finite state machines From Finite State Machines to Regular Expressions

compilation:lecture_03

Anonymous (anonymous@undisclosed.example.com) — 2008-09-29T14:20:45+0200

Lecture 03: Parsing A classic book Recursive Descent Parsing CYK Parsing Algorithm Transforming to Chomsky Normal Form References * Tiger book, Sections 3.1, 3.2 * Slides from previous years: english, french * Compiler Construction by Niklaus Wirth, Chapter 4 * Compiler Construction Tools * MiniJava * AhoUllman

compilation:lecture_04

Anonymous (anonymous@undisclosed.example.com) — 2008-10-05T22:18:55+0200

Lecture 04: Finishing Parsing. Semantic Actions and Building Syntax Trees Summary of Table-Driven LL(1) Parsing Algorithm for First and Follow Sets Building LL Parsing Table Interpreting LL Parsing Table Abstract Syntax Trees Notion of Syntax Trees Modifying Parser to Construct Trees Building a Pretty Printer LR Parsing Preparation Earley Parser Pushdown Automata LR Parsing LL Parser uses Leftmost Derivation LR Parser uses Rightmost Derivation LR Parser Runs Automaton over Stack …

compilation:lecture_05

Anonymous (anonymous@undisclosed.example.com) — 2009-10-15T15:38:30+0200

Lecture 05: Basic Semantic Analysis and Type Checking Interpretation versus Semantic Analysis Java Example for Semantic Analysis Maps in Math Handling Scopes in Interpreters Semantic Analysis as Simplified Interpretation Reporting Errors from Semantic Analysis Reporting Errors Based on Syntax Tree Symbol Table (Environment) Implementation Symbol Table Contents Functional versus Imperative Maps An Efficient Imperative Map An Efficient Functional Map Efficient Comparison for Identifie…

compilation:lecture_06

Anonymous (anonymous@undisclosed.example.com) — 2008-10-26T11:42:03+0200

Lecture 06: Type Checking Typing Rules for Simple Language Lambda Calculus Simple Types for Lambda Calculus Type Checking Let and Letrec Operational Semantics of Lambda with Letrec References * Types and Programming Languages, Chapter 5, Chapter 8, Sections 9.1--9.3 (pages 89-107) * Lambda Calculi with Types

compilation:lecture_07

Anonymous (anonymous@undisclosed.example.com) — 2008-11-01T17:00:55+0200

Type System Soundness. Subtyping Continuing Lecture 06 Type Soundness Theorems Proving Safety Properties using Types Type Soundness for Simply Typed Lambda Calculus Subtyping Notion of Subtyping Subtyping for Functions Subtyping for Assignments References * [A Syntactic Approach to Type Soundness] * Foundations of Software, the EPFL master's level course taught by Prof. Martin Odersky, covers type systems in great depth * Types and Programming Languages, Chapter 5, Chapter 8, Sec…

compilation:lecture_08

Anonymous (anonymous@undisclosed.example.com) — 2008-11-03T12:05:00+0200

Lecture 08: Code Generation for Stack Machines Overview Recall * Phases of a Compiler * Compilers in Action Overview of Compiling to Stack Machine JVM Instructions Compiled Expression Examples Compiled Counting Examples Compiled Factorial Example Compiling Expressions VM for Expressions Prefix Infix Postfix Notation Printing Prefix Infix Postfix Languages using Prefix or Postfix Only Evaluating Postfix Translating Expressions to Stack Machine Translation Correctness for Expre…

compilation:lecture_09

Anonymous (anonymous@undisclosed.example.com) — 2008-11-10T18:02:40+0200

Lecture 09: Compiling Control Flow Recall Lecture 08 * today: the translation of the remaining constructs into JVM Compiling Control-Flow Statements Booleans and Data Representation Linearizing Trees with Control-Flow Branching JVM Instructions Compiling If Then Else Computing Labels Compiling While Compiling Boolean Operators Translation of Relations Postfix Translation of Boolean Operators Compiling Conditional Expressions Short-Circuit Evaluation Better Code Generation for Co…

compilation:lecture_10

Anonymous (anonymous@undisclosed.example.com) — 2008-11-25T13:48:40+0200

Lecture 10: Basics of Dataflow Analysis through Examples Idea of Data Flow Analysis Control-Flow Graph Definition Interpreting CFG Translating Syntax Tree to CFG Constant Propagation Sign Analysis Initialization Analysis Partial order and Lattices Lattices in Dataflow Analysis Continued in Lecture 11 and Lecture 12 Reference * [Lecture notes on static analysis by Michael Schwartzbach] * Tiger book, chapters 10, 17

compilation:lecture_11

Anonymous (anonymous@undisclosed.example.com) — 2008-11-25T13:48:19+0200

Lecture 11: Data-Flow Analysis in Scala Continuation of Lecture 10 Outline: * Control-Flow Graphs in Scala * Translating While Language to CFG * Lattices in Scala * Sign Analysis Sources: * DiGraphs.scala * SimpleCFG.scala * SimpleAST.scala * SimpleTranslate.scala * Lattices.scala * DataFlowAnalysis.scala * SignAnalysis.scala Continued in Lecture 12

compilation:lecture_12

Anonymous (anonymous@undisclosed.example.com) — 2008-11-25T19:12:53+0200

Lecture 12: Applications and Methodology of Data-Flow Analysis Continuation of Lecture 11. Recall: * Lattices.scala * DataflowAnalysis.scala * SignAnalysis.scala Applications of Data-Flow Analysis Concrete Execution as Data-Flow Analysis Designing Correct Data-Flow Analyses Termination of Data-Flow Analysis Java Definite Assignments Initialization Analysis Live Variable Analysis Range Analysis Typestate Analysis

compilation:lecture_13

Anonymous (anonymous@undisclosed.example.com) — 2008-12-08T03:33:22+0200

Lecture 13: Code Generation for Register Machines Remarks: * htmldoc * today we talk about machine code generation Overview of an Optimizing Compiler Recall the Stack Machine: VM for Expressions ARM Architecture Register Machine in Scala xyz Example using GCC Control-Flow Graph to Assembly with Global Variables Register Allocation using Liveness Information Memory Layout for Compiled Program Stack Frames and Procedure Calls Local, Higher-Order, and Dispatched Procedures Instruct…

compilation:lecture_14

Anonymous (anonymous@undisclosed.example.com) — 2008-12-15T10:10:11+0200

Lecture 14: Dynamic Memory Management Recall Memory Layout for Compiled Program * we discuss how to manage the heap (dynamicaly allocated memory) * essential for building structures such as linked lists, trees * implementation of 'new' * contrast to stack Malloc and Free * MallocInfMem.scala * MallocFree.scala * Free Lists by Size

compilation:lecture_15

Anonymous (anonymous@undisclosed.example.com) — 2008-11-25T14:58:48+0200

Lecture 15 - Not (Necessary) Taught This page contains the “Lecture 15” -- material that was not covered in the course Compiling to Low-Level Object Code Basics of Type Inference Constraint-Based Type Checking Note on Polymorphism and Subtyping Misc Trivia Bad Languages

compilation:lexer.scala

Anonymous (anonymous@undisclosed.example.com) — 2008-09-28T14:55:21+0200

class Lexer(ch : CharStream) { val EOL = '\n' val keywords = Map("while" -> WHILE, "if" -> IF, "println" -> PRINTLN, "readln" -> READLN) var current : Token = EOF private def skippedComment : Boolean = { if (ch.current == '/') { ch.next if (ch.current == '/') { ch.next while ((ch.current != EOL) && !ch.eof) ch.next true } else { current = DIV false } } else { false } } private def skipSpaces = { while (((ch.…

compilation:lexerinterface.scala

Anonymous (anonymous@undisclosed.example.com) — 2008-09-10T23:05:13+0200

class Lexer(ch : CharStream) { var current : Token def next : Unit = { ... } }

compilation:lexertest.scala

Anonymous (anonymous@undisclosed.example.com) — 2008-09-11T21:01:23+0200

object LexerTest { def main(args : Array[String]) = { val lex = new Lexer(new CharStream(args(0))) while (lex.current != EOF) { println(lex.current) lex.next } } }

compilation:limitations_of_regular_expressions

Anonymous (anonymous@undisclosed.example.com) — 2008-09-23T22:38:05+0200

Limitations of Regular Expressions Parentheses in expressions, statement blocks {{}{{{}{}}{}}}{}{{}{}} { {} {{{}{}}{}} } {} {{}{}} The language of balanced (matched) parentheses (here: curly braces) * at each point count number of open minus number of closed parantheses

compilation:linearizing_trees_with_control-flow

Anonymous (anonymous@undisclosed.example.com) — 2008-11-09T14:50:56+0200

Linearizing Trees with Control-Flow Evaluating control-flow in interpreter is easy * recall the interpreter in Labs 01 * recall Handling Scopes in Interpreters statement match { ... case IfStat(cond,sThen,sElse) => { interpExpr(e)(cond) match { case BoolValue(b) => { if (b) { interpStats(e, UnitValue, sThen :: stmts1) } else { interpStats(e, UnitValue, sElse :: stmts1) } } case _ => error("Expected boolean as condition") } } …

compilation:links

Anonymous (anonymous@undisclosed.example.com) — 2008-08-23T21:41:39+0200

Compilation: Useful Links Schedule [Official Schedule] Official Course Description The Team Lectures: * Viktor Kuncak Exercises: * Philippe Suter * Ruzica Piskac Assistants-Étudiants * Sebastian Gfeller * Cédric Lavanchy Textbook * Modern Compiler Implementation in Java (2nd Edition): * Andrew Appel's web site * 2nd Edition from Cambridge University Press * 2nd Edition from Amazon.com *

compilation:live_variable_analysis

Anonymous (anonymous@undisclosed.example.com) — 2015-04-21T17:34:55+0200

Live Variable Analysis For each program point, and each variable approximately compute whether the variable is live at that program point Definition: a variable is dynamically live in a concrete program state , if there exists a finite sequence of steps

compilation:ll_parser_uses_leftmost_derivation

Anonymous (anonymous@undisclosed.example.com) — 2008-10-05T19:05:07+0200

LL Parser Uses Leftmost Derivation LL parser, as given by Interpreting LL Parsing Table * decides what production to use * uses stack to remember this right-hand side Parsing is opposite of grammar derivation For grammar E ::= T | T + E T ::= ID a leftmost derivation of ID+ID+ID from E is:

compilation:llvm-intro

Anonymous (anonymous@undisclosed.example.com) — 2011-12-02T16:38:49+0200

Introduction to Using LLVM as a Compiler Backend Assembly and bitcode files The LLVM intermediate representation (IR) language comes with two formats: * bitcode, a binary representation, typically stored in .bc files, and * assembly, an human-readable (text) representation, typically stored in

compilation:local_higher-order_and_dispatched_procedures

Anonymous (anonymous@undisclosed.example.com) — 2008-12-08T02:29:08+0200

Local, Higher-Order, and Dispatched Procedures Simple Local (Nested) Procedures Nested functions can access outside functions. def saveData(f : File) = { def wr(s : String) = { writeStringToFile(f, s) } def wrInt(x : Int) = { wr(integerToString(x)) } wr("") wr("This is my page.") wrInt(2008) wr("") }

compilation:lr_0_parser_actions

Anonymous (anonymous@undisclosed.example.com) — 2008-10-05T21:29:16+0200

LR(0) Parser Actions Let K be parser state at the end of stack and t current token: * if there is a transition for non-empty * shift: push t onto stack * if t is EOF, then accept * reduce: if item K then * pop p from stack (it will be there)

compilation:lr_1_parser_actions

Anonymous (anonymous@undisclosed.example.com) — 2008-10-11T17:43:08+0200

LR(1) Parser Actions This is a natural generalization of SLR Parser Actions Let K be parser state at the end of stack and t current token: * if there is a transition for non-empty * shift: push t onto stack * if t is EOF, then accept * reduce: if item

compilation:lr_parser_runs_automaton_over_stack

Anonymous (anonymous@undisclosed.example.com) — 2008-10-05T19:53:10+0200

LR Parser Runs Automaton over Stack Key question in LR parsing * when to shift * when to reduce, and using which rule Key property: Stack contains a prefix of rightmost derivation consistent with the input so far Next action should preserve this property if possible

compilation:lr_parser_uses_rightmost_derivation

Anonymous (anonymous@undisclosed.example.com) — 2008-10-05T19:05:33+0200

LR Parser Uses Rightmost Derivation In contrast, LR parser * uses rightmost derivation * accumulates right-hand side on stack * then decides which production to use We look at this rightmost derivation backwards, so: * left-to-right parsing

compilation:lr_parsing_tables

Anonymous (anonymous@undisclosed.example.com) — 2008-10-05T22:53:57+0200

LR Parsing Tables So far we assumed that the state (set of items) is given by * always starting in initial state * re-running automaton on entire stack Instead, LR parsers * keep state corresponding to last run * update the state on 'shift'

compilation:lr_parsing_with_lookahead_items

Anonymous (anonymous@undisclosed.example.com) — 2015-04-21T17:34:55+0200

LR Parsing with Lookahead Items Although SLR Parser Actions use lookahead, their finite state machine is computed without considering lookahead LR(k) parser uses more general LR(k) items We explain LR(1) LR(1) item is (X::=p.q,a), written X ::= p.q a where *

compilation:main.scala

Anonymous (anonymous@undisclosed.example.com) — 2008-09-26T13:22:41+0200

package whilelang /** For all programs listed in Programs; prints the code, interprets, simplifies, prints again and re-interprets. */ object Main { def main(args : Array[String]) : Unit = { Programs.programs.foreach(prog => { val (name, code) = prog println("*-*-*-*-*") println("Start of: " + name) println TreePrinter(code) println Interpreter(code) val transformed: Statement = TreeSimplifier(code) println TreePrinter(tra…

compilation:malloc_and_free

Anonymous (anonymous@undisclosed.example.com) — 2008-12-14T19:23:54+0200

Malloc and Free Some programming languages such as C it is programmer's responsibility to allocate and deallocate memory We illustrate this by a model where * ptr=malloc(N) allocates N words of memory and returns a memory address of location for this memory

compilation:mallocfree.scala

Anonymous (anonymous@undisclosed.example.com) — 2008-12-14T18:53:34+0200

// Simple malloc and free, fragmentation possible class Heap(size : Int) { private var mem = new Array[Int](size) // OS would provide this memory private var nextAvailable : Int = 1 // where to allocate next val nextOffset = 0 // offset of 'next' field in free list val sizeOffset = 1 // offset of 'size' field in free list val minFreeListBlockSize = 2 // each free list block must have size at least 2 words // initially, free list contains one block whose size is memory size def …

compilation:mallocinfmem.scala

Anonymous (anonymous@undisclosed.example.com) — 2008-12-14T18:54:22+0200

// This is how to manage memory if it is infinite :) class Heap(size : Int) { private var mem = new Array[Int](size) // OS would provide this memory private var nextAvailable : Int = 0 // where to allocate next def malloc(blockSize : Int) : Int = { val res = nextAvailable nextAvailable = nextAvailable + blockSize initMem(res, nextAvailable) // optional res } def initMem(from : Int, to : Int) = { var i = from while (i < to) { mem(i) = 0; i = i + 1…

compilation:manual_translation_into_bytecode

Anonymous (anonymous@undisclosed.example.com) — 2008-11-14T18:46:08+0200

Translating If Expressions int activityLevel boolean action(int signals, boolean objects, int smart, int pretty) { if ((signals > 5 || !objects) && smart + 2*pretty > 10) { activityLevel++; return true; } else { activityLevel--; return false; } }

compilation:maps_in_math

Anonymous (anonymous@undisclosed.example.com) — 2015-04-21T17:34:55+0200

Maps in Math Mathematical notion of map is a partial function, that is, a function from a subset of to . * * We define Key operation is function update If the value was defined before, now we redefine it. A generalization of update is overriding one map by another:

compilation:mark_and_sweep_collector

Anonymous (anonymous@undisclosed.example.com) — 2008-12-15T01:42:03+0200

Mark and Sweep Garbage Collector Idea: * use free list, as in malloc+free, but do free automatically * mark all reachable objects * insert all unreachable objects into free list How to determine reachable objects? * start from the set of

compilation:memory_fragmentation

Anonymous (anonymous@undisclosed.example.com) — 2008-12-14T22:06:50+0200

Memory Fragmentation Suppose we have only 320 words of memory x1 = alloc(32) x2 = alloc(32) ... x10 = alloc(32) free(x1, 32) free(x3, 32) free(x5, 32) free(x7, 32) free(x9, 32) // now have 160 bytes of free memory z = alloc(50) // fails! Some steps to address this:

compilation:memory_layout_for_compiled_program

Anonymous (anonymous@undisclosed.example.com) — 2008-12-08T00:18:47+0200

Memory Layout for Compiled Program Operating System User Process Code Machine Code User Process Data MaxBlock Stack : \:/ ... /:\ : Dynamically Allocated Heap Global Static Data (Const,Var) 0 Both dynamically allocated heap and stack expand

compilation:method_calls

Anonymous (anonymous@undisclosed.example.com) — 2008-11-09T11:50:02+0200

Method Calls Relevant Instructions Invoking methods: * invokestatic * invokevirtual Returning value from methods: * ireturn * areturn * return Translation Rule for Calls

compilation:minijava

Anonymous (anonymous@undisclosed.example.com) — 2008-09-19T17:56:14+0200

MiniJava MiniJava is the toy language presented in the Tiger book. For the project, we will work on a slight extension to it, MiniJava+. See description of MiniJava.

compilation:minijava_compiler_project

Anonymous (anonymous@undisclosed.example.com) — 2008-09-25T16:02:54+0200

MiniJava+ Compiler Project The main project in this course consists in implementing minijavac, a compiler for a (very slightly) extended version of MiniJava, which we call MiniJava+. You will code all phases of a modern compiler, resulting in an implementation which will allow you to compile source files into Java Bytecode, in the same way

compilation:minijavaplus

Anonymous (anonymous@undisclosed.example.com) — 2008-11-05T09:14:02+0200

MiniJava+ Resource Page MiniJava+ is our extension to MiniJava, and is a strict subset of Java. BNF (reproduced and extended from here) Goal::=MainClass ( ClassDeclaration )* MainClass::=class Identifier { public static void main ( String [ ] Identifier

compilation:minijavaplustyperules

Anonymous (anonymous@undisclosed.example.com) — 2015-04-21T17:34:55+0200

MiniJava+ Type Rules and Constraints The type is used for elements that need to be type-checked but do not carry a type themselves (this includes statements). Class definitions and subtyping Class variables and methods

compilation:mjp-binarysearch

Anonymous (anonymous@undisclosed.example.com) — 2008-09-26T11:55:14+0200

class BinarySearch{ public static void main(String[] a){ System.out.println(new BS().Start(20)); } } // This class contains an array of integers and // methods to initialize, print and search the array // using Binary Search class BS{ int[] number ; int size ; // Invoke methods to initialize, print and search // for elements on the array public int Start(int sz){ int aux01 ; int aux02 ; aux01 = this.Init(sz); aux02 = this.Print(); if (this.Search(8)) System.ou…

compilation:mjp-binarytree

Anonymous (anonymous@undisclosed.example.com) — 2008-09-26T13:30:22+0200

class BinaryTree{ public static void main(String[] a){ System.out.println(new BT().Start()); } } // This class invokes the methods to create a tree, // insert, delete and serach for elements on it class BT { public int Start(){ Tree root ; boolean ntb ; int nti ; root = new Tree(); ntb = root.Init(16); ntb = root.Print(); System.out.println(100000000); ntb = root.Insert(8) ; ntb = root.Print(); ntb = root.Insert(24) ; ntb = root.Insert(4) ; ntb = root.Insert(12) ; …

compilation:mjp-bubblesort

Anonymous (anonymous@undisclosed.example.com) — 2008-09-26T13:25:45+0200

class BubbleSort{ public static void main(String[] a){ System.out.println(new BBS().Start(10)); } } // This class contains the array of integers and // methods to initialize, print and sort the array // using Bublesort class BBS{ int[] number ; int size ; // Invoke the Initialization, Sort and Printing // Methods public int Start(int sz){ int aux01 ; aux01 = this.Init(sz); aux01 = this.Print(); System.out.println(99999); aux01 = this.Sort(); aux01 = thi…

compilation:mjp-factorial

Anonymous (anonymous@undisclosed.example.com) — 2008-09-26T11:54:36+0200

class Factorial{ public static void main(String[] a){ System.out.println(new Fac().ComputeFac(10)); } } class Fac { public int ComputeFac(int num){ int num_aux ; if (num < 1) num_aux = 1 ; else num_aux = num * (this.ComputeFac(num-1)) ; return num_aux ; } }

compilation:mjp-linearsearch

Anonymous (anonymous@undisclosed.example.com) — 2008-09-26T13:28:52+0200

class LinearSearch{ public static void main(String[] a){ System.out.println(new LS().Start(10)); } } // This class contains an array of integers and // methods to initialize, print and search the array // using Linear Search class LS { int[] number ; int size ; // Invoke methods to initialize, print and search // for elements on the array public int Start(int sz){ int aux01 ; int aux02 ; aux01 = this.Init(sz); aux02 = this.Print(); System.out.println(999…

compilation:mjp-linkedlist

Anonymous (anonymous@undisclosed.example.com) — 2008-09-26T13:29:35+0200

class LinkedList{ public static void main(String[] a){ System.out.println(new LL().Start()); } } class Element { int Age ; int Salary ; boolean Married ; // Initialize some class variables public boolean Init(int v_Age, int v_Salary, boolean v_Married){ Age = v_Age ; Salary = v_Salary ; Married = v_Married ; return true ; } public int GetAge(){ return Age ; } public int GetSalary(){ return Salary ; } public boolean Get…

compilation:mjp-quicksort

Anonymous (anonymous@undisclosed.example.com) — 2008-09-26T13:28:11+0200

class QuickSort{ public static void main(String[] a){ System.out.println(new QS().Start(10)); } } // This class contains the array of integers and // methods to initialize, print and sort the array // using Quicksort class QS{ int[] number ; int size ; // Invoke the Initialization, Sort and Printing // Methods public int Start(int sz){ int aux01 ; aux01 = this.Init(sz); aux01 = this.Print(); System.out.println(9999); aux01 = size - 1 ; aux01 = this.Sort…

compilation:mjp-treevisitor

Anonymous (anonymous@undisclosed.example.com) — 2008-09-26T13:26:28+0200

// The classes are basically the same as the BinaryTree // file except the visitor classes and the accept method // in the Tree class class TreeVisitor{ public static void main(String[] a){ System.out.println(new TV().Start()); } } class TV { public int Start(){ Tree root ; boolean ntb ; int nti ; MyVisitor v ; root = new Tree(); ntb = root.Init(16); ntb = root.Print(); System.out.println(100000000); ntb = root.Insert(8) ; ntb = root.Insert(24) ; ntb = root.Insert(4)…

compilation:modifying_parser_to_construct_trees

Anonymous (anonymous@undisclosed.example.com) — 2008-10-04T20:43:43+0200

Modifying a Parser to Construct Trees Recall our WhileParser.scala * each function returned unit (void) type Now: each function * extracts information from tokens * obtains information from recursive calls * returns a new tree.scala node Result: ParserTrees.scala (email me any errors you notice)

compilation:multiway_branches

Anonymous (anonymous@undisclosed.example.com) — 2008-11-03T02:19:17+0200

Multiway Branches tableswitch lookupswitch

compilation:note_on_polymorphism_and_subtyping

Anonymous (anonymous@undisclosed.example.com) — 2008-10-26T22:40:34+0200

Note on Polymorphism and Subtyping Programming languages such as Scala and (sufficiently recent versions of) Java combine parametric polymorphism with subtyping. There are multiple solutions for how to design a language with these two features, but they are beyond this course

compilation:notion_of_hash-consing

Anonymous (anonymous@undisclosed.example.com) — 2008-10-13T03:50:21+0200

Notion of Hash-Consing Notion of not specific to compilers * and need not be used in compilers A generalization of idea of replacing strings with symbols * ensure we can use pointer equality instead of structural equality * avoid constructing duplicate objects that are equal

compilation:notion_of_subtyping

Anonymous (anonymous@undisclosed.example.com) — 2015-04-21T17:34:55+0200

Notion of Subtyping Subtypes as Subsets In systems we have formally studied so far, each expression had exactly one type, such as 'int' or 'int -> bool' * this is not case any more in systems with subtyping We can often think of a type as approximating the set of values

compilation:notion_of_syntax_trees

Anonymous (anonymous@undisclosed.example.com) — 2008-10-06T10:00:57+0200

Notion of Syntax Trees We have seen how to build a parser * complains if the input is wrong * does absolutely nothing if input is correct :) Next step: have parser create representation of the program * this representation is abstract syntax tree

compilation:object_and_reference_manipulation

Anonymous (anonymous@undisclosed.example.com) — 2008-11-03T02:26:18+0200

Object and Reference Manipulation new ifnull ifnonnull getfield putfield

compilation:official_course_description

Anonymous (anonymous@undisclosed.example.com) — 2008-07-28T12:09:50+0200

Official Course Description The course aims to teach the fundamental aspects of analyzing computer languages and mapping them into executable form. At the end of the course, the student should - be able to define the formal syntax of computer languages, - be able to define the meaning of computer languages through interpreters, - know the internal structure and implementation of simple compilers - be able to write a compiler that maps a simple programming language into the code of a virtua…

compilation:operational_semantics_of_lambda_with_letrec

Anonymous (anonymous@undisclosed.example.com) — 2015-04-21T17:34:55+0200

Operational Semantics of Lambda Calculus with Letrec We describe evaluation rules for our lambda calculus with letrec We need such description to make rigorous proofs about compilers, including type systems This is a mathematical description of an interpreter for this language

compilation:overview_of_an_optimizing_compiler

Anonymous (anonymous@undisclosed.example.com) — 2009-11-22T23:08:45+0200

Overview of an Optimizing Compiler source code int i = 0; /* some comment */ int j = 0; while (i < 10) { System.out.println(j); i = i + 1; j = j + 2*i+1; } Lexer list of tokens INT, Identifier("i"), EQUAL, IntNumeral(0), SEMICOLON, INT, Identifier("j"), EQUAL, ... WHILE, OPENPAREN, Identifier("i"), LESSTHAN, IntNumeral(10), CLOSEDPAREN, OPENBRACE, Identifier("System"), DOT, Identifier("out"), ...

compilation:overview_of_classfile_constant_pool

Anonymous (anonymous@undisclosed.example.com) — 2008-11-10T03:12:22+0200

Overview of Classfile Constant Pool Take abstract syntax tree for method type signatures and constants * serialize it as a graph To see it, use javap -verbose Cafebabe does most of these things for you * can unzip Scala source code to see how

compilation:overview_of_compiling_to_stack_machine

Anonymous (anonymous@undisclosed.example.com) — 2008-11-01T23:07:51+0200

Overview of Compiling to Stack Machine Our goal in this lecture is to understand compilation from abstract syntax trees to stack machine code Examples of this: * javac * your MiniJavaPlus compiler * compiler from the Pascal Programming Language to pascal UCSD Pascal P-code machine Source: Java (subset) abstract syntax tree

compilation:parse_trees_ambiguity_and_derivations

Anonymous (anonymous@undisclosed.example.com) — 2008-09-23T22:35:47+0200

Parse Trees, Ambiguity, and Derivations (Continuing from Limitations of Regular Expressions) What is context-free grammar for balanced parantheses? S ::= "{" "}" | "{" S "}" | S S Example: deriving string {{}} {} {{}{}} Definitions: * balanced = given by counting number of open parantheses so far

compilation:parsertrees.scala

Anonymous (anonymous@undisclosed.example.com) — 2008-10-06T10:05:26+0200

Parser for While that Generates Trees /* A very simple version of while language: program ::= statements EOF statements = statement* statement ::= print | assign | while | block write ::= "println" "(" var ")" ";" assign ::= var "=" expr ";" while ::= "while" "(" expr ")" statement block ::= "{" statements "}" expr ::= expr "+" expr | expr "-" expr | expr "*" expr | "(" expr ")" | var | intconst */ class Parser(lex : Lexer) { // program ::= statement* EOF def parseProgram : Li…

compilation:parsingtechniques

Anonymous (anonymous@undisclosed.example.com) — 2008-10-11T17:25:47+0200

Parsing Techniques - A Practical Guide Dick Grune and Ceriel J.H. Jacobs: Parsing Techniques - A Practical Guide * Book Web Page

compilation:phases_of_a_compiler

Anonymous (anonymous@undisclosed.example.com) — 2008-12-06T19:44:46+0200

Selected Phases of a Compiler source code int i = 0; /* some comment */ int j = 0; while (i < 10) { System.out.println(j); i = i + 1; j = j + 2*i+1; } Lexer list of tokens INT, Identifier("i"), EQUAL, IntNumeral(0), SEMICOLON, INT, Identifier("j"), EQUAL, ... WHILE, OPENPAREN, Identifier("i"), LESSTHAN, IntNumeral(10), CLOSEDPAREN, OPENBRACE, Identifier("System"), DOT, Identifier("out"), ...

compilation:pointer_reversal

Anonymous (anonymous@undisclosed.example.com) — 2008-12-14T23:50:48+0200

Pointer Reversal Suppose we write depth-first search in mark and sweep using a stack What is the maximal stack size? * stack of the programming language * explicit stack * pointer reversal: store information within nodes Explicit Stack function DFS(x) if (x is a pointer and record x is not marked) { mark(x) t = 1 stack(t) = x while (t > 0) { x = stack(t) t = t - 1 for each field f_i of record x if (x.f_i is a pointer and x.f_i is not marked…

compilation:polynomials.pscala

Anonymous (anonymous@undisclosed.example.com) — 2008-09-28T16:26:41+0200

// polynomial ::= term ("+" term)* def parsePolynomial = { parseTerm while (lex.current==PLUS) { lex.next parseTerm } } // term ::= factor ("*" factor)* def parseTerm = { parseFactor while (lex.current==MUL) { lex.next parseFactor } } // factor ::= constant | variable | "(" polynomial ")" def parseFactor = { if (lex.current==CONST) lex.next else if (lex.current==IDENT) lex.next else if (lex.current==OPAREN) { lex.next parsePolynomial eat(CPAR…

compilation:polynomialsll.grammar

Anonymous (anonymous@undisclosed.example.com) — 2008-09-28T12:57:00+0200

polynomial ::= term ("+" term)* term ::= factor ("*" factor)* factor ::= constant | variable | "(" polynomial ")"

compilation:polytokens.jj

Anonymous (anonymous@undisclosed.example.com) — 2008-09-11T19:25:54+0200

options { JAVA_UNICODE_ESCAPE = true; } PARSER_BEGIN(Polynomials) public class Polynomials {} PARSER_END(Polynomials) // Insert a specification of a lexical analysis here. TOKEN: { ( | | "_")* > | ()* > | | } SKIP: { " " | "\n" | "\t" } // The following is a simple grammar that will allow you // to test the generated lexer. void Goal(): {} { ( MyToken() …

compilation:polytokentest.java

Anonymous (anonymous@undisclosed.example.com) — 2008-09-11T19:27:04+0200

public class PolyTokenTest { public static void main(String [] args) { try { new Polynomials(System.in).Goal(); System.out.println("Lexical analysis successfull"); } catch (ParseException e) { System.out.println("Lexer Error : \n"+ e.toString()); } } }

compilation:postfix_translation_of_boolean_operators

Anonymous (anonymous@undisclosed.example.com) — 2008-11-10T01:03:47+0200

Postfix Translation of Boolean Operators Eager Boolean Operations Candidate translation, knowing that booleans are 0 or 1: [[ e1 & e2 ]] = [[ e1 ]] [[ e2 ]] iand [[ e1 | e2 ]] = [[ e1 ]] [[ e2 ]] ior This indeed works for &, |

compilation:precedence_in_lr_parsing

Anonymous (anonymous@undisclosed.example.com) — 2008-10-05T23:31:42+0200

Precedence in LR Parsing Using LR parser we can even parse certain ambigous grammars There is an automaton for every grammar, but it may have shift/reduce conflicts For ambigous grammars, even LR(1) automaton will generate conflicts Example: grammar like

compilation:prefix_infix_postfix_notation

Anonymous (anonymous@undisclosed.example.com) — 2008-11-02T18:26:38+0200

Prefix, Infix, and Postfix Notation Let * be a binary operation and * , two expressions We can write in prefix notation infix notation postfix notation Infix is the worst notation: it requires parantheses and parenthese, the other two do not!

compilation:printing_prefix_infix_postfix

Anonymous (anonymous@undisclosed.example.com) — 2008-11-02T18:04:14+0200

Printing Prefix Infix Postfix Recall tree.scala for the while language * it contained pretty-printer for infix expressions Pretty printer for prefix, infix, and postfix expressions: sealed abstract class Expr case class Var(varID: String) extends Expr case class IntLiteral(value: Int) extends Expr case class Plus(lhs: Expr, rhs: Expr) extends Expr case class Times(lhs: Expr, rhs: Expr) extends Expr sealed abstract class Token case class ID(str : String) extends Token case class Const(c :…

compilation:programs.scala

Anonymous (anonymous@undisclosed.example.com) — 2008-09-26T13:22:10+0200

package whilelang; object Programs { /** A program consists of a name and the main statement. */ type Program = Pair[String,Statement] /** Does nothing. */ val skip: Program = ("Skip", Skip) /** Prints out n^2 for n = 1...10. */ val squares: Program = ("Squares", Block( Assign("i", IntLiteral(0)) :: Assign("j", IntLiteral(1)) :: While(LessThan(Var("i"), IntLiteral(10)), Block( Print("", "j") :: Assign("i", Plus(Var("i"), IntLiteral(1))) ::…

compilation:proving_safety_properties_using_types

Anonymous (anonymous@undisclosed.example.com) — 2015-04-21T17:34:55+0200

Proving Safety Properties using Types We next discuss general techniques for proving absence of errors in programs This also tells us how to prove that our type systems are meaningul (sound) Safety Properties of Programs Given a one-step reduction relation

compilation:pushdown_automata

Anonymous (anonymous@undisclosed.example.com) — 2008-10-04T17:01:24+0200

Pushdown Automata in Parsing Why pushdown automata * pushdown automata are like finite automata, but also work with stack * parsing requires stack Equivalence of expressive power: regular expressions non-deterministic FA context-free grammars

compilation:quiz

Anonymous (anonymous@undisclosed.example.com) — 2008-12-15T11:52:18+0200

Quiz Quiz is in room INM 202 where we usually have exercises. Review labs, homeworks, and lectures to prepare. Please arrive by 8:05am * bring EPFL id You may bring any printed material (e.g. Tiger book, lectures, your homeworks, printouts of your labs).

compilation:race

Anonymous (anonymous@undisclosed.example.com) — 2008-12-03T15:37:29+0200

The MiniJava+ Compiler Race To celebrate the completion of the first basic version of your MiniJava+ compilers, we are organizing a competition. We will test all your compilers for correctness against a series of tests (some of which should pass, while others should fail). The tests will cover all phases of your compiler, not only code generation (although the correctness of the execution will be the criterion for all passing examples). In separate tracks, we will measure the size of the gener…

compilation:range_analysis

Anonymous (anonymous@undisclosed.example.com) — 2015-04-21T17:34:55+0200

Range Analysis Properties of Interest A more precise analysis that computes sets to which integer variables belong * still no relations between variables - independent attribute analysis For each program point compute interval (or a union of intervals) to which variable belongs

compilation:rangeanalysislattice.scala

Anonymous (anonymous@undisclosed.example.com) — 2008-11-25T23:55:12+0200

object RangeLattice extends Lattice { sealed abstract class Range case object Empty extends Range // {} case class Bounded(a : Int, b : Int) extends Range // [a,b] { assert (a <= b) } case class LeftUnbounded(b : Int) extends Range // (-inf,b] case class RightUnbounded(a : Int) extends Range // [a,+inf) case object Full extends Range // (-inf,+inf) type Elem = Range def leq(x : Range, y : Range) = (x,y) match { case (Empty,_) => true case (_,Full) => true case (Bou…

compilation:recursive_descent_parsing

Anonymous (anonymous@undisclosed.example.com) — 2008-10-04T16:00:05+0200

Recursive Descent (Predictive) Parsing Recursive descent is a decent parsing technique. descent: a movement downward decent: adequate: sufficient for the purpose; “an adequate income”; “the food was adequate”; “a decent wage”; “

compilation:reference_counting

Anonymous (anonymous@undisclosed.example.com) — 2008-12-14T22:41:45+0200

Reference Counting In each memory location store the number of incoming pointers Free the block if the counter is zero What is the block has pointers itsefl? * decrementing counts when the r is reused again * ensures a bounded amount of work for each operation

compilation:register_allocation_using_liveness_information

Anonymous (anonymous@undisclosed.example.com) — 2008-12-08T12:42:39+0200

Register Allocation using Liveness Information static int x; static int y; static int z; static int res; int f() { int xy; int yz; int xz; int res1; xy = x * y; yz = y * z; xz = x * z; res1 = xy + yz; res = res1 + xz; } How to generate code that we saw in

compilation:register_machine_in_scala

Anonymous (anonymous@undisclosed.example.com) — 2009-11-23T00:35:56+0200

Register Machine in Scala sealed abstract class Value case class Immediate(const : Int) extends Value sealed abstract class Address extends Value case class Register(r : Int) extends Address case class Memory(a : Int) extends Address case class Indirect(r : Int) extends Address case class IndirectOffset(r : Int, offset : Int) extends Address sealed abstract class ArithOp case object Mul extends ArithOp case object Add extends ArithOp case object Sub extends ArithOp …

compilation:reporting_errors_based_on_syntax_tree

Anonymous (anonymous@undisclosed.example.com) — 2008-10-13T07:37:17+0200

Reporting Errors Based on Syntax Tree Suppose we discover undclared variable 'i' in syntax tree * in a program of 100K lines What error message would you like compiler to give? * An ocurrence of variable 'i' not declared * An ocurrence of variable 'i'

compilation:resolving_variable_names

Anonymous (anonymous@undisclosed.example.com) — 2008-10-13T03:54:07+0200

Resolving Variables Recall Semantic Analysis as Simplified Interpretation Even if we associate unique symbols with identifiers, * same identifier can denote different variables at different points This is why symbol table needs to change depending on position in tree Once we look up identifier, we can directly link it to its definition

compilation:scalabestpractice

Anonymous (anonymous@undisclosed.example.com) — 2008-11-19T11:04:21+0200

Scala Best Practice Printing lists is easy When pretty-printing an AST or simply debugging, avoid the following (albeit functional, unnecessarily long) code: printList(listOfThings) def printList(lst: List[A]): Unit = { def printList0(lst: List[A]): Unit = lst match { case x1 :: x2 :: Nil => print(x1 + ", "); printList0(lst.tail) case x1 :: Nil => print(x1) case Nil => ; } print("(") printList0(lst) print(")") }

compilation:semantic_analysis_as_simplified_interpretation

Anonymous (anonymous@undisclosed.example.com) — 2008-10-17T15:10:45+0200

Semantic Analysis as Simplified Interpretation Goal: detect whether there will be errors in any execution Starting point: our interpreter from Handling Scopes in Interpreters /* What did we do compared to interpreter: - erased concrete values in IntValue, BoolValue - erased the use of concrete values in evalExpr, checkType - checking types and initialization earlier: for every getVar - handling of if statements - procedure calls: - check parameters at call (in in…

compilation:short-circuit_evaluation

Anonymous (anonymous@undisclosed.example.com) — 2008-11-10T01:38:14+0200

Short-Circuit Evaluation For correct semantics, we express &&,|| using ?: operator: x && y === x ? y : false ++ x || y === x ? true : y ++ Resulting translation: [[ x && y ]] = [[ x ]] ifeq nFalse [[ y ]] goto nAfter nFalse: iconst_0 nAfter:

compilation:sign_analysis

Anonymous (anonymous@undisclosed.example.com) — 2008-11-17T02:48:05+0200

Sign Analysis Determine whether each variable is guaranteed to be negative, zero, or stringly positive Lattice of possibilities and its meaning Example of analyzing simple loop

compilation:signanalysis.scala

Anonymous (anonymous@undisclosed.example.com) — 2009-11-22T20:06:53+0200

object Signs { // A 5-element abstraction of sets of integers sealed abstract class Sign case object TopSign extends Sign // all integers case object BottomSign extends Sign // {} case object Positive extends Sign // {1,2,3,...} case object Zero extends Sign // {0} case object Negative extends Sign // {...,-3,-2,-1} class SignLattice extends Lattice { // Sign as a lattice type Elem = Sign val top = TopSign // universal set is top val bottom = Bot…

compilation:simple_types_for_lambda_calculus

Anonymous (anonymous@undisclosed.example.com) — 2015-04-21T17:34:55+0200

Simple Types for Lambda Calculus There are several type systems for lambda calculus We consider here the simplest one * types are disjoint * only primitive and function types * every lambda binding specifies its type Type Rules for Simply Typed Lambda Calculus

compilation:simpleast.scala

Anonymous (anonymous@undisclosed.example.com) — 2008-11-24T02:49:14+0200

/* Syntax tree for a toy language */ object SimpleAST { type Ident = String sealed abstract class Statement case class AssignStat(lhs : Ident, rhs : Expression) extends Statement case class PrintStat(e : Expression) extends Statement case class IfStat(cond : Expression, trueS : Statement, falseS : Statement) extends Statement case class WhileStat(cond : Expression, body : Statement) extends Statement case class BlockStat(sts : List[Statement]) extends State…

compilation:simplecfg.scala

Anonymous (anonymous@undisclosed.example.com) — 2008-11-24T02:48:53+0200

object SimpleCFG { type Variable = String // for simplicity sealed abstract class SimpleValue case class VarValue(v : Variable) extends SimpleValue { override def toString = v } case class Const(c : Int) extends SimpleValue { override def toString = { "" + c } } sealed abstract class Operation sealed case class ArithOp extends Operation case object PlusOp extends ArithOp { override def toString = "+" } abstract case class RelOp extends Operation case object…

compilation:simpletranslate.scala

Anonymous (anonymous@undisclosed.example.com) — 2008-11-24T02:49:40+0200

import SimpleCFG._, SimpleAST._ final class ASTtoCFG(cfg : Cfg) { private type Vertex = cfg.Vertex private val TrueConst = 1 private val FalseConst = 0 object FreshName { var counter : Int = 0 def get : String = { counter = counter + 1 "x" + counter } } object Emit { private var pc : Vertex = cfg.entry def getPC : Vertex = { pc } def setPC(v : Vertex) = { pc = v } def statementBetween(v1 : Vertex, s : CfgStmt, v2 : Vertex) = { cfg +=…

compilation:simply_typed_lambda_calculus

Anonymous (anonymous@undisclosed.example.com) — 2015-04-21T17:34:55+0200

Simply Typed Lambda Calculus Lambda calculus is a simple and powerful notation for defining functions. Among its uses are * foundation of programming languages, especially functional languages such as Ocaml, Haskell, and Scala * basis of higher order logic

compilation:slr_parser_actions

Anonymous (anonymous@undisclosed.example.com) — 2008-10-05T22:51:00+0200

SLR Parser Actions SLR (simple LR) is like LR(0) but reduces on (X::=p.) only if additionally: * t follow(X) where is current token Otherwise, same as LR(0) Parser Actions Let K be parser state at the end of stack and t current token: * if there is a transition

compilation:solution

Anonymous (anonymous@undisclosed.example.com) — 2008-10-08T09:52:44+0200

options { STATIC = false; // LOOKAHEAD = 2; } PARSER_BEGIN(WhileParser) class WhileParser { public static void main(String[] args) throws ParseException, TokenMgrError { WhileParser parser = new WhileParser(System.in); parser.Start(); } } PARSER_END(WhileParser) SKIP : { " " | "\t" | "\n" | "\r" | < "//"(~["\n", "\r"])* ("\n" | "\r" | "\r\n")> } TOKEN : { < INTLIT: "0" | ["1"-"9"](["0"-"9"])* > } TOKEN : { < STRLIT: "\"" (~["\"", "\n", "\r"…

compilation:squares.while

Anonymous (anonymous@undisclosed.example.com) — 2008-09-12T00:21:56+0200

// Prints n^2 for n=1...10 i = 0; j = 1; while (i < 10) { println("", j); i = i + 1; // increment counter j = j + 2*i+1; }

compilation:stack_frames_and_procedure_calls

Anonymous (anonymous@undisclosed.example.com) — 2008-12-08T01:01:41+0200

Stack Frames and Procedure Calls Stack Frames To compile procedures, we organize stack into stack frames (activation records) Each procedure call allocates new stack frame on the stack When procedure returns, the stack frame is deallocated This allows us to support recursive procedure calls

compilation:subtyping_for_assignments

Anonymous (anonymous@undisclosed.example.com) — 2015-04-21T17:34:55+0200

Subtyping for Assignments Named Variables If a mutable variable named has type , it means that it is guaranteed to be able to store values in We cannot pretend that can store values of supertype because if we later read a value, we can unexpectedly get value that is not in

compilation:subtyping_for_functions

Anonymous (anonymous@undisclosed.example.com) — 2015-04-21T17:34:55+0200

Subtyping for Functions To obtain lambda calculus with subtyping, we modify only primitive rules if needed and the application rule for Simple Types for Lambda Calculus. We modify application rule to allow not only arguments of exact type, but also of subtype: This modification alone allows us to write e.g.

compilation:subtyping_rules

Anonymous (anonymous@undisclosed.example.com) — 2015-04-21T17:34:55+0200

Subtyping Rules Subtype relation C<:D iff there is a chain of subclass relations from D (the super class) to C (the subclass) How do we modify subtyping rules for * assignments * method calls Assignment Method calls: Method definitions:

compilation:symbol_table_contents

Anonymous (anonymous@undisclosed.example.com) — 2008-10-13T07:41:55+0200

Symbol Table Contents What should be in a symbol table? All information is derived from syntax tree * symbol table is interconnected with syntax tree * in old one-pass compilers there was only symbol table * today it gives faster, easier access to parts of syntax tree

compilation:termination_of_data-flow_analysis

Anonymous (anonymous@undisclosed.example.com) — 2015-04-21T17:34:55+0200

Termination and Efficiency of Data-Flow Analysis Definition: A chain of length is a sequence such that where means, as usual, Definition: A lattice has a finite height if it has a chain of length and every chain is of length at most . A finite lattice is of finite height

compilation:test.jvm

Anonymous (anonymous@undisclosed.example.com) — 2008-09-08T10:27:34+0200

Compiled from "test.java" class Test extends java.lang.Object{ Test(); Code: 0: aload_0 1: invokespecial #1; //Method java/lang/Object."":()V 4: return public static void main(java.lang.String[]); Code: 0: iconst_0 1: istore_1 2: iconst_0 3: istore_2 4: iload_1 5: bipush 10 7: if_icmpge 32 10: getstatic #2; //Field java/lang/System.out:Ljava/io/PrintStream; 13: iload_2 14: invokevirtual #3; //Method java/io…

compilation:test.s

Anonymous (anonymous@undisclosed.example.com) — 2008-09-07T18:03:59+0200

.file "test.c" .section .rodata .LC0: .string "%d\n" .text .globl main .type main, @function main: leal 4(%esp), %ecx andl $-16, %esp pushl -4(%ecx) pushl %ebp movl %esp, %ebp pushl %ecx subl $36, %esp movl $0, -12(%ebp) movl $0, -8(%ebp) jmp .L2 .L3: movl -8(%ebp), %eax movl %eax, 4(%esp) movl $.LC0, (%esp) …

compilation:testpolyinput.poly

Anonymous (anonymous@undisclosed.example.com) — 2008-09-11T19:28:17+0200

x + 3 * y0 * (zLongIdentifier * ! 12)

compilation:tiger_book

Anonymous (anonymous@undisclosed.example.com) — 2008-09-09T15:14:43+0200

Textbook * Modern Compiler Implementation in Java (2nd Edition): * Andrew Appel's web site * 2nd Edition from Cambridge University Press * 2nd Edition from Amazon.com * 2nd Edition from Amazon.de * Textbook materials * from Andrew Appel * from Cambridge University Press * from Jens Palsberg's course

compilation:tokens.scala

Anonymous (anonymous@undisclosed.example.com) — 2008-09-12T13:51:44+0200

sealed abstract class Token case class ID(content : String) extends Token case class IntConst(value : Int) extends Token case object AssignEQ extends Token case object CompareEQ extends Token case object MOD extends Token case object DIV extends Token case object MUL extends Token case object PLUS extends Token case object MINUS extends Token case object LEQ extends Token case object LESS extends Token case object OPAREN extends Token case object CPAREN extends Token case object WHILE extends To…

compilation:tokens_words_of_while_language

Anonymous (anonymous@undisclosed.example.com) — 2008-09-12T15:03:03+0200

Tokens (Words) of While Language token = word (in a general sense) What are the tokens in squares.while example? // Prints n^2 for n=1...10 i = 0; j = 1; while (i < 10) { println("", j); i = i + 1; // increment counter j = j + 2*i+1; } Several token types

compilation:tools_for_constructing_lexers

Anonymous (anonymous@undisclosed.example.com) — 2008-09-20T18:11:56+0200

Tools for Constructing Lexers We can use JavaCC file to generate lexers. Files: * simple lexer for polynomials: polyTokens.jj * simple main file: PolyTokenTest.java * simple test input for lexer: TestPolyInput.poly Instructions: javacc polyTokens.jj javac *.java java -cp . PolyTokenTest < TestPolyInput.poly

compilation:top

Anonymous (anonymous@undisclosed.example.com) — 2009-01-03T11:54:45+0200

Compiler Construction 2008 Course Information Moodle Page for Uploading Your Solutions MiniJava+ Competition results The winners of the 2008 competition are, ex-aequo: * Group 02 - Daniel Chappuis & Stéphane Testuz * Group 13 - Thibaut Beuret & Pierre-François Laquerre ...whose compilers passed the 185 benchmarks without any single problem, congratulations!

compilation:transforming_to_chomsky_normal_form

Anonymous (anonymous@undisclosed.example.com) — 2015-04-21T17:34:55+0200

Transforming a Grammar to Chomsky Form We show how to make a grammar: * without unproductive symbols * without unreachable symbols * -free (no non-start nullable symbols) * without single productions X::=Y (X,Y non-terminals) * without productions of arity more than two

compilation:translating_expressions_to_stack_machine

Anonymous (anonymous@undisclosed.example.com) — 2015-04-21T17:34:55+0200

Translating Expressions to Stack Machine Connection to Postfix Example: translate expression (a*b + b*c + a*c) * 2 into posftix form. Tree: * + 2 * + a b * * b c a c Postfix expression: a b * b c * + a c * + 2 *

compilation:translating_expressions_to_stack_machine_code

Anonymous (anonymous@undisclosed.example.com) — 2008-10-26T12:22:56+0200

Translating Expressions to Stack Machine Code Stack machine containing integers Generating code by postfix traversal of the tree Correctness proof of the translation

compilation:translating_syntax_tree_to_cfg

Anonymous (anonymous@undisclosed.example.com) — 2008-11-17T03:12:13+0200

Translating Syntax Tree to CFG Similar to * fresh variable names instead of stack for expressions * edges in CFG instead of jump instructions * test edges to encode conditional branches Example of translation Building a Translator to CFG Simulating

compilation:translation_correctness_for_expressions

Anonymous (anonymous@undisclosed.example.com) — 2015-04-21T17:34:55+0200

Translation Correctness for Expressions Recall Evaluating Postfix Notation Functions: * * * For simplicity we will omit environments mapping variables * does not affect this proof We often write X instead of List(X) when X is one element Also, we often use same symbol '*' for

compilation:translation_of_relations

Anonymous (anonymous@undisclosed.example.com) — 2008-11-10T00:19:34+0200

Translation of Relations Consider translation of <,=,<=,>,>=,=,!= on integers Operations of type int => int => {0,1} But there are no instructions that do this There are conditional branches for comparison of two stack operands: * in general called

compilation:tree.scala

Anonymous (anonymous@undisclosed.example.com) — 2008-09-26T13:21:40+0200

package whilelang; sealed abstract class Tree sealed abstract class Statement extends Tree sealed abstract class SingleStatement extends Statement case class Print(msg: String, varID: String) extends SingleStatement case class Assign(varID: String, expr: Expression) extends SingleStatement /* The Skip statement represents empty statements. Useful for instance in else blocks of if-then-else constructs. */ case object Skip extends SingleStatement case class Block(body: List[Statement]) extends S…

compilation:treesimplifier.scala

Anonymous (anonymous@undisclosed.example.com) — 2008-09-26T13:22:28+0200

package whilelang object TreeSimplifier { def apply(stat: Statement): Statement = { // replace all for loops by equivalent trees using while loops... } }

compilation:trivia_bad_languages

Anonymous (anonymous@undisclosed.example.com) — 2008-10-26T21:52:08+0200

Answer to Python Question $ python Python 2.5.1 (r251:54863, Jul 31 2008, 23:17:40) [GCC 4.1.3 20070929 (prerelease) (Ubuntu 4.1.2-16ubuntu2)] on linux2 Type "help", "copyright", "credits" or "license" for more information. >>> 100*"I will not design bad languages. " 'I will not design bad languages. I will not design bad languages. I will not design bad languages. I will not design bad languages. I will not design bad languages. I will not design bad languages. I will not design bad languag…

compilation:type_checking_let_and_letrec

Anonymous (anonymous@undisclosed.example.com) — 2015-04-21T17:34:55+0200

Type Checking Let and Letrec Let Expressions Expression can be viewed as a shorthand for because they both evaluate to From this follows the type rule for let expressions: Example: We can represent non-recursive method definitions using let

compilation:type_soundness_for_simply_typed_lambda_calculus

Anonymous (anonymous@undisclosed.example.com) — 2015-04-21T17:34:55+0200

Type Soundness for Simply Typed Lambda Calculus We apply the general method in Proving Safety Properties using Types to prove soundness of Simple Types for Lambda Calculus Basic Notions We consider the set of types given by these two rules: * int, bool * if , then also (In particular types cannot have any 'variables' or 'parameters' as in more complex type systems.)

compilation:types_and_programming_languages

Anonymous (anonymous@undisclosed.example.com) — 2008-10-25T22:16:40+0200

Types and Programming Languages Types and Programming Languages, by Benjamin C. Pierce The MIT Press Massachusetts Institute of Technology Cambridge, Massachusetts 02142 ISBN 0-262-16209-1 *

compilation:types_and_programming_languages_book

Anonymous (anonymous@undisclosed.example.com) — 2008-10-13T04:04:51+0200

Types and Programming Languages Book Types and Programming Languages, by Benjamin C. Pierce The MIT Press, ISBN 0-262-16209-1 * Author's Page for the Book

compilation:typestate_analysis

Anonymous (anonymous@undisclosed.example.com) — 2008-11-26T11:45:18+0200

Typestate Analysis Example Hypothetical class for reading and writing files: class File { public static final UNINITIALIZED=0; public static final OPEN=1; public static final CLOSED=2; int state = UNINITIALIZED [typestate: UNINITIALIZED -> OPEN] public void open(name : String) { ... } [typestate: OPEN] public String readLine() { ... } [typestate: OPEN] public void writeLine(String line) { ... } [typestate: OPEN -> CLOSED] void close() { ... } }

compilation:typing_rules_for_simple_language

Anonymous (anonymous@undisclosed.example.com) — 2015-04-21T17:34:55+0200

Type Checking Rules for a Simple Language Abstract Syntax of a Simple Language This language is similar to one in Semantic Analysis as Simplified Interpretation, but for simplicity assumes programs have only one class (called World) and all members to are assumed to be static. program ::= "class" "World" "{" varDecl* method* "}" method ::= varDecl "(" varDecl* ")" "{" stmt* "return" expr "}" varDecl ::= type ID type ::= "int" | "boolean" | "void" stmt ::= expr | if | while | block if ::= "i…

compilation:typos_in_compiler_construction_by_wirth

Anonymous (anonymous@undisclosed.example.com) — 2008-11-07T16:47:34+0200

Typos in Compiler Construction by Wirth Refers to [This PDF File] Chapter 10: * page 50, the ADD instruction means R0:=R0+R1

compilation:using_finite_state_machines_for_lexical_analysis

Anonymous (anonymous@undisclosed.example.com) — 2008-09-23T22:26:42+0200

Using Finite State Machines to Build Lexers Suppose we have token classes and each is given by regular expression . Consider building an automaton for * a step towards solution Example: Construct (directly) a finite state machine for these classes of tokens:

compilation:variable_capture

Anonymous (anonymous@undisclosed.example.com) — 2015-04-21T17:34:55+0200

Variable Capture We introduce informally concept of variable capture in Lambda Calculus The expressions such as and denote the same thing, namely a function that differ only by names of bound variables. * we say one expression was obtained by another by -renaming

compilation:vm_for_expressions

Anonymous (anonymous@undisclosed.example.com) — 2008-11-02T12:18:34+0200

Stack-Based Virtual Machine for Expression Evaluation Some instructions: * iadd * imul * iload * istore * bipush abstract class Instruction case class Bipush(c : Int) extends Instruction case class Iadd extends Instruction case class Imul extends Instruction case class Iload(slot : Int) extends Instruction case class Istore(slot : Int) extends Instruction class VM(var code : Array[Instruction], var pc : Int, // program counter (current instruction)…

compilation:week_02

Anonymous (anonymous@undisclosed.example.com) — 2008-09-10T16:47:14+0200

Week 02 * Lecture 02 * Labs 02 * Exercises 02

compilation:what_is_a_compiler

Anonymous (anonymous@undisclosed.example.com) — 2008-09-08T10:34:21+0200

What is a compiler? A tool that transforms program in source programming language into a program in target programming language so we can run the compiled program on machine Typically: * source language is a high-level programming language, such as

compilation:while_language

Anonymous (anonymous@undisclosed.example.com) — 2008-09-29T15:03:40+0200

A While Language While-Language is a little language we use in lectures to illustrate basic concepts. The exact definition of what is contained in that language will sometimes vary depending on the specific points we want to illustrate, but a possible concrete syntax is given

compilation:whileparser.scala

Anonymous (anonymous@undisclosed.example.com) — 2008-10-06T10:05:04+0200

Recursive Descent Parser for While Language /* A very simple version of while language: program ::= statements EOF statements = statement* statement ::= print | assign | while | block write ::= "println" "(" var ")" ";" assign ::= var "=" expr ";" while ::= "while" "(" expr ")" statement block ::= "{" statements "}" expr ::= expr "+" expr | expr "-" expr | expr "*" expr | "(" expr ")" | var | intconst */ class Parser(lex : Lexer) { // program ::= statement* EOF def parseProgra…

compilation:why_study_compilers

Anonymous (anonymous@undisclosed.example.com) — 2008-09-09T17:12:03+0200

Why Study Compilers Use knowledge to: * understand how compilers work (use them better) * gain experience with building complex software * build compiler for your next great language * extend language with a new construct you need * adapt existing compiler to new target platform (e.g. embedded CPU)

compilation:why_study_lexical_analysis

Anonymous (anonymous@undisclosed.example.com) — 2008-09-11T18:41:50+0200

Why Study Lexical Analysis Context-free grammars are general, why do we study regular expressions first? “Drunk under the lamppost” effect Simpler problem, understood better, better automated tools * preparation for parsing

compilation:xyz_example_using_gcc

Anonymous (anonymous@undisclosed.example.com) — 2008-12-08T02:52:13+0200

xyz Example using GCC static int x; static int y; static int z; static int res; int f() { res = x * y + y * z + x * z; } We compile it for X86 instruction set, using gcc -S xyz.c Essential part: movl x, %edx movl z, %eax addl %eax, %edx movl y, %eax movl %edx, %ecx imull %eax, %ecx movl x, %edx movl z, %eax imull %edx, %eax leal (%ecx,%eax), %eax /* load effective address, used as add */ movl %eax, res