CSE P 501 25au 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 basically closed-book, but brief reference information and definitions will be provided when appropriate. You should not spend time memorizing reference material. You may bring two 5x8 index cards with whatever hand-written notes you wish with you to use during the exam.

• 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 parse tables
    • Items, item sets, and parser states
    • Shift-reduce and reduce-reduce conflicts
    • LR(0) vs. SLR grammars and how lookahead is used in SLR
• LL and recursive-descent parsers
  • Grammar problems and solutions - left recursion removal, left-factoring common prefixes, etc.
  • Ideas behind hand-written recursive-descent parsers
• Static semantics, type checking & symbol tables
  • Kinds of things checked in this phase of a compiler
  • 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 main 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 (vtables) 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
  • 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 and on the homework
  • Dominators and immediate dominators in CFGs
  • Basic idea of SSA - what it means; be able to hand translate a simple control flow graph into SSA with appropriate phi functions (you do not need to be able to precisely simulate the detailed algorithms that do this as long as you understand the issues and how to obtain the correct results); 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 (for examples covered in class so far).
• Back-end issues. You should have a general familiarity with the basic ideas and algorithms discussed in lecture and be able to solve problems similar to examples in class.
• Instruction selection - what are the basic ideas behind tree pattern matching
• Instruction scheduling - what is list scheduling; what are some of the issues that determine a good instruction schedule (resource contention including registers; operation latencies)
• Register allocation - what is the role of the interference graph and the ideas behind using graph coloring to allocate registers