CS 441G Fall 2002

CS 441G University Handbook Description

The techniques of processing, specifying, and translating high-level computer languages are studied. Topics include finite state machines and lexical analysis, context-free grammars for language specification, attributed translation grammars, language parsing, and automatic generation of compilers by SLR, LALR, and other methods for analyzing context-free grammars. Other topics may include code optimization, semantics of programming languages, and top-down parsing.

Prerequisites: CS-315 and engineering standing.

Requirements, Goals, Friendly Advice, and a Serious Warning

First and foremost, you must be very well organized. You need to know how to design and manipulate complex data structures. You need to know C and Java, one of which in considerable depth. You must be able to work with a small group. You must be able to stick to a schedule and deliver the goods on time or you are in deep trouble.

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.

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 plus the online class notes that you are expected to read cover to cover:

  1. David A. Watt and Deryck F. Brown, Programming Language Processors in Java: Compilers and Interpreters, Prentice Hall, 2000, ISBN: 0130257869.
  2. John R. Levine, Tony Mason, and Doug Brown, Lex & Yacc, O'Reilly & Associates, 1992, ISBN: 1565920007.
  3. C. C. Douglas, Compilers for Algorithmic Languages, MGNet.org, Cos Cob, CT, 1st Edition, 2002.

Some other books that you may find useful are the following:

The Schreiner and Friedman book is nice, but usually out of print. I will lecture from it during parts of October, however. The Aho-Ullman book is out of print, but is vastly superior to the Aho-Sethi-Ullman book for a course at this level. 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 on Tuesday through Thursday.

Day Time
Tuesday 3:15-4:00
Wednesday 9:00-10:00
Thursday 9:00-10:00
or by appointment.

My office is 321A McVey Hall. My office telephone number is 257-2326 and the eFAX is +1-203-547-6273. Feel free to telephone my office as late as 7:00pm. Do not leave voicemail on my office phone. In a pinch, I can be reached at home on Fridays 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). If you are stuck on something, please do not hesitate to contact me.

Warning: The entrance to my office is inside another office (321 McVey). I really do not hear knocking on the outer office's door (I am somewhat hearing impaired). Please just walk in and continue right into 321A and let me know that you are present. Do not worry about disturbing anything going on in the office since I need to know that you present. In particular, do not assume that I will know that you are in the outer office. If I am not in my office, go straight to 325 McVey and ask where am I. I may well be in there and have to be extracted from another inner office. Please be utterly brazen.


Classes normally will meet in 226 OHR (the civil engineering building). Classes will end promptly at 3:15, particularly on Thursdays. I will be assigning reading before classes. If you have not done the reading, please do not come to class until you have caught up. 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.

Should we have to make up classes (which is, unfortunately, likely), they will be in 327 McVey Hall. This is not a great room to take notes in, so bring something hard to write on that fits in your lap.

Homework and the Course Project

Your grade will be based on the homework and any exams that are given in the course. Compilers are written professionally in groups, not by individuals. There are very few exceptions to this and none commercially in recent memory. The class will be broken up into a number of small groups. Each group will produce two complete compilers (one in C and the other in Java) for a small language. All homework and the project will be due no later than December 12 at 2:00 pm.

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 zero tolerance for cheaters. There are enough interesting things to do in life without experiencing being tossed out of school.

Each group will be competing against the rest of the class to see who produces the fastest compilers with the most bells and whistles. Swapping your intellectual product with another group is stupid unless all groups are told to by me.

Your grade will be based 60% on homework and 40% on quizzes. See the quiz web page for a list of when they will be available online. There are 5 quiz dates listed.