COP3402
Systems Programming

Fall 2011

U.C.F.

Charles E. Hughes
Electrical Engineering and Computer Science
University of Central Florida


email: charles.e.hughes@knights.ucf.edu  Use Subject COP3402

Lectures: MW 1930-2045 (7:30PM to 8:45PM), CL1-320; 29 class periods, each 75 minutes long.
Labs: All on Wednesday in COMM-111; Section 11: 4:30-5:20; Section 12: 5:30-6:20; Section 13: 6:30-7:20
Go To Week 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15

Instructor: Charles Hughes; Harris Engineering Center HEC-247C; 823-2762 (use e-mail; I spend most of my time in my lab)
Office Hours: MW 9:45AM-10:45AM; M 5:30-6:30; and by appointment
GTA: Steven Zittrower, steven.zittrower@gmail.com, HEC-250; Th 3:00 to 5:00
           Wenhui Li, liwenhui6328@hotmail.com, HEC-254; Tuesday 4:00 to 5:00

Text: Compilers: Principles, Techniques, & Tools, Second Edition by Alfred V. Aho, Monica S. Lam, Ravi Sethi, and Jeffrey D. Ullman (DRAGON)
ISBN-10: 0321486811 | ISBN-13: 9780321486813

We will cover Chapter 1-6, 8, 9 of DRAGON book

Prerequisites: COP3502 (Computer Science I)

Web Pages:
Base URL: http://www.eecs.ucf.edu/courses/cop3402/fall2011
Course Home Page: COP3402Fall2011
Notes Folder: Notes
Assignments Folder: Assignments
Code Samples: CodeSamples
Course Wiki: http://mclserver.eecs.ucf.edu/trac/courses/wiki/COP3402Fall2011


Assignments: 5 to 8, one of which is the major project. Each assignment will have a due date and 10% will be subtracted for each day late (up to 2 days late, 20% off; more than two days late results in no credit)

Exams: One midterm and a final

Material: I will draw heavily from text by Aho, Lam, Sethi and Ullman. You are responsible for material discussed in notes and in in-class discussions. Not all of this is addressed in text. I highly recommend attending class, interacting with me and listening very carefully when I say a topic is important to me; hint, hint about exam questions ;-)

Important Dates: Labor Day -- September 5; Midterm Exam -- October 10 (Tentative); Withdraw Deadline -- October 27; Final -- December 7, 7:00PM-9:50PM

Evaluation (Tentative):
Mid Term -- 20%
Final Exam -- 30%
Programming and Other Assignments -- 20-25%
Final Programming Project -- 20-25%
Wild Card -- 5% (used to increase weight of what you did well on)
Grading will be  A >= 90%, B+ >= 87%, B >= 80%, C+ >= 77%, C >= 70%, D >= 60%, F < 60%. (minuses may be used in some cases)


Week#1: (8/22, 8/24) -- Chapter 1; Syllabus , Dragon Chapter 1 slides, Hughes Week 1/2 slides
  1. Goals, expectations and rules of the course
  2. A bit of an insight into what I do and what my background is in this domain
  3. Language Processors: pre-processors, compilers, interpreters and analyzers
  4. Source to Target: Compile, [Assemble,] Link, Load ([...] means optional)
  5. Target can be machine language for native or virtual machine
  6. A JVM (Java Virtual Machine) interprets bytecodes but Java runtime systems usually include a JIT (just-in-time translator) to translate to native code
  7. Microsoft's equivalent virtual machine is the CLR (Common Language Runtime) which interprets CIL (Common Intermediate Language) and/or produces native code
  8. The father and mother of  these  virtual machine codes were the Pascal P-code and the Smalltalk bytecode
  9. source -> Preprocessor -> modified source -> Compiler ->assembly program -> Assembler -> relocatable code -> Linker/Loader -> target code
  10. Linker/Loader also has input from libraries and previously compiled/assembled code
  11. Phases of a compiler
  12. Symbol table is key data structure used throughout process

Week#2: (8/29, 8/31) -- Chapter 1; Dragon Chapter 1 slides, Hughes Week 1/2 slides
  1. Overviews and simple examples of phases
  2. Grouping of phases in passes (a pass reads a stream or structure and procudes another stream of structure)
  3. Front-end vs back end phases and the value of virtual traget machines
  4. Compiler tools
  5. A little history of programming languages and their translations -- influence of theory
  6. Memory hierarchies and optimization
  7. Lexical analysis -- hand crafter

Assignment #1

Description of Lexical Analysis Assignment

Due: Monday, September 19 before the end of day (11:59PM)


Week#3: (9/7) -- Chapter 2; Dragon Chapter 2 slides, Hughes Week 3/4 slides
  1. A little history of programming languages and their translations -- influence of theory
  2. Grammars and languages
  3. Determinism vs non-determinism
  4. Ambiguity and its relation to non-determinism
  5. Non-ambiguity in expressions: associativity and precedence
  6. Grammars for various programming constructs: Expressions
  7. Expression grammars (precedence and associativity)


Week#4: (9/12, 9/14) -- Chapter 2; Dragon Chapter 2 slides, Hughes Week 3/4 slides
  1. The Chomsky hierarchy and the hierarchy of recognizers
  2. Syntax-directed translation
  3. Context free grammars
  4. Parse trees
  5. Notion of push down automata (stack memory)
  6. Determinism vs non-determinism
  7. Ambiguity and its relation to non-determinism
  8. Non-ambiguity in expressions: associativity and precedence
  9. Grammars for various programming constructs: Expressions
  10. Expression grammars (precedence and associativity)
  11. Syntax directed translation: attributes and program fragments (semantic actions)
  12. Synthesized versus inherited atributes
  13. Simple syntax-directed translation amenable to automated parser generation
  14. Left vs right recursion and top-down (predictive) vs bottom-up parsing
  15. Virtual non-stack machine overview (no explicit registers)
  16. Virtual stack machine overview: p-code (also no explicit registers)

Assignment #2 

Description of Lexical Analysis Assignment

Due: Monday, October 3 before the end of day (11:59PM)


Week#5: (9/19, 9/21) --   Chapter 3; Dragon Chapter 3 slides, Hughes Week 5/6 slides
  1. Handcrafted lexical analyzer
  2. Symbol tables (Envirment Blocks)
  3. Regular Expressions
  4. Building a lexical analyzer through regular expressions
  5. FLEX lexical analyzer generator (look for download specific to your platform)
  6. History of finite state automata (FSA) -- circuits and pattern matching
  7. Regular expressions and FSAs
  8. FSAs and Regular Grammars
  9. Deterministic vs non deterministic FSAs
  10. Syntax analysis
  11. Top down vs bottom up parsing
  12. Converting left to right recursion, maintaining semantic actions
  13. Left factoring
  14. Extended BNF

Week#6: (9/26, 9/28) --  Chapter 4; Dragon Chapter 4 slides, Hughes Week 5/6 slides
  1. Extended BNF
  2. Syntax graphs / Railroad charts
  3. Designing a recursive descent parser from syntax graphs
  4. Predictive parsing (First and Follow sets)
  5. Nullable symbols and effect on First and Follow
  6. Parsing table from First and Follow
  7. Top down vs bottom up parsing
  8. CKY parsing (great example of dynamic programming)


Week#7: (10/3, 10/5) -- Chapter 4; Review in Class; Help Sessions in Lab; Hughes Week 7/8 slides
  1. Reiteration of basic conflicts on top down and on bottom up parsing
  2. Stack process for each
  3. Topics and Promises for MidTerm # 1
  4. Sample Exam  -- Complete this for discussion on 10/5 (key)
  5. Review and go over sample questions


Week#8: (10/10 (Midterm), 10/12) -- Chapter 4; Hughes Week 7/8 slides
  1. Midterm
  2. Symbol tables (again)
  3. Bottom up vs top down and leftmost versus rightmost (once again)
  4. Finite state automata and pushdown automata
  5. Bottom up parsing with a PDA
  6. Lexical, syntactic and intermediate code based on flex and bison
  7. Notions of error recovery in both various types of parsers
  8. While language processor: while.l and while.y
  9. Bottom up parsing of While language using Bison 
  10. Intermediate code representation as triples


Week#9: (10/17, 10/19) -- Chapter 4, Hughes Week 9/10 Slides

  1. Finite state automata and pushdown automata (again)
  2. Non-deterministic parsing via PDAs
  3. Symbol table management for While language
  4. Symbol table management and hash coding
  5. Symbol tables for nested declarations
  6. Comments on recursive descent parsing of While langauge
  7. Error recovery in recursive descent
  8. Initial discussion of data flow analysis
  9. LR Parsing
  10. SLR as first example
  11. Midterm Exam#1 Key
  12. Note: 10/27 is the Withdraw Deadline

Week#10: (10/24, 10/26) -- Chapter 4; WITHDRAW DATE IS THURSDAY, OCT. 27, Hughes Week 9/10 Slides
  1. LR Parsing
  2. SLR as first example
  3. Basic algorithm
  4. LR(0) items and sets of items
  5. Closure of sets of items
  6. Action and Goto functions
  7. Building the parser
  8. LR(1) items and sets of items
  9. Closure of sets of items
  10. Action and Goto functions
  11. Building the canonical LR parser
  12. Merging states and the LALR parser
  13. Reduce/reduce errors that might arise
  14. Building the LALR parser

    Assignment #3

    Description is contained in While++ file. You also want to look at While language document and start with my while.l and while.y files. Turn in a zip containing the Flex and Bison files that produce a lexical analyzer, parser, intermediate code generator for the While++ language. I have also placed a working version of what I expect you to do and a set of sample inputs at while++.exe, test1.txt, test2.txt and test3Errors.txt.

    Due: Monday, November 7 by 11:59PM


Week#11: (10/31, 11/2) --Chapters 4, 5 and 6 of DRAGON, Hughes Week 11/12 slides 
  1. Ambiguity
  2. Error recovery
  3. Discussion of Assignment#3
  4. Parse trees versus syntax trees
  5. Syntax directed translation
  6. Attributes (synthesized vs inherited)
  7. S-attributed and L-attributed parse trees
  8. Side effects during translation
  9. Creating syntax trees via attributes
  10. Code generation
  11. Triples versus Quads (compact versus easy to move)
  12. Indirect triples as a compromise



Week#12: (11/7, 11/9) -- Chapters 5 and 6 of DRAGON, Hughes Week 11/12 slides
  1. Project Discussions -- lots of them
  2. Back to recursive descent
  3. A bit of language basics
  4. Project Discussions

    Project

    See Project Folder

    Due: 12/1 at 11:59PM



Week#13:  (11/14, 11/16) --  Chapter 8; Material comes from project description and Reference Solution, Hughes Week 13/14 slides
  1. Interpreter folder Assignments/Projects/Triples Interpreter
  2. Project Discussions -- lots of them
  3. Sample recursive descent compiler for Pascal-S (Niklaus Wirth)
  4. Handling of function returns
  5. Handling of Case -- Jump tables versus hashed jump tables vs if--then
  6. Peephole optimizations



Week#14: (11/21, 11/23) -- Chapter  9, Hughes Week 13/14 slides

  1. Data flow analysis
  2. Inter- vs Intra-procedural analysis
  3. Forward vs Backward flow
  4. May vs Must
  5. Def-Use chaining
  6. Variety of optimizations and analyses based of data flow


Week#15: (11/28, 11/30) -- Review in Class; Help Sessions in Lab

  1. Final Exam Topics
  2. Structure of Final
  3. Sample Final (Key)

Final Exam; Wednesday, December 7; 7:00PM - 9:50PM in CL1-320



Week#16: (12/5, 112/7) -- Help Sessions in HEC-101

  1. Help Sessions (Practice Problems with Answers)
Final Exam; Wednesday, December 7; 7:00PM - 9:50PM in CL1-320

UCF (Charles E. Hughes)  -- Last Modified December 5, 2011