Courses/CompilationLecture2006

This page contains the log of the topics that of the CompilationLecture for class EPITA 2006 (i.e., from January 2004 to July 2004). The topic was started with the FormalLanguagesLecture; see the ThlLog2006.

Week 1 January 19, Main.RobertAnisko: Program generators, Introduction to Gperf, Flex, Bison

1. Introduction to scanner/parser generators
   1. Lex/Flex
   2. Yacc/Bison
2. Introduction to Flex
   1. Scanning keywords
   2. Scanning integers: yytext
   3. Scanning identifiers: yytext + yyleng + yylval
   4. Identifier vs. keyword: the ``meta rules (longuest match, first rule)
   5. Using start conditions to handle the nested comments
   6. Using start conditions to handle escapes in strings
3. Introduction to Bison
   1. Writing a simple grammar
   2. Writing calc: %left and so forth
   3. Dealing with ambiguous grammars: learn to read Bison's report
   4. Writing actions
4. Interface Flex & Bison
   1. Write a flex scanner for arithmetics
   2. Write a bison parser for arithmetics
   3. Put pieces of calculator to work

Week 2, January 26, Main.RobertAnisko: Tiger Samples, Fixing Yacc Conflicts

1. The Tiger language
   1. Syntax, expressions, functional flavor
   2. Chunks of declarations, recursion, mutual recursion
   3. Arrays, records, and references
2. Sample programs
   1. print-tree
   2. queens
   3. merge
3. Fixing the Dangling else Shift/Reduce:

	cat >1-if.y <<-EOF
	%%
;exp: "if" exp "then" exp
{| class="wikitable"
|-
	|| "if" exp "then" exp "else" exp
|}

{| class="wikitable"
|-
	|| "exp"
|}

	;
	%%
	EOF
	

1. Fixing the ternary operator Shift/Reduce

	cat >2-ternary.y <<-EOF
	%%
;exp: exp "?" exp ":" exp
{| class="wikitable"
|-
	|| "exp"
|}

	;
	%%
	EOF
	

Week 3, February 2: Fixing Yacc Conflicts

Lectures notes are available in PDF.

1. Melkior
2. Fixing the Dangling else Shift/Reduce:

	cat >1-if.y <<-EOF
	%%
;exp: "if" exp "then" exp
{| class="wikitable"
|-
	|| "if" exp "then" exp "else" exp
|}

{| class="wikitable"
|-
	|| "exp"
|}

	;
	%%
	EOF
	

1. Fixing the ternary operator Shift/Reduce

	cat >2-ternary.y <<-EOF
	%%
;exp: 
  exp "?" exp ":" exp
{| class="wikitable"
|-
	|| "exp"
|}

	;
	%%
	EOF
	

1. Understanding the mysterious Reduce/Reduce

	cat >3-promac.y <<-EOF
	%%
;sentence: 
{| class="wikitable"
|-
	  "proc"  argument '.'  || "proc"  parameter ';'
|}

{| class="wikitable"
|-
	|| "macro" argument ';'  || "macro" parameter '.'	;
|}

;argument: "id";
;parameter: "id";
	%%
	EOF
	

1. Fixing Reduce/Reduce problems: lvalues

	cat >5-lvalues.y <<-EOF
	%%
;exp: typeid "[" exp "]" "of" exp
{| class="wikitable"
|-
	|| lvalue
|}

	;
;lvalue: "id"
{| class="wikitable"
|-
	|| lvalue "[" exp "]"
|}

	;
;typeid: "id"
	;
	%%
	EOF
	

1. Autoconf: tc/configure.ac
2. Automake: tc/src/Makefile.am, tc/src/type/Makefile.am
3. Tracking Locations with Flex.

Week 6, March 8th: History of Programming Languages

1. Template specialization.
2. Traits.
3. Using Traits to factor const and non const visitors.

Week 7, March 15th: History of Programming Languages

See the lecture notes, http://www.lrde.epita.fr/~akim/compil/lecture-notes/history.pdf.

1. Computing Chronology.
2. Eniac.
3. The Baby.
4. Ferranti Pegasus & autocode
5. IBM 704 & FORTRAN I
6. Algol.
7. COBOL.
8. PL/I
9. BASIC.
10. Pascal and its family.

Week 8, March 22th: Types and Type Checking

See the lecture notes, http://www.lrde.epita.fr/~akim/compil/lecture-notes/type-checking.pdf.

1. Why using Types
2. Type Kinds
   1. Atomic types
   2. Composed types
   3. Variants/Unions
   4. Genericity
3. Types Behavior
   1. Equivalence
   2. A Grammar for Types
   3. Subtyping vs. subclassing
4. Tiger Type checking
   1. A Grammar for Types
   2. A TypeVisitor
   3. A TypeEnvironment
   4. Typechecking a simple expression
   5. Typechecking an OpExp

Week 9, March 29th: T4 and History of Object Oriented Programming Languages

See the lecture notes, http://www.lrde.epita.fr/~akim/compil/lecture-notes/object.pdf.

1. Design Issues
   1. The /Template Method/ Design Pattern
   2. The static /Template Method/ using /method templates/ and

template specialization

1. Tiger Type Checking
   1. Type-checking type declarations
      1. The list type
      2. Mutually recursive types
      3. Multiple definitions
   2. Type-checking function declarations
   3. Implementing Header/Body visits generically
2. Object Oriented Programming Languages History
   1. Simula
   2. Smalltalk
   3. C++

Week 10, April 5th: Object Oriented Programming Languages and Eiffel

See the lecture notes, http://www.lrde.epita.fr/~akim/compil/lecture-notes/object.pdf and http://www.lrde.epita.fr/~akim/loo/eiffel.pdf.

1. Bad Properties from OO Languages
2. Eiffel

Week 11, May 3rd: Intermediate Representation 1

See the lecture notes, http://www.lrde.epita.fr/~akim/compil/lecture-notes/intermediate.pdf

1. Intermediate Representations
2. High Level Representation

Week 12, May 24th: Intermediate Representation 2

See the lecture notes, http://www.lrde.epita.fr/~akim/compil/lecture-notes/intermediate.pdf

1. High Level Representation
2. Low Level Representation

Week 13, June 7th: Instruction Selection and Subprograms

See the lecture notes, http://www.lrde.epita.fr/~akim/compil/lecture-notes/instr-selection.pdf and http://www.lrde.epita.fr/~akim/compil/lecture-notes/subprograms.pdf.

1. Instruction Selection
2. Subprograms