CSE P 501 18sp Exam Topics

This is a summary of the topics we have covered this 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 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
    • 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 - 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.