TDT4205     Compiler Construction
(Kompilatorteknikk)
fall semester 2005


News and Announcements

The latest exam papers with proposed solution is found in the list of such, below.   (15.dec'05, P.H.)

I have learned that some students in this course had an exam today, monday. I will therefore show up to answer more questions on Tuesday, 13.dec. at 13:15 in F4.
Observe that the notes 'del09' were handed out in two parts, one ending with 'viable prefixes' and 'valid items' (both of these pages were actually omitted from this year's course) and another part starting 'making SLR parsing tables'. The notes here on the web site are complete and accurate.   (12.dec'05, P.H.)

Reminder: Be sure to bring a copy of the lecture notes AND of the "Proposed solution to exercises 2-4" to the exam.
We meet to discuss questions (spørretime) on Monday 12.dec'05, at 10:15 in F4.   (9.dec'05, P.H.)

The exam is Dec.14. You may bring any papers you wish. Be sure to bring a copy of the lecture notes: there may be tasks where you should program additions to the example compiler.   (17.Nov'05, P.H.)

Next week is the last for ordinary lectures this semester. To get through the material we need to get through, it looks like we will need a short lecture in addition to the one on Monday. Let us meet on Wednesday Nov.23, at 11:15 in F3. We will presumably have time left to answer questions from you.   (17.Nov'05, P.H.)

Exercise 4 is now available on the exercise page.   (03.Nov'05, L.O.)

Sorry folks, my alarm clock did'nt go off so I sat happily working until 11:35. But please: you must knock on my office door when I forget the time like this. Now, all I can do is to provide a solution in writing.   (P.H. 19.okt'05)

For those interested: We will have a discussion of solutions to exercise 2 on wednsday 19.october, at 11:15 hrs., in F3.   (18.Oct'05, P.H.)

Exercise 3 is now available on the exercise page.   (17.Oct'05, L.O.)

Added "Approved exercises" to the exercise page.   (13.Oct'05, L.O.)

Of special interest to the good folks doing the exercises: I was made aware of a bit of theory concerning syntax analysis of proc.s that had slipped my mind. You will find a note on the subject here, we'll take another look at it later.   (10.oct'05, P.H.)

From this week (nr. 41) and on, there will only be lectures on mondays, 10:15-12:00 as usual.   (10.oct'05, P.H.)

Exercise 2 is now available on the exercise page.   (28.Sept'05, L.O.)

Some new parts of the lecture notes are available. The files of the Example Compiler, minimal version, have also been replaced with new, fixing a flaw or two.   (8.sept'05, P.H.)

The first lecture is Monday Aug. 22, 2005, at 10:15 in F4 ("Old Physics" building/ Gamle Fysikk). (19.aug'05, P.H.)

Note that the 'parts' of the current lecture notes often are revised after the material has been presented, to reflect insights gained when lecturing the stuff.   (1.sep'05, P.H.)


Course Description

Aim

To give a good knowledge of techniques for the construction of compilers (programming language translators) and some insight in how to build systems software, more generally.


General Contents

Compilers are a prerequisite for constructing modern software. Compiler construction is a field of computer technology that early reached maturity, with a sound theoretical basis. Elements of this technology are employed in most areas where one does a thorough analysis of texts on a computer. The course discusses grammars, lexical and syntactic analysis, semantic analysis, optimizations, code generation, interpreters and abstract machines, linkers and run time systems. The concrete structure of a compiler that generates code for a realistic computer is studied in some detail.


Recommended background

TDT4165 Programming Languages, TDT4120 Algorithms and Data Structures and TMA4140 Discrete Mathematics.


Activities

Lectures and exercises. If there are students that need it, the course will be given in English. The first 7 weeks, there will be 2 lectures of 2 hours each, the last 7 weeks 1 lecture of 2 hours. Some part of the exercises will be mandatory - details follow later. Time and place for the exercises will be announced later ('Datasal Gombe' will presumably not be used.)


Exam and Grades

The grade for this course is set based on a final exam. All hand-written and printed material is allowed. (Remember to bring a copy of the lecture notes to the exam!)


Syllabus (= Pensum)


Main Topics




Lecture Notes

Current Notes

Will appear here as they are completed.

part00   Course overview. The example compiler: overview, modules dict.h & lexAn.h. 26.aug'05
part01   Grammar notations. The example compiler: module syntax.h. Semantic tree format. 31.aug'05
part02   CPU instruction sets. The example compiler, module machCode.h. Interpreters, example compiler module exec.h; exec.cc & syntax.cc: main programs for the code executer and for the compiler. 01.sep'05
pentium sampler   Some pages from the Intel Pentium manual, to give an idea of the complexities of an industry instruction set. 31.aug'05
part03   Code generation: executing a semantic tree, flattening the tree, code templates, opeRand descriptions. The example compiler: modules rand.h & generate.h. 13.sep'05
part04   More code generation: register allocation, boolean expressions and relational operators; procedures and calls. Proc.s and the dictionary. 24.nov'05
part05   Semantic analysis and optimization passes. Front- and back-ends: preprocessor, linker, assembler. 26.sep'05
part06   Finite automata (state machines): strings and languages, regular expressions, grep & lex, state diagrams & - tables, implementation 22.sep'05
part07   NFAs: executing one, converting reg.exp. to NFA (Thompson's construction; the followpos method). DFAs: converting NFA to DFA (the subset construction) - examples. Searching for reg.exp. in string. Automata and lexical analysis. 5.okt'05
part08   Syntax analysis: Ambiguities, assiciativity, precedence, 'dangling else'. Regular expressions, context free languages, non-context free. Generating grammars. Predictive parsing: FIRST and FOLLOW. Recursive descent. Grammar transformations and semantic tree. Backtracking. Non-recursive predictive parsing, generating tables for -. Definition: LL(1) grammars. Error handling. 5.okt'05
part09   Bottom-up parsing, shift-reduce parser,operator precedence, LR parsers, making SLR parser tables. Short comments on LR(1) parsing and register use for modern 'pipelined' CPUs. 24.nov'05
loesFor2   Proposed solution to exercises 2-4: Overview, inserted code, example run. 24.nov'05


Last year's notes

(This year will comprise mainly the same material, but in a different order.)

part/del00 , part/del01 , part/del02 , part/del03 ,

part/del04 , part/del05 , part/del06 , part/del07 ,

part/del08 , part/del09 , part/del10 , part/del11 ,

part/del12 ,


Exam papers with proposed solutions:

Ordinary Dec. 2005:
oppgavetekst
løsningsforslag
Ordinary Dec. 2004:
oppgavetekst
tasks & proposed solution
Kont. Aug. 2004:
oppgavetekst
løsningsforslag
Ordinary Dec. 2003:
oppgavetekst
tasks
proposed solution
Kont. Aug. 2003:
oppgave
løsningsforslag
Ordinary Dec. 2002:
oppgavetekst m. løsningsforslag


Exercises

see the exercises page!


The Example Compiler, minimal version

  README     How to run
  dict.h     dictionary/ Symbol table
  lexAn.h     lexical analyser
  syntax.h     syntax analyser
  machCode.h     machine code formats, - i/o buffers
  rand.h     operand descriptors
  generate.h     code generation
  syntax.cc     the compilable unit of the compiler
  exec.h     'machine code' interpreter
  exec.cc     the compilable unit of 'machine code' interpreter


The Example Compiler, medium version

  README     How to run
  dict.h     dictionary/ Symbol table
  lexAn.h     lexical analyser
  syntax.h     syntax analyser
  machCode.h     machine code formats, - i/o buffers
  rand.h     operand descriptors
  optim.h     optimization pass
  generate.h     code generation
  syntax.cc     the compilable unit of the compiler
  exec.h     'machine code' interpreter
  exec.cc     the compilable unit of 'machine code' interpreter


Exercises from previous years

Number 1  

Number 2   Reference solution: lexAn.h dict.h machCode.h syntaxnew.h syntaxnew.cc rand.h

Number 3

  • Gamle øvinger (2002): 1 2 3 4 5 6 7 8 9 10
  • Old exercises, in English: 1 2 3 4 5
  • Løsningsforslag: 1 2 3 4 5 6 7 8 9 10
  • Solutions in english (NB: not all will be translated): 3
  • An introduction to lex and yacc can be found here . (helpful for the exercises (?))
  • kopi av de fargelagte lysarkene fra 2002
  • eksamenslignende oppgaver og vedlegg til eksamen høsten 2002


  • Latest update: 15.Dec'05
    P.H.