---

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)

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
• character stream -> Lexical analyzer -> token stream
  
• token stream -> Syntax analyzer -> syntax tree
  
• syntax tree -> Semantic analyzer (Context Analysis/Type Checking) -> syntax tree
  
• syntax tree -> Intermediate code generator -> intermediate representation
  
• intermediate representation -> Machine independent code optimizer (improver) -> intermediate representation
• intermediate representation -> Code generation -> target machine code
• target machine code -> Machine dependent code optimizer (improver) -> target machine code
12. Symbol table is key data structure used throughout process
    

1. Overviews and simple examples of phases
• Lexical analysis
• Syntactic analysis
• Semantic Analysis
• Intermediate code generation
• Code optimization (improvement)
  
• Code generation
• Synbol table management
  
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
• scan generator (lex and flex)
• parser generator (yacc and bison)
• syntax-directed translator (convert tree to intermediate code)
• automatic code generator (translation rules from intermediate to target code)
• data flow analyzer (aid code optimzation by analyzing def-use chains, etc.)
• compiler construction toolkits (collections of above 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)

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)

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)

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

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)

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

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

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

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

1. Project Discussions -- lots of them
   
2. Back to recursive descent
   
3. A bit of language basics
• static versus dynamic
  
• parameter passing
4. Project Discussions

   Project

   See Project Folder
   

   Due: 12/1 at 11:59PM

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)