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, 2006-2007.
CS481 Lab: A laboratory course which must be taken concurrently with CS 480. Involves coding, verification, and validation of a compiler. 1 hour. Alternate years 2006-2007.
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: |
Douglas J. Ryan |
| Email: |
ryandj@pacificu.edu |
| Office: |
Strain 201 |
| Phone: |
(503) 352-2135 |
| Office Hours: |
MW 1:00 pm - 2:00 pm
F 11:00 am - 12:00 pm
or by appt |
| Prerequisite: |
CS 310 Theoretical Computer Science
with a grade of C or better. |
| Meeting Times: |
MW 4:00pm - 5:15pm
F 4:00pm - 4:50pm
|
| Location: |
PT204 |
|
Textbooks
|
Compilers Principles, Techniques, and Tools by Alfred V. Aho Addison-Wesley
The C Programming Language by Brian W. Kernighan Prentice Hall |
|
Course Website:
Prerequisite For: |
http://zeus.cs.pacificu.edu/ryand/cs480/2007/cs480.html
CS480 and 481 must be taken concurrently. |
Tentative Grading:
| Compiler Project |
45% |
| 3 Exams |
40% |
| Final |
15% |
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 23, 2007 |
Week 4 |
| Exam 2 |
Wednesday, March 21, 2007 |
Week 8 |
| Exam 3 |
Friday, April 27, 2007 |
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 1/8 of the total compiler grade. Getting everything to work together is another 1/8 of the total compiler grade.
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 12, 3:00pm - 5:30pm
Policies:
- Programs are to be submitted on zeus using the submit script by 4:00pm on the day it is due. The tar files are to be named yourlastname.tar.gz. Only send zipped files using gzip. Further, on the day the program is due, bring a STAPLED colored hard copy of all code properly ordered to class. If the hard copy is not received at the beginning of class (4:00pm) on the day in which the assignment is due, the entire program will be considered late.
- Assignments can be turned in late with a penalty of 10% per day (or portion thereof) meaning that one minute late is the same as 23 hours and 59 minutes late. You have a total of 3 grace days that can be used over the course of the semester on any assigned portion of the compiler project except the final sub-project which is the Remaining Semantic Actions. Be advised that the last three sub-projects are the most difficult; therefore, using your grace days early on is not advised.
- Make sure to test your program thouroughly on zeus before you turn it in. You may turn in your program only once.
- 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/481 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.
- 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:00pm 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. Just sending an email prior to missing class does not guarantee you will be cleared to miss. Only legitimate reasons will be accepted as excuses for missing class
- Any important issue pertaining to class such as the need to miss an exam or grade issues will not be discussed via email. I will however engage in email discussions regarding issues that need clarifying such as programming assignment questions.
- If you are unhappy with something related to the class, then schedule an appointment to see me so that we can discuss it in my office. Complaining in class or out of class to other students gets us nowhere.
- You may be asked to leave the classroom if you are causing a distraction e.g. cell phone ringing, talking, etc
Spring Break Saturday, March 24 through Sunday, April 1
Senior Projects Day Wednesday, April 25
Academic Calendar 2006-07