CSE P 501 23au 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
  • 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
  • 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 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
  • 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).

In some past years back-end issues like instruction selection, scheduling, and register allocation were covered before the exam. Because of the calendar this year we have not discusssed these topics before the exam, so they will not appear on the test.