---

email: charles.e.hughes@knights.ucf.edu 

---

Lectures: TR 1200-1315 (12:00PM to 1:15PM), HEC-118; 28 class periods, each 75 minutes long.
Labs: Section 11: Thursday 8:30-9:20; Section 12: Thursday 9:30-10:20
Go To Week 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14

Instructor: Charles Hughes; Harris Engineering Center 247C; 823-2762 (use e-mail; I spend most of my time in my lab)
Office Hours: TR 9:45AM-11:15AM
GTA: Remo Pillat, rpillat@knights.ucf.edu, HEC308; OH: M 1430-1630 (2:30PM to 4:30PM)
           Chris Rees, serneum@gmail.com, HEC308; OH: W 1500-1630 (3:00PM to 4:30PM)

Text: System Software Knights (SSK), University of Central Florida Custom Edition, Pearson Custom Publishing 2008, ISBN 978-0-555-04647-0+Notes
Secondary References:
Compilers: Principles, Techniques, & Tools, Second Edition by Alfred V. Aho, Monica S. Lam, Ravi Sethi, and Jeffrey D. Ullman
System Software: An Introduction to Systems Programming, Third Edition by Leland Beck
Concepts of Programming Languages, Eighth Edition by Robert W. Sebesta
Operating Systems: Internals and Design Principles, Sixth Edition by William Stallings

Prerequisites: COP3502 (Computer Science I)

Web Pages:
Base URL: http://www.cs.ucf.edu/courses/cop3402/spring2011
Notes URL: http://www.cs.ucf.edu/courses/cop3402/spring2011/Notes/COP3402NotesSpring2011.pdf

Assignments: 6 to 10. 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 or two midterms and a final

Material: I will draw heavily from text and especially from 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 either of these texts. 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 ;-)

Exam Dates (Tentative): Exam#1 -- February 22; Withdraw Deadline -- March 4; Exam#2 -- MAYBE; Final -- Thursday, April 28, 10:00AM-12:50PM; Spring Break -- March 7-12

Evaluation (Tentative):
Mid Term(s) -- 20%
Final Exam -- 30%
Programming and Other Assignments -- 20%
Final Programming Project -- 25%
Wild Card -- 5% (for instance, to add weights to exams if I do a second midterm)
Grading will be  A >= 90%, B+ >= 87%, B >= 80%, C+ >= 77%, C >= 70%, D >= 60%, F < 60%.

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. Introduction to systems software
4. Machine organization overview: Von Neumann architecture
   

1. Virtual machines overview: p-code (stack architecture)
   
2. Language Processors: Compilers, interpreters and analyzer
3. Phases of a compiler
4. Lexical analysis
5. Syntactic analysis
6. Context Analysis/Type Checking
   
7. Semantic Analysis/Intermediate code generation
8. Code optimization (improvement)
   
9. Code generation
10. Handcrafted lexical analyzer
    

Assignment #1

Assign1Handout

Due: Part 1: February 1 by 11:59PM; Part 2: February 15 by 11:59PM(Key: C, H ) Test Cases (1A); Grading Criteria (1A)

1. Another look at the phases, especially syntax analysis
2. Regular Expressions
3. Building a lexical analyzer through regular expressions
4. FLEX lexical analyzer generator (look for download specific to your platform)
5. History of finite state automata (FSA) -- circuits and pattern matching
   
6. Regular expressions and FSAs
7. FSAs and Regular Grammars
   
8. Deterministic vs non deterministic FSAs
   

Assignment #2 

Starting with pascal.lex, change the rules in my regular expressions to accommodate exponents in numbers.
  Note: An integer followed by an exponent is a real.
Change it to include //, %, ++ and -- as you did in Assign#1. I already did the comments, except for directives.
You do not need to manage directives in this assignment.
While you must just submit the modified grammar, I strongly recommend you download FLEX and try it.
  That's what we will do for checking your changes.

Due: February 17 by 11:59PM (Key) Comments

1. Syntax-directed translation
2. Context free grammars
3. Parse trees
   
4. Notion of push down automata (stack memory)
5. Ambiguity and its relation to non-determinism
6. Non-ambiguity in expressions: associativity and precedence
   
7. Grammars for various programming constructs: Expressions
8. Syntax directed translation: attributes and program fragments (semantic actions)
   
9. Synthesized versus inherited atributes
10. Simple syntax-directed translation amenable to automated parser generation
    
11. Left vs right recursion and top-down (predictive) vs bottom-up parsing

1. Expression grammars (precedence and associativity)
   
2. Extended BNF
3. Converting left to right recursion, maintaining semantic actions
4. Left factoring
5. Syntax graphs / Railroad charts
   
6. Designing a recursive descent parser from a right recursive grammar

1. Predictive parsing (First and Follow sets)
2. Nullable symbols and effect on First and Follow
   
3. Parsing table from First and Follow
4. Top down vs bottom up parsing
5. CKY parsing (great example of dynamic programming)
6. Basic conflicts on top down and on bottom up parsing
   
7. Topics and Promises for MidTerm # 1
8. Sample Exam  -- Complete this for discussion on 2/17 (key)
9. Review and go over sample questions

1. Midterm
2. Symbol tables
3. Lexical, syntactic and intermediate code based on flex and bison
4. Notions of error recovery in both various types of parsers
5. While language processor: while.l and while.y
   

Assignment #3

Consider the grammar
S  →    AB  |  BA
A  →    CD  |  a
B  →     CE  |  b
C  →     a   |  b
D  →    AC
E  →     BC
Use CKY to determine if the following strings are in the associated language.
Report any ambiguity you encounter.
a. abbab
b. baba
c. bbaabb
d. abba
Answer Form is available to fill in.

Due: March 3 by 11:59PM (Key)

1. Bottom up parsing of While language using Bison
   
2. Symbol table management for While language
3. Symbol table management and hash coding
4. Symbol tables for nested declarations
5. Intermediate code representation as triples
6. Error recovery
   
7. Clues on recursive descent parsing of While langauge
8. Error recovery in recursive descent
9. Initial discussion of data flow analysis
10. Midterm Exam#1 Key
11. Note: 3/4 is the Withdraw Deadline

Assignment #4

Rewrite the While language compiler to intermediate code using recursive descent
You must provide the same features that I did on Bison/Flex version.
While language write-up; Reference solution: while.l and while.y
I have also placed Niklaus Wirth's full Pascal-S compiler and interpreter on the site.
Wirth's generated code is not useful but his parser and error recovery should help you.

Due: March 22 by 11:59PM

Week#9: (3/15, 3/17) -- Notes pp. 258-289 (pp. 305-331 of SSK)

1. Bottom up vs top down and leftmost versus rightmost (once again)
2. Finite state automata and pushdown automata
3. Non-deterministic parsing via PDAs
4. LR Parsing
5. SLR as first example
6. Basic algorithm
7. LR(0) items and sets of items
8. Closure of sets of items
9. Action and Goto functions
   
10. Building the parser
    

1. LR(1) items and sets of items
2. Closure of sets of items
3. Action and Goto functions
   
4. Building the canonical LR parser
5. Merging states and the LALR parser
6. Reduce/reduce errors that might arise
7. Ambiguity
8. Error recovery
9. Back to Recursive Descent (show code skeleton for Expression)
   
10. Parse Trees versus Syntax Trees
11. Code generation
12. Triples versus Quads (compact versus easy to move)

1. Syntax directed translation
2. Attributes (synthesized vs inherited)
3. S-attributed and L-attributed parse trees
4. Side effects during translation
   
5. Creating syntax trees via attributes
   
6. Code generation
7. Triples versus Quads (compact versus easy to move)
8. Indirect triples as a compromise
9. Project discussion
   

Project

See Project Folder

Due: April 26 by 11:59PM

1. Project Discussions -- lots of them
2. Peephole optimizations
3. Handling of function returns (not required in your project)
   
4. Handling of Case (not required)  -- Jump tables versus hashed jump tables vs if--then
5. Equivalence classes (motivated by alias) -- union/find started
   

1. Reference Solution in folder Assignments/Project/ReferenceSolution/
   
2. Data flow anlysis
   

Week#14: (4/19, 4/21 (Review in Class; Help Sessions in Lab)) -- Notes pp. 345-388

1. Some data flow
   
2. Interpreter for Rascal in folder Assignments/Projects/Triples Interpreter
   
3. Union/Find -- almost constant
4. Final Exam Topics
5. Sample Final (Key)
   

Final Exam; Thursday April 28; 10:00 - 12:50 in HEC118