CS 441G Fall 2005

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

  1. Kenneth C. Louden, Compiler Construction: Principles and Practice, PWS Publishing Co., 1997, ISBN 0534939724.
    Web page: http://www.cs.sjsu.edu/faculty/louden/cmptext
  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, 5th 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:

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 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. 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 CS441 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 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.

Many Thursdays class 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 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 6 at 6:00 pm.

You will work in pairs on your project. 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 as soon as possible so that I can try to fix the problem before it becomes fatal to your grade. I will reassign the deadbeats to work with each other, given enough warning and proof. 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 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.