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

General Contents

Recommended background

Activities

• F   Mondays 10:15 - 12:00, in F4
• F/Ø Wedndays 11:15 - 13:00, in F3

Exam and Grades

Syllabus (= Pensum)

• The lectures, as will be documented in these web pages.
• what you should have learned by doing all the exercises.

Main Topics

• an example compiler
  (which also serves as an example of a systems programming)
• semantic analysis, code generation, optimizations
  - implemented in the framework of the example compiler
• grammars
• some classical analysis algorithms

Lecture Notes

Current Notes

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

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:

Exercises

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