https://lara.epfl.ch/w/ 2026-07-25T09:36:47+0200 https://lara.epfl.ch/w/ https://lara.epfl.ch/w/lib/tpl/epflv2/images/favicon.ico text/html 2010-10-18T04:25:21+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc10/compiler_compilers?rev=1287368721&do=diff Compiler-Compilers (Compiler/Parser Generators) Compiler-compilers are tools that are used to produce a parser from, essentially, a grammar. The Dinosaurs The most famous examples of such tools are Lex and Yacc. * Lex is a lexical analyzer: it transforms a stream of characters into a stream of tokens. Valid tokens are described eg. with regular expressions. text/html 2010-11-14T20:35:11+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc10/compilers_in_action?rev=1289763311&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 2015-04-21T17:35:07+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc10/earley_parser?rev=1429630507&do=diff Earley Parser Partial slides: [pptx], [pdf] 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 2010-09-28T13:29:00+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc10/exercises_01?rev=1285673340&do=diff Exercises 01 Exercise 1 Convert the following NFAs to deterministic finite automata. a) b) Exercise 2 Design a DFA which accepts all the binary numbers divisible by 6. For example your automaton should accept the words 0, 110 (6 decimal) and 10010 (18 decimal). text/html 2010-10-06T22:48:34+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc10/exercises_02?rev=1286398114&do=diff Exercises 02 Exercise 1 The dangling-else problem happens when the conditional statements are parsed using the following grammar. S := "if" E "then" S S := "if" E "then" S "else" S Find an unambiguous grammar that accepts the same conditional statements and matches the else statement with the nearest unmatched if. text/html 2010-10-12T23:01:59+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc10/exercises_03?rev=1286917319&do=diff Exercises 02 Exercise 1 A CYK parser is parsing the input “Int , Int => Int”. The incomplete tables for two different grammars are given below. * Complete the table. * Find the suitable grammar that actually generates the table. * Construct the table for text/html 2010-11-03T11:41:58+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc10/exercises_04?rev=1288780918&do=diff * CYK parsing algorithm example, taken from here. * Earley parsing algorithm example, taken from last year's course (Problem 2). text/html 2010-10-25T22:18:00+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc10/exercises_05?rev=1288037880&do=diff Exercises 05 Exercise 1 Short questions: * Describe the language that is accepted by an LL(0) grammar. * Describe why a shift/shift conflict is impossible during the LR table construction. * Is is possible that a SLR parser prefers reduction in a shift/reduce conflict? text/html 2010-11-03T10:02:22+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc10/exercises_06?rev=1288774942&do=diff Exercises 06 Exercise 1 Consider the following piece of code. val x = 1 val y = 2 def p() = x + y def q(p: Int => Int) = p(x * y) def f = { val x = 2 q(p + _) } def g(q: Int => Int) = { val y = 3 def p() = x - y q(f) } print(g(_ + 2)) text/html 2010-11-10T15:43:11+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc10/exercises_07?rev=1289400191&do=diff Exercises 07 Exercise 1 Run javac on the following program: class A { } class B extends A { void foo() { } } class Test { public static void main(String[] args) { B[] b = new B[5]; A[] a; a = b; System.out.println("Hello,"); a[0] = new A(); System.out.println("world!"); b[0].foo(); } } text/html 2010-11-17T15:57:59+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc10/exercises_08?rev=1290005879&do=diff Exercises 08 Exercise 1 Translate the following function to JVM instructions. def middle(small: Int, big: Int): Int = { val mid = small + (big - small) / 2 return mid } solution Exercise 2 In addition to the instructions introduced in class, consider the following instructions. text/html 2010-11-29T02:17:17+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc10/exercises_09?rev=1290993437&do=diff Discussion of parsing homework Problem 1: Branch Instruction * Translate the for-loop and if-condition to branch instructions. * Convert the function to byte code. * Use CafeBabe to generate the class file. def bubblesort( xs : Array[Int]) : Array[Int] = { for( i <- 0 until (xs.length - 1)) for( j <- 0 until (xs.length - i - 1)) if( xs(j) > xs(j+1)) { var tmp = xs(j) xs(j) = xs(j + 1) xs(j + 1) = tmp } xs } text/html 2015-04-21T17:35:07+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc10/exercises_10?rev=1429630507&do=diff Exercises 10 In the following problems assume that we have a machine with the registers . All the registers and the integer numbers consist of 2 bytes. We use the temporary variables x1 ... x31 to implement our intermediate code. The goal is to assign each temporary variable xi to a register and to minimize the exploited registers. text/html 2010-11-30T23:33:39+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc10/final-report?rev=1291156419&do=diff Labs: Final Report Your final report is due in early January. 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 2010-11-29T02:11:03+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc10/from_stack_machine_to_register_machine?rev=1290993063&do=diff From Stack Machine to Register Machine Translate each of these stack machine instructions into register machine: Bipush(c : Int) Iadd Imul Iload(slot : Int) Istore(slot : Int) using register machine instructions * with arbitrary addressing * assuming arithmetic operations are done only on registers text/html 2010-09-29T21:54:50+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc10/homework_01?rev=1285790090&do=diff Homework 01 Due Wednesday, 13 October, 10:10am. Please Hand it in to Hossein before the beginning of the exercise session. Problem 1 Given an alphabet , we define the language double as . Prove that double is regular if and only if contains exactly one symbol. text/html 2011-09-29T14:35:58+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc10/homework_02?rev=1317299758&do=diff Homework 02 Due Wednesday, 20 October, 10:10am. Please Hand it in to Hossein before the beginning of the exercise session. Problem 1 A grammar has a cycle if there is a non-terminal such that . * Show that an LL(1) grammar must have no cycles. text/html 2010-10-14T15:49:01+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc10/homework_03?rev=1287064141&do=diff Homework 03 Due Wednesday, 27 October, 10:10am. Please hand it in to Hossein before the beginning of the exercise session. Problem 1 A context-free grammar is in Greibach two-standard form if productions are of the following form. X -> aYZ X -> aY X -> a text/html 2010-11-09T15:49:28+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc10/homework_04?rev=1289314168&do=diff Homework 04 Due Wednesday, 3 November, 10:10am. Please hand it in to Hossein before the beginning of the exercise session. Problem 1 In bottom up parsing replacing the RHS of a rule with its LHS is called reduction. A reductions is called “useless text/html 2010-10-26T00:17:43+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc10/homework_05?rev=1288045063&do=diff Homework 05 Due Wednesday, 10 November, 10:10am. Please hand it in to Hossein before the beginning of the exercise session. Problem 1 Construct an LR(0) parsing table for the following grammar. S -> SS | (S) | () * Locate the shift/reduce conflict in the table. text/html 2010-11-11T19:18:37+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc10/homework_06?rev=1289499517&do=diff Homework 06 Due Wednesday, 17 November, 10:10am. Please hand it in to Hossein before the beginning of the exercise session. Problem 1 Determine if the following piece of codes type check according to the type rules. a) The class Array has a field length in which the length of the array is stored. text/html 2010-11-10T20:04:40+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc10/homework_07?rev=1289415880&do=diff Homework 07 Due Wednesday, 24 November, 10:10am. Please hand it in to Hossein before the beginning of the exercise session. 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. text/html 2010-09-28T22:24:04+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc10/info?rev=1285705444&do=diff Staff Lectures: * Viktor Kuncak Practical Exercises: * Philippe Suter Theoretical Exercises on the Board and Exams: * Hossein Hojjat Assistants-Étudiants: * Etienne Kneuss * Ali Sinan Köksal Secretary: Danielle Chamberlain Schedule * Mondays 10:15-12:00 - Lectures in INM 202 * Wednesday 08:15-10:00 - Project work, in INF3 * text/html 2010-10-12T14:11:27+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc10/lab04-compiler.scala?rev=1286885487&do=diff package toolc import parser.Parser import scala.io.Source class Compiler(val fileName: String) extends Reporter with Parser { val source: Source = Source.fromFile(fileName).withPositioning(true) 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 ex… text/html 2010-10-12T14:06:03+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc10/lab04-parser.scala?rev=1286885163&do=diff package toolc package parser import lexer.Lexer import scala.io.Source /** LL parser for the Tool grammar. */ trait Parser extends Lexer { self: Compiler => import Trees._ import 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 readT… text/html 2010-10-12T14:07:15+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc10/lab04-prettyprinter.scala?rev=1286885235&do=diff package toolc object TreePrinter { import parser.Trees._ def apply(t: Tree): String = { /* construct and return the appropriate string ... */ } } text/html 2010-10-12T14:03:31+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc10/lab04-trees.scala?rev=1286885011&do=diff package toolc package 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 … text/html 2010-10-26T15:35:35+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc10/lab06-analyzer?rev=1288100135&do=diff package toolc package 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 2010-10-26T15:37:17+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc10/lab06-compilerstub?rev=1288100237&do=diff package toolc 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).withPositioning(true) def compile: Unit = { import parser.Trees._ import analyzer.Symbols._ // Parsing var parsedTree: Option[Tree] = None parsedTree = Some(parseSource) terminateIfErrors val mainProg: Program = parsedTree match { … text/html 2010-10-26T15:31:15+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc10/lab06-symbols?rev=1288099875&do=diff package toolc package 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 sy… text/html 2010-10-26T15:34:45+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc10/lab06-treeprinter?rev=1288100085&do=diff package toolc object TreePrinter { import parser.Trees._ /** TreePrinter(tree) will produce the same result as before. */ def apply: (Tree=>String) = apply(false)_ /** TreePrinter.withSymbolIDs(tree) will print the tree with the IDs. */ def withSymbolIDs: (Tree=>String) = apply(true)_ /** We added a parameter and currified the method to build the other two. */ private def apply(withSymbolIDs: Boolean)(t: Tree) = { /* code you had before... */ // ... // Th… text/html 2010-10-27T09:57:15+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc10/lab06-trees?rev=1288166235&do=diff package toolc package 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, stat: StatTree) extends Tree with Symbolic[ClassSymbol] case class ClassDecl(id: Identifier, parent: Option[Identifier],… text/html 2010-10-26T16:21:22+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc10/lab07-compiler?rev=1288102882&do=diff package toolc 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).withPositioning(true) def compile: Unit = { import parser.Trees._ import analyzer.Symbols._ // Parsing var parsedTree: Option[Tree] = None parsedTree = Some(parseSource) terminateIfErrors … text/html 2010-10-26T16:20:05+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc10/lab07-typechecker?rev=1288102805&do=diff package toolc package 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 o… text/html 2010-10-26T16:19:24+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc10/lab07-types?rev=1288102764&do=diff package toolc package 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 … text/html 2010-11-17T09:45:04+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc10/lab09-codegen?rev=1289983504&do=diff package toolc package 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 2010-11-16T15:52:53+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc10/lab09-compiler?rev=1289919173&do=diff package toolc 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).withPositioning(true) def compile(classDir: String): Unit = { import parser.Trees._ import analyzer.Symbols._ val outputDir = classDir + "/" val… text/html 2010-11-16T15:51:39+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc10/lab09-main?rev=1289919099&do=diff package toolc object Main { def main(args: Array[String]) : Unit = { 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.e… text/html 2010-09-22T08:42:04+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc10/labs_01?rev=1285137724&do=diff Labs 01 This week you will build an interpreter in Scala for the while language. We provide you with a parser for the language, and you will thus work directly on the Abstract Syntax Tree (AST) representation of programs. The grammar of this very simple language is given by: text/html 2010-09-29T08:56:37+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc10/labs_02?rev=1285743397&do=diff Labs 02 For this week, you have two tasks. End of Previous Lab Finish the tasks of Labs 01. Please send an email to Philippe Suter at the latest on Oct. 4th with the names of the members of your team. If you want to make a team of less or more than two, please contact Viktor Kuncak or Philippe Suter in advance. text/html 2010-10-12T15:17:49+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc10/labs_03?rev=1286889469&do=diff Labs 03 This assignment is the first real part of the Tool compiler project. Make sure you read the general project overview page first. Note that the page now contains more information than last week. Please note that this lab is to be done in one week. As testcases, you can use the ones that you and the other students in this class wrote. They're available for download text/html 2010-10-12T15:18:38+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc10/labs_04?rev=1286889518&do=diff Labs 04 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 2010-10-12T14:15:26+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc10/labs_05?rev=1286885726&do=diff Labs 05 Finish Labs 04. text/html 2010-10-26T15:26:14+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc10/labs_06?rev=1288099574&do=diff Labs 06 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, Nov. 9th, 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 2010-11-02T20:33:31+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc10/labs_07?rev=1288726411&do=diff Labs 07 This week you will implement type checking in your Tool compiler. After this step, you will have completed the front-end of your compiler. This means that it will be able to reject all invalid programs, and accept all valid programs. You will then be able to turn these valid inputs into assembly code that runs on the JVM, just like text/html 2010-10-26T16:25:09+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc10/labs_08?rev=1288103109&do=diff Labs 08 Finish Labs 07, the last step of your compiler front-end. text/html 2010-11-16T15:36:47+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc10/labs_09?rev=1289918207&do=diff Labs 09 Congratulations, your front-end is complete! You are now one step (and two weeks) away from having written a complete compiler. This week's lab description and stubs are rather short. It's not that we don't want to help you anymore, it's just that the tasks should be straightforward (and there's a bit of reading to do on the text/html 2010-11-16T15:55:34+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc10/labs_10?rev=1289919334&do=diff Labs 10 Finish Labs 09. text/html 2010-12-01T02:16:03+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc10/labs_11?rev=1291166163&do=diff Labs 11: Your Turn You have now written a compiler for a fairly 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 2010-09-28T16:45:54+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc10/lecture_01?rev=1285685154&do=diff Lecture 01: Introduction Slides: * [PDF Slides] Background“ * [Regular Languages and Finite Automata] from Andrew M. Pitts Notes on some of the background: * Strings and languages * Regular expression * Context-Free Grammars References * Tiger book, Chapters 1-2 * Slides from previous years: * Compilation 2007 Slides 1 (French version) * Compilation 2007 Slides 2 (French version) * Compiler Construction by Niklaus Wirth, Chapters 1-3 * Compiler Construction Tool… text/html 2010-09-28T16:58:26+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc10/lecture_02?rev=1285685906&do=diff Lecture 02: Review of pumping lemma and grammars. Lexical Analysis Introduction: * [Introduction to Lecture 2] Limitations of Regular Expressions Context-Free Grammars Hand-Written Scanner for While Language Review: Minimization of State Machines Implementing Finite State Machines Using Finite State Machines for Lexical Analysis Tools for Constructing Lexers References * Tiger book, Chapters 1-2 * Slides from previous years: * Compilation 2007 Slides 1 (French version) * … text/html 2010-10-05T20:45:43+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc10/lecture_03?rev=1286304343&do=diff Lecture 03: Recursive Descent Parsing [Slides for the First Part] Basic Idea of First Symbol Computation Computing Nullable Nonterminals Computing Follow Sets Computing First and Follow Sets Continued in Lecture 03a text/html 2010-10-11T08:57:05+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc10/lecture_03a?rev=1286780225&do=diff Lecture 3a Table-Driven Parser for Balanced Parentheses LL(1) Table-Driven Parsing Overview Algorithm for First and Follow Sets Building LL Parsing Table Interpreting LL Parsing Table text/html 2010-10-11T16:02:53+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc10/lecture_04?rev=1286805773&do=diff Lecture 04: Parsing General Grammars Error Recovery in Top-Down Parser * test error recovery in the Table-Driven Parser for Balanced Parentheses * ensuring entire input is parsed * errors in a parser for polynomial expressions Some tools to build top-down parsers: * JavaCC, while language * Coco/R Compiler Generator * ANTLR [PDF SLIDES] * About Parsing Context-Free Grammars * Chomsky Normal Form text/html 2010-10-18T02:45:39+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc10/lecture_05?rev=1287362739&do=diff Lecture 05: Earley Parser. Semantic Actions. Parsing Combinators Earley Parser Notion of Semantic Action Compiler-Compilers (Compiler Generators) Parsing Combinators text/html 2010-10-31T17:26:06+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc10/lecture_06?rev=1288542366&do=diff Lecture 06: LR Parsing [Classes of Languages] Push Down Automata in Parsing 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 Parsing References * Tiger book, Section 3.3 … text/html 2010-10-27T12:30:03+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc10/lecture_06a?rev=1288175403&do=diff Lecture 06a: Simple Semantic Analysis Scopes of Symbols Simple Errors beyond Syntax Identifiers vs Symbols Example Simple Language with Local Variables Scoping Rules Affect Program Meaning Notation for Maps Maintaining Maps Implementation: Symbol Tables and Error Reporting Symbol Table Contents Functional versus Imperative Maps An Efficient Imperative Map Functional Maps Efficient Comparison for Identifiers Reporting Errors Based on Syntax Tree Type Checking Rules for a Simple Lan… text/html 2010-11-01T14:21:42+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc10/lecture_07?rev=1288617702&do=diff Lecture 07: Type Analysis Lecture: * pdf * pptx References * Tiger book, Chapters 4, 5 * Name Analysis from Compilation'07 * Type Analysis from Compilation'07 * Types and Programming Languages Book * Types and Programming Languages, Chapter 5, Chapter 8, Sections 9.1 text/html 2010-11-07T12:46:18+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc10/lecture_07a?rev=1289130378&do=diff Lecture 07a: Meaning of Types. Subtyping Lecture: * pptx * pdf Type Rules for A Language Similar to Tool text/html 2010-11-09T20:17:03+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc10/lecture_08?rev=1289330223&do=diff Lecture 08: More on Subtyping. Soundness Slides: * pptx * pdf More information: * Foundations of Software Course at EPFL text/html 2010-11-21T17:48:01+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc10/lecture_09?rev=1290358081&do=diff Lecture 09: Code Generation Introduction: * [pptx] * [pdf] Compilers in Action Stack machine JVM Instructions Compiled Expression Examples Compiled Counting Examples Compiled Factorial Example A Byte Code Generation Library The Scala Cafebabe Bytecode Generation Library Overview of Classfile Constant Pool Compiling Expressions VM for Expressions Prefix Infix Postfix Notation Printing Prefix Infix Postfix Languages using Prefix or Postfix Only Evaluating Postfix (Continued i… text/html 2010-11-22T12:39:10+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc10/lecture_10?rev=1290425950&do=diff Lecture 10: Code Generation for Expressions and Statements in Stack Machine Model (Continuing Lecture 09) Expressions VM for Expressions Evaluating Postfix Translating Expressions to Stack Machine Translation Correctness for Expressions Assignments Accessing and Storing Variables Compiled Factorial Example Sequence Compiling Statement Sequence Efficiently Emitting Code Compiling Control-Flow Statements Booleans and Data Representation Branching JVM Instructions Compiling If Then … text/html 2010-11-24T12:20:02+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc10/lecture_10a?rev=1290597602&do=diff Lecture 10a: Compiling Conditionals and Boolean Operators (Continuing Lecture 10.) Review questions: * how to represent 'false' and 'true' * give examples of branching instructions * how to translate: if-then-else * assuming boolean on stack * if (x < y) text/html 2010-12-05T14:00:20+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc10/lecture_11?rev=1291554020&do=diff Lecture 11: Compiling to Register Machines About Register Machines Register machines are an alternative to compilation to stack-based machines; they are closer to modern processors. ARM Architecture Picture of JVM State with: * Procedure Stacks * Slots * Operand Stack text/html 2010-12-07T21:31:01+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc10/lecture_12?rev=1291753861&do=diff Lecture 12: Register Allocation. Data-Flow Analysis Register Allocation using Liveness Information References * Tiger book * [Lecture Slides by Antony L Hosking] * Compiler Construction by Niklaus Wirth, chapters 9,10, 11 Data-Flow Analysis Idea of Data Flow Analysis Idea of Data Flow Analysis Control-Flow Graph Definition Why control-flow graphs instead of syntax trees * they can represent arbitrary jumps * they are simple: conditions and loops represented uniformly text/html 2010-12-13T00:32:32+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc10/lecture_12a?rev=1292196752&do=diff Lecture 12a: Data-Flow Analysis Applications of Data-Flow Analysis Constant Propagation Control-Flow Graph Definition In Scala: * DiGraphs.scala * SimpleCFG.scala Translating Trees to Control-Flow Graphs 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 2010-12-13T13:34:01+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc10/lecture_13?rev=1292243641&do=diff Lecture 13: Data-flow analysis. Heap. Advanced Procedures Continuing Lecture 12a Drawing partial orders and lattices Lattices Source code: * Lattices.scala Lattice height From information on variable, to information on the program: * Products of Lattices How the height changes Precise sets of all states (not practical): text/html 2010-12-13T13:33:34+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc10/lecture_14?rev=1292243614&do=diff Lecture 14 Heap: Explicit Dynamic Memory Management How to implement heap where data lives longer than procedures in which it is created? Malloc and Free Scala code: * MallocInfMem.scala * MallocFree.scala Free Lists by Size References * Donald Knuth. Fundamental Algorithms, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89683-4. Section 2.5: Dynamic Storage Allocation, pp.435–456. text/html 2011-10-24T09:46:43+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc10/maintaining_maps?rev=1319442403&do=diff Maintaining Maps Here is what the maps look like: class World { int sum; int value; // value |-> int, sum |-> int void add(int foo) { // foo |-> int, value |-> int, sum |-> int string z; // z |-> string, foo |-> int, value |-> int, sum |-> int sum = sum + value; value = 0; } // value |-> int, sum |-> int void main(string bar) { // bar |-> string, value |-> int, sum |-> int int y; // y |-> int, bar |-> string, value |-> int, sum |-> int sum… text/html 2010-10-18T00:14:43+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc10/notion_of_semantic_action?rev=1287353683&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 2010-10-18T18:13:55+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc10/parsing_combinators?rev=1287418435&do=diff Parser Combinators For the task of implementing a parser, we've seen two options so far: * Hand-written recursive-descent parsers * Compiler-compilers We now briefly discuss a third, intermediate one: parser combinators. Parsers are Functions text/html 2010-10-18T03:54:22+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc10/parsing_combinators_example?rev=1287366862&do=diff // A minimalistic implementation of parser combinators in Scala object Parsing { def main(args : Array[String]) : Unit = { // Concatenates all command line arguments into a string val argsAsString = args.foldLeft[String]("")(_ + " " + _).trim val argsAsStream = argsAsString.toStream println("Input string: " + argsAsString) // Avoids having to build Keyword("...") parsers for each constant // string implicit def str2parser(str: String) : Parser = new Keyword(str) … text/html 2010-10-26T21:52:16+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc10/simple_errors_beyond_syntax?rev=1288122736&do=diff Simple Errors beyond Syntax Some kinds or errors we can check using straightforward checks: * a class is defined more than once class A { ...} class B { ... } class A { ... } ++ * a variable is defined more than once: int x; int y; int x; ++ text/html 2012-11-25T13:46:53+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc10/static_stack_depth_property?rev=1353847613&do=diff Static Stack Depth Property Claim: if we apply translation above then the stack size at each point in the bytecode can be computed during compilation. * we can check for stack underflow and overflow Why does it hold? * for each assignment statement text/html 2010-10-06T22:48:53+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc10/table-driven_parser_for_balanced_parentheses?rev=1286398133&do=diff Table-Driven Parser for Balanced Parentheses First Grammar It has three alternatives: S ::= "" | ( S ) | S S 1. 2. 3. Goal is to figure out which alternative to use when -- convert | into if-then-else. Compute: nullable = { S } first(S) = { ( } follow(S) = { ( , ) } text/html 2010-09-28T19:00:18+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc10/tool?rev=1285693218&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. See also the Tool Compiler Project page. BNF Goal::=MainObject ( ClassDeclaration )* <EOF> MainObject::=object Identifier text/html 2010-10-06T01:23:43+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc10/tool_compiler_project?rev=1286321023&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 2010-10-25T16:58:59+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc10/tool_reference_compiler?rev=1288018739&do=diff The Tool Reference Compiler The latest version is 1.2. You can obtain it from here. You can run it as follows: java -jar toolc-reference-1.2.jar program.tool Available Options By default, toolc just compiles a Tool program to bytecode like your implementation will. You can however also use the reference implementation for other things. Try to run text/html 2010-09-28T18:54:08+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc10/toolprog-binarysearch.tool?rev=1285692848&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 2010-09-28T18:53:27+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc10/toolprog-factorial.tool?rev=1285692807&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 2010-09-28T19:20:04+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc10/toolprog-maze.tool?rev=1285694404&do=diff object Maze { def main() : Unit = { /* prints a maze of size 20x20 */ println(new MazeArray().init(20).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 2010-09-28T18:55:21+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc10/toolprog-pi.tool?rev=1285692921&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 2010-09-28T18:54:54+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc10/toolprog-quicksort.tool?rev=1285692894&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 2011-09-16T17:02:44+0200 Anonymous (anonymous@undisclosed.example.com) https://lara.epfl.ch/w/cc10/top?rev=1316185364&do=diff Compiler Construction, Fall 2010 This is an archival version of the course. Next edition is Compiler Construction Fall 2011 General Course Information Schedule Moodle system for submitting your lab solutions Previous edition: Compiler Construction 2009 Course Material Week 01, Sep 20: * Labs 01: Introductory Lab Session. Wednesday, 08:15am in INF3 * Lecture 01: Introductory Lecture. Wednesday, 10:15am in CO123