| Class meeting | 6:00-7:15pm TTh, Austin 304 | |||
| Instructor | Karl Abrahamson | |||
| Office | Sci&Tech C-113 | |||
| Office hours |
|
|||
| Phone | 328-9689 | |||
| abrahamsonk@ecu.edu | ||||
| Course web page | www.cs.ecu.edu/~karl/5220/spr08/ | |||
| My web page | www.cs.ecu.edu/~karl/ | |||
| Text | Compilers: Principles, Techniques & Tools (Second Edition) by A. V. Aho, M. S. Lam, R. Sethi and J. D. Ullman |
You should have a good understanding of programming and be able to write well structured and well organized programs in C++ or Java.
The first real compilers were written in the 1950s. Compiler developers had a poor understanding of what they were doing, and did everything in an ad-hoc way. The popular wisdom was that it took 30 person-years to write a compiler, even for a very simple programming language such as early versions of Fortran. (Considering the state of the art at the time, the compiler developers did a remarkably good job. Their code optimizers produced excellent machine code.)
There is probably no aspect of software development that has benefited from developments of the last 40 years more than the construction of compilers. Developments in the theory of computing have led directly to very powerful tools that not only make compiler writing much easier than it once was, but are also useful for other kinds of software. It is now feasible to write a compiler for a small programming language as a course project.
It is useful for a computer scientist to study compiler design for several reasons.
Anyone who does any software development needs to use a compiler. It is a good idea to understand what is going on inside the tools that you use, in order to have a better understanding of their capabilities and their limitations.
Compilers are sophisticated text processors. Most programs need to do some text processing, even if only to read in the contents of a configuration file. Techniques that were developed for writing compilers are useful in a variety of other software.
One of the more useful techniques for software design for large projects is to develop a special-purpose language that makes the project easy to implement. It can take less time and effort, and lead to a higher quality product, to spend the time to develop and implement a small special purpose language and to write the software in that language, than to write the software in a general purpose language. (One example is the language Erlang, which was designed for writing software to control data switches.)
Compilers benefit tremendously from careful analysis of a problem, and from tools for performing that analysis. A study of compiler design gives a good feeling for how a large problem can be broken down and solved in a manner that is not ad-hoc.
Compiler design makes use of formal methods that are rarely seen elsewhere except when quite difficult formal methods are used for general purpose software design. The study of compilers provides a gentle introduction to formal methods.
A course in compilers offers a good opportunity to get experience with development of a larger piece of software.
After completing this course, the student should understand both the theory and practice of compiler design, should be able to describe the components of a compiler and how they relate to one another, and should be able to apply that knowledge to implement a complete compiler for a small programming language.
Topics will be as follows.
Overview of compilers. The compilation process and the anatomy of a compiler.
Lexical analysis. The role of the lexical analyzer. Finite state machines. Regular expressions. Lexical analysis tools and lexer generators.
Context-free grammars. Writing grammars for programming languages.
Parsing. Top-down predictive parsing and LL(1) grammars. Table-driven parsers. Transformations on grammars. Bottom-up parsing, SLR(1), LR(1) and LALR(1) parsers. Parser generators.
Syntax-directed translation. Attributes grammars. Construction of syntax trees. Translation based on syntax trees.
Target languages. Intermediate code and abstract machines.
Table management. The symbol table.
Direct evaluation of syntax trees by an interpreter.
Semantic analysis. Type checking. Control flow and data flow analysis.
Optimazation and code improvement. Peephole optimization. Global optimizations.
This class has a mixture of undergraduate and graduate students. The requirements will be slightly different for those two groups, as follows.
On exams, some questions will be marked as required for graduate students but not for undergraduate students.
Some parts of the project will be required for graduate students, but extra credit for undergraduate students.
I will not take attendance. It is up to you to attend class. You are responsible for announcements and assignments given in class. If you miss a class, it is up to you to obtain notes and any other information that was provided in the class. Excuses that you did not know about something because you did not come to class and did not obtain the information will not count for anything at all.
Those who choose not to attend class can count on doing poorly in this course. If you choose not to attend class, then you must live with the consequences of that decision, however bad they are.
No incompletes will be issued in this course except for extraordinary circumstances, and even then only if you are nearly done already, and have done work of acceptable quality that it is realistic that you can pass the course.
In the event of a weather emergency, information about ECU can be accessed through the following sources:
| ECU emergency notices | http://www.ecu.edu/alert |
|---|---|
| ECU emergency information hotline | 252-328-0062 |
Smoking is not permitted in classrooms. Please turn off telephones while in class.
Students are expected to abide by the university's Student Honor Code. The homework that you do is a critical part of your education. Each student is expected to do his or her own work. That does not mean you are not allowed to discuss your ideas with other students. Working in groups can be beneficial, and I encourage you to talk through ideas with other students. But outright copying is plagiarism, and is unacceptable. Students who copy other students' work, or who allow their work to be copied, or who copy their work from other sources, such as the internet, will receive no credit.
East Carolina University seeks to comply fully with the Americans with Disabilities Act (ADA). Students requesting accommodations based on a covered disability must go to the Department for Disability Support Services, located in Slay 138, to verify the disability before any accommodations can occur. The telephone number is 252-737-1016.