Topics for Final Exam -- Spring 2008

1. Material
• Material from class and web page notes
• From the text: As mentioned in web pages
• Material from assignments
• Material from first exam (roughly 20-25%)


2. Chapter 5 - Bottom up parsing
• Process: shift and reduce, role of stack, handle, build trees from bottom
• Algorithm:
• stack
• shift and reduce
• forest of trees
• LR: Leftmost scan, Rightmost parse, in reverse
• Building LR(0) items and transitions
• Items and dot and closure
• Conflicts: shift-reduce and reduce-reduce
• Differences in SLR, LALR, LR
• Look ahead
• Relative power of top down and bottom up algorithms
• Exercises


3. Chapter 6 - Abstract Syntax Trees
• What's in an AST and why we use them
• Visitor pattern
• What it is and how it's used
• Basic structure - how implemented
• Accept method in abstract parent and in each subclass
• Visit method for each subclass
• Type of params to accept and visit
• Examples: print, evaluate
• Embed actions in javacc code


4. Chapter 7 - Semantic Analysis
• What is analyzed
• What information is stored (eg environments)
• Compile vs run time semantic errors
• Actions that occur at compile time vs runtime
• How tests are made
• Categories of errors, with examples
• Singleton Design Pattern and how used
• Exercises


5. Chapter 8 - Abstract Assembly Tree
• What's in the tree
• Why used
• Contents of AR: params, locals, saved registers, temporary space
• Register pointers
• Procedure entry and exit: what gets saved and who saves it
• Exercises


6. Chapter 9 - Code Generation
• RISC vs CISC
• Memory Organization
• MIPS instructions:
• Memory access: lw and sw
• Immediate: li, addi
• Register arithmetic: add, sub
• Jump and Branch: jr, jal, bgtz, ...
• Expression stack: what it is and how it is implemented
• Accumulator: relation to stack and how used
• Temporaries on the call stack
• Tiling: small and large
• Peephole optimization