LARA: Laboratory for Automated Reasoning and Analysis cc11
https://lara.epfl.ch/w/
2026-06-30T09:42:13+0200LARA: Laboratory for Automated Reasoning and Analysis
https://lara.epfl.ch/w/
https://lara.epfl.ch/w/lib/tpl/epflv2/images/favicon.icotext/html2011-09-28T17:20:38+0200Anonymous (anonymous@undisclosed.example.com)cc11:exercises_01
https://lara.epfl.ch/w/cc11/exercises_01?rev=1317223238&do=diff
Exercises 1
Exercise 1
Assume the following extensions to the regular expressions. In each case describe why the modification does not actually change the expressibility.
* The intersection of two regular expressions.
* The optional expressiontext/html2011-10-11T15:30:55+0200Anonymous (anonymous@undisclosed.example.com)cc11:exercises_02
https://lara.epfl.ch/w/cc11/exercises_02?rev=1318339855&do=diff
Exercises 02
Exercise 1
Show that the grammar
A -> − A
A -> A − id
A -> id
is ambiguous by finding a string that has two different syntax trees.
Now make two different unambiguous grammars for the same language:
a) One where prefix minus binds stronger than infix minus.text/html2015-04-21T17:35:02+0200Anonymous (anonymous@undisclosed.example.com)cc11:exercises_03
https://lara.epfl.ch/w/cc11/exercises_03?rev=1429630502&do=diff
Exercises on Code generation and Dataflow analysis
Exercise 1 (Warm up): Bytecode generation
Translate the following function to JVM instructions.
def middle(small: Int, big: Int): Int = {
val mid = small + (big - small) / 2
return mid
}
Exercise 2: Branch Instructiontext/html2011-12-02T15:13:36+0200Anonymous (anonymous@undisclosed.example.com)cc11:final-report
https://lara.epfl.ch/w/cc11/final-report?rev=1322835216&do=diff
Labs: Final Report
Your final report is due in early January. The code of your extended compiler is due at the same time, and both will be delivered using Git.
Contents of the Report
You are encouraged to use the following (LaTeX) template for your report:text/html2015-04-21T17:35:02+0200Anonymous (anonymous@undisclosed.example.com)cc11:homework_01
https://lara.epfl.ch/w/cc11/homework_01?rev=1429630502&do=diff
Homework 1
Due Wednesday, 5th October, 10:15am. Please hand in to Eva or Giuliano before the labs.
Problem 1
Find a regular expression that generates all alternating sequences of 0 and 1 with arbitrary length (including lengths zero, one, two, ...text/html2011-10-14T09:19:29+0200Anonymous (anonymous@undisclosed.example.com)cc11:homework_02
https://lara.epfl.ch/w/cc11/homework_02?rev=1318576769&do=diff
Homework 02
Due Monday, 17th October, 10:15am. Please hand in before the lecture.
For this homework, recall that a parse tree is a tree that represents the structure of the string to be parsed according to some grammar.
It can be defined recursively as follows:text/html2011-10-22T13:49:53+0200Anonymous (anonymous@undisclosed.example.com)cc11:homework_03
https://lara.epfl.ch/w/cc11/homework_03?rev=1319284193&do=diff
Homework 03
Due Monday, 24th October, 10:15am. Please hand in before the lecture.
Problem 1
A grammar has a cycle if there is a non-terminal such that , i.e. it is possible to derive the nonterminal A from A by a sequence of production rules.
*text/html2011-10-24T17:08:49+0200Anonymous (anonymous@undisclosed.example.com)cc11:homework_04
https://lara.epfl.ch/w/cc11/homework_04?rev=1319468929&do=diff
Homework 04
Due Monday, October 31st, 10:10am.
Recall that a grammar is LR(0) if an LR(0) parsing table constructed for it has no conflicts. It is SLR if the same table has no SLR conflicts. Note that every LR(0) grammar is an SLR grammar.
Problem 1text/html2015-04-21T17:35:02+0200Anonymous (anonymous@undisclosed.example.com)cc11:homework_05
https://lara.epfl.ch/w/cc11/homework_05?rev=1429630502&do=diff
Homework 5
Due Monday, November 14th, 10:10am.
Problem 1
Consider the following grammar.
S -> UT | V "Int" | "Int"
T -> V "Int" | "Int"
U -> S "=>"
V -> T ","
Consider the input to be “Int , Int => Int”.
* Construct the CYK parsing table. Recall that each entrytext/html2015-04-21T17:35:02+0200Anonymous (anonymous@undisclosed.example.com)cc11:homework_06
https://lara.epfl.ch/w/cc11/homework_06?rev=1429630502&do=diff
Homework 6
Due Monday, November 21st, 10:10am.
A unit expression is defined by following grammar
where are unit expressions themselves and is a base unit:
You may use to denote the set of the unit types
For readability, we use the syntactic sugartext/html2011-10-11T18:31:33+0200Anonymous (anonymous@undisclosed.example.com)cc11:lab04-compiler.scala
https://lara.epfl.ch/w/cc11/lab04-compiler.scala?rev=1318350693&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 _ => sys.error("Main program expected f…text/html2011-10-11T18:30:25+0200Anonymous (anonymous@undisclosed.example.com)cc11:lab04-parser.scala
https://lara.epfl.ch/w/cc11/lab04-parser.scala?rev=1318350625&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/html2011-10-11T18:31:02+0200Anonymous (anonymous@undisclosed.example.com)cc11:lab04-prettyprinter.scala
https://lara.epfl.ch/w/cc11/lab04-prettyprinter.scala?rev=1318350662&do=diff
package toolc
object TreePrinter {
import parser.Trees._
def apply(t: Tree): String = {
/* construct and return the appropriate string ... */
}
}text/html2011-10-11T18:30:01+0200Anonymous (anonymous@undisclosed.example.com)cc11:lab04-trees.scala
https://lara.epfl.ch/w/cc11/lab04-trees.scala?rev=1318350601&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/html2011-10-25T01:22:36+0200Anonymous (anonymous@undisclosed.example.com)cc11:lab06-analyzer
https://lara.epfl.ch/w/cc11/lab06-analyzer?rev=1319498556&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/html2011-10-25T13:26:45+0200Anonymous (anonymous@undisclosed.example.com)cc11:lab06-compilerstub
https://lara.epfl.ch/w/cc11/lab06-compilerstub?rev=1319542005&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/html2011-10-25T13:26:09+0200Anonymous (anonymous@undisclosed.example.com)cc11:lab06-symbols
https://lara.epfl.ch/w/cc11/lab06-symbols?rev=1319541969&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 => sys.error("Accessing undefined symbol.")
}
}
/** Notice that creating a symbol will…text/html2011-10-25T01:23:42+0200Anonymous (anonymous@undisclosed.example.com)cc11:lab06-treeprinter
https://lara.epfl.ch/w/cc11/lab06-treeprinter?rev=1319498622&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/html2011-10-25T01:22:57+0200Anonymous (anonymous@undisclosed.example.com)cc11:lab06-trees
https://lara.epfl.ch/w/cc11/lab06-trees?rev=1319498577&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/html2011-11-01T11:47:17+0200Anonymous (anonymous@undisclosed.example.com)cc11:lab07-compiler
https://lara.epfl.ch/w/cc11/lab07-compiler?rev=1320144437&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/html2011-11-01T11:46:00+0200Anonymous (anonymous@undisclosed.example.com)cc11:lab07-typechecker
https://lara.epfl.ch/w/cc11/lab07-typechecker?rev=1320144360&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/html2011-11-01T11:44:46+0200Anonymous (anonymous@undisclosed.example.com)cc11:lab07-types
https://lara.epfl.ch/w/cc11/lab07-types?rev=1320144286&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/html2011-11-21T14:05:37+0200Anonymous (anonymous@undisclosed.example.com)cc11:lab10-codegen
https://lara.epfl.ch/w/cc11/lab10-codegen?rev=1321880737&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(srcFileName: String, gs: GlobalScope, ct: ClassDecl, dir: String): Unit = {
// ...
}
}text/html2011-11-30T12:19:53+0200Anonymous (anonymous@undisclosed.example.com)cc11:lab10-compiler
https://lara.epfl.ch/w/cc11/lab10-compiler?rev=1322651993&do=diff
package toolc
import parser.Parser
import analyzer.Analyzer
import analyzer.TypeChecker
import code.CodeGenerator
import java.io.File
import scala.io.Source
class Compiler(val fileName: String)
extends Reporter
with Parser
with Analyzer
with TypeChecker
with CodeGenerator {
val file = new File(fileName)
val shortName = file.getName
val source = Source.fromFile(file).withPositioning(true)
def compile(classDir: String): Unit = {
import parser.Trees._
im…text/html2011-11-21T14:10:06+0200Anonymous (anonymous@undisclosed.example.com)cc11:lab10-main
https://lara.epfl.ch/w/cc11/lab10-main?rev=1321881006&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]")
sys.exit(1)
}
val compUnit = new Compiler(args(0))
if(args.length == 1) {
compUnit.compile("./")
} else {
if(!"-d".equals(args(1))) {
compUnit.fatalError("Unrecognized option: " + args(1))
}
compUn…text/html2011-09-26T23:59:56+0200Anonymous (anonymous@undisclosed.example.com)cc11:labs_01
https://lara.epfl.ch/w/cc11/labs_01?rev=1317074396&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/html2011-09-28T01:54:24+0200Anonymous (anonymous@undisclosed.example.com)cc11:labs_02
https://lara.epfl.ch/w/cc11/labs_02?rev=1317167664&do=diff
Labs 02
Part 1: Introduction to the Tool Compiler Project
Familiarize yourself with the Tool Programming Language and the Tool Compiler Project. Write two example Tool programs each (4 per group of 2) and make sure you can compile them using the Tool Reference Compiler. Please be creative when writing your programs. We don't need 5 versions of a program computing the Fibonacci sequence. The examples at the end of thetext/html2011-10-07T15:50:03+0200Anonymous (anonymous@undisclosed.example.com)cc11:labs_03
https://lara.epfl.ch/w/cc11/labs_03?rev=1317995403&do=diff
Labs 03
Finish the second part of Labs 02.text/html2011-11-16T10:29:47+0200Anonymous (anonymous@undisclosed.example.com)cc11:labs_04
https://lara.epfl.ch/w/cc11/labs_04?rev=1321435787&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/html2011-10-26T20:27:39+0200Anonymous (anonymous@undisclosed.example.com)cc11:labs_05
https://lara.epfl.ch/w/cc11/labs_05?rev=1319653659&do=diff
Labs 05
Finish Labs 04.text/html2011-10-26T20:31:00+0200Anonymous (anonymous@undisclosed.example.com)cc11:labs_06
https://lara.epfl.ch/w/cc11/labs_06?rev=1319653860&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. 8th, 11.59pm (23h59). Note that the type checker will be due the following week, so make sure you start working on it as early as possible.text/html2011-11-21T14:11:47+0200Anonymous (anonymous@undisclosed.example.com)cc11:labs_07
https://lara.epfl.ch/w/cc11/labs_07?rev=1321881107&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 liketext/html2011-11-22T22:36:54+0200Anonymous (anonymous@undisclosed.example.com)cc11:labs_10
https://lara.epfl.ch/w/cc11/labs_10?rev=1321997814&do=diff
Labs 10
Congratulations, your front-end is complete! You are now one step 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 thetext/html2011-12-02T15:11:13+0200Anonymous (anonymous@undisclosed.example.com)cc11:labs_11
https://lara.epfl.ch/w/cc11/labs_11?rev=1322835073&do=diff
Labs 11: Your Turn
You have now written a compiler for a simple language. The final mini-project of the course is to research, design an implement an extension for the compiler and/or the language it supports. This page gives a list of ideas, but you should also feel free to submit your own by email. All groups will rank the mini-projects in order of preference on thetext/html2011-09-20T23:02:13+0200Anonymous (anonymous@undisclosed.example.com)cc11:labs_setup
https://lara.epfl.ch/w/cc11/labs_setup?rev=1316552533&do=diff
Labs Setup
This page contains instructions on how to set up your computer such that you can:
* program your assignments,
* share them with your teammate via a version control system,
* submit your labs for grading, and
* use our black-box testing system.text/html2011-09-20T22:35:18+0200Anonymous (anonymous@undisclosed.example.com)cc11:lecture_01
https://lara.epfl.ch/w/cc11/lecture_01?rev=1316550918&do=diff
Lecture 01: Introduction
Slides:
* Slides as PDF
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 Too…text/html2011-09-28T00:28:18+0200Anonymous (anonymous@undisclosed.example.com)cc11:lecture_02
https://lara.epfl.ch/w/cc11/lecture_02?rev=1317162498&do=diff
Lecture 02: Lexical Analysis
Partial Slides in PDF
Key insights:
* lexical analyzer maps a stream of characters into a stream of tokens
* while doing that, it typically needs only finite memory
* we can specify tokens for a lexical analyzers using regular expressionstext/html2011-10-06T10:03:22+0200Anonymous (anonymous@undisclosed.example.com)cc11:lecture_03
https://lara.epfl.ch/w/cc11/lecture_03?rev=1317888202&do=diff
Lecture 03: Automatic Construction of Lexers. Basics of Parsing
Lecture 3 PDF Slides
Automatic Construction of Lexers
Equivalence of finite state machines and regular expression languages
Minimization of State Machines
Implementing Finite State Machines
Using Finite State Machines for Lexical Analysis
Basics of Parsing
Context-Free Grammars
(Manually Constructed Parser Sketch is in Slides)
Basic Idea of First Symbol Computation
Computing Nullable Nonterminals
Computing Follow Sets
C…text/html2011-10-24T08:14:28+0200Anonymous (anonymous@undisclosed.example.com)cc11:lecture_04
https://lara.epfl.ch/w/cc11/lecture_04?rev=1319436868&do=diff
Slides
[PDF Slides on manually written parsers]
Additional topics covered
Basic Idea of First Symbol Computation
Computing Nullable Nonterminals
Computing Follow Sets
Computing First and Follow Setstext/html2011-10-19T22:54:59+0200Anonymous (anonymous@undisclosed.example.com)cc11:lecture_05
https://lara.epfl.ch/w/cc11/lecture_05?rev=1319057699&do=diff
Lecture 05
Basic Idea of First Symbol Computation
Computing Nullable Nonterminals
Computing Follow Sets
Algorithm for First and Follow Sets
Table-Driven Parser for Balanced Parentheses
LL(1) Table-Driven Parsing Overview
Building LL Parsing Table
Interpreting LL Parsing Table
Slides on CYK: [pdf], [pptx]text/html2011-10-23T16:14:20+0200Anonymous (anonymous@undisclosed.example.com)cc11:lecture_06
https://lara.epfl.ch/w/cc11/lecture_06?rev=1319379260&do=diff
Lecture 06
[lecture notes]
Earley Parser
Continued in Lecture 07
Exercise 1
Given the following grammar:
S → AaB | aBb
A → a | C
B → FAb | bA
C → CDB | ϵ
D → A | B | ab
E → b | A
F → aF
* Remove ϵ-productions, unit productions and useless non-terminals.
* Put the resulting grammar into Chomsky Normal Form.text/html2011-10-23T16:13:39+0200Anonymous (anonymous@undisclosed.example.com)cc11:lecture_07
https://lara.epfl.ch/w/cc11/lecture_07?rev=1319379219&do=diff
Lecture 07: Earley Parser. Semantic Actions. Combinator Parsing
Slides: [pptx], [pdf]
Earley Parser
Notion of Semantic Action
Parsing Combinators
Compiler-Compilers (Compiler Generators)
Continued in Lecture 08text/html2011-10-28T20:20:24+0200Anonymous (anonymous@undisclosed.example.com)cc11:lecture_08
https://lara.epfl.ch/w/cc11/lecture_08?rev=1319826024&do=diff
Lecture 08
More on Parsing
Context-Free Grammars
[Review Manual Parsing]
Building trees following priorities: [pptx], [pdf]
Parser part of project is due tomorrow.
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
Nice things about LR Parsing
Precedence in LR Parsing
…text/html2011-10-29T20:42:10+0200Anonymous (anonymous@undisclosed.example.com)cc11:lecture_09
https://lara.epfl.ch/w/cc11/lecture_09?rev=1319913730&do=diff
Lecture 09
Last time talked still about Automata for LR Parsing without Lookahead
but did not cover LR Parsing Tables
Name Analysis
Maintaining Maps
Implementation: Symbol Tables and Error Reporting
Symbol Table Contents
Functional versus Imperative Maps
An Efficient Imperative Map
Functional Maps
Reporting Errors Based on Syntax Tree
Type Checking
Type Rules for A Language Similar to Tool
Slides:
* [A lot of dark pptx slides on type checking]
* [Those same slides but now in PDF…text/html2011-11-15T18:34:33+0200Anonymous (anonymous@undisclosed.example.com)cc11:lecture_12
https://lara.epfl.ch/w/cc11/lecture_12?rev=1321378473&do=diff
Lecture 12
[Type inference slides]text/html2011-11-22T19:44:42+0200Anonymous (anonymous@undisclosed.example.com)cc11:lecture_13
https://lara.epfl.ch/w/cc11/lecture_13?rev=1321987482&do=diff
Lecture 13: First Lecture on Code Generation: Examples and Expressions
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 Postfi…text/html2011-11-22T19:44:20+0200Anonymous (anonymous@undisclosed.example.com)cc11:lecture_14
https://lara.epfl.ch/w/cc11/lecture_14?rev=1321987460&do=diff
Lecture 14: Second Lecture on Code Generation: Statements and Conditionals
(Continuing Lecture 13)
Efficiently Emitting Code
Compiling Control-Flow Statements
Booleans and Data Representation
Branching JVM Instructions
Compiling If Then Else
Compiling While
Compiling Relations and Boolean Operators
Translation of Relations
Pay attention here
Postfix Translation of Boolean Operators
Compiling Conditional Expressions
Short-Circuit Evaluation
The Cool Way: Better Code Generation for C…text/html2012-12-02T17:43:50+0200Anonymous (anonymous@undisclosed.example.com)cc11:lecture_15
https://lara.epfl.ch/w/cc11/lecture_15?rev=1354466630&do=diff
Lecture 15: Introduction to Program Analysis
Introductory slides: [pptx], [pdf]
Applications of Data-Flow Analysis
Idea of Data Flow Analysis
Control-Flow Graphs
Key Background
Control-Flow Graph Definition
Why control-flow graphs instead of syntax trees
* they can represent arbitrary jumps
* they are simple: conditions and loops represented uniformlytext/html2011-12-06T15:05:26+0200Anonymous (anonymous@undisclosed.example.com)cc11:lecture_16
https://lara.epfl.ch/w/cc11/lecture_16?rev=1323180326&do=diff
Lecture 16: Data-Flow Analysis
(Continuing Lecture 15)
Slides: [pptx], [pdf]
Background: Partial order and Lattices
Examples for Initialization Analysis
Checking Initialization Using Data-Flow Analysis
References
* [Lecture notes on static analysis by Michael Schwartzbach], especially chapters 4,5,6
* Compiler Construction by Niklaus Wirth, chapters 9,10, 11
* Tiger book, Chapters 7-11, 17
* Abstract Interpretation in a Nutshell by Patrick Cousot (also a course at MIT)
* Lecture…text/html2011-12-12T16:50:25+0200Anonymous (anonymous@undisclosed.example.com)cc11:lecture_17
https://lara.epfl.ch/w/cc11/lecture_17?rev=1323705025&do=diff
Lecture 17: Mapping Program State to Memory, Including Register Allocation
Register Machines and Basic Mapping
Introductory slides: [pptx], [pdf]
Register Machine Model in Scala
Stack Frames and Procedure Calls
Register Allocation
From Stack Machine to Register Machine
Register Allocation using Liveness Information
Sketched: Live-Variable Analysis
Optional Additional Information
Heap: Explicit Dynamic Memory Managementtext/html2011-12-13T10:39:00+0200Anonymous (anonymous@undisclosed.example.com)cc11:project_presentations
https://lara.epfl.ch/w/cc11/project_presentations?rev=1323769140&do=diff
Project presentations
Schedule:
In INM 202
8:15 -- Group 4, Garbage Collection
8:35 -- Group 2, Generics: Type-Parametric Programming
8:55 -- Group 11, ADTs with Pattern-Matching
9:15 -- Group 8, First-class Functions
9:35 -- Group 9, Liberal Syntaxtext/html2011-09-27T23:44:09+0200Anonymous (anonymous@undisclosed.example.com)cc11:tool
https://lara.epfl.ch/w/cc11/tool?rev=1317159849&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 Identifiertext/html2011-09-28T01:04:49+0200Anonymous (anonymous@undisclosed.example.com)cc11:tool_compiler_project
https://lara.epfl.ch/w/cc11/tool_compiler_project?rev=1317164689&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 waytext/html2011-12-07T20:08:31+0200Anonymous (anonymous@undisclosed.example.com)cc11:tool_reference_compiler
https://lara.epfl.ch/w/cc11/tool_reference_compiler?rev=1323284911&do=diff
The Tool Reference Compiler
The latest version is 1.9. You can obtain it from here.
You can run it as follows:
java -jar toolc-reference-1.9.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 runtext/html2011-09-28T01:14:36+0200Anonymous (anonymous@undisclosed.example.com)cc11:toolprog-binarysearch.tool
https://lara.epfl.ch/w/cc11/toolprog-binarysearch.tool?rev=1317165276&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/html2011-09-28T01:14:09+0200Anonymous (anonymous@undisclosed.example.com)cc11:toolprog-factorial.tool
https://lara.epfl.ch/w/cc11/toolprog-factorial.tool?rev=1317165249&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/html2011-09-28T01:17:27+0200Anonymous (anonymous@undisclosed.example.com)cc11:toolprog-maze.tool
https://lara.epfl.ch/w/cc11/toolprog-maze.tool?rev=1317165447&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/html2011-09-28T01:15:50+0200Anonymous (anonymous@undisclosed.example.com)cc11:toolprog-pi.tool
https://lara.epfl.ch/w/cc11/toolprog-pi.tool?rev=1317165350&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/html2011-09-28T01:15:11+0200Anonymous (anonymous@undisclosed.example.com)cc11:toolprog-quicksort.tool
https://lara.epfl.ch/w/cc11/toolprog-quicksort.tool?rev=1317165311&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/html2012-11-25T14:32:21+0200Anonymous (anonymous@undisclosed.example.com)cc11:top
https://lara.epfl.ch/w/cc11/top?rev=1353850341&do=diff
Compiler Construction 2011
For latest version see this page.
Quick links: Moodle page , Repository server , Tool Compiler Project
General Information
Note that:
* lectures, exercises, and labs are interchangeable
* attendance is strongly recommended in all slots
Will follow closely the structure of