Catalog Description:
CS480 Lecture: An introduction to compilers. Topics
to include: attribute grammars, syntax-directed translations, lex,
yacc, LR(1) parsers, symbol tables, semantic analysis, and code
generation. Prerequisite: CS 310 with C or better. 3 hours. Alternate
years, 2008-2009.
Topics:
- History of programming languages
- Brief survey of programming paradigms
- Procedural languages
- Object-oriented languages
- Functional languages
- Declarative, non-algorithmic languages
- Scripting languages
- The effects of scale on programming methodology
- The concept of a virtual machine
- Hierarchy of virtual machines
- Intermediate languages
- Comparison of interpreters and compilers
- Language translation phases (lexical analysis, parsing, code generation, optimization)
- Machine-dependent and machine-independent aspects of translation
- The conception of types as a set of values with together with a set of operations
- Declaration models (binding, visibility, scope, and lifetime)
- Overview of type-checking
- Garbage collection
- Procedures, functions, and iterators as abstraction mechanisms
- Parameterization mechanisms (reference vs. value)
- Activation records and storage management
- Type parameters and parameterized types
- Modules in programming languages
- Application of regular expressions in lexical scanners
- Parsing (concrete and abstract syntax, abstract syntax trees)
- Application of context-free grammars in table-driven and recursive-descent parsing
- Symbol table management
- Code generation by tree walking
- Architecture-specific operations: instruction selection and register allocation
- Optimization techniques
- The use of tools in support of the translation process and the advantages thereof
- Program libraries and separate compilation
- Building syntax-directed tools
Learning objectives:
- Summarize the evolution of programming languages illustrating how this history has led to the paradigms available today.
- Identify at least one distinguishing characteristic for each of the programming paradigms covered in this unit.
- Evaluate the tradeoffs between the different paradigms,
considering such issues as space efficiency, time efficiency (of both
the computer and the programmer), safety, and power of expression.
- Distinguish between programming-in-the-small and programming-in-the-large.
- Describe the importance and power of abstraction in the context of virtual machines.
- Explain the benefits of intermediate languages in the compilation process.
- Evaluate the tradeoffs in performance vs. portability.
- Compare and contrast compiled and interpreted execution models, outlining the relative merits of each..
- Describe the phases of program translation from source code to executable code and the files produced by these phases.
- Explain the differences between machine-dependent and
machine-independent translation and where these differences are evident
in the translation process.
- Explain the value of declaration models, especially with respect to programming-in-the-large.
- Identify and describe the properties of a variable such as its associated address, value, scope, persistence, and size.
- Discuss type incompatibility.
- Demonstrate different forms of binding, visibility, scoping, and lifetime management.
- Defend the importance of types and type-checking in providing abstraction and safety.
- Evaluate tradeoffs in lifetime management (reference counting vs. garbage collection).
- Explain how abstraction mechanisms support the creation of reusable software components.
- Demonstrate the difference between call-by-value and call-by-reference parameter passing.
- Defend the importance of abstractions, especially with respect to programming-in-the-large
- Describe how the computer system uses activation records to manage program modules and their data.
- Describe the steps and algorithms used by language translators.
- Recognize the underlying formal models such as finite state
automata, push-down automata and their connection to language
definition through regular expressions and grammars.
- Discuss the effectiveness of optimization.
- Explain the impact of a separate compilation facility and the existence of program libraries on the compilation process.
The above topics and learning objectives were taken from the Computing Curricula 20001 recommendations found at: http://www.computer.org/education/cc2001/final/chapter05.htm.
| Professor: |
Chadd Williams |
| Email: |
chadd@pacificu.edu |
| Office: |
Strain 202 |
| Phone: |
(503) 352-3041 |
| Office Hours: |
Tuesday 11-noon
Wednesday 2 - 3:30 pm
Friday 1:30 - 3 pm
or by appt |
| Prerequisite: |
CS 310 Theoretical Computer Science
with a grade of C or better. |
| Meeting Times: |
MWF 4:45pm - 5:50pm
|
| Location: |
Price Hall 204 |
|
Textbooks
|
Compilers Principles, Techniques, and Tools by Alfred V. Aho Addison-Wesley
(The red dragon book! ISBN: 0-201-10088-6)
The C Programming Language by Brian W. Kernighan Prentice Hall
|
|
Course Website:
|
http://zeus.cs.pacificu.edu/chadd/cs48009/
|
Tentative Grading:
| Compiler Project |
45% |
| Unannounced Quizzes |
3% |
| 3 Exams |
39% |
| Final Exam |
13% |
Percent Breakdown:
| |
|
92-100 |
A |
90-92 |
A- |
| 88-90 |
B+ |
82-88 |
B |
80-82 |
B- |
| 78-80 |
C+ |
72-78 |
C |
70-72 |
C- |
| 68-70 |
D+ |
60-68 |
D |
|
|
| |
|
0-60 |
F |
|
|
Tentative dates for Midterms:
| Exam 1 |
Friday, February 27, 2009 |
Week 4 |
| Exam 2 |
Friday, April 3, 2009 |
Week 8 |
| Exam 3 |
Friday, May 1, 2009 |
Week 12 |
Compiler Project:
-
Symbol Table & Error Handler
-
Lexical Analyzer
-
Recursive Descent Parser
-
Operator Precedence Parser
-
Semantic Actions for Declarations
-
Semantic Actions for Expressions
-
Remaining Semantic Actions
Each sub-project will constitute 12% of the total
compiler grade. Getting everything to work together is another 13% of
the total compiler grade. Project ZERO is worth 3% of the Compiler
Project
Compiler Project Grading:
|
Program successfully executes to specifications
|
70%
|
|
Acceptable structure, style, documentation, efficiency. You must follow the coding guidelines.
|
30%
|
Date of Final:
Saturday, May 16, 3:00pm - 5:30pm
Policies:
- Programs
must be in your Subversion repository on Zeus at 11:59 pm the day they
are due. Further, on the day the program is due, turn in a STAPLED
colored hard copy of all code properly ordered to the instructor by
11:59 pm. This may be slid under the instructor's door. If the hard
copy is not received by the appointed time, the entire program will be
considered late.
- Assignments
can be turned in late with a penalty of 10% per day (for a maximum of
two days,
nothing more than two days late will be graded). One minute
late is the same as 23 hours and 59 minutes late. You MUST inform
the instructor, via email
(subject: CS480 LATE), no later than 6 hours before the deadline that
you will be turning in your project late. Otherwise, I'll grade
what you have in your repository. The last programming project,
Semantic Actions 3, may NOT be turned in late.
- Make sure to test your program thouroughly on zeus and on the lab machines before you turn it in.
- A program that does not successfully compile or produces no output loses 70% of the assignment grade.
- No early or late exams/finals will be given.
- The
cheating policy is defined in the Pacific Catalog as well as the
Academic Policy that each of you signed upon entering Pacific
University. Be sure you read or reread this policy carefully.
All code written for CS480 is to be an original design and an original
implementation. The Web, textbooks, and any other references are simply
references for you. Copying source code from any source is prohibited
unless specifically stated by the instructor. Further, source code is
not to exchange hands in any form or by any medium except when sending
your solutions to the instructor. It is OK to share high level ideas
during the design phase, share information dealing with OS issues,
debugger issues, in general, development issues that do not involve
code writing. I strongly encourage use of the CS Messageboards for this
type of discussion. http://zeus.cs.pacificu.edu/messageboards
- Sanctions that may be imposed for academic dishonesty are:
- F in the course for any form of academic dishonesty
- It is NOT acceptable to turn in someone else's program. This would be a violation of policy 6.
- All
code in any form generated from this course becomes the intellectual
property of Pacific University. You may not share this code with anyone
without obtaining written permission from Pacific University.
- Neither
computer failure, software failure, nor lack of computer access are
accepted as excuses for late programs; therefore, start work on the
programs as soon as they are assigned, don't put them off until the
last minute. Further, corruption of programs due to bad disk media is
also not accepted as an excuse for late programs; therefore, always
keep a current backup of all programs on a separate disk.
- Attendance
at every class is critical to your success in this course. I expect you
to be on time and ready to go once it's 4:45 pm and that you stay until
the end of class. Any missed lecture is your responsibility to make up;
just remember, if you fall behind, it may be very difficult to catch up.
- The
instructor reserves the right to raise or lower a student's grade based
on class participation and attendance. Specifically, participation can
raise or lower your final grade by 1/3 of a grade. Further, your final
grade may be lowered by 1/3 of a grade for each day (or portion
thereof) of class missed. Please notify me PRIOR to class if you must
miss class for any reason. Only legitimate reasons
will be accepted as excuses for missing class
- You may be asked to leave the classroom if you are causing a distraction e.g. cell phone ringing, talking, etc
- If you
have a complaint regarding a grade on an assignment or exam, write a
one paragraph description of why you feel the grade is incorrect and
deliver it to the instructor. The paragraph must be delivered to the
instructor within one calendar week of when the graded material is
returned to the student.
- If
you have a documented disability covered under the ADA then services
and accommodations are available from LSS (Learning Support Services).
If you need reasonable accommodations to fully participate in course
activities or meet course requirements, you must contact Edna K.
Gehring, Director of LSS , at X2107. She will meet with you, review the
documentation of their disabilities, and discuss the services Pacific
offers.