CSE P 501 16wi Exam Topics

This is a summary of the topics we have covered this quarter that you are responsible for on the exam.

During the exam you may refer to the following material:

No additional books or reference materials are allowed, including homework assignments, sample solutions, or old exams.

You may use electronic copies of these materials provided you only look at material linked from this topic list page on the course website. You may not access any other information on the Internet or any other resources on your computer.

  • 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
    • Constructing REs and DFAs (but you do not need to know the full 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
    • Attrribute 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 - look up the details when needed)
  • 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 lecture
    • Dominators and immediate dominators; how to find a loop in a control flow graph
    • Basic idea of SSA - what it means; be able to hand translate a simple control flow into SSA with appropriate phi functions (you do not need to be able to precisely simulate the detailed algorithms that do this); dominance frontiers
    • 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 .

In past years back-end issues like instruction selection and scheduling plus register allocation were covered before the exam. This year we presented other material earlier and did not get to this before the week of exam, so you will not be tested on those topics.