Course Guidelines
Instructor: Tom Fuller (Tom.Fuller@principia.edu) x5279; home
374-2001 (6am to 10pm unless urgent)
Hours: Often: Stop by the office or make an appointment
on the sheet outside my door.
Text: Thomas W. Parsons, Introduction
to Compiler Construction; CS Press, 1992 (1997 printing: even
in 2006, this is an outstanding text). ISBN 0-7167-8261-8
Prerequisites
Prerequisites for this course are: CS263 (Computer Architecture II) and CS276 (OOP). CS280 (Programming Languages) is strongly recommended.
Catalog Description
"Concepts necessary for designing and developing a compiler. Topics include lexical analysis, parsing, semantic analysis, symbol table management, and code generation. Students will implement a small compiler as a project."
Course Objectives
Upon completing this course, students will be able to:
Design
Understand, design, and build a recursive descent compiler.
The source language is Modula-2
(used in Europe for system programs and favorite child of the world's most brilliant
compiler designer, Niklaus Wirth). The target language
is Microsoft Macro Assembler 6.11. The implementation
language is C#.
Design and implement a helpful and effective user interface for a compiler.
Design and implement a lexer that transforms a source language file into its
component tokens.
Design and implement a parser that transforms a token list into its parse tree.
Design and implement an emitter that transforms a parse tree into corresponding
assembler language.
Design and implement support classes as necessary.
The design should reflect sound object-oriented programming principles, cohesion, minimal coupling, clear interface, economy, and efficiency.
Problem Solving, Technical Knowledge and
its Application
Solve the mathematical and logical problems associated with lexing, parsing,
and emitting.
Solve problems (at application and analytic levels) associated with formal language
grammars and compiler design.
Ability to learn
Independently research questions related to language features and effectively
make appropriate selections.
Gain fluency in the concepts of compiler design and implementation: finite state
automata, lexical analysis, context-free and context-sensitive languages, language
parsing, recursive descent parsing, procedure implementation, assembly code,
linking, optimization, and related ideas.
Ethics, Professionalism, Effective communication
Describe the classes and methods so that a knowledgeable reader of the code
can understand and extend them.
Give unambiguous credit to every source of algorithm and problem-solving (classmates,
professors, research, etc.)
Persist in seeking and discovering solutions to difficult algorithmic problems.
Conduct of the Course
Project Tasks:
One of the two central tasks for this course is the creation of a working compiler for a subset of Modula-2. You will develop a grammar for this Modula-2 subset, and will be given a set of Modula-2 test programs which must generate correct output for your compiler to be considered correct and complete. You will then be asked to propose, design, and implement an extension to the basic grammar.
Having made clear the central importance of the compiler project, I must also explain that this is not just a programming course. You must also articulate the above-mentioned course concepts. To that end ...
Course Journal:
Please maintain a scientific journal for this course. Record your discoveries, hypotheses, wrong turns, suspicions, problems, solutions -- in short, record your activity for the course. Your course journal will also contain a record of your time and activities outside of class. As you work, record the time spent. At the end of each day's activities, sum the time spent as a fraction: the numerator is this day's time; the denominator is the total time for the course so far. Use the hh.h format: e.g. 2.5/44.2.
Keep your journal as a text file. Accumulate each day’s entry at the front of the ongoing file. Mail the whole file to me before 11:59 pm each Saturday of the course (including tenth week but due before our last meeting).
Quizzes
We will have short quizzes as needed to determine your mastery of the course theory. These will always be announced: either in class, through email, the Web, or phone mail.
Day-to-Day Course Mechanics.
We will use a seminar format. We will meet as a class only as needed for you to obtain the concepts needed to complete the compiler and to understand the theory. All class days are optional. However, as I consider previous course offerings (taught by John Hooper, Ross McAninch, and me), it’s clear that you need to frequently state course concepts in your own language. Class meetings provide an opportunity for you to do this. Please be ready each course day to recite, write, explain, give examples, and, in general, wrestle mentally and verbally with the material.
Please be free to provide feedback to me about the course. I will get some of that from reading your journals. I will ask for written feedback on occasion. You should also feel very comfortable about telling me when you are having difficulty or when you are finding a course activity especially effective in helping you learn.
Machine Time and Lab Standards
There are other students taking programming-intensive courses this quarter. Never assume that machines will be available whenever you show up. Plan time carefully. There are no system-based excuses for missed deadlines. It is smart to get well in front of the schedule and to back up to the net, CD's, and jump drives. This also allows more time for the fun stuff after you’ve met the minimum requirements.
Grading
In the last millennium, the compiler for CS 380 was completed in phases: Lexer, Symbol Table, Parser, Code Generation. In Spring 2000, we built a working compiler (lex, parse, generate assembler code, and assemble the code) for each week after the lexer was complete. This worked very well, so we continue this practice. Grades for compiler phases count for 80% of the final grade. The journal and quizzes count 20%. Fine class support can nudge the grade upward a couple percent.
Each submission will be graded on several criteria (ranked by importance):
Function: Does the solution solve the problem? Does the program work correctly on test examples (known and unknown)? Does it adhere to the specification? Is the code free from defects or design flaws that would cause it to fail on comparable test cases? Notice that this criterion relates to Design and Problem-Solving Learning Themes.
Submission: Is the submission complete (project directories, example files, test evidence, correct localization, etc.)? This criterion relates to Professionalism.
Maintainability: Does the code meet the Style Standard? This relates to Design and Communication
Efficiency: Is the program free from awkward design, redundancy, unnecessary variables or calculations? This relates to Design and to lesser degree Technical Knowledge.
Class Policies and Classroom Decorum
No attendance is required. However, I expect that the class meetings will be essential to your progress. You are responsible for all interim deadlines, and for changes that may be announced in class. Class begins at 2:00 sharp. The "exquisite manners" expected of Principia students include active, unselfish support of class discussion and discussants. This naturally implies refraining from actions that undermine or distract the class.
Note on plagiarism: As you know, plagiarism is grounds for suspension from the college. Regrettably, it happens; gratefully, it is rare. At this point in your computer science career, there should be little need for help from others. In the degree that you complete assignments on your own, this course fulfills its objectives. Much material is available from the Modula-2 manuals, Visual Studio, and assembler books. If you receive any help -- even yelled across the lab -- it must be acknowledged with line by line specificity. If you are desperately blocked and I cannot be reached, then get the help you need, and label every line of code that was made possible by that help. Note that it is fine to use generic code examples on the web, but not symbol tables, parsers, lexers, emitters, assembly code, etc. Of course, even generic code examples must be acknowledged clearly to not be considered plagiarism.
Revised: January 15, 2007 1:49 PM