CSE P 501 Exam Topics

This is a summary of the topics we have covered up to this point in the quarter that you are responsible for on the exam. The exam is closed-book, but brief reference information and definitions will be provided if appropriate. You should not spend time memorizing reference material.

• Interpreters and compilers - key differences
• Gross structure of compilers - tasks of front/middle/back ends
• Basic notions of grammars - productions, terminals, non-terminals
• Regular expressions and DFAs
  • RE operators (the basic mathematical ones; not extensions found in various language libraries or utility programs
  • Constructing REs and DFAs (but you are not responsible for the formal RE -> NFA -> DFA construction algorithms)
• Scanners - transforming character streams to token streams
• Context-free grammars
  • Derivations, leftmost, rightmost, etc.
  • Constructing grammars for sets of strings
  • Ambiguity
  • First, follow, and nullable
• LR parsing
  • Shift-reduce parsing
  • Construction of LR(0) and SLR(1) parse tables
    • Items, item sets, and parser states
    • Shift-reduce and reduce-reduce conflicts
    • LR(1) vs. SLR grammars and how lookahead is used in SLR
• LL and recursive-descent parsers
  • Constructing hand-written recursive-descent parsers
  • Grammar problems and solutions - left recursion removal, left-factoring common prefixes, etc.
• Static semantics & symbol tables
  • Kinds of things checked in this phase of a compiler
  • Attribute grammar formalism
  • Basic symbol table structures for languages like MiniJava
  • Representation of type information in a compiler
• Basic x86-64 architecture
  • Core instruction set - don't memorize details, but be able to read and write simple code
  • Be able to translate simple C-level functions into x86-64 assembly language, including, in particular, calling conventions and stack frame layouts (don't memorize - reference information will be provided as appropriate - but you should know the core ideas)
• Code shape
  • Representation of common high-level language constructs in x86-64 assembly language
  • Representation of objects and implementation of new
  • Implementation of method calls and dynamic dispatch
    • Method tables and overriding
    • Be sure you understand basic Java rules for method overriding and field hiding in extended classes
• Intermediate representations, particularly:
  • Abstract syntax trees (ASTs)
  • Control-flow graphs, basic blocks
• Analysis and optimization
  • Value numbering techniques
  • General form of dataflow equations (def, use, in, and out sets) and how these can be used to analyze typical problems like liveness; be able to set up or solve simple problems like the ones we saw in class
  • Dominators and immediate dominators in CFGs without loops (i.e., for dominator value numbering)
  • Interaction between analysis and optimizations - what can we do with the information that is discovered by the analysis; how to the transformations interact with the analysis; when is a transformation safe (for examples covered in class so far).

In past years back-end issues like instruction selection and scheduling plus register allocation were covered before the exam. Similarly, previous exams contained material on loops, dominators, and loop optimizations. Because of the calendar this year we have not discusssed these topics before the exam, so they will not appear on the test.