https://lara.epfl.ch/w/ 2026-06-14T14:53:26+0200 https://lara.epfl.ch/w/ https://lara.epfl.ch/w/lib/tpl/epflv2/images/favicon.ico text/html 2015-04-21T17:35:15+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/about_parsing_context-free_grammars?rev=1429630515&do=diff About Parsing Potentially Ambiguous 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 Applications: * text/html 2009-09-14T00:42:29+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/abstract_syntax_of_while?rev=1252881749&do=diff 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 text/html 2015-04-21T17:35:15+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/accessing_and_storing_variables?rev=1429630515&do=diff Accessing and Storing Variables Local Variables Review instructions iload and istore from JVM Spec. Assigning indices (called slots) to local variables: * in which compiler phase. What information about the symbol do we need to know? * how to compute the indices? text/html 2014-05-26T19:11:17+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/algorithm_for_first_and_follow_sets?rev=1401124277&do=diff Algorithm for Computing First and Follow Sets nullable = {} foreach nonterminal X: first(X)={} follow(X)={} for each terminal Y: first(Y)={Y} follow(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 if i=1 or {Y(1),...,Y(i-1)} subset of nullable then first(X) = first(X) union first(Y(i)) for j = i+1 to k if i=k or {Y(i+1),...Y(k)} subset of nullable then … text/html 2009-09-13T22:23:33+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/alternatives_to_compilation?rev=1252873413&do=diff Alternatives to compilation? Interpreter A program that reads source code and directly executes it * does not generate the translation of the source program first [Interpreter] Compiler Advantages of compilers over interpreters: * once compiled, execution can be much faster text/html 2010-10-24T23:55:13+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/an_efficient_imperative_map?rev=1287957313&do=diff 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 text/html 2010-12-08T10:05:35+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/applications_of_data-flow_analysis?rev=1291799135&do=diff Applications of Data-Flow Analysis * optimization * correctness Optimization Some optimization examples: * common subexpression elimination using available expression analysis * avoid recomputing (automatically or manually generated) identical expressions text/html 2010-11-29T00:37:33+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/arm_architecture?rev=1290987453&do=diff 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: text/html 2012-11-25T22:05:17+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/array_manipulation?rev=1353877517&do=diff Array Manipulation Consider the following (high-level) JVM instructions from JVM Spec: * newarray * anewarray * iaload * iastore * arraylength Similar remarks apply as for general objects. Java arrays contain information about * the content of the array text/html 2015-04-21T17:35:15+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/automata_for_lr_parsing_without_lookahead?rev=1429630515&do=diff Automata for LR Parsing without Lookahead These automata are used to construct LR(0) and SLR parsers * same automata, SLR just uses some extra information We describe their states and transitions If was original start symbol, we * add (D'::=D eof) to grammar text/html 2009-09-26T12:31:31+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/avoiding_left_recursion_in_recursive_descent?rev=1253961091&do=diff Avoiding Left Recursion in Recursive Descent Instead of polynomial ::= term ("" | "+" polynomial) consider grammar defining the same language: polynomial ::= ("" | polynomial "+") term we need to parse polynomial, so we check which alternative to parse, so we check whether the current symbol is parsed by polynomial, so text/html 2013-10-07T09:29:06+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/basic_idea_of_first_symbol_computation?rev=1381130946&do=diff Basic Idea of First Symbol Computation When Exactly Does Recursive Descent Work? When can we be sure that recursive descent parser will parse grammar correctly? * it will accept without error exactly when string can be derived Consider grammar without repetition construct * (eliminate it using right recursion). text/html 2010-11-22T01:17:13+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/booleans_and_data_representation?rev=1290385033&do=diff 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 text/html 2012-11-20T23:33:57+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/branching_jvm_instructions?rev=1353450837&do=diff JVM Instructions for Branching See goto statement in JVM Spec Conditional branch on comparison to zero: * if_<cond> * 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: text/html 2013-10-07T09:31:10+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/building_ll_parsing_table?rev=1381131070&do=diff Building LL Parsing Table Parsing table for LL parser is of form choice : Nonterminal -> Token -> Set[Int] We compute 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): X ::= p(X,1) | ... | p(X,i) | ... | p(X,n) text/html 2009-10-04T20:56:44+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/charstream.scala?rev=1254682604&do=diff 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)) … text/html 2015-04-21T17:35:15+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/checking_initialization_using_data-flow_analysis?rev=1429630515&do=diff Checking Initialization Using Data-Flow Analysis We follow the methodology of Designing Correct Data-Flow Analyses Defining Properties of Interest We represent program execution as a sequence of program states and simple statements. Program state is where * is a program point text/html 2009-10-04T17:37:28+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/chomsky_normal_form?rev=1254670648&do=diff Chomsky Normal Form A grammar is in Chomsky normal form if it has only these kinds of productions: X ::= Y Z X ::= t S ::= "" where * X,Y,Z denote non-terminals * t denotes terminals * S is the start non-terminal * if S::=“” appears, then S does not appear on right-hand side of another rule text/html 2009-09-13T22:31:39+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/collatz.while?rev=1252873899&do=diff x = 13; while (x > 1) { println("x=", x); if (x % 2 == 0) { x = x / 2; } else { x = 3 * x + 1; } } text/html 2012-11-25T19:42:39+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/compilation_as_tree_transformation?rev=1353868959&do=diff Compilation as Tree Transformation Motivation: * elegant and efficient compilation for conditionals * compilation for more complex control structures To describe this compilation we introduce an imaginary, big, instruction branch(c,nThen,nElse) text/html 2012-11-20T22:11:19+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/compiled_counting_examples?rev=1353445879&do=diff 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 … text/html 2009-11-02T01:35:16+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/compiled_expression_examples?rev=1257122116&do=diff 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 } text/html 2012-11-20T20:54:47+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/compiled_factorial_example?rev=1353441287&do=diff 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: text/html 2010-11-14T20:19:09+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/compiler_construction_by_niklaus_wirth?rev=1289762349&do=diff Compiler Construction by Niklaus Wirth You can download here the textbook [Compiler Construction, by Niklaus Wirth]. text/html 2012-09-21T12:08:27+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/compiler_construction_tools?rev=1348222107&do=diff Some Compiler Construction Tools JLex Java CUP JavaCC Coco/R Antlr Parser Combinators: Chapter 31 of Programming in Scala text/html 2009-12-14T02:35:47+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/compiler_interface_to_garbage_collector?rev=1260754547&do=diff Compiler Interface to Garbage Collector Garbage collector needs to know * reference roots * reference fields Need to generate information on * global variables * heap: tag each record with its type information, like class descriptors for dynamic method calls from text/html 2010-09-22T01:47:13+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/compilers_in_action?rev=1285112833&do=diff Compilers in Action gcc Compiler for C Example program in C programming language #include <stdio.h> 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: text/html 2009-11-03T20:14:40+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/compiling_conditional_expressions?rev=1257275680&do=diff 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 * text/html 2012-11-20T23:23:34+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/compiling_if_then_else?rev=1353450214&do=diff 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 nElse [[ sThen ]] goto nAfter nElse: [[ sElse ]] nAfter: text/html 2015-04-21T17:35:15+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/compiling_statement_sequence?rev=1429630515&do=diff Compiling Statement Sequence text/html 2012-11-20T23:25:23+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/compiling_while?rev=1353450323&do=diff Compiling While Assume the compilation of c will generate a sequence that will leave 0 or 1 on the stack, expressing the truth value of c: [[ while(c) s ]] = nStart: [[c]] if_eq nAfter [[s]] goto nStart nAfter: ... Example text/html 2013-10-07T09:30:19+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/computing_follow_sets?rev=1381131019&do=diff Computing Follow Sets The Need for Follow What if we have X = Y Z | U and U is nullable? When can we choose a nullable alternative (U)? * if current token is either in first(U) or it could follow non-terminal X t is in follow(X), if there exists a derivation containing substring X t text/html 2009-11-03T20:09:24+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/computing_labels?rev=1257275364&do=diff 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: text/html 2010-10-05T20:43:12+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/computing_nullable_nonterminals?rev=1286304192&do=diff Nullable Non-terminals In general, a non-terminal can expand to empty string * example: statement sequence in while language grammar first(Y Z) = first(Y)? what if Y can derive empty string?++ A sequence of non-terminals is nullable if it can derive an empty string text/html 2009-11-08T21:28:24+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/concrete_syntax_of_while?rev=1257712104&do=diff 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 ::= "+" | "-" | "*" | "/" | "%" | "==" | ">" | "<" | "&&" | "||" text/html 2009-10-04T21:45:22+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/concrete_vs_abstract_syntax_trees?rev=1254685522&do=diff Concrete vs Abstract Syntax Trees Concrete Syntax Tree Given a grammar, a concrete syntax tree is a directed tree with ordered children, given like this: * leaves are labeled by terminals (tokens) * internal nodes are labelled by non-terminals text/html 2010-12-06T00:32:12+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/constant_propagation?rev=1291591932&do=diff Constant Propagation Computes that certain expressions are constants. For each variable maintains * (initial value) * some constant value C * the information that the value is not known to be constant int 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 em… text/html 2011-11-28T02:37:43+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/control-flow_graph_definition?rev=1322444263&do=diff Control-Flow Graph Definition Related to traditional notion of flow charts Example program 1: while (i < 10) { println(j); i = i + 1; j = j +2*i + 1; } Corresponding control-flow graph: [CFG for Squaring] Example program 2: int i = n; while (i > 1) { println(i); if (i % 2 == 0) { i = i / 2; } else { i = 3*i + 1; } } text/html 2009-11-23T00:46:05+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/control-flow_graph_to_assembly_with_global_variables?rev=1258933565&do=diff 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)) text/html 2010-09-28T22:23:35+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/course_information?rev=1285705415&do=diff Staff Lectures: * Viktor Kuncak Practical and Theoretical Exercises: * Philippe Suter * Giuliano Losa Assistants-Étudiants: * Etienne Kneuss * Pierre-François Laquerre Secretary: Danielle Chamberlain Schedule * Mondays 10:15-12:00 - Lectures in INM 202 * Wednesday 08:15-10:00 - Project work, in text/html 2015-04-21T17:35:15+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/cyk_parsing_algorithm?rev=1429630515&do=diff CYK Parsing Algorithm for General Context-Free Grammars Assume the grammar is in Chomsky Normal Form. Example Grammar S ::= L R | S S | L X X ::= S R L ::= "{" R ::= "}" Consider an input string { { } { } { } } For each terminal t in input, for which non-terminal X is it the case that X text/html 2009-11-15T17:58:09+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/decomposing_complex_expressions?rev=1258304289&do=diff Decomposing Complex Expressions [Simplifying Expressions in CFG] Example: x = y * z + u * v becomes t1 = y * z t2 = u * v x = t1 + t2 text/html 2009-09-27T23:04:39+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/describing_balanced_parantheses?rev=1254085479&do=diff Describing Balanced Parentheses Parentheses in expressions, statement blocks, nested definitions, etc: {{}{{{}{}}{}}}{}{{}{}} { {} {{{}{}}{}} } {} {{}{}} The language of balanced (matched) parentheses (here: curly braces) * at each point count number of open minus number of closed parantheses text/html 2015-04-21T17:35:15+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/designing_correct_data-flow_analyses?rev=1429630515&do=diff Designing Correct Data-Flow Analyses We describe guidelines to design a correct analysis for a set of properties of interest Define Properties of Interest Define precisely what property is needed (depends on the application), e.g. * absence of errors text/html 2009-11-29T20:06:54+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/dispatched_procedures?rev=1259521614&do=diff Dynamic Method Dispatch in Object-Oriented Languages How do we know which method is invoked here in the following: var x : Object; println(x.toString()) The invoked method depends on the dynamic type of 'x'. We can view the method to execute as a field of function type text/html 2009-10-11T14:41:21+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/dragon_book?rev=1255264881&do=diff Dragon Book Compilers: Principles, Techniques, and Tools (2nd Edition) by Alfred V. Aho, Monica S. Lam, Ravi Sethi, Jeffrey D. Ullman Note that all references we make are to the 2nd edition, which has more material than the previous edition. text/html 2015-04-21T17:35:15+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/earley_parser?rev=1429630515&do=diff Earley Parser What is Earley Parser A parser for context-free grammars * works for arbitrary (even ambiguous) context-free grammars * driven by the input stream and start symbol * uses the well-known technique of dynamic programming (avoids unnecessary computation) text/html 2009-10-15T17:08:46+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/efficient_comparison_for_identifiers?rev=1255619326&do=diff 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 text/html 2015-04-21T17:35:15+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/efficiently_emitting_code?rev=1429630515&do=diff 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? text/html 2010-10-11T08:58:23+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/error_recovery_in_top-down_parser?rev=1286780303&do=diff Error Recovery According to some opinions error recover is not worth it * one error tends to trigger others * report error and stop * put cursor on the error * restart when user fixes it Approaches to error recovery in recursive descent parsing: text/html 2009-11-02T01:41:43+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/evaluating_postfix?rev=1257122503&do=diff 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 { … text/html 2009-12-14T16:01:18+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/exam?rev=1260802878&do=diff Stub for the exam Language: this time, we just extend Tool. Lexical Analysis We add the operators => (implication) and <=> (boolean equivalence, like !(x ^^ y)). Draw a deterministic automaton that accepts <=, =, ==, >=, =>, <=>, using longest-match rule. Mark different accepting states. text/html 2009-11-08T23:56:53+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/example_efficient_code_for_conditionals?rev=1257721013&do=diff 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; } } } text/html 2009-10-15T16:55:09+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/example_for_type_checking?rev=1255618509&do=diff Example for Type Checking class World { boolean z; int u; int f(boolean y) { z = y; if (u > 0) { int z; z = f(u) + 3; return z+z; } else { return 0; } } } text/html 2010-12-13T00:48:28+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/examples_for_initialization_analysis?rev=1292197708&do=diff Example for Initialization Analysis class Test { static void test(int p) { int n; p = p - 1; if (p > 0) { n = 100; } while (n != 0) { System.out.println(n); n = n - p; } } } What does compiler do with the above program? text/html 2009-12-14T01:27:49+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/examples_of_lazy_evaluation?rev=1260750469&do=diff Examples of Lazy Evaluation Example 1 evenNats = 0 : (map (+2) evenNats) firstTen = take 10 evenNats Hugs> :load /home/kuncak/lecture15/evenNats.hs Main> firstTen [0,2,4,6,8,10,12,14,16,18] Main> Example 2 ite c x y = if c then x else y test q = ite (q == 0) 100 (1.0 / q) v = test 0 text/html 2009-10-13T21:22:27+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/exercices_04?rev=1255461747&do=diff Exercises 04 text/html 2009-10-01T15:07:02+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/exercises_01?rev=1254402422&do=diff Exercises 01 Exercise 1 Write a regular expression for binary numbers greater than 101. Exercise 2 Write a regular expression for strings over the alphabet {a,b,c} that don't contain the continuous substring baa. Exercise 3 Constructing a lexer's DFA. See Tiger Book, Chapter 2.4 text/html 2009-10-01T15:05:40+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/exercises_02?rev=1254402340&do=diff Exercises 02 Exercise 1 Write an unambiguous grammar for palindromes over the alphabet {a,b}. Exercise 2 Write an unambiguous grammar that match the strings that match regular expression a*b* and have more as than bs. Exercise 3 Write a LL(1) grammar that accepts the same language as the following: text/html 2009-10-10T19:56:33+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/exercises_03?rev=1255197393&do=diff Exercices 03 Consider the following grammar: S' -> S EOF S -> s S -> i c S S -> i c S e S * Parse the following string: “icicses” using Earley parsing (show the list of sets of items you get until the string is recognized). * How many parses did you get? text/html 2009-10-14T18:09:04+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/exercises_04?rev=1255536544&do=diff Exercises 04 Exercise 1 a) Build the LR(0) DFA for this grammar: S → E eof E → id E → id (E) E → E + id b) Is this an LR(0) grammar? Give evidence. c) Is this an SLR grammar? Give evidence. d) Is this an LR(1) grammar? Give evidence. text/html 2009-10-21T17:24:07+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/exercises_05?rev=1256138647&do=diff Exercices 05 Write down the type derivation tree for the example for type checking seen in the course. [Solution] text/html 2009-10-26T19:47:50+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/exercises_06?rev=1256582870&do=diff Type check example expressions. Multiple possible types and example of type schema. Consider lambda with variable capture, with naive substitution. Example of evaluation. What scoping policy is this? Show that type checking soundness fails. formally capture-avoiding and capture non-avoiding substitution, and showing that subject reduction property for type systems fails to hold if you do not have capture avoiding substitution. text/html 2009-11-10T23:33:05+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/exercises_08?rev=1257892385&do=diff 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; } } text/html 2009-12-14T10:19:36+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/final-report?rev=1260782376&do=diff Labs: Final Report Your final report is due on Sat. January 9th, 23.55. Please submit it through Moodle. The code of your extended compiler is due at the same time. Contents of the Report You are encouraged to use the following (LaTeX) template for your report: text/html 2009-11-29T12:48:26+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/free_lists_by_size?rev=1259495306&do=diff 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 text/html 2009-11-25T18:34:35+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/full_employment_theorem_for_compiler_writers?rev=1259170475&do=diff Full Employment Theorem for Compiler Writers Informal Statement The problem of given a program and a property that is true for some programs and false for other programs, check (precisely) whether program satisfies is undecidable if property talks only about the values computed by the program and program termination (and not e.g. how the values are computed). text/html 2012-10-30T23:08:05+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/functional_maps?rev=1351634885&do=diff Efficient Functional Maps Functional Balanced Search Trees Idea: * update creates a new path (copying only log(n) nodes) * lookup and update in log(n) We present a simplified example that stores integers * a real implementation stores comparable text/html 2009-10-15T17:06:49+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/functional_versus_imperative_maps?rev=1255619209&do=diff 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 * correspond to text/html 2009-12-14T02:30:11+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/generational_garbage_collectors?rev=1260754211&do=diff 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 text/html 2010-12-01T11:09:05+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/global_function_pointers?rev=1291198145&do=diff Global Function Pointers To pass global (static) functions, we simply pass their addresses We need to know the calling convention for all function values that can be called var exlaim = "!!!" def simpleNotify(msg : String) = { println(msg) } def noisyNotify(msg : String) = { beep(1024) popUp(msg) beep(2048) popUp(msg + exclaim) beep(512) } def alarm(time : Int, notify : msg => unit) = { if (currentTime==time) { notify("Wake up!") } } alarm(0700, simpleNotify) alarm(0800,… text/html 2009-10-13T19:16:14+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/grammar_of_formulas_in_cup?rev=1255454174&do=diff Grammar for Logical Formulas for Java CUP Parser The following is a LALR(1) grammar with precedence declarations for a subset of Isabelle/HOL formulas. /* Terminals (tokens returned by the scanner). */ terminal EQUALS, AND, ASSIGN, UNION, ALL, EX, NOT, DOT, LPAREN, RPAREN; terminal LCURLYBRACKET, RCURLYBRACKET, COMMA; terminal String ID; /* Non-terminals */ non terminal boundform; non terminal boundform_list; non terminal formula; non terminal f… text/html 2010-09-28T16:56:40+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/hand-written_scanner_for_while_language?rev=1285685800&do=diff Hand-Written Lexical Analyzer for While Lexical Analyzer Also called: lexer, scanner, or tokenizer Transforms sequence of characters w h i l e ( c o u n t < 1 0 ) { LF c o u n t = into sequence of tokens while ( count text/html 2009-11-30T10:35:13+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/higher-order_functions?rev=1259573713&do=diff Higher-Order Functions None of the previous techniques works when nested functions are returned as arguments Consider example: object Test extends Application { def greet(firstLine : String, message : String) = { println(firstLine) println(message) } def getGreeter(title : String) : (String => Int) = { var myLine = "Dear " + title def myGreeter(name : String) = { println(myLine + " " + name) myLine = myLine + "..." println("How are you doing today?"… text/html 2009-10-01T16:29:01+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/homework_01?rev=1254407341&do=diff Homework 01 Due Wednesday, 30th September, 10:15am. Hand it in to Giuliano Losa before the beginning of the exercise session. Problem 1 Write a regular expression for the language of nonnegative integer constants in the C programming language, where numbers beginning with O are octal constants and other numbers are decimal constants. text/html 2009-10-10T19:11:00+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/homework_02?rev=1255194660&do=diff Homework 02 Problem 1 Find nullable, FIRST, and FOLLOW sets for this grammar; then construct the LL(1) parsing table. 1.S′ → S EOF 2.S → 3.S → XS 4.B → \ begin { WORD } 5.E → \ end { WORD } 6.X → BSE 7.X → { S } 8.X → WORD text/html 2009-10-21T16:46:36+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/homework_03?rev=1256136396&do=diff Homework 03 Problem 1 Transform the following grammar to Chomsky Normal Form: S -> (S)|A A -> SS|““ Please give the detailed steps of the algorithm. Problem 2 Consider the following grammar: E ::= E+E E ::= E*E E ::= E=E E ::= Num | true | false text/html 2009-10-21T16:48:06+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/homework_04?rev=1256136486&do=diff Homework 04 To be handed out on October 21st, 2009, together with Homework 03. Consider the following grammar of a simple programming language: S :::= E eof E ::= if (E) E E ::= if (E) E else E E ::= E + E E ::= (E) E ::= ID where the tokens are: eof, if, (, ), else, +, id text/html 2009-10-28T21:57:22+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/homework_05?rev=1256763442&do=diff Homework 05 To be handed on October 28th, 10AM Problem 1 If the following programs type-check according to the rules given in the course, give the corresponding type derivation tree, otherwise give a partial tree that shows where it doesn't work (like in text/html 2009-11-11T00:00:42+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/homework_06?rev=1257894042&do=diff Homework 06: Type Checking Arrays Problem 1: Java's type system The following Java program defines a Cell class, which stores an integer that can only be set once, and defines its subclass ReusableCell, which has additional functionality to reset the value. It then declares and assigns values to arrays of Cell and ReusableCell objects. text/html 2015-04-21T17:35:15+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/homework_07?rev=1429630515&do=diff Homework 7 This homework is important, it may carry more points than others. For this homework only, you can do it in groups of 2 and hand in only one solution per group, but write down the name of others that you worked with. We consider a small language that contains the x^y operator. Our goal is to design a system where x^y is never evaluated for negative y. text/html 2009-11-19T20:23:40+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/homework_08?rev=1258658620&do=diff Translate manually into bytecodes using the techniques in Compilation as Tree Transformation: * First translate the while loop to instructions. * Give code for the loop * Take care of the rest b should be treated as a member of the current class. boolean b; int f(int x, int y, int z) { while ((!b && (x > 2*(y+z))) || (x < 2*y +z)) { x = x +3; } return x; } text/html 2010-12-06T01:01:42+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/idea_of_data_flow_analysis?rev=1291593702&do=diff Idea of Data Flow Analysis We 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) text/html 2009-12-14T02:11:10+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/idea_of_garbage_collection?rev=1260753070&do=diff Idea of Garbage Collection Idea: * 'free' from Lecture 14 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 * text/html 2015-04-21T17:35:15+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/idea_of_type_rules?rev=1429630515&do=diff Idea of Type Rules Notation for Type Rules We write to indicate that * is well-typed inside and has resulting type Examples: Type rule for addition: e1 : Int, e2 : Int ------------------ e1+e2 : Int For <=: e1 : int, e2 : int ------------------ e1<=e2 : boolean text/html 2009-10-15T15:28:52+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/identifiers_vs_symbols_example?rev=1255613332&do=diff Identifiers vs Symbols Example 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); } } text/html 2010-12-07T21:56:50+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/if_statements_to_cfg?rev=1291755410&do=diff Conferting If Statements to CFG [Translating If to CFG] Note: better translation uses two destination vertices, analogously to Compilation as Tree Transformation text/html 2009-09-15T14:58:45+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/implementing_finite_state_machines?rev=1253019525&do=diff 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]] text/html 2009-12-14T02:26:21+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/incremenatal_garbage_collectors?rev=1260753981&do=diff 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 text/html 2009-11-29T23:35:35+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/instruction_selection?rev=1259534135&do=diff 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 text/html 2009-11-30T00:50:37+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/instruction_selection_using_tree_grammars?rev=1259538637&do=diff Instruction Selection Using Tree Grammars Maximal Munch * start from root * take tile with most nodes that fits Dynamic Programming More sophisticated: dynamic programming * bottom up * find best tiling for each subtree See Tiger book, page 182 Compiling Dynamic Programming Tiling for Given Architecture text/html 2009-09-15T23:22:13+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/interpreter.scala?rev=1253049733&do=diff 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... } } text/html 2009-11-09T00:55:10+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/interpreting_cfg?rev=1257724510&do=diff 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 text/html 2009-10-11T13:49:04+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/interpreting_ll_parsing_table?rev=1255261744&do=diff Interpreting 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 { case {i} => // exactly one choice rhs = p(X,i) // choose correct rig… text/html 2009-10-04T20:37:55+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/isquares.while?rev=1254681475&do=diff Example Program to Feed Into While Language Pretty Printer i = 0; j = 0; while (i - 10) { i = i + 1; j = j + 2*i+1; println(j);} text/html 2009-09-15T15:03:48+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/javacc?rev=1253019828&do=diff JavaCC Is a compiler compiler: generates lexers and parsers. URL: <https://javacc.dev.java.net/> It has been used for realistic Java parsers and is used in the Tiger book. text/html 2012-11-19T01:55:52+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/jvm_instructions?rev=1353286552&do=diff JVM Instructions Reference From JVM Spec: * JVM Instruction Summary * Example instruction descriptions: * imul What instructions operate on: * operands that are part of instruction itself, following their op code (unique number for instruction) * operand stack - used for computation text/html 2009-09-23T00:32:31+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/lab02-build.xml?rev=1253658751&do=diff <?xml version="1.0" encoding="UTF-8" ?> <project name="toolc" default="dist" basedir="."> <description> The toolc project: building a compiler for the Tool programming language. </description> <!-- All settings can be overridden in a file called local.properties. --> <!-- Scala & Java --> <property environment="env" /> <property name="scala.home" value="${env.SCALA_HOME}" /> <property name="scala-library.jar" value="${scala.home}/lib/scala-library.jar" /> … text/html 2009-09-23T00:22:06+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/lab02-compiler.scala?rev=1253658126&do=diff package tool import scala.io.Source import lexer.Lexer class Compiler(val fileName: String) extends Reporter with Lexer { import lexer.Tokens._ val source: Source = Source.fromFile(fileName) def compile: Unit = { var t: Token = Token(BAD) do { t = nextToken print(t.info + "(" + t.posString + ") ") } while(t.info != EOF) terminateIfErrors } } text/html 2009-09-23T00:23:44+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/lab02-factorial.tool?rev=1253658224&do=diff object Factorial { def main() : Unit = { println(new Fact().computeFactorial(10)); } } class Fact { def computeFactorial(num : Int) : Int = { var num_aux : Int; if (num < 1) num_aux = 1; else num_aux = num * (this.computeFactorial(num - 1)); return num_aux; } } text/html 2009-09-23T00:02:04+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/lab02-lexer.scala?rev=1253656924&do=diff package tool.lexer import scala.io.Source trait Lexer { // This indicates to the Scala compiler that this trait will be composed with // a Compiler. This implies that the methods from the Reporter class will be // available at run-time, as well as the reference to the Source object. self: Compiler => import Tokens._ // You have access to the variable source defined in Compiler.scala, of the type // scala.io.Source in here. You need to use it as your character stream for the /… text/html 2009-09-23T00:18:43+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/lab02-main.scala?rev=1253657923&do=diff package tool object Main { def main(args: Array[String]) { if (args.length != 1) { Console.err.println("usage: toolc <File.tool>") System.exit(-1) } val compUnit = new Compiler(args(0)) compUnit.compile } } text/html 2009-09-22T23:54:35+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/lab02-positional.scala?rev=1253656475&do=diff package tool /** 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 => private var _pos: Int = -1 def pos: Int = _pos def setPos(pos: Int): self.type = { this._pos = pos self } /** Copies the position from another Positional object. Returns the * object on which the setPos method was called. */ def setPos(other: P… text/html 2009-09-23T00:04:39+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/lab02-reporter.scala?rev=1253657079&do=diff package tool trait Reporter { // Informs scalac that this will be mixed-in with the class Compiler, so // we'll have access to the source file information (scala.io.Source has nice // methods for displaying error messages). this: Compiler => private var foundErrors = false /** Simple warnings */ def warn(msg: String): Unit = outputErrorMsg("Warning", msg) def warn(msg: String, i: Int): Unit = report(i, "Warning: " + msg) def warn(msg: String, pos: Positional): Unit = warn(ms… text/html 2009-09-23T00:11:01+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/lab02-tokens.scala?rev=1253657461&do=diff package tool.lexer object Tokens { /** The info attached to a token (beside the position). For most tokens this is just the class information (eg. "it's a colon"). For literals and identifiers, this also contains the proper information (eg. "this number literal represents 42"). */ sealed trait TokenInfo { def tokenClass: TokenClass } /** All tokens have a corresponding token class: for instance, all identifiers have the IDCLASS. For "informationless" t… text/html 2009-09-28T19:31:00+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/lab03-compiler.scala?rev=1254159060&do=diff package tool import parser.Parser import scala.io.Source class Compiler(val fileName: String) extends Reporter with Parser { val source: Source = Source.fromFile(fileName) def compile: Unit = { import parser.Trees._ // Parsing var parsedTree: Option[Tree] = None parsedTree = Some(parseSource) terminateIfErrors val mainProg: Program = parsedTree match { case Some(p:Program) => p case _ => scala.Predef.error("Main program expected from parser.") … text/html 2009-09-28T19:10:53+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/lab03-parser.scala?rev=1254157853&do=diff package tool.parser import tool.lexer.Lexer import scala.io.Source /** LL parser for the Tool grammar. */ trait Parser extends Lexer { self: Compiler => import Trees._ import tool.lexer.Tokens._ def parseSource: Tree = { readToken // initializes the parser by calling the method in the Lexer. val tree: Tree = parseGoal terminateIfErrors tree } /** Store the current token, as read from the lexer. */ private var currentToken: Token = Token(BAD) def readToken: … text/html 2009-09-28T19:18:27+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/lab03-prettyprinter.scala?rev=1254158307&do=diff package tool object TreePrinter { import parser.Trees._ def apply(t: Tree): String = { /* construct and return the appropriate string ... */ } } text/html 2009-09-28T19:00:32+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/lab03-trees.scala?rev=1254157232&do=diff package tool.parser object Trees { sealed trait Tree extends Positional case class Program(main: MainObject, classes: List[ClassDecl]) extends Tree case class MainObject(id: 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 extends Tree case c… text/html 2009-10-13T22:01:43+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/lab05-analyzer?rev=1255464103&do=diff package tool.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 = /* ... */ } text/html 2009-10-21T08:45:04+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/lab05-compilerstub?rev=1256107504&do=diff package tool import parser.Parser import analyzer.Analyzer import scala.io.Source class Compiler(val fileName: String) extends Reporter with Parser with Analyzer { val source: Source = Source.fromFile(fileName) def compile: Unit = { import parser.Trees._ import analyzer.Symbols._ // Parsing var parsedTree: Option[Tree] = None parsedTree = Some(parseSource) terminateIfErrors val mainProg: Program = parsedTree match { case Some(p:Program… text/html 2009-10-13T21:59:32+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/lab05-symbols?rev=1255463972&do=diff package tool.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 will… text/html 2009-10-13T22:02:34+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/lab05-treeprinter?rev=1255464154&do=diff package tool 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... */ // ... // Thi… text/html 2009-10-13T22:00:42+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/lab05-trees?rev=1255464042&do=diff package tool.parser object Trees { import analyzer.Symbols._ sealed trait Tree extends Positional // You should 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, parent: Option[… text/html 2009-10-21T08:44:08+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/lab06-compiler?rev=1256107448&do=diff package tool import parser.Parser import analyzer.Analyzer import analyzer.TypeChecker import scala.io.Source class Compiler(val fileName: String) extends Reporter with Parser with Analyzer with TypeChecker { val source: Source = Source.fromFile(fileName) def compile: Unit = { import parser.Trees._ import analyzer.Symbols._ // Parsing var parsedTree: Option[Tree] = None parsedTree = Some(parseSource) terminateIfErrors val mainProg: Progra… text/html 2009-10-20T22:34:23+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/lab06-typechecker?rev=1256070863&do=diff package tool.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 in … text/html 2009-10-20T22:33:24+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/lab06-types?rev=1256070804&do=diff package tool.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 obje… text/html 2009-11-03T17:07:38+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/lab08-codegen?rev=1257264458&do=diff package tool.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 = { // ... } } text/html 2009-11-04T10:25:45+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/lab08-compiler?rev=1257326745&do=diff package tool import parser.Parser import analyzer.Analyzer import analyzer.TypeChecker import code.CodeGenerator import scala.io.Source class Compiler(val fileName: String) extends Reporter with Parser with Analyzer with TypeChecker with CodeGenerator { val source: Source = Source.fromFile(fileName) def compile(classDir: String): Unit = { import parser.Trees._ import analyzer.Symbols._ val outputDir = classDir + "/" val checkDir: java.io.File = new … text/html 2009-11-04T10:24:09+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/lab08-main?rev=1257326649&do=diff package tool object Main { def main(args: Array[String]) { var parsedTree: Option[parser.Trees.Tree] = None if (args.length != 1 && args.length != 3) { Console.err.println("usage: toolc <File.tool> [-d outputdir]") System.exit(-1) } val compUnit = new Compiler(args(0)) if(args.length == 1) { compUnit.compile("./") } else { if(!"-d".equals(args(1))) { Console.err.println("Unrecognized option: " + args(1)) System.exit(-1) … text/html 2009-09-16T10:33:38+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/labs_01?rev=1253090018&do=diff 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 text/html 2009-09-23T00:43:53+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/labs_02?rev=1253659433&do=diff Labs 02 This assignment is the first part of the Tool 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 Write two small Tool programs per person (four per group of two) to constitute a corpus of test cases that we will use throughout the compiler project. text/html 2009-10-13T21:45:57+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/labs_03?rev=1255463157&do=diff Labs 03 This week and the next one, you'll work on the second part of the Tool compiler project. Your goal is to manually implement a recursive-descent parser to transform programs described by the Tool 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. text/html 2009-10-07T10:01:23+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/labs_04?rev=1254902483&do=diff Labs 04 Finish Labs 03. text/html 2009-10-21T17:16:16+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/labs_05?rev=1256138176&do=diff Labs 05 This week you will add name analysis to your Tool 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 Tuesday, Oct. 27th, 11.55pm (23h55). Note that the type checker will be due the following week, so make sure you start working on it as early as possible. text/html 2009-10-20T22:30:20+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/labs_06?rev=1256070620&do=diff Well, for some definition of (in)valid. text/html 2009-10-20T22:05:20+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/labs_07?rev=1256069120&do=diff Labs 07 You should have handed in Labs 05 by now. How about you celebrate by finishing Labs 06 ? text/html 2009-11-03T17:09:40+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/labs_08?rev=1257264580&do=diff Labs 08 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 :) text/html 2009-11-11T09:08:35+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/labs_09?rev=1257926915&do=diff Labs 09 Finish Labs 08. text/html 2010-11-21T18:10:00+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/labs_10?rev=1290359400&do=diff Labs 10: Your Turn You have now written a compiler for a simple language. There are plenty of ways you can improve the compiler or the language it supports. We present some ideas you can build on. You will have to write a small proposal describing what you want to implement and how you plan to do it. This proposal should include: text/html 2015-04-21T17:35:15+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/lambda_calculus?rev=1429630515&do=diff 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 text/html 2010-11-14T20:32:16+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/languages_using_prefix_or_postfix_only?rev=1289763136&do=diff 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 text/html 2010-09-28T16:43:19+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/lecture_01?rev=1285684999&do=diff Lecture 01: Introduction. Lexical Analysis Course Information Compilers and Interpreters What is a Compiler Compilers in Action Phases of a Compiler Why Study Compilers Describing Syntax of (Programming) Languages While Language Abstract Syntax of While Strings and languages Regular expression Tokens (Words) of While Language Context-Free Grammars Concrete Syntax of While References * Tiger book, Chapters 1-2 * Slides from previous years: * Compilation 2007 Slides 1 (Fren… text/html 2009-10-04T17:51:47+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/lecture_02?rev=1254671507&do=diff Lecture 02: Lexical Analysis Course Information Phases of a Compiler Lexical Analysis without Tools Why Study Lexical Analysis Hand-Written Scanner for While Language Towards a Systematic Approach to Lexing State Machines and Regular Expressions Finite state machine Determinization of finite state machine Finite state machine with epsilon transitions Closure properties of finite state machines Equivalence of finite state machine and regular expression languages Limitations of Regula… text/html 2009-10-04T17:52:04+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/lecture_03?rev=1254671524&do=diff Lecture 03 We have seen lexical analysis in Lecture 02. Phases of a Compiler Describing Balanced Parantheses Recursive Descent Parsing Recursive Descent Idea Recursive Descent for Polynomials Left Factoring Recursive Descent Avoiding Left Recursion in Recursive Descent While Language Parser First, Null, Follow Sets Basic Idea of First Symbol Computation Computing Nullable Nonterminals Computing Follow Sets LL(1) Table-Driven Parsing Algorithm LL(1) Table-Driven Parsing Overview E… text/html 2009-10-11T12:15:41+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/lecture_04?rev=1255256141&do=diff Lecture 04 Continuing Lecture 03 Notion of Semantic Action Syntax Trees Concrete vs Abstract Syntax Trees Modifying Parser to Construct AST Pretty Printing AST Textbook Parsing of General Context-Free Grammars About Parsing Context-Free Grammars Chomsky Normal Form CYK Parsing Algorithm Transforming to Chomsky Normal Form A Direct Method for Efficiently Parsing General Context-Free Grammars Earley Parser Next: deterministic bottom up parsing in Lecture 05 text/html 2009-10-15T12:21:10+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/lecture_05?rev=1255602070&do=diff Lecture 05: LR Parsing Continuing Lecture 04, Lecture 03 Announcement: projects updated, include Earley parser Introduction Pushdown Automata LL Parser uses Leftmost Derivation LR Parser uses Rightmost Derivation LR Parser Runs Automaton over Stack LR Parser without Lookahead Automata for LR Parsing without Lookahead LR(0) Parser Actions SLR Parser Actions LR Parser with Lookahead LR Parsing with Lookahead Items LR(1) Parser Actions LR Parsing Tables Precedence Precedence in LR … text/html 2009-10-26T19:46:46+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/lecture_06?rev=1256582806&do=diff Lecture 06: Semantic Analysis Intro Scopes of Symbols Identifiers vs Symbols Example Simple Language with Local Variables Scoping Rules Affect Program Meaning Notation for Maps Type Checking Rules for a Simple Language Idea of Type Rules Type Rules using Environment Type Rules for Statements and Expressions Type Rule for Block Statement Example for Type Checking Implementation: Symbol Tables and Error Reporting Symbol Table Contents Functional versus Imperative Maps An Efficient I… text/html 2009-11-01T22:48:37+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/lecture_07?rev=1257112117&do=diff Lecture 07: Soundness of Type Systems Continuing Lecture 06 Functional Maps Lambda Calculus with Simple Types Lambda Calculus Simple Types for Lambda Calculus Type Checking Let and Letrec Type Soundness for Simple Types Proving Safety Properties using Types Operational Semantics of Lambda with Letrec Type Soundness for Simply Typed Lambda Calculus Continued in Lecture 08 References * Types and Programming Languages, Chapter 5, Chapter 8, Sections 9.1--9.3 (pages 89-107) * Lambda… text/html 2010-10-31T22:46:53+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/lecture_08?rev=1288561613&do=diff Advanced Types. Code Generation Continuation of Lecture 07 Subtyping Notion of Subtyping Subtyping for Functions Subtyping for Assignments and Soundness Idea Subtyping with Assignments and Generics Types Expressing Program Properties Liquid Types Demo Type Checking References * Lambda Calculi with Types * [A Syntactic Approach to Type Soundness] * Foundations of Software, the EPFL master's level course taught by Prof. Martin Odersky, covers type systems in greater depth * Types… text/html 2009-11-04T13:43:32+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/lecture_09?rev=1257338612&do=diff Lecture 09: Compiling Expressions to Stack Machine 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 Expressions Emitting Code for Assignments Accessing and Storing Variables Compiling Statement Sequence Efficiently Emitting Code Compiling Control-Flow Statements Booleans and Data Representation Compiling … text/html 2009-11-15T22:30:42+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/lecture_10?rev=1258320642&do=diff Lecture 10 Continuing Lecture 09 Compiling Control Flow Branching JVM Instructions Compiling If Then Else Compiling While Compiling Boolean Operators Translation of Relations Postfix Translation of Boolean Operators Compiling Conditional Expressions Short-Circuit Evaluation Better Code Generation for Conditions Example Efficient Code for Conditionals Compilation as Tree Transformation Method Calls in JVM Compiled Factorial Example Method Calls Objects in JVM Object and Referenc… text/html 2009-11-17T12:16:39+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/lecture_11?rev=1258456599&do=diff Data-Flow Analysis Applications of Data-Flow Analysis How to Generate Control-Flow Graph Recall Control-Flow Graph Definition from the end of Lecture 10 In Scala: * DiGraphs.scala * SimpleCFG.scala Translation of syntax trees to control-flow graphs is (at a high-level) similar to translation from regular expressions to finite-state machines (see text/html 2009-11-25T00:33:27+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/lecture_12?rev=1259105607&do=diff Lecture 12: Data Flow Analysis Algorithms. Initialization Analysis Continuing Lecture 11 Scala Code for Data-Flow Analysis * DataFlowAnalysis.scala * SignAnalysis.scala Correctness of Data-Flow Analysis Designing Correct Data-Flow Analyses Initialization Analysis Examples for Initialization Analysis Checking Initialization Using Data-Flow Analysis Live Variable Analysis Live-Variable Analysis Continued (surprise, surprise) in text/html 2009-11-29T11:23:26+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/lecture_13?rev=1259490206&do=diff Lecture 13: Live-Variable Analysis. Compiling to Register Machines Continuing Lecture 12 Live Variable Analysis Live-Variable Analysis Full Employment Theorem for Compiler Writers Register Machines Register machines are an alternative to compilation to stack-based machines in Lecture 09; they are closer to modern processors. ARM Architecture text/html 2010-10-01T21:58:50+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/lecture_14?rev=1285963130&do=diff Lecture 14: Procedures, Memory, SSA, Instruction Selection Continuing from Lecture 13 Compiling Advanced forms of Procedures Stack Frames and Procedure Calls Simple Nested Procedures Global Function Pointers Higher-Order Functions Dispatched Procedures References * Tiger book, chapters 6, 15 * Simon L. Peyton Jones, The Implementation of Functional Programming Languages, Prentice-Hall, 1987 text/html 2009-12-16T16:29:17+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/lecture_15?rev=1260977357&do=diff Lecture 15: Overview of Some Additional Topics Schedule Martin Vechev talk Elements of Garbage Collection (GC) Idea of Garbage Collection Reference Counting Mark and Sweep Collector * Pointer Reversal Memory Fragmentation Simple Copying Collector <- Generational Garbage Collectors Incremenatal Garbage Collectors Compiler Interface to Garbage Collector References * Tiger book, Chapter 13 * [Java without Coffee Breaks] * [Write Barrier Removal by Static Analysis] * [CGCExpl… text/html 2009-09-27T23:05:55+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/left_factoring_recursive_descent?rev=1254085555&do=diff Left Factoring Recursive Descent Consider a variant of grammar with this definition: polynomial ::= term | term "+" polynomial How to write parsePolynomial procedure for this grammar? * 'term' can be arbitrarily complex * which alternative to choose? text/html 2009-09-27T23:07:18+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/lexer.scala?rev=1254085638&do=diff 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.… text/html 2009-09-14T01:16:20+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/lexerinterface.scala?rev=1252883780&do=diff class Lexer(ch : CharStream) { var current : Token def next : Unit = { ... } } text/html 2009-09-14T01:17:47+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/lexertest.scala?rev=1252883867&do=diff object LexerTest { def main(args : Array[String]) = { val lex = new Lexer(new CharStream(args(0))) while (lex.current != EOF) { println(lex.current) lex.next } } } text/html 2009-09-16T00:28:48+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/limitations_of_regular_expressions?rev=1253053728&do=diff Limitations of Regular Expressions Take a deterministic finite state machine with states. Suppose that a word of with is accepted by the machine. This means that the machine went through some state twice, say after reading and then after reading symbols of the word. text/html 2010-11-22T01:48:04+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/linearizing_trees_with_control-flow?rev=1290386884&do=diff Linearizing Trees with Control-Flow Evaluating control-flow in interpreter is easy * recall the interpreter, as in Labs 01 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") } } ... } text/html 2015-04-21T17:35:15+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/live-variable_analysis?rev=1429630515&do=diff Live-Variable Analysis For each program point, and each variable approximately compute whether the variable is: * definitely not live: its current value will not be used in the future, or * it is possibly live: its value may be used in the future text/html 2009-09-27T23:11:15+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/ll_1_table-driven_parsing_overview?rev=1254085875&do=diff LL(1) Table-Driven Parsing Overview First, compute nullable, first, follow Then, make parsing table which stores the alternative, given * non-terminal being parsed (in which procedure we are) * current token Given (X ::= | ... | ) we insert alternative j into table iff text/html 2009-10-04T23:32:01+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/ll_parser_uses_leftmost_derivation?rev=1254691921&do=diff 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: text/html 2009-10-11T18:04:31+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/lr_0_parser_actions?rev=1255277071&do=diff 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) text/html 2009-10-11T19:45:47+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/lr_1_parser_actions?rev=1255283147&do=diff 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 text/html 2010-10-24T22:24:33+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/lr_parser_runs_automaton_over_stack?rev=1287951873&do=diff LR Parser Runs Automaton over Stack Key property: Stack contains a prefix of rightmost derivation consistent with the input so far * this property depends also on the initial symbol Next action of the parser should preserve this property Key question in LR parsing text/html 2009-10-04T23:38:10+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/lr_parser_uses_rightmost_derivation?rev=1254692290&do=diff 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 text/html 2011-10-28T20:34:33+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/lr_parsing_tables?rev=1319826873&do=diff 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' text/html 2015-04-21T17:35:15+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/lr_parsing_with_lookahead_items?rev=1429630515&do=diff 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 * text/html 2009-09-15T23:23:02+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/main.scala?rev=1253049782&do=diff 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… text/html 2010-12-13T08:58:07+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/malloc_and_free?rev=1292227087&do=diff Malloc and Free In some programming languages, e.g. in 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 text/html 2010-12-01T02:03:13+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/mallocfree.scala?rev=1291165393&do=diff // 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 … text/html 2010-12-01T01:57:17+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/mallocinfmem.scala?rev=1291165037&do=diff // 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… text/html 2009-12-14T10:10:27+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/mark_and_sweep_collector?rev=1260781827&do=diff 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 text/html 2009-12-14T10:12:14+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/memory_fragmentation?rev=1260781934&do=diff 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! Our memory starts to look like the Rolex Learning Center! text/html 2010-11-29T01:26:53+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/memory_layout_for_compiled_program?rev=1290990413&do=diff 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 text/html 2012-11-25T15:21:53+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/method_calls?rev=1353853313&do=diff Method Calls Consult relevant section in JVM Spec Relevant Instructions Invoking methods: * invokestatic * invokevirtual Returning value from methods: * ireturn * areturn * return Translation Rule for Calls [[ x = myMethodName(e1,e2) ]] = [[e1]] [[e2]] invoke(virtual/static) #13 istore #x .... constant pool area 0: "hello, world" 1: ... 13: className.myMethodName/(II)I ... text/html 2009-12-14T03:10:27+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/mode_analysis?rev=1260756627&do=diff Mode Analysis Determine which parameters used as inputs, which as outputs * if some parameter is always output, it can be handled more efficiently Constraint-based mode analysis of mercury by David Overton, Zoltan Somogyi, Peter J. Stuckey ([pdf]) More generally, semantic simplification analyses: text/html 2009-10-04T20:59:43+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/modifying_parser_to_construct_ast?rev=1254682783&do=diff Modifying Parser to Construct AST 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 text/html 2009-12-14T10:58:45+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/motivation_for_lazy_evaluation?rev=1260784725&do=diff Motivation for Lazy Evaluation def ite[A](c : Boolean, thenV : A, elseV : A) = { if (c) thenV else elseV } def bigFraction(x : Int, y : Int) : Boolean = { ite(y==0, true, x/y > 100) } Ideally, each function call (like ite(c,t,e) ) can be replaced by its body without changing program behavior. text/html 2009-12-14T02:56:24+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/non-determinism_and_underspecification?rev=1260755784&do=diff Non-Determinism and Underspecification Underspecified command is command that gives one result, but program semantics does not say which one. * Example: parameter order in C compilers is underspecified * user cannot assume that parameters are evaluated e.g. left-to-right text/html 2015-04-21T17:35:15+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/notation_for_maps?rev=1429630515&do=diff Notation for Maps 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: text/html 2009-10-15T17:09:29+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/notion_of_hash-consing?rev=1255619369&do=diff 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 text/html 2009-10-04T20:13:12+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/notion_of_semantic_action?rev=1254679992&do=diff Semantic Actions in a Compiler Parser as Recognizer In the theory of formal languages, a parser is simply an algorithm with: INPUT: * context-free grammar with a start symbol * a word (sequence of terminal symbols) OUTPUT: * yes, if in the grammar text/html 2015-04-21T17:35:15+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/notion_of_subtyping?rev=1429630515&do=diff 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 text/html 2012-11-25T15:25:39+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/object_and_reference_manipulation?rev=1353853539&do=diff Object and Reference Manipulation Consider the following (high-level) JVM instructions from JVM Spec: * new * ifnull * ifnonnull * getfield * putfield In lower level code, these instructions are implemented by mapping objects into chunks of memory. The addresses of dynamically allocated objects are returned by a memory allocator (malloc in C) or garbage collector in Java. Such memory management routines implement an illusion of a large graph-like memory, by finding free space in RAM… text/html 2015-04-21T17:35:15+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/operational_semantics_of_lambda_with_letrec?rev=1429630515&do=diff 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 text/html 2012-11-19T01:14:16+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/overview_of_classfile_constant_pool?rev=1353284056&do=diff 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 text/html 2009-11-02T01:37:39+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/overview_of_compiling_to_stack_machine?rev=1257122259&do=diff 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 tool compiler * compiler from the Pascal Programming Language to pascal UCSD Pascal P-code machine Source: Java (subset) abstract syntax tree text/html 2009-10-04T20:35:41+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/parsertrees.scala?rev=1254681341&do=diff Parser for While Language 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 parsePro… text/html 2009-11-02T01:31:46+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/phases_of_a_compiler?rev=1257121906&do=diff 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"), ... text/html 2009-11-29T22:29:07+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/phi_functions_in_ssa_form?rev=1259530147&do=diff Phi Functions in SSA Form Consider translating s = y if (x < 0) { res = - x s = s -1 } else { res = x s = s + 1 } p = res * s We could rename each block: s0 = y if (x < 0) { res0 = - x s1 = s0 -1 } else { res1 = x s2 = s0 + 1 } p = res? * s? text/html 2009-12-14T02:21:11+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/pointer_reversal?rev=1260753671&do=diff Pointer Reversal Suppose we write depth-first search in mark and sweep using a stack What is the maximal stack size? How can we represent the stack? * same stack we use for procedures * explicit stack data structure on the heap * pointer reversal: store information within nodes text/html 2009-09-27T23:05:08+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/polynomials.pscala?rev=1254085508&do=diff // 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… text/html 2009-09-15T15:04:12+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/polytokens.jj?rev=1253019852&do=diff options { JAVA_UNICODE_ESCAPE = true; } PARSER_BEGIN(Polynomials) public class Polynomials {} PARSER_END(Polynomials) // Insert a specification of a lexical analysis here. TOKEN: { <IDENTIFIER: <LETTER> (<LETTER> | <DIGIT> | "_")* > | <CONSTANT: <DIGIT> (<DIGIT>)* > | <LETTER: ["a"-"z"] | ["A"-"Z"]> | <DIGIT: ["0"-"9"]> } SKIP: { " " | "\n" | "\t" } // The following is a simple grammar that will allow you // to test the generated lexer. void Goal(): {} { ( MyToken() … text/html 2009-09-15T15:04:40+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/polytokentest.java?rev=1253019880&do=diff 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()); } } } text/html 2015-04-21T17:35:15+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/postfix_translation_of_boolean_operators?rev=1429630515&do=diff Postfix, Eager, Translation of Boolean Operators Eager function argument = argument that is always evaluated in the function In Java and many programming languages, all function arguments are eager In Haskell, all function arguments are lazy by default - evaluated only if they are used in the given computation text/html 2009-10-11T19:01:08+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/precedence_in_lr_parsing?rev=1255280468&do=diff 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 text/html 2013-11-03T12:12:23+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/prefix_infix_postfix_notation?rev=1383477143&do=diff 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, the other two do not! text/html 2009-10-04T21:46:40+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/pretty_printing_ast?rev=1254685600&do=diff Pretty Printing AST Consider a pretty printer that: * parses input source code * builds abstract syntax tree * prints abstract syntax tree, perhaps with improved formatting * generate again source code * create javadoc * create input for latex that produces nice listing text/html 2015-04-21T17:45:59+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/primes.el?rev=1429631159&do=diff ;;; primes.el --- prime number support for Emacs Lisp library code ;; Copyright (C) 1999 ;; Free Software Foundation, Inc. ;; This file is part of GNU Emacs. ;; GNU Emacs is free software; you can redistribute it and/or modify ;; it under the terms of the GNU General Public License as published by ;; the Free Software Foundation; either version 2, or (at your option) ;; any later version. ;; GNU Emacs is distributed in the hope that it will be useful, ;; but WITHOUT ANY WARRANTY; with… text/html 2009-11-02T01:40:01+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/printing_prefix_infix_postfix?rev=1257122401&do=diff 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 :… text/html 2009-09-15T23:20:44+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/programs.scala?rev=1253049644&do=diff 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))) ::… text/html 2009-12-14T03:02:45+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/prolog_examples?rev=1260756165&do=diff Prolog Examples app([],Y,Y). app([H|T], Y, [H|Z]) :- app(T, Y, Z). ?- app(X, Y, [1,2,3,4,5]). X = [], Y = [1, 2, 3, 4, 5] ; X = [1], Y = [2, 3, 4, 5] ; X = [1, 2], Y = [3, 4, 5] ; X = [1, 2, 3], Y = [4, 5] ; X = [1, 2, 3, 4], Y = [5] ; X = [1, 2, 3, 4, 5], Y = [] ; text/html 2015-04-21T17:35:15+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/proving_safety_properties_using_types?rev=1429630515&do=diff 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 text/html 2011-10-19T04:20:43+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/pushdown_automata?rev=1318990843&do=diff Pushdown Automata in Parsing Pushdown automata are like finite automata, but also work with stack * next state is given by: * current state * current input symbol read * top of the stack * within each step the automaton can pop a symbol or push a symbol onto stack text/html 2015-04-21T17:35:15+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/range_analysis_example?rev=1429630515&do=diff Range Analysis Example Analysis Domain Continue the example from Sets of States at Each Program Point but instead of allowing to denote all possible sets, we will allow sets represented by expressions which denote the set . Thus, is the lower bound and is the upper bound. To ensure that we have only a few elements, we let text/html 2009-11-30T11:25:06+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/recovering_expression_trees_from_ssa_form?rev=1259576706&do=diff Recovering Expression Trees from SSA Form After doing some transformations on control-flow graph, we may wish to revert back to trees In SSA form, for each variable we can look up its definition, which makes finding appropriate trees easy Suppose we do this recursively, but do not look up definitions that involve Phi nodes and loads from memory text/html 2009-09-26T13:11:24+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/recursive_descent_for_polynomials?rev=1253963484&do=diff Recursive Descent for Polynomials In context-free grammars we have seen a grammar of polynomials. Consider first this version of grammar: polynomial ::= term ("+" term)* term ::= factor ("*" factor)* factor ::= constant | variable | "(" polynomial ")" This grammar version is very nice for recursive descent parsing text/html 2009-09-26T13:26:09+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/recursive_descent_idea?rev=1253964369&do=diff Recursive Descent Idea 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”; “enough food”; text/html 2009-12-14T10:10:05+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/reference_counting?rev=1260781805&do=diff Reference Counting In each memory location store the number of incoming pointers Free the block if the counter is zero Jargon File: One day a student came to Moon and said, "I understand how to make a better garbage collector. We must keep a reference count of the pointers to each cons." Moon patiently told the student the following story: "One day a student came to Moon and said, `I understand how to make a better garbage collector... text/html 2012-12-10T01:56:17+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/register_allocation_using_liveness_information?rev=1355100977&do=diff 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 text/html 2009-11-23T00:40:08+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/register_machine_model_in_scala?rev=1258933208&do=diff Register Machine Model in Scala Contrast this to stack machine in VM for Expressions 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 o… text/html 2009-10-18T22:58:36+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/reporting_errors_based_on_syntax_tree?rev=1255899516&do=diff 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' text/html 2009-12-14T03:32:01+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/scaludita_examples?rev=1260757921&do=diff Scaludita Examples Scaludita is based on Udita system but adapted to Scala by Tihomir Gvero Finding a Solution of Simple Constraint def assume(p : Boolean) = Verify.ignoreIf(!p) def choose = Verify.getInt(1,20) val y = 11 val x = choose assume(10 < y && x < 5 && y < 3*x) println("x = " + x) text/html 2012-11-17T18:48:33+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/scoping_rules_affect_program_meaning?rev=1353174513&do=diff Scoping Rules Affect Program Meaning We define several different scoping rules, rules that define which variable is visible where. We show * the same program can have different meaning under different scoping rules * scoping rules can affect which programs are considered valid text/html 2015-04-21T17:35:15+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/sets_of_states_at_each_program_point?rev=1429630515&do=diff Sets of States at Each Program Point Consider the program i = 0; while (i < 10) { if (i > 1) i = i + 3; else i = i + 2; } A possible corresponding control-flow graph is: [CFG for Simple Loop] Suppose that * program state is given by the value of the integer variable i text/html 2012-11-20T23:45:59+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/short-circuit_evaluation?rev=1353451559&do=diff 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: text/html 2009-12-14T10:13:15+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/simple_copying_collector?rev=1260781995&do=diff Simple 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 text/html 2009-12-14T11:08:04+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/simple_implementations_of_lazy_evaluation?rev=1260785284&do=diff Simple Implementations of Lazy Evaluation Explicit Check Replace x = f(p,q) y = g(x) def g(y) = { y + 1 } with x = Thunk(_ => f(p,q)) y = g(x) def g(y) = { y.get()+1 } where class Thunk[A](var toCompute : Unit => A) var res : A = _ var computed : Boolean = false def get : A = { if (computed) res else { res = toCompute() computed = true } } } text/html 2009-10-15T15:53:07+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/simple_language_with_local_variables?rev=1255614787&do=diff Simple Language with Local Variables This is a Java-like language that we use to illustrate basic concepts of scopes and type checking. For simplicity, assume * programs have only one class (called World) * all class members are static. The following is text/html 2009-11-29T17:38:58+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/simple_nested_procedures?rev=1259512738&do=diff Simple 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("<body>") wr("This is my page.") wrInt(2008) wr("</body>") } text/html 2015-04-21T17:35:15+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/simple_types_for_lambda_calculus?rev=1429630515&do=diff 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 text/html 2009-10-12T00:41:02+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/slr_parser_actions?rev=1255300862&do=diff 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 Here is then the algorithm: Let K be parser state at the end of stack and t current token: text/html 2010-12-07T21:41:46+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/source_and_target_cfg_vertices?rev=1291754506&do=diff Source and Target CFG Vertices Translation of an AST construct in general takes: * initial vertex * target vertex (or two target vertices for conditional statements) Sequence of Statements Sequence of statements: s1;s2 v0 ---------> v1 becomes text/html 2009-09-13T22:30:50+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/squares.while?rev=1252873850&do=diff // 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; } text/html 2009-11-29T22:33:08+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/ssa_form_and_its_advantages?rev=1259530388&do=diff SSA Form and Its Advantages SSA = Static single assignment form A form of control-flow graph with at most one assignment statement for each variable We will see that each program can be transformed into SSA form * by introducing more variables and some special notation) Advantage of SSA form: text/html 2009-11-25T00:29:59+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/stack_frames_and_procedure_calls?rev=1259105399&do=diff 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 text/html 2009-12-14T01:53:25+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/strictness_analysis?rev=1260752005&do=diff Strictness Analysis If the argument of function is used at least once, then lazy evaluation (in a side-effect-free language) gives same result as call by value. Therefore, compiler can optimize such function and its call by evaluating argument before the call text/html 2015-04-21T17:35:15+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/subtyping_for_assignments_and_soundness_idea?rev=1429630515&do=diff Subtyping for Assignments and Soundness Idea Consider a language with * classes containing methods * subclassing * assignments of local variables Example: class C { def m = {...} } class D extends C { def n = {...} } // thus, D <: C class Main { def main = { var x : D = new D var y : C = new C // y = x ? // x = y ? x.n y.m } } text/html 2015-04-21T17:35:15+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/subtyping_for_functions?rev=1429630515&do=diff 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. text/html 2015-04-21T17:35:15+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/subtyping_with_assignments_and_generics?rev=1429630515&do=diff Subtyping with Assignments and Generics 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 text/html 2011-10-29T18:13:15+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/symbol_table_contents?rev=1319904795&do=diff Symbol Table Contents Symbol table: a function from identifiers in the current scope to the symbol that defines relevant information about this identifier All information is derived from syntax tree * symbol table is interconnected with syntax tree text/html 2009-09-12T20:33:33+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/test.jvm?rev=1252780413&do=diff Compiled from "test.java" class Test extends java.lang.Object{ Test(); Code: 0: aload_0 1: invokespecial #1; //Method java/lang/Object."<init>":()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… text/html 2009-09-12T20:32:31+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/test.s?rev=1252780351&do=diff .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) … text/html 2009-09-15T15:05:31+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/testpolyinput.poly?rev=1253019931&do=diff x + 3 * y0 * (zLongIdentifier * ! 12) text/html 2009-09-12T20:36:59+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/tiger_book?rev=1252780619&do=diff 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 text/html 2009-09-14T01:15:54+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/tokens.scala?rev=1252883754&do=diff 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… text/html 2009-09-14T00:49:36+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/tokens_words_of_while_language?rev=1252882176&do=diff 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 text/html 2009-10-28T17:51:41+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/tool?rev=1256748701&do=diff Tool Resource Page Tool stands for Toy Object-Oriented Language, and it is the programming language for which you will write a compiler in this course. BNF Goal::=MainObject ( ClassDeclaration )* <EOF> MainObject::=object Identifier { def main ( ) : Unit = { text/html 2009-12-01T17:19:32+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/tool_compiler_project?rev=1259684372&do=diff The Tool Compiler Project The main project in this course consists in implementing toolc, a compiler for a small, Java-like, object-oriented progamming language, which we call Tool. 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 text/html 2009-09-23T14:52:02+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/toolprog-binarysearch.tool?rev=1253710322&do=diff object BinarySearch { def main(): Unit = { 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 { var number : Int[]; var size : Int; // Invoke methods to initialize, print and search // for elements on the array def Start(sz : Int) : Int = { var aux01 : Int; var aux02 : Int; aux01 = this.Init(sz); aux02 = this.Pri… text/html 2009-09-23T14:51:35+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/toolprog-factorial.tool?rev=1253710295&do=diff object Factorial { def main() : Unit = { println(new Fact().computeFactorial(10)); } } class Fact { def computeFactorial(num : Int) : Int = { var num_aux : Int; if (num < 1) num_aux = 1; else num_aux = num * (this.computeFactorial(num - 1)); return num_aux; } } text/html 2009-09-24T19:14:51+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/toolprog-maze.tool?rev=1253812491&do=diff object Maze { def main() : Unit = { /* prints a maze of size 25x25 */ println(new MazeArray().init(25).printMaze()); } } class MazeArray { var size : Int; var prng : PseudoRandomNumberGenerator; var walls : Int[]; var wallCount : Int; var vertOffset : Int; var wallIDs : Int[]; var cells : Int[]; var cellCount : Int; var pipeChar : String; var horzChar : String; var plusChar : String; var t1Char : String; var t2Char : String; var t3Char : String; var … text/html 2009-09-23T14:54:02+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/toolprog-pi.tool?rev=1253710442&do=diff object Pi { def main() : Unit = { if(new Computer().computePi()) { println("Ok"); } else { println("error"); } } } class Computer { def computePi() : Bool = { var j : Int; var value : Frac; var inter : Real; println("First method"); println("************"); value = new Frac().init(0,1); j = 0; while(j < 3) { println(value.toString() + " ~= " + new Real().init(0,10).evalFrac(value).toString()); … text/html 2009-09-23T14:53:34+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/toolprog-quicksort.tool?rev=1253710414&do=diff object QuickSort { def main() : Unit = { 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 { var number : Int[]; var size : Int; // Invoke the Initialization, Sort and Printing // Methods def Start(sz : Int) : Int = { var aux01 : Int; aux01 = this.Init(sz); aux01 = this.Print(); println(9999); aux01 = size - 1… text/html 2009-09-15T15:03:31+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/tools_for_constructing_lexers?rev=1253019811&do=diff 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 text/html 2015-04-21T17:49:40+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/tooltypesystem?rev=1429631380&do=diff Tool 2009 Typing 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 * 1 * 2 * 3 * 4 * 5 * 6 * 7 text/html 2011-09-20T15:52:36+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/top?rev=1316526756&do=diff Compiler Construction 2009 This is an archival version of the course. Next edition: Compiler Construction 2011 Course Material for 2009 Course Information Week 01, Sep 14: * Lecture 01: Compiler Phases. Describing Languages (Monday 10:15) * Labs 01 (Wednesday 8:15) * Lecture 02: Lexical Analysis (Wednesday 10:15) Week 02, Sep 21: * Monday is a holiday * Labs 02 (Wednesday 8:15) * Exercises 01 (Wednesday 10:15) text/html 2009-09-15T23:00:17+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/towards_a_systematic_approach_to_lexing?rev=1253048417&do=diff Towards a More Systematic Approach We have seen how to make a lexer for simple language What if the language has complex operators, each of which can be part of another, e.g. > >= => ===> == how do can we make sure to produce a correct sequence of tokens? text/html 2015-04-21T17:35:15+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/transforming_to_chomsky_normal_form?rev=1429630515&do=diff Transforming a Grammar to Chomsky Form Noam Chomsky 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 text/html 2009-11-29T21:46:31+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/translating_basic_blocks_to_ssa_form?rev=1259527591&do=diff Translating Basic Blocks to SSA Form y = 0 x = a x = x + y y = y + x x = x * b We introduce index for each assignment to variable assignment When we use the variable, we refer to the variable together with its index (last place where it was assigned) text/html 2015-04-21T17:35:15+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/translating_expressions_to_stack_machine?rev=1429630515&do=diff 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 * text/html 2009-11-09T00:57:11+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/translating_syntax_tree_to_cfg?rev=1257724631&do=diff Translating Syntax Tree to CFG Similar to what we had so far, but * 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 text/html 2015-04-21T17:35:15+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/translation_correctness_for_expressions?rev=1429630515&do=diff Translation Correctness for Expressions Recall Evaluating Postfix Notation Functions: * evaluation: * compilation: * virtual machine: 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 text/html 2015-04-21T17:35:15+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/translation_of_relations?rev=1429630515&do=diff Translation of Relations Consider translation of <,=, < = ,>,>=,=,!= on integers Operations of type Note: there are no instructions that take two integers from stack and leave the result of comparison on stack There are conditional branches for comparison of two stack operands: text/html 2010-11-29T02:14:04+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/treating_registers_as_stack?rev=1290993244&do=diff Treating Registers as Stack One approach (works with sufficiently many registers, e.g. 15 or 31): * treat registers as a stack of bounded depth * keep at compile time index i of current stack position * if position is i, we treat Reg_i (the i-th resiter) as the top of stack text/html 2009-09-15T23:19:44+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/tree.scala?rev=1253049584&do=diff 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… text/html 2009-11-30T11:41:33+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/tree_tiling_of_xyz_example?rev=1259577693&do=diff Tree Tiling of xyz Example We write 'reg' to denote arbitrary reg_i . Suppose we have the following instructions, with associated costs (cycle estimate): instruction cost ri <- rj 1 ri <- Plus(ri,rj) 2 r1 <- Plus(ri,rj) 2 r2 <- Mul(r2,r3) text/html 2009-09-15T23:21:30+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/treesimplifier.scala?rev=1253049690&do=diff package whilelang object TreeSimplifier { def apply(stat: Statement): Statement = { // replace all for loops by equivalent trees using while loops... } } text/html 2015-04-21T17:35:15+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/type_checking_let_and_letrec?rev=1429630515&do=diff 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 text/html 2015-04-21T17:35:15+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/type_rule_for_block_statement?rev=1429630515&do=diff Type Rules for Block Statement Note that variable declarations are allowed in blocks * we type statements one by one * declarations introduce new bindings into the environment We apply these rules (with those listed first having higher priority): text/html 2015-04-21T17:35:15+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/type_rules_for_statements_and_expressions?rev=1429630515&do=diff Type Rules for Statements and Expressions Type Rule for Method Calls Method calls are just function applications: Type Rule for Assignment Answer: Type Rule for If Statement Answer: Type Rule for Conditional Expression Answer: Type Rule for While Statement text/html 2015-04-21T17:35:15+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/type_rules_using_environment?rev=1429630515&do=diff Type Rules using Environment To know types of variables, type rules must refer to the environment. Notation means that in environment , expression is type correct and has type * is a partial function from names (of variables, operators, and methods) to types text/html 2015-04-21T17:35:15+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/type_soundness_for_simply_typed_lambda_calculus?rev=1429630515&do=diff 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.) text/html 2009-11-02T00:30:23+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/types_expressing_program_properties?rev=1257118223&do=diff Types Expressing Program Properties Suppose that we wish to define types such as type upto[n] = {x:Int | 0 <= x & x < n} type posArr = {f:Array[Int] | forall i:upto[f.length]. 0 <= f(i)}var w : upto[v] var a : posArr = new Array[10] var i : upto[10] var p : upto[MAXINT] a[i] = 4 // must prove: 0 <= i < 10, 0 <= 4 p = a[0] // must prove: 0 <= 0 < 10, 0 <= a[0] < 10 text/html 2011-09-24T23:35:57+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/using_finite_state_machines_for_lexical_analysis?rev=1316900157&do=diff 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: text/html 2015-04-21T17:35:15+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/variable_capture?rev=1429630515&do=diff 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 text/html 2012-11-20T20:40:23+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/vm_for_expressions?rev=1353440423&do=diff Stack-Based Virtual Machine for Expression Evaluation Check these instructions in JVM Spec: 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) … text/html 2009-09-13T19:05:26+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/what_is_a_compiler?rev=1252861526&do=diff What is a compiler? A tool that transforms program in source programming language into a program in target programming language so that we can run the compiled program on machine Source Language Typically a 'high-level' programming language, such as: text/html 2009-11-08T21:29:01+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/while_language?rev=1257712141&do=diff 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 text/html 2009-09-26T12:32:49+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/while_language_parser?rev=1253961169&do=diff While Language Parser The ideas so far should be sufficient to write most simpler parsers by hand A parser for a toy language: WhileParser.scala * simplified version of Concrete Syntax of While * can connect to Hand-Written Scanner for While Language i.e. Lexer.scala text/html 2010-12-07T21:44:01+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/while_statements_to_cfg?rev=1291754641&do=diff While Statements to CFG [Translating While to CFG] Note: better translation uses two destination vertices text/html 2009-09-27T23:06:46+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/whileparser.scala?rev=1254085606&do=diff 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… text/html 2009-09-14T09:41:42+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/why_study_compilers?rev=1252914102&do=diff 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) text/html 2009-09-15T23:03:56+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/why_study_lexical_analysis?rev=1253048636&do=diff Why Study Lexical Analysis Lexical analysis is one of the simplest aspects of compilers Almost never a problem in practice Why do we need to study it? Reason 1: It is also the first phase of a compiler So we study it first. Reason 2: 'Drunk under the lamppost' effect text/html 2015-04-21T17:35:15+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc09/xyz_example_using_gcc?rev=1429630515&do=diff 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