EEN594 (Compiler Construction) Spring 2011
Tue Thur 11:00-12:15 in MM218

Information

• Intel Processor (Pentium, etc.) Reference Manuals

Assignments

1. Create a code generator using the operator precedence stack-based method, to accept simple expressions consisting of just operators, numbers and variables. Create a virtual machine capable of executing the code produced to correctly evaluate the expressions.
2. The whole project.
   • The parser and pretty-printer is due on Friday 15th April.

Class History, etc.:

	Class 1		Tues 18‑1‑2011		General introduction to the subject. Simple code-generation of expressions (by operator priority) for a virtual machine.
	Class 2		Thurs 20‑1‑2011		What would be needed to automate that code generation in a practical way? The idea of simple VM code as an intermediary, making the generation of native intel code easier.
	Class 3		Tues 25‑1‑2011		A really simple virtual machine, incrementally improved. Get it correct the easy way, then make it more sophisticated in small steps, never giving the correctness a chance to slip away.
	Class 4		Thurs 27‑1‑2011		Shift-Reduce Parsing.
	Class 5		Tues 1‑2‑2011		Varieties of decisions about syntax to remove natural ambiguities and make parsing (both for computers and human readers) easier.
	Class 6		Thurs 3‑2‑2011		Varieties of programming language, what kinds of statements are necessary, values and type systems.
	Class 7		Tues 8‑2‑2011		Maybe you thought about how something simple like a sorting algorithm should look in a nice friendly programming language: what we can learn from thinking in that direction. The dope vector: how real arrays work.
	Class 8		Thurs 10‑2‑2011		Code generation for more realistic computers, taking advantage of registers.
	Class 9		Tues 15‑2‑2011		Letting the code generator decide for itself where values should go, representing an operand, conditional execution: generate a jump if an expression is false.
	Class 10		Thurs 17‑2‑2011		We have completed a method of code generation for a simple language. Considering instruction encoding, two pass assembly, labels, and a plan for the symbol table.
	Class 11		Tues 22‑2‑2011		Strict layering: Line input system enhances error reporting; lexical analyser knows nothing about syntax; parser knows nothing about form of tokens - why bother with making a parse tree instead of producing code on the fly; optimisation by constant folding and by restructuring the tree; code generation; keyhole optimisation; assembly. Introducing the relationship between shift-reduce and recursive descent parsers.
	Class 12		Thurs 24‑2‑2011		Technicalities of top-down parsing: First sets, Follow sets, Nullable productions. Generating top-down parsers, being able to check that a grammar is unambiguous.
	Class 13		Tues 1‑3‑2011		The magic of activation records: they are not necessarily stack frames. The static link and nested function definitions versus function pointers.
	Class 14		Thurs 3‑3‑2011		Co-routines: disentangling mutual recursion to solve the producer-consumer problem, activation records not behaving like a stack.
	Class 15		Tues 8‑3‑2011		Different types of grammars and the Chomsky Hierarchy.
	Class 16		Thurs 10‑3‑2011		The real difference between LL1 and LR1 parsing. How to extend LL1's power without changing the technique. pdfs - Grammar, Recursive Descent: b, e, Shift Reduce: c, d, f.
			Spring Break
	Class 17		Tues 22‑3‑2011		Recursive descent and LL1 naturally go hand-in-hand. A strictly LL1 parser can not handle grammars with left recursion, so they can't parse normal left-to-right evaluating expressions. But so what? The simple technique of using a loop solves the problem. It may not be strictly LL1, but it is clean and recursive descent. Looking at the values of important variables when this method is used, and seeing that they exactly duplicate the stack as it was with shift-reduce parsing, so we just added a little LR part to an otherwise LL parser.
	Class 18		Thurs 24‑3‑2011		The usefulness of a pretty-printer. Beginning semantic analysis: type-checking. Single shared node for each identifier every time it appears, parse-tree nodes represent types.
	Class 19		Tues 29‑3‑2011		Carrying forward position dependent information on variables from type checker to code generator. More efficient implementations of tree nodes. The high-tide mark, but not needed for Pascal-like languages where local variables can only be declared at the very beginning of a function. Representing types, and where C's syntax leads to trouble.
	Class 20		Thurs 31‑3‑2011		Declarations and Types. Code generation for functions.
	Class 21		Tues 5‑4‑2011		Pre-call code when Activation Records are self-contained objects. Dynamic Link and Static Link; continuation address rather than return address. Nested functions and dynamic free variables.
	Class 22		Thurs 7‑4‑2011		Full details of function call and return when normal stack frames are in use.
	Class 23		Tues 12‑4‑2011		Implementing object orientation. Renaming methods as functions with automatic "this" parameter; methods can be ordinary data members that contain pointers to functions; methods may be replaced at run-time; all data members may be replaced by pointers to get functions, so evreything in an object is just a pointer to a function; instead of members having a fixed offset from beginning of object, known to the compiler, the object can be a hash table; new methods may be added at run time; optimising the hash table: open hashing, size is power of two keeping fullness less than 0.5, using "interned" strings as keys; object includes extra pointer to seond object to use when searches fail: gives inheritance; the delegation model.
	Class 24		Thurs 14‑4‑2011		Rapid prototyping: the two hour programming language, part one.
	Class 25		Tues 19‑4‑2011		The two hour programming language, part two: cons, head, tail, set, variables, booleans, if, while, sequences, read, print, quote, eval, macros.
	Class 26		Thurs 21‑4‑2011		Local variables and functions, traditional Lisp.
	Class 27		Tues 26‑4‑2011		A complete Lisp interpreter, except for one thing: discovering the need for garbage collection while trying out the Lisp programming style with a few list-processing functions.
	Class 28		Thurs 28‑4‑2011		Garbage Collection, the mark-and-sweep method. Everything in use must be protected, even temporary values stored in the interpreter's own local variables, so an explicit stack made of cons-cells is needed.