CS 441G Fall 2004

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 or C++, one of which in considerable depth. 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. 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 is one traditional textbook plus the online class notes that you are expected to read cover to cover:

  1. John R. Levine, Tony Mason, and Doug Brown, Lex & Yacc, O'Reilly & Associates, 1992, ISBN: 1565920007.
  2. C. C. Douglas, Compilers for Algorithmic Languages, MGNet.org, Cos Cob, CT, 2nd Edition, 2004.

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:

http://lambda.uta.edu/cse5317/notes.pdf Design and Construction of Compilers, Leonidas Fegaras, 2004.
http://scifac.ru.ac.za/compilers Compilers and Compiler Generators: an introduction with C++, P. D. Terry, Rhodes University, 1997.
http://www.compilers.net/Dir/Free/Books A set of links to free compiler related books on the net.
http://www.thefreecountry.com Free programmers' resources including links to many free compilers, some of whom's source code is readily available to inspect.
http://www.sai.msu.su/sal/F/1 Scientific applications on Linux, which includes an extensive list of links to compilers.
http:///www.compilerconnection.com Links to compiler information.

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 1:45-3:00
Wednesday 8:30-9:30
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 RMB 323 (the building formerly known as the Robotics building). Classes will end promptly at 1:45, particularly on Thursdays. 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.

Homework and the Course Project

Your grade will be based on the homework and the three 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 December 7 at 12:30 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.

Course Evaluation Questions Specific to this Class

This class has taught me how to

37. Learn how to write a regular expression.

38. Generate a lexer.

39. Generate a parser.

40. Write a code generator.

41. Design and write a complex programming project.

42. Document a large programming project, including what works and what does not or is not implemented.