CS 541 Spring 2006

Course Description

Intermediate aspects of a compilation process for high-level languages. Theoretical and practical issues in developing a complete translator. Code generation for expressions, control ststements, and procedures (including parameter passing). Symbol tables, runtime organization for simple and structured variables. Using cimpilers and translators for automation (filters, programs writing programs). Prerequisites: CS-441G or instructor's consent.

Requirements, Goals, Friendly Advice, and a Serious Warning

Students must be adept programmers in a modern computer language (e.g., C) and have a good working knowledge of machine organization and architecture. You must be comfortable designing and manipulating complex data structures.

First and foremost, you must be very well organized. At the end of this course, you should know how to write a translator and how to use a compiler generator. This includes use of regular pattern expressions, lexical analysis, parsing, and code generation. Some of the software tools you will use are lex (or flex) and yacc (or byacc or bison). Your lexer and parser will be generated by lex and yacc (or their equivalents).

You will also be exposed to how corporations do product development in a "profit center" format. Once you are evaluated on a part of the course project, you will have the option of bailing out of your previous work and using the best of the rest of the class as you continue with the next part. Of course, there is no guarantee that you will be any more successful with others' work, but you will have the opportunity to compete again on a level playing field.

Warning: This course has a lot of work associated with it. Not only is there a bear of a class project (a compiler), but there is homework, too. If this is too much work for you, then do everyone a favor and change to another course sooner rather than later. Should you drop the class or change to auditing, please let me know immediately.

Textbooks and Suggested Reading

There are two traditional textbooks and an online book, which you are expected to read cover to cover.

  1. Alfred V. Aho, Ravi Sethi, and Jeffrey D. Ullman, Compilers: Theory and Practice, Addison-Wesley, 1990. ISBN: 0201100886.
  2. John R. Levine, Tony Mason, and Doug Brown, Lex & Yacc, O'Reilly & Associates, 1992. ISBN: 1565920007.
  3. C. C. Douglas, Advanced Compilers for Algorithmic Languages, MGNet.org, Cos Cob, CT, 4th Edition, 2006.

There are some quite useful online books, notes, and information sources. Searching on Google will lead you to many sources. Among my favorites are the following:

The Schreiner and Friedman book is nice, but usually out of print. I may lecture from it during parts of February or March. The Aho-Ullman book is out of print, but is vastly superior to the Aho-Sethi-Ullman book. The Kernighan-Ritchie book is a classic, but is somewhat outdated. I personally liked the first draft of the first chapter of the first edition (circa September, 1977). However, there are literally thousands of other C books that you can choose from. Any recent one that you like will do fine.

Office Hours and Contact Information

My office hours will be by appointment only this term, but Tuesdays before and after class should be a safe bet that I will be in my office.

My office is 514H RMB (the building formerly known as the Robotics building). My office telephone number is 257-2438 and the eFAX is +1-203-547-6273.Feel free to telephone my office as late as 6:00pm. It is a bad idea to leave voicemail on my office phone. In a pinch, I can be reached at home on Friday evenings and weekends only at +1-203-625-9449 (this is in Connecticut, not Kentucky). Please do not call me at home before 9:00 am or after 9:00 pm. I respond to e-mail (douglas-craig@cs.yale.edu) fairly quickly (always include a phone number where I can call you back and CS541 in the subject). If you are stuck on something, please do not hesitate to contact me. Please be utterly brazen.

Classroom and CSLab

Classes normally will meet in RGAN 207. Classes will begin and end promptly on time. I will be assigning reading before classes. I will assume that you have done the reading and can be called on to answer any question that comes up from your classmates or me. I am going to use the Socratic method of teaching instead of spoon feeding the material to you.

Most Thursday classes will be assigned to the CSLab facilities for work in groups on the course project or homework.

Homework and the Course Project

Your grade will be based on the homework and the multi-part course project. Compilers are written professionally in groups, not by individuals. There are very few exceptions to this and none commercially in recent memory. All homework and the project will be due no later than May 2 at 6:00 pm. I do not want hear the I word and do not plan on giving any such grades.

You will work in pairs on your project and many of the homeworks. You will get to offer me advice on a partner, but I will assign the pairs based on the course survey. There may be one group of three at the beginning of the course. By the end, there may be more than one group of three. Should you be partnered with an utter deadbeat, let me know. I will reassign the deadbeats to work with each other. I want the work to be split evenly, or close thereof.

It is quite easy to either cheat or plagiarize in this course, even by accident. Do not exchange code unless you have been explicitly told to do so. Do not swap printed or electronic versions either. Do not look over a shoulder and take notes. Do not try to be a lawyer and find a clever way of doing something similar to these examples. Getting caught cheating or plagiarizing will result in a grade of E and possibly much worse, including expulsion from the university and legal proceedings against you. I have no tolerance for cheaters. There are plenty of interesting things to do in life without experiencing being tossed out of school.

Course Evaluation Questions Specific to this Class

This class has taught me how to

37. How to specify lexical and syntactical structure of languages.

38. How to use regular patterns and grammars.

39. How to use parsing and translation techniques for automation of computing tasks.

40. How to use tools to generate lexical analyzers, parsers, translators, and code generators.

41. How to organize runtime storage for static and dynamic objects.

42. Design and write a complex programming project.