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:
- Kenneth C. Louden, Compiler Construction: Principles and Practice, PWS Publishing Co., 1997,
Web page: http://www.cs.sjsu.edu/faculty/louden/cmptext
- John R. Levine, Tony Mason, and Doug Brown, Lex & Yacc, O'Reilly & Associates, 1992, ISBN: 1565920007.
- 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:
- Axel T. Schreiner and H. George Friedman, Jr., Introduction to Compiler Construction with UNIX, Prentice-Hall, New York, 1985, ISBN 0-13-474396-2. See http://www.cs.rit.edu/~ats and click on Books.
- Alfred V. Aho and Jeffrey D. Ullman, Principles of Compiler Design, Addison-Wesley, 1977.
- Alfred V. Aho, Ravi Sethi, and Jeffrey D. Ullman, Compilers: Theory and Practice, Addison-Wesley, 1990.
- Brian W. Kernighan and Dennis M. Ritchie, The C Programming Book, Prentice-Hall, 1988.
- Tony Stubblebine, Regular Expression Pocket Reference: Regular Expressions for Perl, C, PHP, Python, Java, and .NET, O'Reilly & Associates, 2003.
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 (email@example.com) 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.