Text: The Art of Compiler Design, Pittman&Peters
SBU policy is that they own the Syllabus; other material is the property of the instructor who prepared it.
Some interesting stuff about Turing Machines
Itty Bitty Stack Machine Specification
Feb.13 P.93, #1c,1d,1h, 6b,6c,7 (for 6b,6c)
Feb.18 Build a DFSA for your Tiny Java tokens from the regular expressions. Show your work. Write a recognizer (scanner) in Java from the DFSA. Show that it works.
Feb.25 Convert your Tiny Java grammar to LL(1). Prove it by showing the selection sets for all alternatives (and iterators, if any).
Mar.4 P.155, #1c,1d,1e,1f; 2c,2d,2e,2f; 3c
Mar.25 Add type-checking semantics to your Tiny Java grammar, in the form of an attribute grammar.
Apr.8 Add code generation semantics (for Itty Bitty Stack Machine) to your Tiny Java grammar.
Apr.10 Convert your Tiny Java attribute grammar to recursive-descent Java and show that it correctly parses and type-checks Tiny Java programs. Note: deviations from your grammar will be severely penalized; if the grammar is wrong, FIX THE GRAMMAR FIRST (and resubmit it).
Apr.15 Add the code generation semantics from your grammar to your recursive-descent Java code implementation, and show that it correctly compiles Tiny Java programs and that they run correctly in the IBSM simulator. Note: deviations from your grammar will be severely penalized; if the grammar is wrong, FIX THE GRAMMAR FIRST (and resubmit it).
May 6 p.284, #1,2,3
May 22 (take-home final): Build (by hand) the LR(1) parse table (or whatever limited version of LR(k) such as SLR, as will accept the language) for the following grammar, and write an interpreter in TinyJava that uses this table and runs on the Itty Bitty Stack Machine. Compile the interpreter on your own compiler and use it to execute the program to be handed out at 10:30 (the scheduled time for the final). To keep your scanner simple, you may limit your interpreter to support only integers and 26 one-letter variables.
P -> S+(Same grammar, with regular expression extensions removed)
S -> V "=" E ";"
E -> E "+" T | T
T -> T "*" F | F
F -> V | N | "(" E ")"
V -> letter
N -> digit+
Prerequisites: Approval of department chair
Course Goals: Students who successfully complete this course will
* Understand finite-state autamata and their relationship to language translation and grammarsCIS-4953, Compiler Design (special topic) This is your only chance in the known future to pick up the one course in this department where the instructor literally "wrote the book", which is also an extension of his PhD research. Pittman is passionate about grammar-based translator design (see also BibleTrans link). Using appropriate tools, you can write a simple compiler in a few hours, and a productive real-world translator in a few days. Because this is a special topics course, it is not known when it will be offered again at SBU.
* Design and implement compilers using formal grammars
* Be able to write finite-state scanners and recursive-descent parsers
Rev. 2003 May 20a